Sur la reconstruction des polynômes linéaires : un nouvel algorithme de décodage des codes de Gabidulin

Pierre Loidreau

doi:10.1016/j.crma.2004.10.004

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 Loidreau ¹

¹ 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.

Résumé
Abstract

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 : 2004-08-25
Accepté le : 2004-10-05
Publié le : 2004-11-02

DOI : 10.1016/j.crma.2004.10.004

Affiliations des auteurs :

Pierre Loidreau ¹

¹ 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/

Bibliographie
Cité par

[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