This paper proposes a novel shift-sum decoding method for non-binary cyclic codes, which only requires finite field operations but yields advanced decoding performance. Using the cyclically different minimum-weight dual codewords (MWDCs) and their proper shifts, a frequency matrix can be obtained as a reliability metric for identifying the error positions and magnitudes. By analyzing the statistical distributions of the matrix entries, the rationale for the shift-sum decoding’s advanced error-correction capability is revealed. Based on this decoding method, a hard-decision iterative shift-sum (HISS) decoding algorithm is first proposed. It can correct errors beyond half of the code’s minimum Hamming distance. By further utilizing the reliability information obtained from the channel, a soft-decision iterative shift-sum (SISS) decoding algorithm is then proposed to improve the decoding performance. Both the HISS and the SISS algorithms are realized only with polynomial multiplications and numerical comparisons, which are hardware-friendly. To further improve the error-correction performance, the HISS and SISS algorithms can be integrated in a Chase decoding mechanism for handling the test-vectors. Simulation results on Reed-Solomon (RS) and non-binary BCH (NB-BCH) codes show that the proposed algorithms yield a competent decoding and complexity performances in comparison with the existing decoding algorithms.

This paper proposes the re-encoding transformed (ReT) based list decoding using the module basis reduction (BR) interpolation for algebraic geometric (AG) codes on Cabcurves. The two ReT approaches are introduced to facilitate the BR interpolation. One is realized by the bivariate Lagrange polynomial. The other is conducted by the ReT of Reed-Solomon (RS) codes based on the mathematical structure of AG codes. The ReT based BR interpolation (ReT-BR) algorithm for decoding the AG codes is further introduced. Finally, complexity of the proposed algorithm is analyzed and validated by the simulation results, demonstrating its complexity advantage over the non-ReT counterpart.

In this paper, we consider how to partition the parity-check matrices (PCMs) to reduce the hardware complexity and increase decoding throughput for the row layered decoding of quasi-cyclic low-density parity-check (QC-LDPC) codes. First, we formulate the PCM partitioning as an optimization problem, which targets to minimize the maximum column weight of each layer while maintaining a block cyclic shift property among different layers. As a result, we derive all the feasible solutions for the problem and propose a tight lower bound ωLBon the minimum possible maximum column weight to evaluate a solution. Second, we define a metric called layer distance to measure the data dependency between consecutive layers and further illustrate how to identify the solutions with desired layer distance from those achieving the minimum value of ωLB= 1, which is preferred to reduce computation delay. Next, we demonstrate that up-to-now, finding an optimal solution for the optimization problem with polynomial time complexity is unachievable. Therefore, both enumerative and greedy partition algorithms are proposed instead. After that, we modify the quasi-cyclic progressive edge-growth (QC-PEG) algorithm to directly construct PCMs that have a straightforward partition scheme to achieve ωLBor the desired layer distance. Simulation results showed that the constructed codes have better error correction performance and achieve less average number of iterations than the underlying 5G LDPC codes.

In this paper, we propose a mutual information-maximizing quantized layered min-sum (MIM-QLMS) decoder for quasi-cyclic low-density parity-check (QC-LDPC) codes. Our proposed decoder operates similarly to a layered min-sum decoder with additional reconstruction and quantization operations by using single-input lookup tables (LUTs). In particular, we first develop the protograph-based MIM density evolution to design the LUTs, which may differ for each iteration and each edge in the protograph of the QC-LDPC codes. Furthermore, to minimize the memory requirement for storing the LUTs, we propose an optimization method to unify all LUTs into only four distinct LUTs, which can be used for all decoding iterations. To the best of our knowledge, the proposed MIM-QLMS decoders are the first class of layered finite alphabet iterative decoders (FAIDs) that are designed based on accurately tracking the probability distributions of the exchanged messages. Simulation results show that for 3-bit (resp. 4-bit) exchanged message precision, the proposed MIM-QLMS decoders can reasonably (resp. generally) outperform the state-of-the-art layered FAIDs and the layered normalized min-sum decoder, in terms of both the error rate performance and the average number of iterations.

Using the minimum weight dual codewords (MWDCs) of a cyclic code, the shift-sum decoding can correct errors beyond half of the code's minimum Hamming distance. It utilizes the frequency of the syndrome polynomials' coefficients to identify the erroneous positions and correct the errors. This paper analyzes the plausibility of the shift-sum decoding for both binary and non-binary cyclic codes. It first determines the probability distributions of the frequency of the syndrome polynomials' coefficients as well as their expected values for the erroneous and non-erroneous positions. Based on these characterizations, this work further provides an analysis for the iterative shift-sum decoding, unveiling the statistical rationale on the shift-sum decoding's capability of correcting errors beyond the half distance bound.

This paper proposes the low-complexity Chase (LCC) decoding using basis reduction (BR) interpolation for Reed-Solomon (RS) codes, namely the LCC-BR algorithm. With received soft information, a number of decoding test-vectors are formulated. The LCC-BR algorithm first constructs a common basis which will be utilized by the following individual basis constructions of all test-vectors. This eliminates the redundant computation in BR interpolation, resulting in a low decoding complexity. Moreover, the LCC-BR algorithm can decode each test-vector in parallel, lowering the decoding latency. This paper further proposes the progressive LCC-BR (PLCC-BR) algorithm that decodes the test-vectors sequentially and terminates once the intended message is found. This progressive decoding is realized without additional memory cost. Simulation results show the complexity and latency advantages of the proposed algorithms over the other benchmark algorithms.

This paper proposes a novel shift-sum decoding scheme for non-binary cyclic codes. Using minimum-weight dual codewords and their cyclic shifts, a reliability measure can be yielded as an indicator for the error position and the error magnitude. Based on this shift-sum decoding concept, a harddecision iterative decoding algorithm is proposed, which can correct errors beyond half of the code’s minimum Hamming distance. By utilizing reliability information from the channel, a soft-decision iterative decoding algorithm is further introduced to improve the decoding performance. These two shift-sum based iterative decoding algorithms are realized with polynomial multiplication and integer (or real number) comparisons, which are hardware-friendly. Simulation results on Reed-Solomon codes and non-binary BCH codes show the decoding potential of the proposed algorithms.

The interpolation based algebraic soft decoding yields a high decoding performance for Reed-Solomon (RS) codes with a polynomial-time complexity. Its computationally expensive interpolation can be facilitated using the module structure. The desired Gröbner basis can be achieved by reducing the basis of a module. This paper proposes the low-complexity Chase (LCC) decoding algorithm using this module basis reduction (BR) interpolation technique, namely the LCC-BR algorithm. By identifying η unreliable symbols, 2ηdecoding test-vectors will be formulated. The LCC-BR algorithm first constructs a common basis which will be shared by the decoding of all test-vectors. This eliminates the redundant computation in decoding each test-vector, resulting in a lower decoding complexity and latency. This paper further proposes the progressive LCC-BR algorithm that decodes the test-vectors sequentially and terminates once the maximum-likelihood decision decoding outcome is reached. Exploiting the difference between the adjacent test-vectors, this progressive decoding is realized without any additional memory cost. Complexity analysis shows that the LCC-BR algorithm yields a lower complexity and latency, especially for high rate codes, which will be validated by the numerical results.

The Koetter-Vardy (KV) algorithm achieves advanced decoding performance for Reed-Solomon (RS) codes but with a high computational cost. This paper studies the lowcomplexity KV decoding that utilizes the module minimization (MM) interpolation technique, namely the KV-MM algorithm. A module contains bivariate polynomials that interpolate all the prescribed points with their multiplicity. Presenting the module basis as a matrix over univariate polynomials, row operation further reduces it into the Gröbner basis, delivering the interpolated polynomial. We will also introduce the re-encoding transformed KV-MM algorithm by giving an explicit construction for the module basis. This research shows MM interpolation yields a remarkably lower complexity for KV decoding than the conventional Koetter's interpolation, especially for high rate codes. This is also true when the re-encoding transform is applied. This finding is a rectification of some earlier results.

The interpolation based algebraic decoding for Reed-Solomon (RS) codes can correct errors beyond half of the code's minimum Hamming distance through constructing a minimum polynomial Q(x,y) and finding its y-roots. The progressive algebraic soft decoding (PASD) constructs Q(x, y) with a progressively enlarged y-degree and terminates once the message is decoded, adapting the decoding capability and computation to the channel. This paper proposes the re-encoding transformed PASD algorithm, in which Q(x, y) is progressively constructed by the low-complexity module minimization (MM) technique. Re-encoding transform (ReT) results in a common divisor for polynomials of the image of the submodule basis. It can be removed, leading to a simpler image expansion and reduction. Consequently, Q(x,y) is constructed through the isomorphic image of the progressively enlarged submodule basis. Our complexity analysis characterizes the complexity reduction brought by the transform and shows high rate codes benefit a greater complexity reduction.

The interpolation‐based algebraic decoding for Reed–Solomon (RS) codes can correct errors beyond half of the code's minimum Hamming distance. Using soft information, the algebraic soft decoding (ASD) further improves the decoding performance. This paper presents a unified study of two classical ASD algorithms, the algebraic Chase decoding and the Koetter‐Vardy decoding. Their computationally expensive interpolation is solved by the module minimisation (MM) technique which consists of basis construction and basis reduction. Compared with Koetter's interpolation, the MM interpolation yields a smaller computational cost for the two ASD algorithms. Re‐encoding transform is further applied to reduce the decoding complexity by reducing the degree of module generators. Based on assessing the degree of module seeds, a complexity reducing approach is introduced to further facilitate the two ASD algorithms. Computational cost of the two algorithms as well as their re‐encoding transformed variants will be analysed. Performance of the two ASD algorithms will be compared under decoding expenditure benchmark, providing more practical insights of their applications.

The algebraic soft-decision decoding (ASD) of Reed–Solomon (RS) codes yields a competent decoding performance with a polynomial-time complexity. But its complexity remains high due to the interpolation that generates the interpolation polynomial$Q(x,y)$. The progressive ASD (PASD) algorithm has been introduced to construct$Q(x,y)$with a progressively enlarged$y$-degree, adjusting its error-correction capability and computation to the received information. However, this progressive decoding is realized at the cost of memorizing the intermediate decoding information. To overcome this challenge, this paper proposes a new PASD algorithm which is evolved from the ASD using module minimization (MM) interpolation. Polynomial$Q(x,y)$can be constructed through the image of the progressively enlarged submodule basis without the need of memorizing the intermediate decoding information, eliminating the memory cost of progressive decoding. The MM interpolation also attributes to a remarkably lower complexity than the original PASD algorithm. Furthermore, a complexity reducing variant is proposed based on assessing the degree of Lagrange interpolation polynomials. We also analyze the complexity of the proposed decoding methods and reveal their channel dependent feature. Our simulation results show their low-complexity and advanced decoding performances.

The algebraic soft decoding (ASD) algorithm achieves advanced decoding performance for Reed-Solomon (RS) codes. However, its complexity remains high making it impractical. This is due to the interpolation. The progressive ASD (PASD) algorithm adjusts the decoding computation to the reliability of received information. Its interpolation generates the intended polynomial Q(x, y) with a progressively enlarged y- degree, and terminates once the message is decoded. But this progressive decoding is realized at the cost of memorizing the intermediate decoding information. This paper proposes a new PASD algorithm, in which the progressive interpolation is realized by the module minimization (MM) technique. Polynomial Q(x, y) can be found through the progressively enlarged images of submodule's basis without memorizing the intermediate decoding information. The MM interpolation also grants it a significantly lower complexity than the original PASD algorithm that uses Koetter's interpolation. Our simulation results will verify its advanced decoding performance and low-complexity feature.