On the decoding of binary cyclic codes with the Newton's identities

Abstract : We revisit in this paper the concept of decoding binary cyclic codes with Gröbner bases. These ideas were first introduced by Cooper, then Chen, Reed, Helleseth and Truong, and eventually by Orsini and Sala. We discuss here another way of putting the decoding problem into equations: the Newton's identities. Although these identities have been extensively used for decoding, the work was done manually, to provide formulas for the coefficients of the locator polynomial. This was achieved by Reed, Chen, Truong and others in a long series of papers, for decoding quadratic residue codes, on a case-by-case basis. It is tempting to automate these computations, using elimination theory and Gröbner bases. Thus, we study in this paper the properties of the system defined by the Newton's identities, for decoding binary cyclic codes. This is done in two steps, first we prove some facts about the variety associated to this system, then we prove that the ideal itself contains relevant equations for decoding, which lead to formulas. Then we consider the so-called online Gröbner bases decoding, where the work of computing a Gröbner basis is done for each received word. It is much more efficient for practical purposes than preprocessing and substituting into the formulas. Finally, we conclude with some computational results, for codes of interesting length (about one hundred).
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2009, Gröbner Bases in Cryptography, Coding Theory, and Algebraic Combinatorics, 44 (12), pp.1608-1625. 〈http://www.sciencedirect.com/science/article/B6WM7-4V2NKC8-1/2/7fbca42d51ecd00f706121b11a52a44b〉. 〈10.1016/j.jsc.2008.02.006〉
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00509219
Contributeur : Daniel Augot <>
Soumis le : mardi 10 août 2010 - 18:27:09
Dernière modification le : mercredi 18 avril 2018 - 11:07:06
Document(s) archivé(s) le : vendredi 12 novembre 2010 - 11:46:08

Fichiers

gbdecode-revised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Daniel Augot, Magali Bardet, Jean-Charles Faugère. On the decoding of binary cyclic codes with the Newton's identities. Journal of Symbolic Computation, Elsevier, 2009, Gröbner Bases in Cryptography, Coding Theory, and Algebraic Combinatorics, 44 (12), pp.1608-1625. 〈http://www.sciencedirect.com/science/article/B6WM7-4V2NKC8-1/2/7fbca42d51ecd00f706121b11a52a44b〉. 〈10.1016/j.jsc.2008.02.006〉. 〈inria-00509219〉

Partager

Métriques

Consultations de la notice

712

Téléchargements de fichiers

335