The Inspiration Of Ldpc Codes

The full name of LDPC code is low-density parity-check code, which means only few 1’s are shown on the parity-check matrix. For a linear block code, such as LDPC codes, we can find a fundamental decoding condition, cHT=0 where c is a code word and H is a parity-check matrix. If we do the matrix multiplication, we may get the following results. For example, c0+c1+c3=0; c3+c4+c7=0 where ci is the ith coded bit. Therefore, c0 is only influenced by c1 and c3.

Gallager proposed LDPC codes in 1962. The inspiration of LDPC codes is from less influence among different coded bits. For any code word, every coded bit can be corrected by two other bits assumed that there are three 1’s in a parity-check matrix row. If intrinsic information (received probability) doesn’t affect every coded bit, we can correct error bits through other extrinsic information (propagated probability). As block size increases, the coded bits become less correlated. Thus, we think of every coded bit as an independent bit and do an iterative algorithm called belief propagation. Finally, the decoded bits will be determined by both intrinsic information and extrinsic information.

http://www.shvoong.com/exact-sciences/engineering/electrical-engineering/communications-signal-processing/1630485-inspiration-ldpc-codes/

Properties of LDPC Codes

1.Properties of LDPC Codes
1.1 Sparse Parity Matrix
A sparse matrix is a matrix populated with few ones in each row and column. More precisely, the ratio of nonzero entries into that matrix is kept low. This is the reason why they are called “low-density”. In particular, an (n,wc,wr) low-density-code is a code of block length n with a matrix like that of Fig..1 whose parity matrix has wc 1’s in each column, and wr 1’s in each row.

Fig. 1 low-density code matrix; N=20, wc =3, wr =4

1.2 Regular LDPC Codes
A regular LDPC code is a linear block code whose parity matrix H contains exactly wc 1’s in each column and wr = wc(n/n-k) 1’s in each row. The code rate is k/n and wc is extremely smaller than (n-k). Similarly, wr is extremely smaller than n. In [3], Markey shows that wc = 3 is necessary for good codes.

1.3 Irregular LDPC Codes
If the number of 1's per column or row is not constant, the code is an irregular LDPC code. It’s very easy to determine whether an LDPC code is regular or irregular through its graphical representation. Usually, irregular LDPC codes outperform regular LDPC codes.

2. Characteristics of LDPC Codes
In some specific situations, we can get the following characteristics.
2.1 Large dmin
Some facts can help LDPC codes achieve this goal. First, any two columns have an overlap of at most one 1. Secondly, the sparse property allows us to avoid over-lapping. Less over-lapping means high independence among different coded bits. The condition makes LDPC decoder good decoding ability and low bit error rate.

2.2 Low Complexity
The "Low Density" characteristic only applies to the H matrix (i.e., the parity check matrix). H matrix is a decision criterion and represents decoding algorithm. Thus, lower density in the H matrix yields low-complexity in the decoder.

3 Advantage of LDPC codes
3.1 Near-capacity Performance
Shannon's theory tells us that “long” and “random” codes achieve capacity. LDPC codes provide the solution and attain near-capacity performance. However, it doesn’t mean that an LDPC code is the best code. Different codes are good at different things. For example, Turbo Codes are better at low code rates, i.e., R = 1/2 and below.

We know that irregular LDPC codes have better performance than regular LDPC codes. Therefore, the key to a good LDPC code is how to design it. There are methodical procedures for designing LDPC codes, especially irregular ones. [4] proposes a class of efficiently encodable irregular LDPC codes which might be called extended IRA codes.

LDPC Codes History

The history of coding starts with the seminal work of Claude Shannon on the mathematical theory of communication in 1948. He demonstrated that errors induced by a noisy channel can be reduced to any desired level as long as the information rate is less than the capacity of the channel. The theoretical maximum information transfer rate is called Shannon limit.

In 1962, Gallager proposed a low-density parity-check code in his doctoral dissertation. LDPC codes are defined by a sparse parity-check matrix. They provided near-capacity performance but difficult implementation. Also, the concatenated RS and convolutional codes were considered perfectly suitable for error control coding. Thus, his remarkable thesis was forgotten by coding researchers for almost 20 years. In 1981, Tanner generalized LDPC codes and created a bipartite graph used to represent those codes. However, it was still ignored by coding theorists.

LDPC codes were noticed again by some researchers in the mid-1990’s. They began to investigate codes on graph and iterative decoding. Markey and other researchers discovered the advantage between linear block codes which generated by sparse matrix and iterative decoding based on belief propagation. And by that time the decoding complexity looked achievable. Since that time, a lot of papers have been published and LDPC has become popular so far.