Discrete Fourier Transform and Gröbner Bases

Using multivariate polynomials, Gröbner bases have a great theoretical interest in decoding cyclic codes beyond their BCH capability [1],[2], but unfortunately have a high complexity [7]. From engineers point of view, the complexity comes in particular from the number of needed indeterminates, from the maximal number of needed polynomials during Buchberger’s algorithm (this number is unknown), and from the maximal number of attempts before recovering the error polynomial e(X). In this paper we propose a new algorithm, using Gröbner bases and Discrete Fourier Transform. In most of the cases this algorithm needs fewer indeterminates than Chen et al. algorithm [1], and at most as many as for XP algorithm [9] (sometimes less). In some cases the maximal number of needed polynomials for calculations is reduced to 1. Finally, it is shown that only one attempt is needed for recovering e(X).

Authors and Affiliations

1. AAECC/IRIT, University Paul Sabatier, 31062, Toulouse cedex 4, France

   A. Poli & M. C. Gennero

2. Department of Computer Sciences, Fudan University, Shanghai, China

   D. Xin

Editors and Affiliations

1. Department of Electrical Engineering, University of Hawaii, 2540 Dole St., # 483, Honolulu, HI, 96822, USA

   Marc Fossorier  & Shu Lin  & 

2. Institute of Industrial Science, University of Tokyo, 7-22-1, Roppongi, Minato-ku, Tokyo, 106, Japan

   Hideki Imai

3. AAECC/IRIT, Université Paul Sabatier, 118, Route de Narbonne, F31067, Toulouse, Cedex, France

   Alain Poli

Reprints and permissions

© 1999 Springer-Verlag Berlin Heidelberg

Policies and ethics