Brevet FR3061393A1 — publié le 20180629

PROCEDES DE CODAGE ET DE DECODAGE DE PAQUETS DE DONNEES DANS UN CORPS DE GALOIS La présente invention concerne les systèmes de communication ou d'enregistrement de données dans lesquels, afin d'améliorer la fidélité de la transmission ou du stockage, on soumet les données à un codage de canal. L'invention concerne plus particulièrement la transmission de paquets de données sur un canal affecté par des pertes de paquets. Sur un tel canal, certains paquets sont reçus parfaitement (grâce à une modulation et un codage convenablement définis au niveau de la couche physique) ; en revanche, d'autres paquets ne sont pas reçus, soit parce que ces paquets sont supprimés en raison d'une congestion dans un routeur, soit parce qu'ils sont reçus dans de mauvaises conditions (bruit, interférences) et ne peuvent être décodés correctement. Un tel canal de transmission est appelé « canal à effacements », et les paquets perdus sont dits « effacés ». Les systèmes de transmission de paquets sur des canaux provoquant des effacements comprennent par exemple : - le stockage de masse, ainsi que le stockage distribué, systèmes dans lesquels les pertes de données sont dues à des pannes de disques durs ou de serveurs ; - la diffusion en broadcast ou en multicast eMBMS (evolved Multimedia 20 Broadcast Multicast Services) en LIE (Long Term Evolution), pour la transmission de fichiers ou de programmes audiovisuels en continu (streaming); et - la transmission en temps réel de la Voix ou de la Vidéo sur des canaux à pertes, tels que VoLTE (Voice over LIE) ou WebRTC (Web Real-Time 25 Communication). On rappelle que le codage de canal consiste, quand on forme des mots de code envoyés à un récepteur ou enregistrés sur un support de données, à introduire une certaine redondance dans les données. Au niveau du récepteur, le procédé de décodage associé exploite alors judicieusement cette redondance 30 pour détecter d'éventuelles erreurs de transmission et si possible les corriger ; cette approche s'applique aussi bien au recouvrement de données individuelles qu'au recouvrement de paquets effacés. 3061393 2 Plus précisément, on transmet, au moyen de chaque mot de code, des informations initialement contenues dans un nombre prédéterminé k de symboles prélevés dans un alphabet de taille finie q ; on calcule à partir de ces k symboles d'information un nombre n>k de symboles appartenant à cet 5 alphabet, qui constituent les composantes d'un mot de code. L'ensemble des mots de code obtenus quand chaque symbole d'information prend une valeur quelconque dans l'alphabet, constitue une sorte de dictionnaire appelé « code » de « dimension » k et de « longueur » n. On appelle distance minimale d d'un code la plus petite distance de 10 Hamming entre deux mots différents de ce code, la distance de Hamming étant, par définition, le nombre d'emplacements où deux mots de même longueur possèdent un symbole différent. La distance minimale d, ainsi que le « rendement » R = k ln, sont des paramètres importants du code ; en particulier, un code de distance minimale d permet de corriger (d-1) 15 effacements en utilisant un décodage optimal. Certains codes, appelés codes linéaires, sont tels que toute combinaison linéaire de mots de code (avec les coefficients pris dans l'alphabet) est encore un mot de code. Ces codes peuvent, de façon commode, être associés à une matrice H de dimension (n - k )x n, dite matrice de parité : un mot X = (xi,--- , ) de longueur n donné est un mot de code si, et seulement si, il vérifie la relation : H - XT = 0 (où l'exposant T indique la transposition). Lorsque la taille q de l'alphabet est une puissance d'un nombre premier, on peut donner à cet alphabet une structure de corps, appelé corps de Galois et noté GF (q) , dont les éléments non-nuls peuvent être commodément identifiés comme étant chacun égal à a.1-1 pour une valeur correspondante de j, où j = 1,...,q -1 , et où a est une racine ( q -1)ème primitive de l'unité dans GF (q) . Lorsque, en particulier, q =2-, où m > 1, le corps de Galois est également appelé « corps d'extension binaire ». Actuellement, les systèmes de transmission de paquets sur des canaux provoquant des effacements mettent souvent en oeuvre des procédés de codage/décodage opérant au niveau des paquets de données, notamment 3061393 3 lorsque les contraintes de délais interdisent la retransmission des paquets perdus : dans ces systèmes, un émetteur envoie à un récepteur, d'une part, un ensemble de paquets de données originaux, et d'autre part un ensemble de paquets de redondance qui seront utilisés pour récupérer les paquets perdus. 5 Ces paquets supplémentaires sont appelés « paquets de réparation » ; leur nombre est tel que le récepteur pourra récupérer les paquets utiles avec une haute probabilité. Il est en effet plus efficace de coder/décoder au niveau de paquets de données qu'au niveau de données individuelles, et ce, pour les raisons 10 suivantes. Considérons, comme illustré sur la figure 1, un ensemble de paquets de données ayant la même longueur et contenant chacun L symboles appartenant à GF (2-) (chaque symbole est donc composé de m bits). En supposant que l'on utilise un code linéaire, le codage est effectué sur 15 n paquets {11, 132, - - - , Pn} (incluant les paquets de données originaux et les paquets de réparation), de manière à ce que chaque colonne de symboles constitue un mot d'un code linéaire C(n,k) de longueur n et de dimension k. L'on a ainsi L mots de code à coder ou à décoder pour chaque ensemble de n paquets. Un codage/décodage au niveau des paquets permet d'exécuter 20 une seule opération (portant sur les n paquets) au lieu de L opérations (les symboles formant ces paquets), ce qui est une grande réduction de la complexité, particulièrement pour le décodage. En particulier, la récupération de paquets perdus dans un canal à effacements consiste à résoudre un ensemble d'équations de parité faisant 25 intervenir des paquets, ce qui peut être réalisé au moins de deux façons : - une approche optimale, appelée méthode de « maximum de vraisemblance », consistant à résoudre un système linéaire ; et - une approche moins performante, mais moins complexe, appelée méthode BP (initiales des mots anglais « Belief Propagation » signifiant 30 « Propagation de Croyance »), consistant en une solution itérative, ligne par ligne, du système linéaire ; cette méthode exige d'avoir, à chaque itération, au 3061393 4 moins une équation de parité faisant intervenir un seul paquet perdu, sinon le décodage échoue. On connaît divers codes adaptés aux canaux à effacements. Ces codes sont efficaces, à condition de travailler sur une longue séquence de paquets 5 (quelques milliers au moins). En particulier, certains de ces codes, tels que les codes « RaptorQ » définis dans le document RFC 6330 de l'IETF (Internet Engineering Task Force), opèrent dans des corps d'extension binaires GF(2m). En effet, de tels codes (où, rappelons-le, m > 1) sont plus avantageux que les codes binaires ( m =1) 10 sur le plan du rendement R=kIn et de la distance minimale relative 8 = d I n. L'arithmétique de ces corps d'extension met en oeuvre l'addition bit à bit, et la multiplication d'éléments dans GF(2m). L'addition bit à bit est simple à mettre en oeuvre, mais la multiplication repose classiquement sur un mécanisme logiciel de consultation de table de multiplication, mécanisme typiquement complexe et lent. 15 Par ailleurs, de simples considérations d'algèbre linéaire permettent de montrer que la résolution d'un système d'équations de parité dans GF(2m) faisant intervenir des paquets de données peut être ramenée à des additions de paquets, et à des multiplications d'un paquet par un même élément de GF(2m) , c'est-à-dire des combinaisons linéaires de paquets avec des coefficients pris 20 dans GF(2m). On remarque aussi que c'est l'opération élémentaire mise en oeuvre dans le codage de réseau linéaire, mentionné brièvement ci-dessus. Or, lorsqu'il faut multiplier tous les éléments d'un vecteur donné X = (xi,- - - , ) composé d'éléments de GF(2m) par un même élément a de GF (2') , on ne peut pas consulter ladite table de multiplication de façon 25 vectorielle ; autrement dit, il faut consulter la table pour chaque élément xt du vecteur, ce qui est d'autant plus lent que le vecteur est plus long. La présente invention concerne donc, selon un premier aspect, un procédé de codage de paquets de données, comprenant les étapes suivantes : - réception de paquets de données utiles, chaque paquet de données 30 utiles contenant symboles constitués chacun d'une suite de m > 1 bits, et 3061393 5 - codage desdits paquets de données utiles de manière à obtenir n>k paquets codés contenant chacun L symboles constitués d'une suite de m bits, ledit codage étant réalisé au moyen d'un code linéaire C(n,k) de longueur n et de dimension k opérant sur le corps d'extension binaire GF (2') défini au 5 moyen d'un polynôme primitif choisi. Ledit procédé de codage est remarquable en ce que ladite étape de codage des paquets de données utiles comprend au moins une sous-étape de multiplication Q= a - P de tous les symboles d'un paquet de données P=(xi,---,xL) dans lequel xi , pour j = -.,L, est un symbole composé d'une suite de m bits , 10 où i =0,- - -,m-1, par un même nombre a appartenant à GF (2m), et en ce que ladite multiplication est effectuée de la manière suivante : a) on remplit une matrice binaire X de dimension m x L en plaçant les bits x composant chaque symbole xj le long de la j -ième colonne de ladite matrice X; 15 b) on calcule une matrice binaire Y, de dimension m x L, définie par le produit matriciel Y = M(a)xX, où M(a) est la matrice binaire de dimensions m x m dont les colonnes respectives contiennent les coordonnées binaires des éléments respectifs 20 {a, aa, - --, an"a} ; et c) on obtient le paquet de données Q =(yi,---,y), dans lequel chaque symbole y1, pour j=1,2,---,L, est composé des m bits yij , où i=0,---,m-1, situés sur la j -ième colonne de ladite matrice Y. Grâce à ces dispositions, on peut remplacer le mécanisme classique de 25 consultation de table de multiplication par un ensemble d'opérations binaires effectuées de manière vectorielle au niveau des paquets. La présente invention est donc particulièrement avantageuse car, si elle permet une mise en oeuvre logicielle du codage ou du décodage comme les techniques de l'état de l'art, elle permet d'utiliser efficacement un circuit électronique en même temps, ou 30 complètement à la place, de moyens logiciels. 3061393 6 Selon des caractéristiques particulières, lesdites matrices M(a), pour a= a1 et i=1,2,.-.,m-1, sont extraites d'une matrice de référence T de dimension m x (2m + m 2). Grâce à ces dispositions, on peut aisément obtenir les matrices M(a) 5 sans aucun calcul, par simple lecture dans une unique matrice T construite et stockée préalablement à la mise en oeuvre dudit procédé de codage. Corrélativement, l'invention concerne un procédé de décodage de paquets de données, comprenant les étapes suivantes : - réception de n > 1 paquets de données codés, chaque paquet de 10 données codé contenant 1 symboles constitués d'une suite de m >1 bits, lesdits paquets de données ayant été codés au moyen d'un code linéaire C(n,k) de longueur n et de dimension k, où 1 k 1 bits, et - coder lesdits paquets de données utiles de manière à obtenir n>k paquets codés contenant chacun L symboles constitués d'une suite de m bits, ledit codage étant réalisé au moyen d'un code linéaire C(n,k) de longueur n et de dimension k opérant sur le corps d'extension binaire GF (2' ) défini au 25 moyen d'un polynôme primitif choisi. Ledit dispositif de codage est remarquable en ce qu'il comprend en outre, dans le but d'effectuer une multiplication Q=a-P, requise pour le codage des paquets de données utiles, de tous les symboles d'un paquet de données P dans lequel xi, pour j= 1, - - .,L, est un symbole composé d'une suite de m bits 3061393 8 où i =0,- - .,m-1, par un même nombre a appartenant à GF (2m), des moyens pour : - remplir une matrice binaire X de dimension m x L en plaçant les bits composant chaque symbole xj le long de la j -ième colonne de ladite matrice 5 X; - calculer une matrice binaire Y, de dimension m x L, définie par le produit matriciel Y = M(a)xX, où M(a) est la matrice binaire de dimensions m x m dont les colonnes 10 respectives contiennent les coordonnées binaires des éléments respectifs {a, aa, - --, am la} ; et - obtenir le paquet de données Q=(yi,---,yL), dans lequel chaque symbole y1, pour j=1,2,...,L, est composé des m bits yu , où i =0,- - .,m-1, situés sur la j -ième colonne de ladite matrice Y. 15 Selon des caractéristiques particulières, ledit dispositif de codage comprend en outre des moyens pour extraire lesdites matrices M(a), pour a =a' et i =1,2,- - .,m-1, d'une matrice de référence T de dimension mx (2m +m-2). L'invention concerne aussi, deuxièmement, un dispositif de décodage de 20 paquets de données, comprenant des moyens pour : - recevoir n> 1 paquets de données codés, chaque paquet de données codé contenant L symboles constitués d'une suite de m >1 bits, lesdits paquets de données ayant été codés au moyen d'un code linéaire C(n,k) de longueur n et de dimension k, où 1 k 1. On entend par là qu'a tout symbole donné composé de m bits x, où i =0,- - -,m-1, on associe l'élément de GF (2') , noté x , dont les coordonnées binaires sur une base 5 canonique {1, a, a', --- , am-1} choisie sont précisément lesdits bits xo ; autrement dit : m-1 - =IXiia , i=0 où a est une racine d'un polynôme primitif prédéterminé. On va expliquer à présent comment on peut effectuer la multiplication 10 dans GF(2m) uniquement au moyen d'additions binaires (on rappelle que l'addition binaire est également appelée « OU exclusif », et notée « XOR »). Prenons un exemple dans le corps GF(24) construit à partir du polynôme primitif p(X) = X4 + X +1, où a vérifie l'équation : a4 = 1 + a. Le résultat de la multiplication de l'élément x = xo + a + x2 a2 + x3a3, de 15 coordonnées binaires .)C, E 10,11, par l'élément a = ao + a + a2 a2 +a3a3, de coordonnées binaires a, E 10,11, est l'élément y = yo + y1 a + y2 a2 + y3a3 dont les coordonnées binaires y, E 10,11 sont obtenues comme suit : y= ax= xoa + (a a) + x2(a2 a) + x3(a3 a) Yo - - xo 0 Y1 = a a a a 2a a3a x = M (a) x Xi Y2 x2 X2 _Y3_ X _ 3_ _X3_ par définition de la matrice M(a), dont les colonnes successives sont 20 constituées par les coordonnées binaires des éléments a, a a, a2 a et a' a de GF(24) successivement. Pour calculer ces colonnes, on notera, par exemple, que 3061393 14 a a = ao a + a, a2 ± a2 a3 ± a3a4 = ao a + a, a2 ± a2 a3 ± a3 + a) = a3 + (a3 + ao)a + a, a2 ± a2 a3 On procède de la même façon pour a2a et a'a . Le résultat final est : Yo ao a3 a2 al X0 .Y1 al a3 + a0 a3 + a2 a2 +al X1 Y2 a2 a1 a3 +a0 a3 +a2 X2 323 a3 a2 a1 a3 +a0 X3 Dans le cas général d'un corps GF(2m) pour m quelconque, on calcule : 5 Y =M(a)xX , (1) où : - X est le vecteur colonne contenant les m coordonnées binaires X, E 10,11 de x, - Y est le vecteur colonne contenant les m coordonnées binaires 10 y, E 10,11 de y, et - la matrice M(a) , Où a E GF (2m), est la matrice binaire m x m dont les colonnes contiennent les coordonnées binaires des éléments {a, a a, - - am-la } de GF(2m), soit M (a) = a aa --- am 1 a 15 On dira que la matrice M(a) est « l'équivalent binaire » de l'élément a pour la multiplication dans GF(2m) . Comme tous les éléments non-nuls de GF(2m) peuvent être écrits sous la forme a = ak pour un certain entier 0 k 2m -2, on peut se contenter de considérer les matrices 20 M (ce k ) k+m-1 associées aux puissances consécutives de a. 3061393 15 On notera que toutes ces matrices peuvent être obtenues en consultant une « grande » matrice binaire T= 1 a a2 ak+m-1 --- an-11 a--- am-2 , n = 2m - 1 de dimension mx (2m +m-2), construite préalablement, dont les colonnes 5 contiennent les coordonnées de ak pour k > o. Dans cette matrice T, que l'on appellera « matrice de référence », les (m -1) dernières colonnes sont une simple copie des (m-1) premières colonnes. M(ak ) est alors la sous-matrice obtenue en extrayant les colonnes n° (k +1) à (k+m) de la matrice de référence T, ce que l'on notera ainsi : 10 M (ak ) = T(:, k +1: k + m) , pour k = 0,1,- - -,2m - 2. Par définition, le produit de deux éléments a = ak et b=al est égal à a(k ou (k +1) = (k +1) mod (2m -1), de sorte que la matrice associée au produit ak xal est M(a(k+/)), que l'on peut lire directement dans la matrice de référence T ; on peut ainsi obtenir très simplement le produit des matrices 15 M(ak ) et M(ai) par : M(ak x m (al ) m(a(k+1) De la même manière, la matrice associée à l'inverse d'un élément a = ak est [m(ak)Tl = m(an-k) , puisque M (ak ) x m(an-k ) m(a) m(a0), qui est la matrice identité. 20 Si l'on prend le même exemple sur GF(24) (construit à partir du polynôme primitif p(X)=1+ X + X4), la matrice de référence T est donnée par : 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 0 0 0 T= 3061393 16 , de sorte que, par exemple : 1 M(a10) = 1 1 1 0 0 1 1 1 1 1 1 1 1 0 1 1 M (a14 ) 1 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 M (a4 ) 1 0 0 1 1 1 0 0 0 1 1 1_ 0 0 1 On vérifie facilement, par exemple, que le produit des matrices binaires m(a4) x m(aio, ) est bien égal à M(a14) comme prévu. 5 En poursuivant le même exemple, on trouve : 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 = m(i), M(a5) = 0 0 1 1 , et M (a5 ) x M (ail)) = 1 0 1 0 1 1 0 1 0 1 1 0_ de sorte que M(a5)= [M(al )]1, ou encore [M(a5)] = M(a19). Comme autre exemple, la multiplication par a9 = a + a' dans GF (24) est donnée par le produit matriciel : 10 Yo 321 Y2 _Y3 _ 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 1 X X0 Xi ± X3 X1 X0 ± X1 ± X2 ± X3 X2 Xi ± X2 ± X3 X X0 ± X2 ± X3 _ 3 _ On notera que cette expression n'utilise que des XORs des coordonnées binaires x, E 10,11 de l'élément x. On peut ainsi commodément effectuer la multiplication de tout élément x de GF(2m) par tout élément a E GF (2') sur la base de l'équation (1) ci-dessus 15 et des sous-matrices de la matrice de référence T, ce qui ne fait intervenir que des XORs des coordonnées de x. On va expliquer à présent comment on peut utiliser cette méthode pour effectuer la multiplication par tout élément a E GF (2') au niveau des paquets. Le produit matriciel de l'équation (1) peut être aisément parallélisé lorsque 20 chaque x, est un vecteur binaire de longueur L. Par exemple, la multiplication par un élément a dans GF(24) devient : 3061393 17 Y0,1, Y0,2, - YU, Y1,2, - Y2,1' Y2,2' - Y3,1, Y3,2, - - - YO,L ao al a3 a2 al - - - XO,L - - 1,L a2 a3 + a0 a3 + a2 a2 + al X0,1, X0,2 - - X2,L - - Y2,L Y3,L a3 al a3 + a0 a3 + a2 a + a X2,1, x2,2' - X31, X3 1 , - - - , - - a2 a 1 3 0 _ où, avantageusement, toutes les opérations sont effectuées dans GF (2) . On utilisera ci-après la notation x(i,:)= xi,2, - - - , ) pour dénoter la ligne n° i d'une matrice X de dimension mx L ; le produit matriciel ci-dessus 5 peut alors être commodément vu comme mettant en oeuvre des XORs de ces lignes x(i,:). Par exemple, la multiplication par a' = a + a' présentée ci-dessus peut être commodément écrite sous la forme : y(0,:) 0 1 0 1 x(0,:) x(1,:)+ x(3,:) - y(1,:) 1 1 1 1 x(1,:) x(0,:)+ x(1,:)+ x(2,:)+ x(3,:) y(2,:) 0 1 1 1 x(2,:) x(1,:)+ x(2,:)+ x(3,:) y(3,:) 1 0 1 1 x(3,:) x(0,:)+ x(2,:)+ x(3,:) Les considérations ci-dessus exp iquent comment on peut, au cours du 10 codage ou du décodage dans un corps de Galois GF (2') , où ln > 1, défini au moyen d'un polynôme primitif prédéterminé, calculer un paquet Q = a - P, où le nombre a appartient à GF (2') , et P est un paquet de données P = (xi, - - - ,x L) , dans lequel xj , pour j =1,- - -,L, avec L 1, est un symbole composé d'une suite de m bits xij , où i = 0,- - -,m-1. 15 Selon le présent mode de réalisation, on met en oeuvre les sous-étapes suivantes. a) On remplit une matrice binaire X de dimension m x L en plaçant les bits xij composant chaque symbole xj le long de la j -ième colonne, comme illustré schématiquement sur la figure 5. On désigne par x(i,:) la i-ème ligne, où 20 i = 0. - -rn -1 , de cette matrice X. Autrement dit, si l'on regarde le paquet P comme une ligne de bits numérotés de 1 àmxL, la ligne x(i,:) est définie par : P[i +1+ / / = 0. - - L -1 . 3061393 18 b) On calcule la matrice binaire Y, de dimension m x L, au moyen du produit matriciel : Y =M(a)xX, où la matrice M(a) est l'équivalent binaire, défini ci-dessus, de l'élément a. 5 Comme expliqué ci-dessus, effectuer ce produit matriciel revient à calculer les lignes de la matrice Y par des XORs de lignes de la matrice X, selon des motifs binaires déterminés par les lignes de la matrice M(a) . On opère ainsi, avantageusement, de manière vectorielle sur les L symboles du paquet P. c) On obtient finalement le paquet Q=(y1,...,y), dans lequel 10 chaque symbole y1, pour j=1,2,---,L, est composé des m bits yi j, où i = 0,- - .,m-1, situés sur la j -ième colonne de la matrice Y obtenue précédemment. Autrement dit, il suffit de lire la matrice Y colonne par colonne. On va, pour terminer, expliquer comment on peut utiliser cette méthode pour effectuer, toujours au niveau des paquets, la multiplication par n'importe 15 quelle matrice A dont les éléments at,, appartiennent à GF(2m), où m > 1. En effet, une telle matrice peut être aisément transformée en une matrice binaire, que l'on appellera « image binaire » de la matrice A, en remplaçant tous ses éléments at,j E GF(2m) par leurs équivalents binaires m x m définis ci- dessus. Cela est notamment le cas pour la matrice de parité d'un code linéaire. 20 Considérons par exemple un code de Reed-Solomon défini sur GF(24) (pour la définition de ces codes, fréquemment utilisés, cf. l'article de I. Reed et G. Solomon intitulé « Polynomial codes over certain finite fields », J. Soc. Indust. Appl. Math, vol. 8, pages 300 à 304, 1960). Sa matrice de parité est : 1 a a2 a3 a4 a5 a6 a7 a8 a9 a1° a11 a12 a13 a14 1 a2 _4 a6 a8 a10 a12 a14 a a3 a5 d a a a13 11 13 25 25 On obtient une image binaire « en blocs » de la matrice H en remplaçant chaque élément ak par son équivalent binaire M(ak) de dimension 4 x 4 , comme illustré sur la figure 6. En enlevant les parenthèses internes, on obtient une image binaire « aplatie » de la matrice H, comme illustré sur la figure 7. H= 3061393 19 La forme de la figure 6 est plus adaptée au procédé selon l'invention, chaque opération aid xi dans l'arithmétique de GF(2'") étant remplacée par un produit d'une matrice binaire m x m par une matrice binaire m x L lorsque l'on parallélise les traitements sur des paquets de L symboles de GF(2'n). 5 L'invention peut être mise en oeuvre au sein des noeuds, par exemple un noeud émetteur ou un noeud récepteur, de réseaux de communication, au moyen de composants logiciels et/ou matériels. Les composants logiciels pourront être intégrés à un programme d'ordinateur classique de gestion de noeud de réseau. C'est pourquoi, comme 10 indiqué ci-dessus, la présente invention concerne également un système informatique. Ce système informatique comporte de manière classique une unité centrale de traitement commandant par des signaux une mémoire, ainsi qu'une unité d'entrée et une unité de sortie. De plus, ce système informatique peut être utilisé pour exécuter un programme d'ordinateur comportant des instructions 15 pour la mise en oeuvre de l'un quelconque des procédés de codage, ou de décodage, de paquets de données selon l'invention. En effet, l'invention vise aussi un programme d'ordinateur téléchargeable depuis un réseau de communication comprenant des instructions pour l'exécution des étapes d'un procédé de codage, ou de décodage, de paquets de 20 données selon l'invention, lorsqu'il est exécuté sur un ordinateur. Ce programme d'ordinateur peut être stocké sur un support lisible par ordinateur et peut être exécutable par un microprocesseur. Ce programme peut utiliser n'importe quel langage de programmation, et se présenter sous la forme de code source, code objet, ou de code intermédiaire 25 entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. L'invention vise aussi un support d'informations, inamovible, ou partiellement ou totalement amovible, lisible par un ordinateur, et comportant des instructions d'un programme d'ordinateur tel que mentionné ci-dessus. 30 Le support d'informations peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comprendre un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de 3061393 20 circuit microélectronique, ou un moyen d'enregistrement magnétique, tel qu'un disque dur, ou encore une clé USB (« USB flash drive » en anglais). D'autre part, le support d'informations peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble 5 électrique ou optique, par radio ou par d'autres moyens. Le programme d'ordinateur selon l'invention peut être en particulier téléchargé sur un réseau de type Internet. En variante, le support d'informations peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour 10 être utilisé dans l'exécution de l'un quelconque des procédés de codage, ou de décodage, de paquets de données selon l'invention. REVENDICATIONS1. Procédé de codage de paquets de données, comprenant les étapes suivantes : - réception de paquets de données utiles, chaque paquet de données utiles contenant 1 symboles constitués chacun d'une suite de m > 1 bits, et - codage desdits paquets de données utiles de manière à obtenir n>k paquets codés contenant chacun L symboles constitués d'une suite de m bits, ledit codage étant réalisé au moyen d'un code linéaire C(n,k) de longueur n et de dimension k opérant sur le corps d'extension binaire GF (2') défini au moyen d'un polynôme primitif choisi, caractérisé en ce que ladite étape de codage des paquets de données utiles comprend au moins une sous-étape de multiplication Q=a-P de tous les symboles d'un paquet de données P = (xi,- - - , xL) dans lequel x, pour j =1,- - -,L, est un symbole composé d'une suite de m bits xij , où i=0,- - -,m-1 , par un même nombre a appartenant à GF (2' ) , et en ce que ladite multiplication est effectuée de la manière suivante : a) on remplit une matrice binaire X de dimension m x L en plaçant les bits xij composant chaque symbole xj le long de la j -ième colonne de ladite matrice X; b) on calcule une matrice binaire Y, de dimension m x L, définie par le produit matriciel Y =M(a)xX, où M(a) est la matrice binaire de dimensions m x m dont les colonnes respectives contiennent les coordonnées binaires des éléments respectifs {a, a a, - - - , am 1 a} ; et c) on obtient le paquet de données Q = (yi,- - - , y L), dans lequel chaque symbole y1, pour j=1,2,---,L, est composé des m bits yi j, où i = 0,- - - ,m -1, situés sur la j -ième colonne de ladite matrice Y. 3061393 22 2. Procédé de codage selon la revendication 1, caractérisé en ce que lesdites matrices M(a), pour a = a1 et i =1,2,- - -,m -1, sont extraites d'une matrice de référence T de dimension mx (2m +m- 2). 5 3. Procédé de décodage de paquets de données, comprenant les étapes suivantes : - réception de n>1 paquets de données codés, chaque paquet de données codé contenant symboles constitués d'une suite de m >1 bits, lesdits paquets de données ayant été codés au moyen d'un code linéaire C(n,k) 10 de longueur n et de dimension k, où 1 k 4. Procédé de décodage selon la revendication 3, caractérisé en ce que lesdites matrices M(a), pour a = a' et i =1,2,- - .,m-1, sont extraites d'une matrice de référence T de dimension mx (2m +m- 2). 5. Dispositif de codage de paquets de données, comprenant des 10 moyens pour : - recevoir k 1 paquets de données utiles, chaque paquet de données utiles contenant 1 symboles constitués chacun d'une suite de m > 1 bits, et - coder lesdits paquets de données utiles de manière à obtenir n>k paquets codés contenant chacun L symboles constitués d'une suite de m bits, 15 ledit codage étant réalisé au moyen d'un code linéaire C(n,k) de longueur n et de dimension k opérant sur le corps d'extension binaire GF (2') défini au moyen d'un polynôme primitif choisi, caractérisé en ce qu'il comprend en outre, dans le but d'effectuer une multiplication Q= a - P, requise pour le codage des paquets de données utiles, 20 de tous les symboles d'un paquet de données P = (xi,- - - ,xL) dans lequel xi , pour j=1,---,L, est un symbole composé d'une suite de m bits x, où i =0,- par un même nombre a appartenant à GF (2') , des moyens pour : - remplir une matrice binaire X de dimension m x L en plaçant les bits xu 25 composant chaque symbole xi le long de la j -ième colonne de ladite matrice X; - calculer une matrice binaire Y, de dimension m x L, définie par le produit matriciel Y = M (a)xX, 3061393 24 où M(a) est la matrice binaire de dimensions m x m dont les colonnes respectives contiennent les coordonnées binaires des éléments respectifs {a, aa, - --, am la} ; et - obtenir le paquet de données Q=(yi,---,yL), dans lequel chaque 5 symbole y1, pour j=1,2,...,L, est composé des m bits y, , où i =0,- - .,m-1, situés sur la j -ième colonne de ladite matrice Y. 6. Dispositif de codage selon la revendication 5, caractérisé en ce qu'il comprend en outre des moyens pour extraire lesdites matrices M(a), pour 10 a =a et i =1,2,- --m-1, d'une matrice de référence T de dimension mx (2m +m-2). 7. Dispositif de décodage de paquets de données, comprenant des moyens pour : 15 - recevoir n > 1 paquets de données codés, chaque paquet de données codé contenant L symboles constitués d'une suite de m >1 bits, lesdits paquets de données ayant été codés au moyen d'un code linéaire C(n,k) de longueur n et de dimension k, où 1 k 8. Dispositif de décodage selon la revendication 7, caractérisé en ce 15 qu'il comprend en outre des moyens pour extraire lesdites matrices M(a), pour a =a et i=1,2,---,m-1, d'une matrice de référence T de dimension mx (2m +m-2). 9. Noeud émetteur, caractérisé en ce qu'il comprend un dispositif de 20 codage selon la revendication 5 ou la revendication 6. 10. Noeud récepteur, caractérisé en ce qu'il comprend un dispositif de décodage selon la revendication 7 ou la revendication 8. 25 11. Système de transmission (R) de données, comprenant au moins un noeud émetteur (1) selon la revendication 9 et au moins un noeud récepteur (2) selon la revendication 10, mutuellement connectés par un canal (T) sujet à des effacements de paquets.30