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
Notes
Parents
- Multi-edge LDPC code — LDPC codes based on protographs can be formulated as multi-edge LDPC codes [8].
- \(q\)-ary 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 [9].
- Quasi-cyclic LDPC (QC-LDPC) code
- Spatially coupled LDPC (SC-LDPC) code — SC-LDPC codes can be interpreted as protograph LDPC codes [10].
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
- 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