Search

In this paper, novel hard-decision iterative decoding algorithms for binary Reed-Muller (RM) codes are presented. First, two algorithms are devised based on the majority-logic decoding algorithm with reliability measures of the received sequence. The bit-flipping (BF) and the normalized bit-flipping (NBF) decoding algorithms are hard-decision decoding algorithms. According to the updated hard reliability measures, the BF and NBF algorithms flip one bit of the received hard-decision sequence at a time in each iteration. The NBF decoding algorithm performs better than the BF decoding algorithm by normalizing the reliability measures of the information bits. Moreover, the BF and NBF algorithms are modified to flip multiple bits in one iteration to reduce the average number of iterations. The modified decoding algorithms are called the multiple-bits-flipping (MBF) algorithm and the normalized multiple-bits-flipping (NMBF) algorithm, respectively. The proposed algorithms have low computational complexities and can converge rapidly after a small number of iterations. The simulation results show that the proposed hard-decision decoding algorithms outperform the conventional decoding algorithm.

We investigate the performance of majority-logic decoding in both reversible and finite-time information erasure processes performed on macroscopic bits that contain N microscopic binary units. While we show that for reversible erasure protocols single-unit transformations are more efficient than majority-logic decoding, the latter is found to offer several benefits for finite-time erasure processes: Both the minimal erasure duration for a given erasure and the minimal erasure error for a given erasure duration are reduced, if compared to a single unit. Remarkably, the majority-logic decoding is also more efficient in both the small-erasure error and fast-erasure region. These benefits are also preserved under the optimal erasure protocol that minimizes the dissipated heat. Our work therefore shows that majority-logic decoding can lift the precision-speed-efficiency trade-off in information erasure processes.

This paper studies an extension and improvement of the joint detection-decoding algorithm for nonbinary LDPC-coded modulation systems. The iterative joint detection-decoding (IJDD) algorithm in [1] combines nonbinary LDPC decoding with signal detection based on the hard-message passing strategy, resulting in significantly reduced decoding complexity. However, it applies only to majority-logic decodable nonbinary LDPC codes with high column weight. For nonbinary LDPC codes with low column weight, a noticeable performance loss will be incurred. To handle this problem, we propose a reliability-based iterative joint detection-decoding (also termed improved IJDD) algorithm, which combines the accumulated reliability of symbols based on the one-step majority-logic decoding (MLGD) algorithm and a Chase-like local list decoding algorithm. Simulation results show that the improved IJDD algorithm outperforms the IJDD algorithm by about 0.3 dB using nonbinary LDPC codes with high column weight, and by about 3 dB using nonbinary LDPC codes with low column weight (dv = 4), while maintaining the low complexity of decoding. Compared to the FFT-QSPA, the proposed algorithm has a performance degradation of 0.5 dB in the high column weight regime, and about 1 dB in the low column weight regime. [ABSTRACT FROM AUTHOR]

This paper presents bit-reliability based majority-logic decoding (MLgD) algorithms for non-binary LDPC codes. The proposed algorithms pass only one Galois field element and its reliability along each edge of the Tanner graph of a non-binary LDPC code. Since their reliability updates are in terms of bits rather than symbols, they are more efficient than traditional MLgD based decoding algorithms. By weighting the soft reliability of the extrinsic information-sums based on their hard reliability, the proposed algorithms can achieve good error performance for non-binary LDPC codes with various column weights. Moreover, their computational complexity and memory consumption are remarkably reduced compared with existing MLgD based decoding algorithms. As a result, they provide effective tradeoffs between error performance and complexity for decoding of non-binary LDPC codes. [ABSTRACT FROM AUTHOR]

We propose an easy-to-implement hard-decision majority-logic decoding algorithm for Reed—Muller codes RM(r,m) with m ≥ 3, m/2 ≥ r≥ 1. The presented algorithm outperforms the best known majority-logic decoding algorithms and offers highly parallel decoding. The result is of special importance for safety- and time-critical applications in embedded systems. A simple combinational circuit can perform the proposed decoding. In particular, we show how our decoder for the three-error-correcting code RM(2, 5) of dimension 16 and length 32 can be realized on hardware level. [ABSTRACT FROM PUBLISHER]

Short-length Reed—Muller codes under majority-logic decoding are of particular importance for efficient hardware implementations in real-time and embedded systems. This paper significantly improves Chen's two-step majority-logic decoding method for binary Reed—Muller codes RM(r,m), r ≤ m/2, if — systematic encoding assumed — only errors at information positions are to be corrected. Some general results on the minimal number of majority gates are presented that are particularly good for short codes. Specifically, with its importance in applications as a 3-error-correcting, self-dual code, the smallest non-trivial example, RM(2,5) of dimension 16 and length 32, is investigated in detail. Further, the decoding complexity of our procedure is compared with that of Chen's decoding algorithm for various Reed—Muller codes up to length 2^10. [ABSTRACT FROM AUTHOR]

This paper presents two novel reliability-based iterative majority-logic decoding algorithms for LDPC codes. Both algorithms are binary message-passing algorithms and require only logical operations and integer additions. Consequently, they can be implemented with simple combinational logic circuits. They either outperform or perform just as well as the existing weighted bit-flipping or other reliability-based iterative decoding algorithms for LDPC codes in error performance with a faster rate of decoding convergence and less decoding complexity. Compared to the sum-product algorithm for LDPC codes, they offer effective trade-offs between performance and decoding complexity. [ABSTRACT FROM AUTHOR]

We investigate the performance of majority-logic decoding in both reversible and finite-time information erasure processes performed on macroscopic bits that contain N microscopic binary units. While we show that for reversible erasure protocols single-unit transformations are more efficient than majority-logic decoding, the latter is found to offer several benefits for finite-time erasure processes: Both the minimal erasure duration for a given erasure and the minimal erasure error for a given erasure duration are reduced, if compared to a single unit. Remarkably, the majority-logic decoding is also more efficient in both the small-erasure error and fast-erasure region. These benefits are also preserved under the optimal erasure protocol that minimizes the dissipated heat. Our work therefore shows that majority-logic decoding can lift the precision-speed-efficiency trade-off in information erasure processes. [ABSTRACT FROM AUTHOR]