Protograph LDPC code

Protograph LDPC code[1–3]

Description

Binary version of a \(q\)-ary protograph LDPC code. Its parity check matrix can be put into the form of a block matrix consisting of either a sum of permutation sub-matrices or the zero sub-matrix.

Protection

The minimum distance of protograph codes is bounded by a function of the number of commuting permutation-matrix blocks [4].

Notes

For reviews on protograph LDPC codes, see Ref. [5].

Cousin

Algebraic LDPC code— Some deterministic protograph LDPC codes [6] can be obtained from the theory of voltage graphs [7,8].

Member of code lists

Primary Hierarchy

Classical Domain

Binary Kingdom

Binary codeECC

Binary group-orbit codeECC

Linear binary codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC

Low-density parity-check (LDPC) code\(q\)-ary LDPC Tanner Linear \(q\)-ary LRC Distributed-storage ECC

Multi-edge LDPC code

Parents

Multi-edge LDPC code

LDPC codes based on protographs can be formulated as multi-edge LDPC codes [9].

\(q\)-ary protograph LDPC code\(q\)-ary LDPC Tanner Linear \(q\)-ary LRC Distributed-storage ECC

Protograph LDPC code

Children

Accumulate-repeat-accumulate (ARA) code

ARA codes can be formulated as protograph LDPC codes [2].

Irregular repeat-accumulate (IRA) code

IRA codes can be formulated as protograph LDPC codes [2].

Repeat-accumulate-accumulate (RAA) code

RAA codes can be formulated as protograph LDPC codes [10].

Quasi-cyclic LDPC (QC-LDPC) code

Spatially coupled LDPC (SC-LDPC) code

SC-LDPC codes can be interpreted as protograph LDPC codes [11].

References

[1]: Thorpe, Jeremy. "Low-density parity-check (LDPC) codes constructed from protographs." IPN progress report 42.154 (2003): 42-154.
[2]: D. Divsalar, C. Jones, S. Dolinar, and J. Thorpe, “Protograph based LDPC codes with minimum distance linearly growing with block size”, GLOBECOM ’05. IEEE Global Telecommunications Conference, 2005. 5 pp. (2005) DOI
[3]: D. Divsalar, S. Dolinar, and C. Jones, “Protograph LDPC Codes over Burst Erasure Channels”, MILCOM 2006 1 (2006) DOI
[4]: D. J. C. MacKay and M. C. Davey, “Evaluation of Gallager Codes for Short Block Length and High Rate Applications”, The IMA Volumes in Mathematics and its Applications 113 (2001) DOI
[5]: Y. Fang, G. Bi, Y. L. Guan, and F. C. M. Lau, “A Survey on Protograph LDPC Codes and Their Applications”, IEEE Communications Surveys & Tutorials 17, 1989 (2015) DOI
[6]: C. A. Kelley, “On codes designed via algebraic lifts of graphs”, 2008 46th Annual Allerton Conference on Communication, Control, and Computing 1254 (2008) DOI
[7]: C. A. Kelley and J. L. Walker, “LDPC codes from voltage graphs”, 2008 IEEE International Symposium on Information Theory 792 (2008) DOI
[8]: L. W. Beineke, R. J. Wilson, J. L. Gross, and T. W. Tucker, editors , Topics in Topological Graph Theory (Cambridge University Press, 2009) DOI
[9]: D. G. M. Mitchell, R. Smarandache, and D. J. Costello, “Quasi-cyclic LDPC codes based on pre-lifted protographs”, 2011 IEEE Information Theory Workshop 350 (2011) DOI
[10]: D. Divsalar, S. Dolinar, J. Thorpe, and C. Jones, “Constructing LDPC codes from simple loop-free encoding modules”, IEEE International Conference on Communications, 2005. ICC 2005. 2005 1, 658 DOI
[11]: A. Beemer, S. Habib, C. A. Kelley, and J. Kliewer, “A Generalized Algebraic Approach to Optimizing SC-LDPC Codes”, (2017) arXiv:1710.03619

Page edit log

Victor V. Albert (2023-05-04) — most recent

Cite as:

“Protograph LDPC code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/protograph_ldpc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/tanner/irregular/protograph_ldpc.yml.