Algebraic Soft Decoding of Elliptic Codes

This paper proposes algebraic soft decoding (ASD) for one-point elliptic codes, where the interpolation is realized through the perspective of obtaining a Grobner basis. The desired interpolation polynomial Q(x, y, z) is the minimum candidate in the basis. This work shows how to obtain such a Grobner basis. Based on an interpolation multiplicity matrix M, an interpolation ideal I-M can be defined. With a predefined decoding output list size (OLS) l (l >= deg(z) Q), an equivalent interpolation module I-M,I-l can be led to. By further defining the Lagrange interpolation functions, a basis of the interpolation module can be constructed. The desired Grobner basis can be obtained by reducing this module basis. Finally, the decoding complexity is also analyzed.