Symbol flipping decoding of non-binary low density parity check codes

Abstract

NB-LDPC codes have shown better bit error performance than their binary counterpart but at the cost of an increased computational complexity. Furthermore, these decoding algorithms need to be implemented efficiently to fulfil the cost, time, power and bandwidth requirement. In addition, NB-LDPC codes are capable of correcting symbol wise error and are particularly suitable for burst noise channels where multiple bits are corrupted successively. The classical sum-product non-binary LDPC algorithm has a better performance than binary sum-product algorithm for short block length and low-rate codes. Using iterative belief propagation algorithms, NB-LDPC codes can be decoded in time linear to the block length. High decoding complexity is a main challenge in VLSI implementation of NB-LDPC codes. The research in this thesis is focused on proposing low complexity symbol flipping NB-LDPC decoding algorithms achieving the low complexity design of decoder to ensure optimum performance both at the waterfall and error floor regions. This thesis presents three new approaches to develop low complexity and improved performance symbol flipping NB-LDPC decoding algorithms. Firstly, a method of short-listing through voting has been introduced to update variable nodes which possibly have incorrect tentative decision and are most likely to be corrected. The proposed method plays key role in reducing complexity and enhances the error correction capability of the NB-LDPC decoder. Five improved algorithms are presented using the voting based short-listing of the variable nodes. These five algorithms are used with BPSK modulation. The proposed schemes give an appealing trade-off between complexity and performance in comparison to the existing schemes. The method of short-listing by voting significantly lowers the decoding computational complexity. Secondly, to achieve the goal of high data rate using higher order QAM modulation, new joint iterative detection-decoding NB- LDPC algorithms are presented. Three new algorithms for improving the bit error rate performance of the non-binary LDPC decoder are presented. The first type is the symbol flipping decoding algorithm using a flipping function based on the channel reliability to identify the least reliable symbol position. The second and third type of joint algorithms are improvement to iterative joint detection-decoding algorithm by using the method of iterative hard decision based majority logic to select the new candidate symbol value. In these algorithms, if the predicted symbol value satisfies the check sum, then the value is declared as correct otherwise the value is adjusted and sent back to the QAM detector. The feedback value to the QAM detector is adjusted by using Euclidean distance between the current symbol and the newly selected symbol value. The complexity analysis shows that these proposed decoding algorithms help in reducing the overall latency. Thirdly, a layered based symbol flipping decoding algorithm is proposed for BPSK modulation. Layered decoding is the way to get efficient and high-throughput implementation of LDPC decoders. A new adaptive grouping of variable nodes in each iteration using bit reliability and majority voting of individual received symbol is presented for the class of symbol flipping decoding of NB-LDPC codes. Grouping of variable nodes and the subsequent decoding is based on individual symbol reliability and majority logic voting. Voting and bit reliability of symbols are used to form groups from high priority to low priority. A high priority group is considered to contain most un-reliable variable nodes and is decoded on priority while the second priority group contains variable nodes having second level of reliability. This novel hard decision adaptive group based decoding algorithm is different from the scheme used for soft iterative message passing algorithms. Though in this method, apparently the cumulative density function to forms groups increases complexity but it is computed once for each value of SNR but the overall decoding computational complexity is reduced as only the selected group is proceed. Therefore, this proposed scheme can be considered suitable for many applications.