Research On Efficient Bit Flipping Deconding Algorithm For LDPC Codes

Low-density parity-check(LDPC)codes have error correction performance close to the Shannon limit.Meanwhile,LDPC codes have low decoding complexity and high throughput.As a result,LDPC codes are widely used in practical applications.The bit flipping(BF)decoding algorithm of LDPC codes has the lowest complexity,but the error correction performance is also the worst.It is of great significance to study and improve the BF decoding algorithm of LDPC codes.This thesis aims to study and improve the BF decoding of LDPC codes under binary symmetric channels.The specific work content is as follows:(1)We introduce the basic knowledge of LDPC codes,and elaborate on a variety of classical BF algorithms: original BF algorithm,gradient descent bit flipping(GDBF)algorithm,probabilistic gradient descent bit flipping(PGDBF)algorithm,probabilistic parallel bit flipping(PPBF)algorithm,tabu-list random-penalty gradient descent bit flipping(TRGDBF)algorithm and information storage bit flipping(ISBF)algorithm.(2)Inspired by the idea of column layered scheduling of the belief propagation(BP)algorithm,for a variety of BF algorithms that require threshold calculation,the layered idea is applied to the BF algorithm,and the layered BF algorithm is obtained.Meanwhile,in order to further simplify the computation of flipping threshold based on layer threshold,two effective techniques are used: the forward-backward calculation method and the two-max approximation method.Simulation results based on the(3,6)LDPC code show that the layered BF scheme has a great improvement in terms of both error correction performance and throughput.Especially,compared to the PGDBF algorithm,the layered PGDBF algorithm can reduce the frame error rate and bit error rate by one order,and reduce the average number of iterations by about 40%.(3)We consider to improve two BF algorithms.On the one hand,for the GDBF algorithm that requires threshold calculation,a partial probabilistic gradient descent bit flipping(PPGDBF)scheme and a threshold gradient descent bit flipping(TGDBF)scheme are proposed.Simulations show that the PPGDBF algorithm can achieve a tradeoff between the error correction performance and the throughput compared to the GDBF algorithm and the PGDBF algorithm,and the TGDBF algorithm can reduce the frame error rate and bit error rate by at least one order compared with the GDBF algorithm at the cost of slightly increasing the average number of iterations.On the other hand,for the PPBF algorithm that does not need threshold calculation,a threshold is added,leading to a cyclic threshold probabilistic parallel bit flipping(CTPPBF)algorithm.Through simulations,it is found that the CTPPBF algorithm can reduce the frame error rate and bit error rate by 2% compared with the PPBF algorithm,and reduce the average number of iterations by about 14%.In this thesis,the principle of the BF decoding algorithms are revealed,and various improved BF decoding schemes are proposed to achieve better error correction performance and/or lower average number of iterations.This is of great significance for promoting and strengthening the application of the BF decoding algorithms of LDPC codes in practice.