Efficient Encoding of Low-Density Parity-Check Codes

Low-density parity-check codes can be considered serious competitors to turbo codes in terms of performance and complexity and they are based on a similar philosophy: constrained random code ensembles, and iterative decoding algorithms. In this paper we consider the encoding problem for low-density parity-check codes. More generally, we consider the encoding problem for codes specified by sparse parity-check matrices. We show how to exploit the sparseness of the parity-check matrix to obtain efficient encoders. For the (3,6)-regular low-density parity-check code for example, the complexity of encoding is essentially quadratic in the block length. However, we show that the associated coefficient can be made quite small, so that encoding codes even of length n ~ 100,000 is still quite practical. More importantly, for all known "good" codes we show that the encoding complexity is actually linear in the block length.