Abstract
This paper introduces a novel list decoding algorithm for 2-interleaved binary alternant codes, a class that includes widely used codes such as BCH and Goppa. By combining trivariate polynomial interpolation with subfield-specific multiplicity assignments, the authors demonstrate a decoding radius that can exceed the theoretical binary Johnson radius with high probability. The algorithm leverages the joint structure of interleaved codewords and the specific properties of binary subfields to improve error correction performance beyond traditional limits.
Introduction
In error correction, unique decoding is limited to correcting errors up to half the minimum distance of the code. List decoding offers a more powerful alternative by returning a list of all possible codewords within a larger radius, thereby increasing the likelihood of message recovery in high-noise environments. While list decoding for Reed-Solomon codes is well-established, applying these techniques to binary alternant codes—critical for applications like post-quantum cryptography—presents significant challenges. This work addresses these challenges by employing "interleaving," where multiple codewords share the same error locations, to push the decoding radius past the traditional Johnson radius.
Methods
The proposed decoding algorithm integrates three key concepts:
- Interleaving: Two codewords are treated as a single matrix where errors occur column-wise. This provides the decoder with more structural information to identify error locations.
- Trivariate Interpolation: Following the Parvaresh-Vardy approach, the algorithm finds a polynomial $G(X, Y, Z)$ that passes through points related to the received data. Using three variables instead of the usual two allows for a larger decoding radius.
- Subfield Multiplicities: Since the codes are binary but interpolation happens in an extension field, the authors use a technique from the Koetter-Vardy algorithm. They assign specific weights (multiplicities) to points based on their consistency with the binary subfield, treating the subfield constraint as "soft information" to guide the decoder.
The recovery process involves computing resultants of the interpolation polynomials to extract the original message polynomials $f(X)$ and $g(X)$.
Key Results
The algorithm was evaluated using synthetic simulations of 2-interleaved binary alternant codes with length $n=32$ and minimum distance $d=13$.
As illustrated in Figure 1, the proposed algorithm's upper bound on the decoding radius is strictly higher than that of the Guruswami-Sudan, Koetter-Vardy, and standard Parvaresh algorithms for the chosen parameters. In simulations, the algorithm successfully decoded up to $t=10$ errors, whereas the standard binary Johnson radius for these parameters is approximately $7.5$.
The success of the algorithm is probabilistic. Figure 2 shows how the choice of multiplicities $(m_1, m_2)$ affects the success rate. With optimal parameters, the failure probability becomes negligible. Furthermore, the authors prove that the list size remains polynomial relative to the code parameters, ensuring computational feasibility despite the increased complexity of trivariate interpolation.
Conclusion
This work demonstrates that leveraging subfield properties and interleaving can significantly enhance the list decoding capabilities for binary alternant codes. While the interpolation step is computationally intensive ($O(n^2 m_1^8)$) and the success is probabilistic, the ability to exceed the Johnson bound represents a significant advancement. Future research may explore more efficient interpolation architectures and the extension of this framework to $L$-interleaved codes for even greater decoding radii.
Summary updated