Techniques to improve iterative decoding of linear block codes

Abstract

In the field of forward error correction, the development of decoding algorithms with a high error correction performance and tolerable complexity has been of great interest for the reliable transmission of data through a noisy channel. The focus of the work done in this thesis is to exploit techniques used in forward error correction in the development of an iterative soft-decision decoding approach that yields a high performance in terms of error correction and a tolerable computational complexity cost when compared to existing decoding algorithms. The decoding technique developed in this research takes advantage of the systematic structure exhibited by linear block codes to implement an information set decoding approach to correct errors in the received vector outputted from the channel. The proposed decoding approach improves the iterative performance of the algorithm as the decoder is only required to detect and correct a subset of the symbols from the received vector. These symbols are referred to as the information set. The information set, which matches the length of the message, is then used decode the entire codeword. The decoding approach presented in the thesis is tested on both Reed Solomon and Low Density Parity Check codes. The implementation of the decoder varies for both the linear block codes due to the different structural properties of the codes. Reed Solomon codes have the advantage of having a row rank inverse property which enables the construction of a partial systematic structure using any set of columns in the parity check matrix. This property provides a more direct implementation for finding the information set required by the decoder based on the soft reliability information. However, the dense structure of the parity check matrix of Reed Solomon codes presents challenges in terms of error detection and correction for the proposed decoding approach. To counter this problem, a bit-level implementation of the decoding technique for Reed Solomon codes is presented in the thesis. The presentation of the parity check matrix extension technique is also proposed in the thesis. This technique involves the addition of low weight codewords from the dual code, that match the minimum distance of the code, to the parity check matrix during the decoding process. This helps add sparsity to the symbol-level implementation of the proposed decoder. This sparsity helps with the efficient exchange of the soft information during the message passing stage of the proposed decoder. Most high performance Low Density Parity Check codes proposed in literature lack a systematic structure. This presents a challenge for the proposed decoding approach in obtaining the information set. A systematic construction for a Quasi-Cyclic Low Density Parity Check code is also presented in this thesis so as to allow for the information set decoding. The proposed construction is able to match the error correction performance of a high performance Quasi-Cyclic Low Density Parity Check matrix design, while having the benefit of a low complexity construction for the encoder. In addition, this thesis also proposes a stopping condition for iterative decoding algorithms based on the information set decoding technique. This stopping condition is applied to other high performance iterative decoding algorithms for both Reed Solomon codes and Low Density Parity Check codes so as to improve the iterative performance. This improves on the overall efficiency of the decoding algorithms.