Threshold based multi-bit flipping decoding of binary LDPC codes - Masunda, Kennedy Tohwechipi Fudu (My University, 2017)
There has been a surge in the demand of high speed reliable communication infrastructure in the last few decades. Advanced technology, namely the internet has transformed the way people live and how they interact with their environment. The Internet of Things (IoT) has been a very big phenomenon and continues to transform infrastructure in the home and work place. All these developments are underpinned by the availability of cost-effective, reliable and error free communication services. A perfect and reliable communication channel through which to transmit information does not exist. Telecommunication channels are often characterised by random noise and unpredictable disturbances that distort information or result in the loss of information. The need for reliable error-free communication has resulted in advanced research work in the field of Forward Error Correction (FEC). Low density parity check (LDPC) codes, discovered by Gallager in 1963 provide excellent error correction performance which is close to the vaunted Shannon limit when used with long block codes and decoded with the sum-product algorithm (SPA). However, long block code lengths increase the decoding complexity exponentially and this problem is exacerbated by the intrinsic complexity of the SPA and its approximate derivatives. This makes it impossible for the SPA to be implemented in any practical communication device. Bit flipping LDPC decoders, whose error correction performance pales in comparison to the SPA have been devised to counter the disadvantages of the SPA. Even though, the bit flipping algorithms do not perform as well as the SPA, their exceeding low complexity makes them attractive for practical implementation in high speed communication devices. Thus, a lot of research has gone into the design and development of improved bit flipping algorithms. This research work analyses and focusses on the design of improved multi-bit flipping algorithms which converge faster than single-bit flipping algorithms. The aim of the research is to devise methods with which to obtain thresholds that can be used to determine erroneous sections of a given codeword so that they can be corrected. Two algorithms that use multi-thresholds are developed during the course of this research. The first algorithm uses multiple adaptive thresholds while the second algorithm uses multiple near optimal SNR dependant fixed thresholds to identify erroneous bits in a codeword. Both algorithms use soft information modification to further improve the decoding performance. Simulations show that the use of multiple adaptive or near optimal SNR dependant fixed thresholds improves the bit error rate (BER) and frame error rate (FER) correcting performance and also decreases the average number of iterations (ANI) required for convergence. The proposed algorithms are also investigated in terms of quantisation for practical applications in communication devices. Simulations show that the bit length of the quantizer as well as the quantization strategy (uniform or non-uniform quantization) is very important as it affects the decoding performance of the algorithms significantly.
Submitted in fulfilment of the academic requirements for the Master of Science in Engineering in Electrical and Information Engineering degree in the School of Electrical and Information Engineering at the University of Witwatersrand, Johannesburg, South Africa. August 2017
Keywords: Coding theory; Error-correcting codes (Information theory); Algorithms; Telecommunication; Information theory