Decoding Reed-Solomon codes by solving a bilinear system with a Gröbner basis approach - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Decoding Reed-Solomon codes by solving a bilinear system with a Gröbner basis approach

Résumé

Decoding a Reed-Solomon code can be modeled by a bilinear system which can be solved by Gröbner basis techniques. We will show that in this particular case, these techniques are much more efficient than for generic bilinear systems with the same number of unknowns and equations (where these techniques have exponential complexity). Here we show that they are able to solve the problem in polynomial time up to the Sudan radius. Moreover, beyond this radius these techniques recover automatically polynomial identities that are at the heart of improvements of the power decoding approach for reaching the Johnson decoding radius. They also allow to derive new polynomial identities that can be used to derive new algebraic decoding algorithms for Reed-Solomon codes. We provide numerical evidence that this sometimes allows to correct efficiently slightly more errors than the Johnson radius.
Fichier principal
Vignette du fichier
articleISIT.pdf (300.13 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03533311 , version 1 (18-01-2022)

Identifiants

Citer

Magali Bardet, Rocco Mora, Jean-Pierre Tillich. Decoding Reed-Solomon codes by solving a bilinear system with a Gröbner basis approach. ISIT 2021 - IEEE International Symposium on Information Theory, Jul 2021, Melbourne, Australia. pp.872-877, ⟨10.1109/ISIT45174.2021.9517838⟩. ⟨hal-03533311⟩
40 Consultations
81 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More