Wednesday, 18 July 2007

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.

No comments: