Algebraic codes are important in communication and storage systems where soft information is limited and decoding efficiency is critical. Among them, algebraic-geometric (AG) codes are promising candidates to replace the widely used Reed-Solomon (RS) codes. However, their more sophisticated algebraic structure results in high decoding complexity, hindering their practical application. This paper proposes a novel interpolation-based algebraic soft decoding (ASD) for one of the most important AG codes - Hermitian codes. Given a designed maximum decoding output list size (OLS), the interpolation module is constructed, and the decoding is formulated as finding a desired Gröbner basis of this module that contains the interpolation polynomial. The re-encoding transform (ReT) specifically designed for ASD is proposed, enabling the modified basis reduction (BR) interpolation to achieve lower complexity. The ReT is formulated by defining Lagrange interpolation polynomials over the Hermitian function fields and appropriately choosing the re-encoding points. By exploiting the linear code property, the ReT transforms a subset of interpolation points to have zeroz-coordinates, which allows a common factor to be extracted from the module basis polynomials, thereby simplifying the interpolation. This paper further proposes an improved ReT employing more re-encoding points. It enables the common factor to have a greater degree, yielding a more significant complexity reduction. This also leads to an early termination for the decoding. Theoretical analysis and numerical results demonstrate that the two proposed ReT schemes efficiently facilitate the ASD for Hermitian codes.

This paper proposes a new interpolation-based algebraic soft decoding (ASD) for Hermitian codes. The interpolation is realized through basis reduction (BR) that is facilitated by the re-encoding transform (ReT). The ReT is formulated by defining Lagrange interpolation polynomials over the Hermitian function fields and choosing proper re-encoding points. It transforms the interpolation points, which can lead to a reduced BR interpolation complexity. With a designed decoding output list size (OLS), the interpolation module basis can be formulated. The ReT results in polynomials of the module basis having a common factor. It can be extracted from the polynomials, resulting in a simpler basis reduction. An enhanced ReT is further proposed. It enables the basis polynomials having a common factor with a greater degree, yielding a more significant complexity reduction. Numerical results show that both of the two proposed ReT can facilitate the ASD for the advanced decoding of Hermitian codes.

This paper proposes the low-complexity Chase (LCC) decoding for Hermitian codes, which is facilitated by both the improved interpolation and root-finding. By identifying$\eta $unreliable received symbols,$2^{\eta }$test-vectors are formulated, each of which is decoded by the interpolation based Guruswami-Sudan (GS) algorithm. To reduce both the interpolation complexity and latency, the re-encoding transform (ReT) is introduced through defining the Lagrange interpolation polynomials over the Hermitian function fields. The interpolation polynomial is further computed through module basis reduction (BR) that yields the Gröbner basis that contains the desired polynomial. The BR interpolation exhibits a greater parallelism than the conventional Kötter’s interpolation. Moreover, the$2^{\eta }$root-finding processes are facilitated by estimating the codewords directly from the interpolation outcomes. It eliminates the re-encoding computation for identifying the most likely candidate from the decoding output list. It is also shown that the average LCC decoding complexity can be further reduced by both assessing the re-encoding outcome and decoding the test-vectors progressively. They can achieve an early decoding termination once a codeword that satisfies the maximum likelihood (ML) criterion is found. Our simulation results demonstrate that the decoding complexity and latency can be significantly reduced over the existing decoding algorithms.

This paper proposes two low-complexity Chase (LCC) decoding algorithms for elliptic codes, which are realized by K¨otter’s interpolation and the basis reduction (BR) interpolation, respectively. They are both developed from the perspective of computing the Gr¨obner bases of the interpolation modules. By identifying η unreliable symbols, 2η decoding testvectors are formulated and the corresponding interpolation modules can be defined. The re-encoding transform (ReT) is further introduced to facilitate the interpolation. The LCC-K ¨otter decoding performs interpolation for the common elements, producing an intermediate outcome shared by all test-vectors. The desired Gr¨obner basis w.r.t. each test-vector can be obtained in a binary tree growing fashion. The new interpolation process can start from intermediate nodes of the previously interpolated paths, resulting in a low complexity. But the decoding latency cannot be contained. In contrast, the LCC-BR decoding performs the common computation in basis construction, which partly substantiates the bases for all interpolation modules. The subsequent basis construction and reduction can be performed in parallel. Besides a low complexity, it offers a latency advantage over the LCC-K¨otter decoding. The decoding complexity and latency are analyzed and verified numerically. The LCC decoding performance are also presented, demonstrating their advantage over both the Guruswami-Sudan decoding and the algebraic soft decoding. Moreover, the performance advantage of elliptic codes over the Reed-Solomon (RS) codes is demonstrated.

This paper proposes an efficient root-finding algorithm for the interpolation-based unique decoding of one-point elliptic and hyperelliptic codes. Instead of finding a message polynomial, it directly computes a codeword from the interpolation polynomial. It first determines the error positions through the error locator polynomial that is contained in the interpolation polynomial. Subsequently, the corresponding codeword symbols are determined based on the root-finding equation that is reformulated as a linear system of univariate polynomials. The proposed algorithm demonstrates superiority to the Roth-Ruckenstein (RR) algorithm, especially in the scenarios that the decoder is required to output a codeword and the re-encoding transform (ReT) technique is employed.