Description
The first LDPC code construction. The rows of the parity check matrix of this regular code are divided into equal subsets, and columns in the first subset are randomly permuted to yield the corresponding rows in subsequent subsets. For example, the parity-check matrix \begin{align} \begin{pmatrix} 1 & 1 & 0 & 0\\ 0 & 0 & 1 & 1\\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 \end{pmatrix} \tag*{(1)}\end{align} contains two subsets, each consisting of two rows, and the last two rows are obtained from the first two by exchanging the second and third columns.
Protection
With high probability, random GL codes have constant distance [2]. There exist GL codes that are able to correct errors of weight less than \(c n\) for some constant \(c\) in order \(O(n\log n)\) decoding operations [3].
Rate
GL codes nearly achieve Shannon capacity against binary-input additive Gaussian white noise using iterative decoding [4,5]. GL codes can outperform RS codes at short block length [6].
Parents
- Regular LDPC code — GL codes are the first LDPC codes.
- Generalized Gallager code
Cousin
- Combinatorial design code — Some Steiner systems can be used to construct Gallager codes [6].
References
- [1]
- R. Gallager, “Low-density parity-check codes”, IEEE Transactions on Information Theory 8, 21 (1962) DOI
- [2]
- R. Gallagher, Low-density parity check codes. 1963. PhD thesis, MIT Cambridge, MA.
- [3]
- V. V. Zyablov, M. S. Pinsker, “Estimation of the error-correction complexity for Gallager low-density codes”, Probl. Peredachi Inf., 11:1 (1975), 23–36; Problems Inform. Transmission, 11:1 (1975), 18–28
- [4]
- D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes”, Electronics Letters 33, 457 (1997) 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]
- D. J. C. MacKay and M. C. Davey, “Evaluation of Gallager Codes for Short Block Length and High Rate Applications”, Codes, Systems, and Graphical Models 113 (2001) DOI
Page edit log
- Victor V. Albert (2023-05-04) — most recent
Cite as:
“Gallager (GL) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/gallager