Low-Complexity Chase Decoding of Hermitian Codes With Improved Interpolation and Root-Finding

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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\eta $ </tex-math></inline-formula> unreliable received symbols, <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2^{\eta }$ </tex-math></inline-formula> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$2^{\eta }$ </tex-math></inline-formula> 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.