Low Density Parity Check¶

An LDPC code consists of a sparse matrix with very few ones in each row and column, called the “Parity Check Matrix”. Usually, each row of the matrix is designed to be linearly independent from the other rows, which is an assumption we have made for our project. Regular codes have an equal number of non-zero elements in each column and an equal number in each row, while irregular codes can have a varying number [1].
When multiplied by a column vector “codeword” in modulo 2 arithmetic, the result should be a column vector of 0’s. The code word consists of a block of “parity” check bits, which has the same length as the number of rows, and a block of data bits. The rate of the code is the number of data bits divided by the number of columns in the matrix. The process of encoding is determining the set of parity bits that, when concatenated with the data bits, will multiply the parity check matrix and create a column of zeros. The decoding process determines the set of bits that were transmitted with this property based on the received packet [2].

In some cases, LDPC codes can be constructed to have better performance than Turbo codes, another widely used error correction code. Additionally, LDPC codes are advantageous in that they use a lower complexity iterative decoding “belief propagation” algorithm which can be implemented in parallel in hardware. The decoder is also very good at detecting errors in the received codeword while also determining when it is unable to correctly decode the packet. Although the encoding complexity is somewhat high, the powerful properties of LDPC codes have warranted their inclusion in many standards such as IEEE 802.16, 802.20, 802.3 and DVB-RS2 [2].

References¶

[1] David J. C. MacKay, Information Theory, Inference and Learning Algorithms Cambridge University, 2003
[2] T. K. Moon, Error Correcting Coding: Mathematical Methods and Algorithms New York: Wiley, 2005