On formulas for decoding binary cyclic codes

Abstract : We adress the problem of the algebraic decoding of any cyclic code up to the true minimum distance. For this, we use the classical formulation of the problem, which is to find the error locator polynomial in terms of the syndroms of the received word. This is usually done with the Berlekamp-Massey algorithm in the case of BCH codes and related codes, but for the general case, there is no generic algorithm to decode cyclic codes. Even in the case of the quadratic residue codes, which are good codes with a very strong algebraic structure, there is no available general decoding algorithm. For this particular case of quadratic residue codes, several authors have worked out, by hand, formulas for the coefficients of the locator polynomial in terms of the syndroms, using the Newton identities. This work has to be done for each particular quadratic residue code, and is more and more difficult as the length is growing. Furthermore, it is error-prone. We propose to automate these computations, using elimination theory and Grbner bases. We prove that, by computing appropriate Grbner bases, one automatically recovers formulas for the coefficients of the locator polynomial, in terms of the syndroms.
Type de document :
Communication dans un congrès
IEEE International Symposium on Information Theory, 2007 (ISIT 2007), Jun 2007, Nice, France. IEEE, pp.2646-2650, 2007, 〈10.1109/ISIT.2007.4557618〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00123312
Contributeur : Daniel Augot <>
Soumis le : mardi 9 janvier 2007 - 12:39:35
Dernière modification le : mardi 5 juin 2018 - 10:14:24
Document(s) archivé(s) le : mercredi 7 avril 2010 - 01:56:03

Fichiers

decode_cyclique.arxiv.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Daniel Augot, Magali Bardet, Jean-Charles Faugère. On formulas for decoding binary cyclic codes. IEEE International Symposium on Information Theory, 2007 (ISIT 2007), Jun 2007, Nice, France. IEEE, pp.2646-2650, 2007, 〈10.1109/ISIT.2007.4557618〉. 〈inria-00123312〉

Partager

Métriques

Consultations de la notice

261

Téléchargements de fichiers

174