Protograph LDPC code[13] 


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.


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


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




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


Thorpe, Jeremy. "Low-density parity-check (LDPC) codes constructed from protographs." IPN progress report 42.154 (2003): 42-154.
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
D. Divsalar, S. Dolinar, and C. Jones, “Protograph LDPC Codes over Burst Erasure Channels”, MILCOM 2006 (2006) DOI
C. A. Kelley and J. L. Walker, “LDPC codes from voltage graphs”, 2008 IEEE International Symposium on Information Theory (2008) DOI
L. W. Beineke et al., editors , Topics in Topological Graph Theory (Cambridge University Press, 2009) 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
Y. Fang et al., “A Survey on Protograph LDPC Codes and Their Applications”, IEEE Communications Surveys & Tutorials 17, 1989 (2015) DOI
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
D. Divsalar et al., “Constructing LDPC codes from simple loop-free encoding modules”, IEEE International Conference on Communications, 2005. ICC 2005. 2005 DOI
A. Beemer et al., “A Generalized Algebraic Approach to Optimizing SC-LDPC Codes”, (2017) arXiv:1710.03619
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 (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.
@incollection{eczoo_protograph_ldpc, title={Protograph LDPC 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:

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