Efficient encoding of low-density parity-check codes

Low-density parity-check (LDPC) codes can be considered serious competitors to turbo codes in terms of performance and complexity and they are based o n a similar philosophy: constrained random code ensembles and iterative dec oding algorithms. In this paper, we consider the encoding problem for LDPC codes, More genera lly, we consider the encoding problem for codes specified by sparse parity- check matrices. We show how to exploit the sparseness of the parity-check m atrix to obtain efficient encoders, For the (3, 6)-regular LDPC code, for e xample, the complexity of encoding is essentially quadratic in the block le ngth, However, we show that the associated coefficient can be made quite sm all, so that encoding codes even of length n similar or equal to 100 000 is still quite practical. More importantly, we will show that "optimized" cod es actually admit linear time encoding.