Protograph LDPC code[13] 

Description

LDPC code whose parity-check matrix is constructed using the lifting procedure (defined below) applied to the incident matrix of a sparse graph called, in this context, a protograph. 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.

Lifting: Given the incidence matrix \(A\) of a protograph, each non-zero entry is replaced by a sum of \(\ell\)-dimensional permutation matrices while each zero entry is replaced by the \(\ell\)-dimensional zero matrix. The resulting matrix is called a lift of \(A\). The permutation matrices can be chosen randomly or deterministically, with a deterministic lift also called a permutation voltage assignment in the theory of theory of voltage graphs [4,5].

For example, the lift of a two-dimensional incidence matrix using two-dimensional permutation matrices associated with the group \(\mathbb{Z}_2\) is as follows: \begin{align} \begin{pmatrix}1 & 1\\ 0 & 1 \end{pmatrix}\to\begin{pmatrix}\begin{smallmatrix}0 & 1\\ 1 & 0 \end{smallmatrix} & \begin{smallmatrix}0 & 1\\ 1 & 0 \end{smallmatrix}\\ \begin{smallmatrix}0 & 0\\ 0 & 0 \end{smallmatrix} & \begin{smallmatrix}1 & 0\\ 0 & 1 \end{smallmatrix} \end{pmatrix}~. \tag*{(1)}\end{align} Here, the two non-zero entries in the top row are replaced by the exchange permutation while the bottom non-zero entry is replaced by the trivial permutation.

Protection

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

Notes

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

Parents

Children

Cousin

  • Algebraic LDPC code — Some deterministic protograph LDPC codes [11] can be obtained from the theory of voltage graphs [4,5].

References

[1]
Thorpe, Jeremy. "Low-density parity-check (LDPC) codes constructed from protographs." IPN progress report 42.154 (2003): 42-154.
[2]
D. Divsalar et al., “Protograph based LDPC codes with minimum distance linearly growing with block size”, GLOBECOM ’05. IEEE Global Telecommunications Conference, 2005. (2005) DOI
[3]
D. Divsalar, S. Dolinar, and C. Jones, “Protograph LDPC Codes over Burst Erasure Channels”, MILCOM 2006 (2006) DOI
[4]
C. A. Kelley and J. L. Walker, “LDPC codes from voltage graphs”, 2008 IEEE International Symposium on Information Theory (2008) DOI
[5]
L. W. Beineke et al., editors , Topics in Topological Graph Theory (Cambridge University Press, 2009) 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
[7]
Y. Fang et al., “A Survey on Protograph LDPC Codes and Their Applications”, IEEE Communications Surveys & Tutorials 17, 1989 (2015) DOI
[8]
D. G. M. Mitchell, R. Smarandache, and D. J. Costello, “Quasi-cyclic LDPC codes based on pre-lifted protographs”, 2011 IEEE Information Theory Workshop (2011) DOI
[9]
D. Divsalar et al., “Constructing LDPC codes from simple loop-free encoding modules”, IEEE International Conference on Communications, 2005. ICC 2005. 2005 DOI
[10]
A. Beemer et al., “A Generalized Algebraic Approach to Optimizing SC-LDPC Codes”, (2017) arXiv:1710.03619
[11]
C. A. Kelley, “On codes designed via algebraic lifts of graphs”, 2008 46th Annual Allerton Conference on Communication, Control, and Computing (2008) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: protograph_ldpc

Cite as:
“Protograph LDPC code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/protograph_ldpc
BibTeX:
@incollection{eczoo_protograph_ldpc, title={Protograph LDPC code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/protograph_ldpc} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/protograph_ldpc

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/tree/main/codes/classical/bits/tanner/irregular/protograph_ldpc.yml.