Linear Time Encoding of LDPC Codes

Details Linear Time Encoding of LDPC Codes Linear Time Encoding of LDPC Codes

2008-10-15

arxiv.org/abs/0810.2781v1

Computer Science

Information Theory

36 pages, 13 figures, submitted to IEEE Transactions on Information Theory

Scientific paper

In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method ``label-and-decide.'' We prove that the ``label-and-decide'' method is applicable to Tanner graphs with a hierarchical structure--pseudo-trees-- and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs--the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm--the ``label-decide-recompute.'' Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general LDPC codes where the encoding complexity is proved to be less than $4 \cdot M \cdot (\overline{k} - 1)$, where $M$ is the number of independent rows in the parity check matrix and $\overline{k}$ represents the mean row weight of the parity check matrix.

Affiliated with

Also associated with

No associations

Rating

Linear Time Encoding of LDPC Codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linear Time Encoding of LDPC Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear Time Encoding of LDPC Codes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-303995