Description
Binary linear code with a sparse generator matrix. Alternatively, a member of an infinite family of \([n,k,d]\) codes for which the number of nonzero entries in each row and column of the generator matrix are both bounded by a constant as \(n\to\infty\). The dual of an LDGM code has a sparse parity-check matrix and is called an LDPC code.
Rate
Certain LDGM codes come close to achieving Shannon capacity [1].
Parents
Child
Cousins
- Single parity-check (SPC) code — Concatenated SPCs are LDGM [2].
- Irregular repeat-accumulate (IRA) code — IRA codes replace the outer 1-in-3 repetition encoding step in RA codes with an LDGM code.
- Low-density parity-check (LDPC) code — The dual of an LDPC code has a sparse generator matrix and is called an LDGM code.
- Hsu-Anastasopoulos LDPC (HA-LDPC) code — HA-LDPC codes are a concatenation of an LDPC and an LDGM code.
- MacKay-Neal LDPC (MN-LDPC) code — \((l,r,1\))-MN-LDPC codes are LDGM [3].
- Quantum low-density parity-check (QLDPC) code — LDGM codes can yield CSS [4–7] and non-CSS [8,9] QLDPC codes. Some of the LDGM-based CSS codes have \(n\)-independent minimum distance and no code capacity threshold [10; Sec. 4.2].
References
- [1]
- J. Garcia-Frias and Wei Zhong, “Approaching Shannon performance by iterative decoding of linear codes with low-density generator matrix”, IEEE Communications Letters 7, 266 (2003) DOI
- [2]
- T. R. Oenning and Jaekyun Moon, “A low-density generator matrix interpretation of parallel concatenated single bit parity codes”, IEEE Transactions on Magnetics 37, 737 (2001) DOI
- [3]
- K. KASAI and K. SAKANIWA, “Spatially-Coupled MacKay-Neal Codes and Hsu-Anastasopoulos Codes”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E94-A, 2161 (2011) arXiv:1102.4612 DOI
- [4]
- Hatuying Lou and J. Garcia-Frias, “Quantum error-correction using codes with low density generator matrix”, IEEE 6th Workshop on Signal Processing Advances in Wireless Communications, 2005. DOI
- [5]
- H. Lou and J. Garcia-Frias, "On the Application of Error-Correcting Codes with Low-Density Generator Matrix over Different Quantum Channels," 4th International Symposium on Turbo Codes & Related Topics; 6th International ITG-Conference on Source and Channel Coding, Munich, Germany, 2006, pp. 1-6.
- [6]
- J. Garcia-Frias and Kejing Liu, “Design of near-optimum quantum error-correcting codes based on generator and parity-check matrices of LDGM codes”, 2008 42nd Annual Conference on Information Sciences and Systems (2008) DOI
- [7]
- P. Fuentes et al., “Design of low-density-generator-matrix–based quantum codes for asymmetric quantum channels”, Physical Review A 103, (2021) DOI
- [8]
- P. Fuentes et al., “Approach for the construction of non-Calderbank-Steane-Shor low-density-generator-matrix–based quantum codes”, Physical Review A 102, (2020) DOI
- [9]
- P. Fuentes et al., “Performance of non-CSS LDGM-based quantum codes over the misidentified depolarizing channel”, 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) (2020) DOI
- [10]
- J.-P. Tillich and G. Zemor, “Quantum LDPC Codes With Positive Rate and Minimum Distance Proportional to the Square Root of the Blocklength”, IEEE Transactions on Information Theory 60, 1193 (2014) arXiv:0903.0566 DOI
Page edit log
- Victor V. Albert (2022-08-15) — most recent
Cite as:
“Low-density generator-matrix (LDGM) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/ldgm
Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/tanner/ldgm.yml.