Research On The Regular Low-Density Parity-Check Codes

In 1948, Shannon clarified the approach for reliably communication is channel coding. As one of the cores in communication system, the channel coding arrests more and more engineers' attention. The Shannon information theory is elementary in the field of channel coding technology, which also guided their developments.LDPC(Low-Density Parity-Check) Codes who have sparse check matrix and can be denoted by bipartite graph were proposed by Gallarge in 1962. The codes have performance approaching Shannon limit, their decoding procedure have low complexity and can be operated parallelly, which suits for hardware application. The LDPC codes attracted few attentions at that time due to the computation limit until the invention of Turbo codes. Since the rediscovery of LDPC codes in recent years, there has been renewed interest in LDPC codes.This paper first researched LDPC codes in encoding and decoding respectively. On the hand of encoding, the direct encoding destroys the sparse property of the check matrix, the complexity was high. The paper studied some simplify encoding algorithm which can encode under approximately linear complexity and proposed an algorithm based on iteratively erasure decoding, which also has approximately linear complexity and the preprocessing is simpler,the algorithm calculated a few key check bites first, then regarded the remain check bits as erased, those erased bits can be recovered through the iterative erasure decoding. On the other hand of decoding, iterative message passing algorithm has been employed to decode. In each iteration, the message was propagated between the check nodes and bit nodes in the Tanner graph. Having studied the iterative algorithm based on probability domain and LLR domain, a simplified BP algorithm was present. The algorithm improved the flow of decoding procedure and speeded up the decoding by decreasing the number of loops in each iteration.Tanner graph for LDPC codes have cycles, when the number of iterations reach the quantity of the minimum cycle (girth), the messages propagated between the nodes became dependent which will hurt the performance. So the girth should be considered in the construction of LDPC codes. The paper reviewed some present construction and proposed some design method to construct LDPC codes with large girth. The first one was based on 3D lattice, under this construction, girth 8 LDPC codes can be designed with column weight greater than 3, for column weight 3 codes design, a method based on 2D lattice was present, the last construction was recursive one, which was used to designed column weight 2 LDPC codes with girth 12 or 16. All the codes are cyclic or quasi-cyclic, which is easy to encode and store.Due to the important role of girth, the paper studied the girth distribution of LDPC codes. Beside it, density evolution and code distance are also studied. Density evolution is a very important tool to analyze LDPC code, which is used to calculate the capacity of an ensemble of codes with specified degree distribution, additionally, it can solve the problem of finding good degree distribution. Beside it, minimum distance is also important for error correcting codes. The most popular way to compute the code weight distribution was based on impulse-error method. Different from it, a novel algorithm based on cycle-expanding was introduced. For a cycle in the Tanner graph, a tree was expanded from the bit nodes in the cycle, in each depth, employing the erasure decoding algorithm to find stopping set, due to a code word can be regarded as a special stopping set, so the algorithm can find a lot of low weight code words, the lowest weight found was the minimum distance of the LDPC code. Comparing with other algorithm, it was relatively fast.