Gallager (GL) code[1,2] 


The first LDPC code. 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.


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].


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].




R. Gallager, “Low-density parity-check codes”, IEEE Transactions on Information Theory 8, 21 (1962) DOI
R. Gallagher, Low-density parity check codes. 1963. PhD thesis, MIT Cambridge, MA.
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
D. J. C. MacKay and R. M. Neal, “Near Shannon limit performance of low density parity check codes”, Electronics Letters 33, 457 (1997) DOI
D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices”, IEEE Transactions on Information Theory 45, 399 (1999) DOI
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

Your contribution is welcome!

on (edit & pull request)— see instructions

edit on this site

Zoo Code ID: gallager

Cite as:
“Gallager (GL) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023.
@incollection{eczoo_gallager, title={Gallager (GL) code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Gallager (GL) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023.