Guruswami-Sudan Decoding of Elliptic Codes Through Module Basis Reduction

This paper proposes the Guruswami-Sudan (GS) list decoding algorithm for one-point elliptic codes, in which the interpolation is realized by the module basis reduction (BR). Elliptic codes are a kind of algebraic-geometric (AG) codes with a genus of one. Over the same finite field, they have a greater codeword length than Reed-Solomon (RS) codes, capable of correcting more errors. The GS decoding consists of interpolation and root-finding, while the former that determines the interpolation polynomial $\mathcal {Q}(\text {x}, \text {y}, \text {z})$ dominates the decoding complexity. By defining the Lagrange interpolation function over an elliptic function field, a basis of the interpolation module can be constructed. The desired Grobner basis that contains $\mathcal {Q}(\text {x}, \text {y}, \text {z})$ can be determined by reducing the constructed basis. This is namely the BR interpolation and it requires less finite field arithmetic operations than the conventional Kotter’s interpolation, facilitating the GS decoding. Re-encoding transform (ReT) is further introduced to facilitate the BR interpolation. This work also shows that both the BR interpolation and its ReT variant will have a lower complexity as the code rate ${k}/{n}$ increases, where n and ${k}$ are the length and dimension of the code, respectively. Our numerical results demonstrate the complexity advantage of the BR interpolation over Kotter’s interpolation, and the performance advantage of elliptic codes over RS codes.