Performance estimation, code construction and decoding of finite-length low-density parity-check codes

Chenying Wang

Guangen Wu, Pinyi Ren

Focused on the problem that short cycles degrade the iterative decoding performance of finite length LDPC, a class of improved low density parity check (LDPC) codes constructed based on Gallager's form is designed. On the basis of keeping down the basic form of Gallager's construction, a quasi-cyclic form is used, then the new codes are free of cycles of length 4 and have good minimum distance. Simulation results demonstrated that the improved codes are better than Gallager's codes when block length is small

Junho Cho

Eric T. Psota

Low-density parity-check codes are commonly decoded using iterative message-passing decoders, such as the min-sum and sum-product decoders. Computer simulations demonstrate that these suboptimal decoders are capable of achieving low probability of bit error at signal-to-noise ratios close to capacity. However, current methods for analyzing the behavior of the min-sum and sum-product decoders fails to produce usable bounds on the probability of bit error. Thus, the resulting probability of bit error when using these decoders remains largely unknown for signal-to-noise ratios beyond the reach of simulation. For this reason, it is worth considering alternative methods for decoding low-density parity-check codes. New methods for decoding low-density parity-check codes, known as finite tree-based decoders, are presented as alternative decoders for low-density parity-check codes. The goal of the finite tree-based decoders is to achieve probability of bit error comparable to that of the min-sum and sum-product decoders, while allowing for computationally tractable performance analysis. Finite tree-based decoding requires the construction of finite trees derived from the Tanner graph of the low-density parity-check code. The resulting size of the finite trees allows for current analytical techniques, such as deviation bounds and density evolution, to be used to predict the probability of bit error of finite tree-based decoding of short-to-moderate length low-density parity-check codes. Simulation results show that finite tree-based decoders are capable of outperforming current iterative decoders at high signal-to-noise ratios. Examples are also given where finite tree-based decoding provably approaches maximum-likelihood performance as the signal-to-noise ratio grows large. A new method is also presented for lower bounding the minimum distance of low-density parity-check codes. This new lower bound is used as a cost criteria for the construction of low-density parity-check codes with both large girth and minimum-distance properties. Codes generated with this new construction technique are shown in simulations to outperform codes generated with the progressive edge-growth algorithm, using both iterative decoding and finite tree-based decoding.

Xudong Ma

S. Hirst, B. Honary

A generalised low-density parity-check code (GLDPC) is a low-density parity-check code in which the constraint nodes of the code's graph are replaced with component or subcodes other than single parity checks. Gallager's bit-flipping algorithm for LDPCs is generalised to the class of GLDPCs with Hamming subcodes. The proposed weighted bit-flip voting (WBFV) method is iterative and uses only the hard decision decoder of the Hamming subcodes. Decoding of Hamming-based GLDPCs using WBFV has been simulated on the binary symmetric channel. Simulation results are presented showing the variation in performance with voting rule, graph construction and block length. In terms of the dependence of coding gains and complexity on the GLDPC block length, the proposed method is found to display a good performance to decoding complexity trade-off. Performance is found to compete well with other more conventional hard decision decoding schemes.