Low-Complexity Algebraic Soft Decoding of Hermitian Codes With Re-Encoding Transform
Authors:
- 27 March 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (6) , 3771-3783
Abstract
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 zero $z$ -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.Keywords
Funding Information
- National Natural Science Foundation of China (62471503)
- Natural Science Foundation of Guangdong Province (2024A1515010213)
This publication has 32 references indexed in Scilit:
- List decoding of Hermitian codes using Gröbner basesJournal of Symbolic Computation, 2009
- Algebraic Function Fields and Codes2009
- List decoding of Reed–Solomon codes from a Gröbner basis perspectiveJournal of Symbolic Computation, 2008
- On lattice reduction for polynomial matricesJournal of Symbolic Computation, 2003
- Efficient root-finding algorithm with application to list decoding of algebraic-geometric codesIEEE Transactions on Information Theory, 2001
- Efficient decoding of Reed-Solomon codes beyond half the minimum distanceIEEE Transactions on Information Theory, 2000
- Improved decoding of Reed-Solomon and algebraic-geometry codesIEEE Transactions on Information Theory, 1999
- Algebraic-geometry codesIEEE Transactions on Information Theory, 1998
- Fast decoding of algebraic-geometric codes up to the designed minimum distanceIEEE Transactions on Information Theory, 1995
- An efficient maximum-likelihood-decoding algorithm for linear block codes with algebraic decoderIEEE Transactions on Information Theory, 1994