Majority-logic decoding of binary block codes

Zakaria M’rabet, Fouad Ayoub, Mostafa Belkasmi

In this paper, we devise a non-binary version of the Soft-Input Soft-Output Iterative Threshold Decoder (ITD). This is a continuation of our work where the devised algorithm is the upgrade of the non-iterative non-binary Soft-Input Hard-Output Threshold Decoder (TD), which is itself an upgrade of previous work on the Hard-Input Hard-Output non-binary Majority-Logic Decoder (MLGD). The proposed ITD showed an improvement compared to its predecessors where coding gains of 1.5dB and 2.5dB were observed compared to the TD algorithm and the MLGD algorithm respectively, at a bit error rate (BER) of 10-5. The proposed decoder is best suited for One-Step Majority-Logic decodable codes with a large orthogonal structure in their dual codes, such as finite geometry codes, which are also Low-Density Parity-Check codes. The performances of our decoder are presented in terms of bit, symbol, and block error rates, and the proposed decoder has shown to outperform the best well-known decoders for LDPC codes as displayed by the simulation results. Where the proposed decoder offers a coding gain of 1dB compared to the Min-Max algorithm, 1.5dB of coding gain compared to the ISRB algorithm, and 1.6dB of coding gain compared to the KV algorithm at a block error rate (BLER) of 10-4. Also, the computational complexity of our decoder is proven to be lower than that of the ISRB algorithm, which has itself been proven to be less complex than the other algorithms in the study conducted by its authors.

Paul D. Laity

Saïd Nouh, Achraf El Khatabi, Mostafa Belkasmi

In this paper we present an efficient algorithm to decode linear block codes on binary channels. The main idea consists in using a vote procedure in order to elaborate artificial reliabilities of the binary received word and to present the obtained real vector r as inputs of a SIHO decoder (Soft In/Hard Out). The goal of the latter is to try to find the closest codeword to r in terms of the Euclidean distance. A comparison of the proposed algorithm over the AWGN channel with the Majority logic decoder, Berlekamp-Massey, Bit Flipping, Hartman-Rudolf algorithms and others show that it is more efficient in terms of performance. The complexity of the proposed decoder depends on the weight of the error to decode, on the code structure and also on the used SIHO decoder.

A. Murad, Thomas E. Fuja

Chenrong Xiong, Zhiyuan Yan

Non-binary low-density parity-check (LDPC) codes have some advantages as opposed to their binary counterparts, but unfortunately their decoding complexity is a significant challenge. Hence, the iterative soft-reliability-based (ISRB) majority-logic decoding algorithm is attractive for non-binary LDPC codes, since it involves only finite field additions and multiplications as well as integer additions and comparisons. In this paper, we propose an improved ISRB majority-logic decoding algorithm by using a new reliability update. Our improved algorithm achieves better error performance and faster convergence, while further reducing the computational complexity. For instance, for a (16, 16)-regular (255, 175) cyclic Euclidean geometry LDPC code over GF(28), the proposed algorithm achieves a 0.15 dB coding gain and improves the convergence speed by 10% at a block error rate of 10-4versus the ISRB majority-logic decoding algorithm. Compared with the ISRB majority-logic decoding algorithm, the proposed algorithm requires the same numbers of finite field additions and multiplications but fewer integer additions and comparisons. Furthermore, the ISRB majority-logic decoding algorithm is based on the accumulation of reliability information, and hence the numerical range of the reliability information increases with iterations. In contrast, the proposed reliability update has a fixed numerical range and thus simplifies hardware implementations.

V. Mimis