Pade approximants and key lattices for decoding alternant codes

Abstract

In this paper we present two methods for algebraic decoding of alternant codes. The paper recalls fundamental facts of these codes and the concept of key equation introduced by Berlekamp on which decoding is based. The first method is based on Pade approximants. The second method consist of translating the key equation into a lattice over the ring of polynomials, called key lattice which depends on the syndrome, and then seek a shortest vector in this key lattice, with degrees constraints. The key lattice approach, following the fruitfull formulation of H. W. Lenstra, is based on a result of Grigor'ev showing that computing a minimal vector in the mentioned lattice is polynomial. The computational complexity of the proposed methods are given in terms of the error-correction capability of the codes and results in tractable polynomial time algorithms. A fast parallel version of the key lattice method is deduced.