Description
An LDPC code whose parity-check matrix has a fixed number of ones in each row and each column. Such a code is called \((j,k)\)-regular if each column has weight \(j\) (variable-node degree) and each row has weight \(k\) (check-node degree). If the parity-check matrix has \(n\) columns and \(m\) rows, then regularity implies \(nj = mk\).Protection
Random \((j,k)\)-regular LDPC codes have minimum distance that grows linearly with block length for any fixed \(j \geq 3\) (with \(k > j\)) [2,3].Rate
An ensemble of \((j,k)\)-regular LDPC codes has a design rate \(1 - j/k\). This is a lower bound on the true rate, is the true rate if all constraints are linearly independent, and equals the rate asymptotically [2][4; Sec. 3.4].Decoding
The BP decoding threshold for regular codes is strictly below the Shannon capacity for any fixed \(j,k\) [4; Sec. 3.11].Cousin
- Irregular LDPC code— Irregular LDPC codes have variable node and check node degrees, while regular LDPC codes have fixed node degrees. Irregular LDPC codes with optimized degree distributions can outperform regular ones under iterative decoding [5,6].
Primary Hierarchy
Low-density parity-check (LDPC) code\(q\)-ary LDPC Tanner Linear \(q\)-ary LRC Distributed-storage ECC
Parents
Regular LDPC codes are regular binary Tanner codes defined on sparse graphs whose constraint nodes represent parity-check codes.
Regular LDPC code
Children
Cycle LDPC codes form a class of regular QC LDPC codes [7].
Expander codes yield an explicit (i.e., non-random) asymptotically good LDPC code family [8].
GL codes are the first LDPC codes.
MN-LDPC codes re-invigorated the study of LDPC codes about 30 years after their discovery.
References
- [1]
- R. Gallager, “Low-density parity-check codes”, IEEE Transactions on Information Theory 8, 21 (1962) DOI
- [2]
- R. Gallager, Low-density parity check codes. 1963. PhD thesis, MIT Cambridge, MA.
- [3]
- M. Lentmaier, D. G. M. Mitchell, G. P. Fettweis, and D. J. Costello, “Asymptotically Regular LDPC Codes with Linear Distance Growth and Thresholds Close to Capacity”, (2010) arXiv:1005.1062
- [4]
- T. Richardson and R. Urbanke, “The renaissance of gallager’s low-density parity-check codes”, IEEE Communications Magazine 41, 126 (2003) DOI
- [5]
- D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices”, IEEE Transactions on Information Theory 45, 399 (1999) DOI
- [6]
- T. J. Richardson and R. L. Urbanke, “The capacity of low-density parity-check codes under message-passing decoding”, IEEE Transactions on Information Theory 47, 599 (2001) DOI
- [7]
- R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, and D. J. Costello, “LDPC Block and Convolutional Codes Based on Circulant Matrices”, IEEE Transactions on Information Theory 50, 2966 (2004) DOI
- [8]
- M. Sipser and D. A. Spielman, “Expander codes”, IEEE Transactions on Information Theory 42, 1710 (1996) DOI
Page edit log
- Victor V. Albert (2023-05-04) — most recent
Cite as:
“Regular LDPC code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/regular_ldpc