Efficient encoding of low-density parity-check codes
Top Cited Papers
- 1 February 2001
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 47 (2) , 638-656
- https://doi.org/10.1109/18.910579
Abstract
Low-density parity-check (LDPC) 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. We consider the encoding problem for LDPC 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 LDPC 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/spl sime/100000 is still quite practical. More importantly, we show that "optimized" codes actually admit linear time encoding.Keywords
This publication has 14 references indexed in Scilit:
- Design of capacity-approaching irregular low-density parity-check codesIEEE Transactions on Information Theory, 2001
- The capacity of low-density parity-check codes under message-passing decodingIEEE Transactions on Information Theory, 2001
- Error-Correcting Codes That Nearly Saturate Shannon's BoundPhysical Review Letters, 1999
- Comparison of constructions of irregular Gallager codesIEEE Transactions on Communications, 1999
- Expander codesIEEE Transactions on Information Theory, 1996
- Linear-time encodable and decodable error-correcting codesIEEE Transactions on Information Theory, 1996
- Near Shannon limit performance of low density paritycheck codesElectronics Letters, 1996
- Spin-glass models as error-correcting codesNature, 1989
- Explicit constructions of graphs without short cycles and low density codesCombinatorica, 1982
- A recursive approach to low complexity codesIEEE Transactions on Information Theory, 1981