In this thesis we present our work in the domain of non-binary decoding algorithm for general classes of non-binary LDPC codes. Binary Low-Density Parity-Check (LDPC) codes were originally presented by Gallager in 1963, and after some fundamental theo- retical advancement, they were considered in standards like DVB-S2, WI-MAX, DSL, W-LAN etc. Later on, Non-Binary LDPC (NB-LDPC) codes were proposed in liter- ature, and showed better performance for small lengths or when used on non-binary channels. However, the advantages of using NB-LDPC codes come with the conse- quence of a heavily increased decoding complexity. For a code defined in GF (q), the complexity is of the order O (q2). Similarly, the memory required for storing messages is of order O (q). Consequently, the implementation of an LDPC-decoder defined over a field order q > 64 becomes practically impossible. The main objective of the thesis is to develop reduced complexity algorithms for non-binary LDPC codes that exhibit excellent performance and are practically implementable. For better decoding per- formance, not only the decoding algorithm is important, but also the structure of the code plays an important role. With this goal in mind, a new family of codes called cluster-NB-LDPC codes was developed and specific improvements of the NB decoder for cluster-NB-LDPC codes were proposed. Our principal result is that we were able to propose decoders for cluster-NB-LDPC codes with reduced complexity compared to usual decoders for NB-LDPC codes on fields, without any performance loss in error correction capability. iv Acknowledgements In the first part of the thesis, we modify the EMS algorithm for cluster codes. We see that the direct implementation of the EMS algorithm to NB cluster-LDPC codes is not a feasible option. There is a loss in performance and an increase in decoding complexity. Therefore, we propose some modification in the procedure, which not only significantly improves the decoding performance but also decreases the decoding complexity. It places the same limits on the number of operations at the check nodes as the EMS algorithm for GF (q)-codes i.e. O (nmlognm), with nm << q. We then propose another method, based on the diversity of cluster codes, to improve the per- formance of the EMS algorithm for cluster codes. It also helps in reducing the overall complexity of the decoder. In the end we compare the decoding performance using this method and analyze the effect on the decoding complexity. In the last part of the chapter, we propose a new direction for the decoding of LDPC codes. It is based on the creation of lists of codewords that are local to the parity check nodes. The list is constructed recursively in a tree structure, which makes it a good candidate for hardware implementation. It is a new method and requires further im- provement. As an initial report, we have obtained good results with less number of computations.
