Low-Density Parity Check (LDPC) Encoding

Low-density parity check (LDPC) is a linear error-correcting code that uses a parity check matrix that provides only a few 1s with respect to a much larger number of 0s. The main advantage of the parity check matrix is that it provides a performance that is close to the capacity of many different channels and linear time complex algorithms for decoding. Furthermore, parity check matrices are suited for implementations that make heavy use of parallelism.

An LDPC code is a block code that has a parity check matrix H, every row and column of which is sparse. A Regular Gallager Code is a LDPC code in which every column of H has some weight, j, and every row has some weight, k. Regular Gallager codes are constructed at random subject to these constraints.

For example, if

• the number of ones in each column (j) = 3
• the number of ones in each row (k) = 6
• the number of columns (n) = 12
• the number of rows (m) = 6 (because m = n*j/k)
• the rate of (n, j, k) LDPC Code is R≥ 1- (j/k)

Then

If the number of 1s per column or row is not constant, the code is an irregular LDPC code. Usually, irregular LDPC codes outperform regular LDPC codes.

Refer to the following resources for more information about the algorithms and methods used in LDPC coding:

• Bernhard M. J. Leiner, "LDPC codes - a Brief Tutorial," April 2005. http://users.tkk.fi/pat/coding/essays/ldpc.pdf
• Shokrollahi, Amin. LDPC Codes: An Introduction. Digital Fountain, Inc. Fremont: 2004. http://www.ipm.ac.ir/IPM/homepage/Amin2.pdf
• Richardson, Thomas J. and Rüdiger L. Urbanke. "Efficient Encoding of Low-Density Parity-Check Codes." IEEE Transactions on Information Theory 47(2): 2001.
• The flooding decoding algorithm is according to following reference : Sun, Jian. "An Introduction to Low Density Parity Check (LDPC) Codes." WCRL Seminar Series Wireless Communication Research Laboratory,West Virginia University: 2003.
• The serial decoding algorithm is according to following reference : Sharon, E. et al. "An Efficient Message Passing Schedule for LDPC Decoding." 2004 23rd IEEE Convention of Electrical and Electronics Engineers in Israel 23: 2004.