1999 | OriginalPaper | Buchkapitel
Discrete Fourier Transform and Gröbner Bases
verfasst von : A. Poli, M. C. Gennero, D. Xin
Erschienen in: Applied Algebra, Algebraic Algorithms and Error-Correcting Codes
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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).