Comptes Rendus
no. 10
Informatique théorique
Sur la reconstruction des polynômes linéaires : un nouvel algorithme de décodage des codes de Gabidulin

Présenté par : Yves Meyer

Pierre Loidreau1
1 Laboratoire de mathématiques appliquées, ENSTA, 32, bd Victor, 75015 Paris, France
Comptes Rendus. Mathématique, Volume 339 (2004) no. 10, pp. 745-750.

Nous présentons un problème de reconstruction de polynômes linéaires ainsi qu'un algorithme en temps polynomial de résolution de ce problème dans un cas simple. Nous en déduisons un algorithme alternatif performant de décodage des codes de Gabidulin introduits en 1985.

We describe a reconstruction problem for linearized polynomials. We equally describe a polynomial-time algorithm enabling to solve this problem in a simple case. From this algorithm we deduce an alternative efficient decoding algorithm for Gabidulin codes introduced in 1985.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2004.10.004
Pierre Loidreau 1

1 Laboratoire de mathématiques appliquées, ENSTA, 32, bd Victor, 75015 Paris, France 
@article{CRMATH_2004__339_10_745_0,
     author = {Pierre Loidreau},
     title = {Sur la reconstruction des polyn\^omes lin\'eaires : un nouvel algorithme de d\'ecodage des codes de {Gabidulin}},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {745--750},
     publisher = {Elsevier},
     volume = {339},
     number = {10},
     year = {2004},
     doi = {10.1016/j.crma.2004.10.004},
     language = {fr},
}
TY  - JOUR
AU  - Pierre Loidreau
TI  - Sur la reconstruction des polynômes linéaires : un nouvel algorithme de décodage des codes de Gabidulin
JO  - Comptes Rendus. Mathématique
PY  - 2004
SP  - 745
EP  - 750
VL  - 339
IS  - 10
PB  - Elsevier
DO  - 10.1016/j.crma.2004.10.004
LA  - fr
ID  - CRMATH_2004__339_10_745_0
ER  - 
%0 Journal Article
%A Pierre Loidreau
%T Sur la reconstruction des polynômes linéaires : un nouvel algorithme de décodage des codes de Gabidulin
%J Comptes Rendus. Mathématique
%D 2004
%P 745-750
%V 339
%N 10
%I Elsevier
%R 10.1016/j.crma.2004.10.004
%G fr
%F CRMATH_2004__339_10_745_0
Pierre Loidreau. Sur la reconstruction des polynômes linéaires : un nouvel algorithme de décodage des codes de Gabidulin. Comptes Rendus. Mathématique, Volume 339 (2004) no. 10, pp. 745-750. doi : 10.1016/j.crma.2004.10.004. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2004.10.004/

[1] E.R. Berlekamp Algebraic Coding Theory, Aegean Press Park, 1984

[2] E.R. Berlekamp, L. Welch, Error Correction of Algebraic Block Codes, US Patent, Number 4, 633, 470, 1986

[3] E.M. Gabidulin Theory of codes with maximal rank distance, Probl. Inf. Transm., Volume 21 (1985), pp. 1-12

[4] E.M. Gabidulin A fast matrix decoding algorithm for rank-error correcting codes (G. Cohen; S. Litsyn; A. Lobstein; G. Zémor, eds.), Algebraic Coding, Lecture Notes in Comput. Sci., Springer-Verlag, 1991, pp. 126-133

[5] E.M. Gabidulin; A.V. Paramonov; O.V. Tretjakov Ideals over a non-commutative ring and their application in cryptology, Lecture Notes in Comput. Sci., vol. 573, 1991, pp. 482-489

[6] O. Öre On a special class of polynomials, Trans. Amer. Math. Soc., Volume 35 (1933), pp. 559-584

[7] O. Öre Contribution to the theory of finite fields, Trans. Amer. Math. Soc., Volume 36 (1934), pp. 243-274

[8] A.V. Ourivski; E.M. Gabidulin; B. Honary; B. Ammar Reducible rank codes and their applications to cryptography, IEEE Trans. Inform. Theory, Volume 49 (2003) no. 12, pp. 3289-3293

[9] R.M. Roth Maximum-Rank array codes and their application to crisscross error correction, IEEE Trans. Inform. Theory, Volume 37 (1991) no. 2, pp. 328-336

[10] M. Sudan Decoding Reed–Solomon codes beyond the error-correction diameter, Proceedings of the 35th Annual Allerton Conference on Communication, Control and Computing, 29 septembre – 1er octobre, 1997, pp. 215-224

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Comments on the origin of the genetic code: a 27-codon hypothetical precursor of an intricate 64-codon intermediate shaped the modern code

Jean Weissenbach

C. R. Biol (2020)

On the origin of the genetic code: a 27-codon hypothetical precursor of an intricate 64-codon intermediate shaped the modern code

Bernard Dujon

C. R. Biol (2020)