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

Loidreau, Pierre1
1 Laboratoire de mathématiques appliquées, ENSTA, 32, bd Victor, 75015 Paris, France
Comptes Rendus. Mathématique, Tome 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
Loidreau, Pierre 1

1 Laboratoire de mathématiques appliquées, ENSTA, 32, bd Victor, 75015 Paris, France 
@article{CRMATH_2004__339_10_745_0,
     author = {Loidreau, Pierre},
     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},
     url = {http://www.numdam.org/articles/10.1016/j.crma.2004.10.004/}
}
TY  - JOUR
AU  - Loidreau, Pierre
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
UR  - http://www.numdam.org/articles/10.1016/j.crma.2004.10.004/
DO  - 10.1016/j.crma.2004.10.004
LA  - fr
ID  - CRMATH_2004__339_10_745_0
ER  - 
%0 Journal Article
%A Loidreau, Pierre
%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
%U http://www.numdam.org/articles/10.1016/j.crma.2004.10.004/
%R 10.1016/j.crma.2004.10.004
%G fr
%F CRMATH_2004__339_10_745_0
Loidreau, Pierre. Sur la reconstruction des polynômes linéaires : un nouvel algorithme de décodage des codes de Gabidulin. Comptes Rendus. Mathématique, Tome 339 (2004) no. 10, pp. 745-750. doi : 10.1016/j.crma.2004.10.004. http://www.numdam.org/articles/10.1016/j.crma.2004.10.004/

[1] Berlekamp, E.R. 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] Gabidulin, E.M. Theory of codes with maximal rank distance, Probl. Inf. Transm., Volume 21 (1985), pp. 1-12

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

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

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

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

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

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

[10] Sudan, M. 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 :