Brevet FR3064858A1 — publié le 20181005

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 dit « de réseau » (« Network Coding » en anglais). 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 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 à 25 pertes, tels que VoLTE (Voice over LIE) ou WebRTC (Web Real-Time Communication). On rappelle que le codage de réseau (cf. par exemple l'article de R. Koetter et M. Medard intitulé « An algebraic approach to network coding », IEEE/ACM Transactions on Networking, vol. 11, n° 5, oct. 2003, pages 782 à 30 795) consiste à transmettre des informations dans des paquets de données de telle sorte que ces informations suivent plusieurs trajets dans une infrastructure distribuée comprenant des noeuds qui servent de relais (ou de routeurs). 3064858 2 La présente invention concerne plus particulièrement le cas dans lequel les relais peuvent stocker et retransmettre (« store and forward » en anglais) les paquets de données utiles entrant dans ces relais, mais peuvent aussi, comme illustré sur la figure 1, retransmettre des paquets de données utiles qui résultent 5 d'un traitement sur ces paquets d'entrée, c'est-à-dire qui constituent une certaine fonction f de ces paquets d'entrée. On supposera que les paquets de données utiles contenus dans tous ces paquets de données ont tous le même nombre de bits. Si ce nombre est un multiple d'un entier m supérieur à 1, on peut considérer que chaque paquet de 10 données utiles est constitué de L symboles de m bits appartenant à un corps d'extension binaire GF (2m ) . On rappelle à cet égard que l'on appelle corps de Galois (noté GF (q)) un ensemble de q éléments dont les éléments non-nuls peuvent être identifiés comme étant chacun égal à a pour une valeur correspondante de j, où j =1,...,q-1, et où a est une racine ( q -1 )ème 15 primitive de l'unité dans GF (q) ; lorsque, en particulier, q = 2m , où m > 1, le corps de Galois est également appelé « corps d'extension binaire ». Chaque relais peut transférer sans modification les paquets de données utiles qu'il reçoit, ou transmettre sur le lien de sortie une combinaison linéaire de paquets reçus sur les liens d'entrée, étant entendu que, comme expliqué ci- 20 dessus (canal à effacements), certains paquets envoyés par d'autres noeuds du réseau peuvent ne pas avoir être reçus (auxquels cas le relais ne cherche pas à retrouver les paquets effacés). Lorsque les paquets d'entrée Xi.--X' sont tous constitués de L éléments de GF (2m ) , une opération très simple sur ces paquets d'entrée consiste à effectuer une addition bit à bit (on rappelle que l'addition bit à bit est également appelée « OU exclusif », et notée « XOR ») des paquets d'entrée : Y =Xi e X2 e - - - e x' . Une règle de calcul plus complexe du paquet de sortie Y met en oeuvre des combinaisons linéaires des paquets d'entrée X1. - - Xn avec des coefficients ai c GF (2m) , c'est-à-dire : 3064858 3 Y = a1 X1a2 X2 e---() an X Cette relation entrée-sortie fait maintenant intervenir des multiplications dans le corps GF (2m) . Par commodité de notation, nous représenterons ci-après l'opération XOR par le symbole usuel ( + ) de l'addition, de sorte que la relation 5 précédente s'écrit : Y = a2 X2+ - - - ± an X n La transmission de paquets d'information d'une source S vers un destinataire (ou récepteur) D via un réseau N peut être décrite par un graphe (voir figure 2) dont les noeuds représentent des relais tels que celui illustré sur la 10 figure 1, et les branches représentent les liens existants entre : la source et un ou plusieurs relais, le destinataire et un ou plusieurs relais, et entre les relais eux-mêmes. La source S émet une suite de paquets d'information {P" P2, - - - , Pk} , dits 15 paquets initiaux. Un même paquet /3, peut circuler sur plusieurs chemins du réseau N issus de S. Le destinataire D peut donc recevoir un nombre k de paquets de données utiles R, , chacun d'entre eux pouvant être : - une copie d'un des paquets P1, s'il a été transmis par des noeuds retransmettant sans modification les paquets qu'ils reçoivent, ou 20 - une combinaison linéaire de la forme Ri cia Pi+ Ci2 P2 ± - - - ± Ci,k Pk =1Ci Pi j=1 s'il est passé par des relais effectuant des combinaisons linéaires, les coefficients étant pris dans un corps d'extension GF (2m) ; les relais du réseau N effectuent des combinaisons linéaires sur les paquets d'un même flot 25 (allant de la même source S vers le même destinataire D) avec des coefficients qui peuvent soit être déterminés une fois pour toutes, soit être tirés au sort à chaque application dans le cas du codage de réseau dit « aléatoire ». Il faut noter que, les différents chemins entre la source S et le destinataire D ayant potentiellement des longueurs différentes (en nombre de branches) et 3064858 4 des retards différents, les paquets reçus le sont dans un ordre qui peut être différent de celui des paquets émis. D'autre part la topologie du réseau n'est pas nécessairement connue du destinataire et/ou de l'émetteur. Cela signifie que le destinataire reçoit un nombre n de paquets qui sont chacun une combinaison 5 linéaire des paquets /3, suivante : c1,1 C1,2 RnL C2,1 C2,1 C2, k = Rn C1 n, c2 - - - Cn k , émis par la source S, ce que l'on peut écrire de la façon Cl,k PI P2 Pk _ = K x PI P2 Afin de retrouver ces paquets Pi à partir des paquets reçus R, , il faut que la matrice K soit connue du destinataire, et, lorsqu'elle est connue, qu'elle soit 10 de rang k. Il faut en particulier que le destinataire dispose d'un nombre k de paquets reçus R, , sans quoi la matrice serait de rang inférieur à k et l'on ne pourrait pas remonter aux paquets P.. Cette technique du codage de réseau consiste donc en un codage/décodage au moyen d'un code sans rendement prédéfini (« rateless 15 code » en anglais) à cause de la contrainte k, n pouvant être (théoriquement) infini. En fait il s'agit d'une instance des codes dits « codes fontaine » (« fountain codes » en anglais), avec les différences suivantes : - il existe plus d'un chemin entre source et destinataire, et les paquets reçus par un même destinataire peuvent avoir suivi des chemins différents ; 20 - les combinaisons linéaires des paquets d'information Pi ne sont pas effectuées par la source mais par les éléments du réseau (codage distribué) ; - les coefficients de ces combinaisons linéaires peuvent être prédéterminés et fixes dans le temps, ou bien être tirés au sort par les noeuds du réseau ; ce dernier cas (décrit dans l'article de T. Ho, M. Médard, R. Koetter, 25 D.R. Karger, M. Effros, J. Shi, et B. Leong intitulé « A random linear Network Coding approach to multicast », IEEE Trans. Information Theory, vol. 52, n° 10, oct. 2006, pages 4413 à 4430) est appelé « codage de réseau aléatoire » (« Random Linear Network Coding », ou RLNC, en anglais). 3064858 5 On notera que l'utilisation de codes sans rendement prédéfini pour récupérer les paquets perdus durant des phénomènes de congestion permet d'envisager la possibilité de mettre en oeuvre des protocoles de transmission de données par paquets sans faire appel au mécanisme de contention 5 classiquement utilisé pour éviter les collisions, d'où un gain en termes de simplicité de mise en oeuvre et de rapidité d'exécution. Cela étant, de simples considérations d'algèbre linéaire permettent de montrer que la résolution d'un système d'équations dans GF(2m) faisant intervenir des paquets de données peut être ramenée à des additions de paquets 10 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 dans GF(2m). Dans le cadre de ces calculs, l'addition bit à bit est simple à mettre en oeuvre, mais la multiplication dans GF(2m) repose classiquement sur un mécanisme logiciel de consultation de table de multiplication. 15 Or, lorsqu'il faut multiplier tous les éléments d'un vecteur donné , x') composé d'éléments de GF(2'") par un même élément a de GF(2) , on ne peut pas consulter ladite table de multiplication de façon vectorielle ; autrement dit, il faut consulter la table pour chaque élément x du vecteur, ce qui est d'autant plus lent que le vecteur est plus long. 20 La présente invention concerne donc, selon un premier aspect, un procédé de codage de paquets de données dans un réseau (N), comprenant les étapes suivantes : - réception de r 1 paquets de données utiles Y, constitué chacun par une combinaison linéaire 25 j=1 j où les coefficients ci(t) sont pris dans un corps d'extension GF(2m) défini au moyen d'un polynôme primitif choisi, des mêmes 1 paquets d'information {Po P2 , - - - , Pk} , dits paquets initiaux, chaque paquet d'information contenant L 1 symboles constitués chacun d'une suite de m > 1 bits ; 3064858 6 - calcul d'un paquet de données utiles sortant Y' constitué par une combinaison linéaire i=1 desdits paquets de données utiles Y, où les coefficients ai sont pris dans ledit 5 corps d'extension GF (2m) ; et - émission dudit paquet de données utiles sortant Y'. Ledit procédé de codage est remarquable en ce que ladite étape de calcul du paquet de données utiles sortant Y' comprend au moins une sous-étape de multiplication Q=a-P de tous les symboles d'un paquet de données 10 P=(xi,---,xL) dans lequel x3, pour j =1,- - -,L, est un symbole composé d'une suite de m bits xi] , 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) remplissage d'une matrice binaire X de dimension mxL en plaçant les bits xi] composant chaque symbole xi le long de la j -ième colonne 15 de ladite matrice X ; b) calcul d'une matrice binaire Y, de dimension mxL, définie par le produit matriciel Y = M(a)xX, où M(a) est la matrice binaire de dimensions mxm dont les colonnes 20 respectives contiennent les coordonnées binaires des éléments respectifs { a, a a, am la} ; et c) obtention du paquet de données Q=(yi,---,yL), dans lequel chaque symbole y], pour j =1,2,- est composé des m bits yu, où i =0,- situés sur la j-ième colonne de ladite matrice Y. 25 Grâce à ces dispositions, on peut remplacer le mécanisme classique de 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 3064858 7 logicielle du codage ou du décodage comme les techniques de l'état de l'art, elle permet aussi d'utiliser efficacement un circuit électronique simultanément à des moyens logiciels, ou à leur place. On notera en particulier que le procédé selon l'invention se prête bien à la 5 virtualisation. On peut en effet supposer que certaines fonctions nécessiteront le recours à des coprocesseurs matériels tels qu'un circuit logique programmable (« Field-Programmable Gate Array », ou FPGA, en anglais), un processeur graphique (« Graphics Processing Unit », ou GPU, en anglais), ou un processeur de signal numérique (« Digital Signal Processor », ou DSP, en anglais), pour 10 accélérer certains traitements nécessitant une grande puissance de calcul, tels que les traitements de chiffrement, mais aussi ceux introduits par le codage de canal et par le codage de réseau. La présente invention est donc particulièrement avantageuse dans le cadre d'une fonctionnalité de codage de réseau virtualisée (« Virtualized Network Function », ou VNF, en anglais) 15 principalement écrite sous forme logicielle et recourant à un accélérateur matériel mettant en oeuvre la multiplication dans GF (2-) en mode paquet. Selon des caractéristiques particulières, 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). 20 Grâce à ces dispositions, on peut aisément obtenir les matrices M(a) 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 : 25 - réception de n > 1 paquets de données codés R1, R2, ..., Rn, où, pour i =1,- -,n, chaque paquet de données codé Ri= JP1+ Ci,2 P2+ - - - ± Ci,k Pk Pj j=1 est une combinaison linéaire des mêmes paquets d'information Pi contenant chacun 1 symboles constitués d'une suite de m > 1 bits, et où les 3064858 8 coefficients. sont pris dans un corps d'extension GF(2m) défini au moyen d'un polynôme primitif choisi, et - résolution du système formé par lesdites combinaisons linéaires, de manière à obtenir lesdits paquets d'information Pj . 5 Ledit procédé de décodage est remarquable en ce que ladite étape de résolution d'un système de combinaisons linéaires 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 x1, pour j est un symbole composé d'une suite de m bits xu , où 10 i =0,- 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 xu 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 xL, définie par le produit matriciel Y = M(a)xX, où la matrice M(a) est la matrice binaire de dimensions mxm dont les colonnes respectives contiennent les coordonnées binaires des éléments 20 respectifs { a, aa, Crin la} ; et c) on obtient le paquet de données Q = (yi,- - - , y L), dans lequel chaque symbole y, pour j=1,2,--,L, est composé des m bits yu, où i =0,- situés sur la j -ième colonne de ladite matrice Y. Les avantages offerts par ce procédé de décodage sont essentiellement 25 les mêmes que ceux offerts par le procédé de codage succinctement exposés ci- dessus. 3064858 9 Selon des caractéristiques particulières, lesdites matrices M(a), pour a = al et i =1,2,- -,m-1, sont extraites d'une matrice de référence T de dimension mx(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 décodage. Selon un deuxième aspect, l'invention concerne divers dispositifs. Elle concerne ainsi, premièrement, un dispositif de codage de paquets de données, comprenant des moyens pour : 10 - recevoir r 1 paquets de données utiles Y, constitué chacun par une combinaison linéaire y cy) p j=1 j où les coefficients cj(t) sont pris dans un corps d'extension GF (21" ) défini au moyen d'un polynôme primitif choisi, des mêmes k 1 paquets d'information 15 {Po P2, - - - , Pk} , dits paquets initiaux, chaque paquet d'information contenant L symboles constitués chacun d'une suite de m > 1 bits ; - calculer un paquet de données utiles sortant Y' constitué par une combinaison linéaire i=1 20 des paquets de données utiles Yi, où les coefficients a, sont pris dans ledit corps d'extension GF (21" ) ; et - émettre ledit paquet de données utiles sortant Y'. Ledit dispositif de codage est remarquable en ce qu'il comprend en outre, dans le but d'effectuer au moins une multiplication Q = a - P, requise pour le calcul du 25 paquet de données utiles sortant Y', de tous les symboles d'un paquet de données P = (xi,-- - ,xL ) dans lequel x1, pour j=1,--,L, est un symbole 3064858 10 composé d'une suite de m bits xu , 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 composant chaque symbole x le long de la j -ième colonne de ladite matrice 5 X; - calculer une matrice binaire Y, de dimension MX L, définie par le produit matriciel Y =M(a)xX, où M(a) est la matrice binaire de dimensions mx m dont les colonnes 10 respectives contiennent les coordonnées binaires des éléments respectifs { a, a a, - - - , am 1 a} ; et - obtenir le paquet de données Q=(y1,...,yL), dans lequel chaque symbole y» pour j =1,2,-, L, est composé des m bits yu, où i = 0,- 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 =al et i =1,2,- -,m -1, d'une matrice de référence T de dimension mx (2,m + 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 R1, R2, Rfl, où, pour i =1,- -,n, chaque paquet de données codé Ri = P1 CP2+---±Ci,k Pk =1Ci j=1 est une combinaison linéaire des mêmes paquets d'information Pi 25 contenant chacun 1 symboles constitués d'une suite de m > 1 bits, et où les coefficients. sont pris dans un corps d'extension GF(2m) défini au moyen d'un polynôme primitif choisi ; et 3064858 11 - résoudre le système formé par lesdites combinaisons linéaires, de manière à obtenir lesdits paquets d'information Pi. Ledit dispositif de décodage est remarquable en ce qu'il comprend en outre, dans le but d'effectuer au moins une multiplication Q= a - P, requise pour la 5 résolution dudit système de combinaisons linéaires, de tous les symboles d'un paquet de données P =(x,-- - xL ) dans lequel x1, pour j=1,--,L, est un symbole composé d'une suite de m bits xij , où i =0,- par un même nombre a appartenant à GF (2-) , des moyens pour : - remplir une matrice binaire X de dimension m XL en plaçant les bits 10 composant chaque symbole xj le long de la j-ième colonne de ladite matrice X; - calculer une matrice binaire Y, de dimension mxL, définie par le produit matriciel Y =M(a)xX, 15 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 - obtenir le paquet de données Q=(yi,---,yL), dans lequel chaque symbole y, pour j=1,2,--,L, est composé des m bits yu, où 20 situés sur la j-ième colonne de ladite matrice Y. Selon des caractéristiques particulières, ledit dispositif de codage comprend en outre des moyens pour extraire lesdites matrices M(a), pour a = al et i=1,2,---,m-1, d'une matrice de référence T de dimension mx (2m +m-2). 25 Selon un troisième aspect, l'invention concerne : - un noeud, dit noeud relais, d'un réseau de communication, comprenant un dispositif de codage tel qu'exposé succinctement ci-dessus, et 3064858 12 - un noeud, dit noeud destinataire, d'un réseau de communication comprenant un dispositif de décodage tel qu'exposé succinctement ci-dessus. Naturellement, un noeud d'un réseau de communication peut comprendre à la fois un dispositif de codage et un dispositif de décodage tels qu'exposés 5 succinctement ci-dessus. Les avantages offerts par ces dispositifs et ces noeuds sont essentiellement les mêmes que ceux offerts par les procédés corrélatifs succinctement exposés ci-dessus. On notera qu'il est possible de réaliser ces dispositifs dans le contexte 10 d'instructions logicielles et/ou dans le contexte de circuits électroniques. Selon un quatrième aspect, l'invention concerne un réseau de communication, comprenant au moins un noeud relais tel que décrit succinctement ci-dessus et au moins un noeud destinataire tel que décrit succinctement ci-dessus. 15 On notera que dans un tel réseau de communication, ledit noeud relais et ledit noeud destinataire doivent, pour être mutuellement compatibles, utiliser non seulement le même corps d'extension binaire GF (2') , c'est-à-dire la même valeur de m, mais en outre la même représentation de ce corps, c'est-à-dire le même polynôme primitif. 20 L'invention vise également un programme d'ordinateur téléchargeable depuis un réseau de communication et/ou stocké sur un support lisible par ordinateur et/ou exécutable par un microprocesseur. Ce programme d'ordinateur est remarquable en ce qu'il comprend des instructions pour l'exécution des étapes du procédé de codage de paquets de données succinctement exposé ci- 25 dessus, ou du procédé de décodage de paquets de données succinctement exposé ci-dessus, lorsqu'il est exécuté sur un ordinateur. Les avantages offerts par ce programme d'ordinateur sont essentiellement les mêmes que ceux offerts par lesdits procédés. D'autres aspects et avantages de l'invention apparaîtront à la lecture de la 30 description détaillée ci-dessous de modes de réalisation particuliers, donnés à titre d'exemples non limitatifs. La description se réfère aux figures qui l'accompagnent, dans lesquelles : 3064858 13 - la figure 1, décrite ci-dessus, représente l'opération effectuée par un noeud relais dans le codage de réseau, - la figure 2, décrite ci-dessus, représente schématiquement un système de transmission T selon l'invention, 5 - la figure 3 représente schématiquement la structure d'un paquet de données selon un mode de réalisation de l'invention, - la figure 4 représente la relation entre l'opération effectuée par un noeud relais R dans le codage de réseau, et la structure du paquet de données transmis par ce noeud relais R, 10 - la figure 5 représente, au niveau d'un noeud relais R, la relation entre les paquets de données entrants et le paquet de données transmis, - la figure 6 représente, au niveau d'un noeud relais R, la relation entre les paquets de données entrants et le paquet de données transmis lorsqu'un paquet de données entrant est effacé, 15 - la figure 7 représente schématiquement un noeud relais R selon un mode de réalisation de l'invention, - la figure 8 représente schématiquement un noeud destinataire D selon un mode de réalisation de l'invention, et - la figure 9 représente la représentation d'un vecteur de L symboles 20 appartenant à GF(2m) sous la forme d'une matrice binaire m x L. On va expliquer pour commencer comment on peut, selon un mode de réalisation de l'invention, transporter dans chaque paquet de données transmis les informations sur la manière dont ce paquet de données transmis a été construit à partir de paquets d'information /3, initiaux (émis par la source S). Pour 25 ce faire, comme illustré sur la figure 3, on insère, par exemple entre l'en-tête (désigné par « header » sur les figures 3, 4, 5 et 6), et la partie utile (désignée par « payload » sur ces mêmes figures) du paquet de données, une suite C de k symboles de m bits égaux aux coefficients dans GF(2m) de la décomposition du paquet de données utiles transmis sur k paquets d'information 13, . 3064858 14 Par conséquent, les identifiants des paquets /3, initiaux sont respectivement égaux à C = (0,- -,0,1,0,- - 0) où 1 est le i-ème symbole de m bits, les autres symboles étant nuls. Lorsqu'un relais R du réseau N transmet un paquet d'information sans le 5 modifier, l'identifiant est inchangé. Lorsque ce relais effectue une combinaison linéaire de paquets d'information /3, , l'identifiant contient la liste des coefficients c2,- - -,c} utilisés, certains des coefficients pouvant être nuls, comme illustré sur la figure 4. Lorsqu'un relais R effectue une combinaison linéaire : 10 = Yi a2 Y2 + --- de paquets de données utiles Y déjà codés par d'autres noeuds du réseau, chaque paquet de données utiles Y, étant caractérisé par un vecteur d'identifiants C(1) , le vecteur d'identifiants C' du paquet de données sortant contient les combinaisons linéaires des identifiants des paquets d'entrée, comme 15 illustré sur la figure 5. Ainsi, l'opération faite sur les identifiants lors de la combinaison linéaire à coefficients dans GF(r) est exactement la même que celle effectuée sur les paquets de données utiles ; le relais R peut donc avantageusement faire ces deux opérations en une seule fois. 20 On notera que cette méthode fonctionne même en cas de perte de paquets. Par exemple, si un relais R devait combiner trois paquets de données utiles Yi , Y2 et Y3, mais qu'il n'a pas reçu ce dernier pour une raison quelconque, il calcule la combinaison des paquets de données utiles Yi et Y2, et indique dans l'en-tête les coefficients cl, résultant de cette combinaison, comme illustré sur la 25 figure 6. Autrement dit, l'en-tête d'un paquet de données utiles R reçu par le destinataire D indique toujours correctement la manière dont ce paquet de données utiles R a été obtenu à partir de paquets d'information /3, initiaux. Par conséquent, suite à la réception des paquets de données utiles {R" R2 , - - - , } , la matrice K mentionnée ci-dessus sera connue du destinataire, comme requis. 3064858 15 On notera également que la mise en oeuvre de cette méthode ne nécessite pas de connaître la topologie du réseau, puisque l'information sur la manière dont les paquets ont été codés est transportée dans les paquets eux-mêmes. Elle est dite non-cohérente dans la littérature technique. 5 Pour retrouver les paquets d'information {Pp- - -, Pk } à partir des paquets reçus, le destinataire D procède comme suit : - la source S n'attend pas d'acquittement pour chaque paquet qu'elle transmet ; - le destinataire D n'envoie pas d'acquittement lorsqu'il reçoit un paquet 10 codé ; - pour chaque paquet de données utiles Yi = [C R.]reçu, le destinataire D extrait l'identifiant Ci = ; on dispose ainsi d'une équation linéaire R, = c,,, P, + c ,,2 P2 ± - - - ± C Pk ; - dès que le destinataire D dispose de k telles équations, il vérifie si le 15 rang de la matrice du système est égal à k , en utilisant n'importe quelle méthode classique (par exemple la méthode de Gauss) ; l'article de C. Studholme et I. Blake intitulé « Random matrices and codes for the erasure channel », Algorithmica, vol. 56, n° 4, pages 605 à 620 (2310), démontre que, dans le cas d'une matrice remplie aléatoirement, la matrice est de rang égal à k 20 avec une grande probabilité ; - si le rang est inférieur à k , le destinataire D attend la réception de nouveaux paquets jusqu'à ce que la condition de rang égal à k soit vérifiée ; de préférence, on fixe une limite n max au nombre de paquets émis par la source S, et le destinataire D envoie un acquittement négatif (NACK) s'il n'arrive pas à 25 obtenir une matrice inversible après la fin de la transmission des n max paquets ; dans ce cas, la source envoie des paquets codés supplémentaires jusqu'à ce que le décodage soit possible ; - une fois que cette condition est vérifiée, on résout le système linéaire suivant : 3064858 16 C1,1 C1,2 Cl,k PI C2,1 C2,1 C2,k P2 R2 _c1 cn,2 - - - c',k_ _Pk_ ce qui fait intervenir des opérations d'addition/soustraction, et de multiplication des symboles d'un paquet par un même scalaire a E GF (2') , opérations que l'on peut, grâce à l'invention, effectuer par paquets, c'est-à-dire de manière 5 parallélisée. La figure 7 représente schématiquement un noeud relais R selon un mode de réalisation de l'invention. Le relais R comporte un module de réception 10, un module d'extraction 11, un module 12 de calcul du paquet de données utiles sortant, un module 10 mémoire 13, un module de construction 14 et un module de transmission 15. Le module d'entrée 10 est adapté à recevoir des paquets de données entrants de la part d'autres noeuds du réseau N, et à transmettre ces paquets de données entrants au module d'extraction 11. Le module d'extraction 11 est adapté à extraire de chaque paquet entrant son en-tête (désigné par « H» sur la 15 figure 7), et à transmettre au module de calcul 12 le reste du paquet entrant, c'est-à-dire l'ensemble formé par un vecteur d'identifiants C(1) et un paquet de données utiles Y, (désigné par « payload » sur la figure 7). Le module de calcul 12 est adapté à puiser les coefficients a dans le module mémoire 13 pour calculer, en parallèle : 20 - le paquet de données utiles sortant = a2 Y2 + et - le vecteur d'identifiants sortant C', dont les composantes sont c't = ac(1) + a2 c(2) + en mettant en oeuvre le procédé de multiplication dans GF(2m) selon l'invention. 25 On notera, concernant le module mémoire 13, que : - ce module peut être intégré dans le relais R comme représenté sur la figure 7, ou constituer une source externe consultable par le relais R, et 3064858 17 - les coefficients ce, peuvent être constants pour un relais R donné, ou varier à chaque nouveau paquet entrant dans le relais R (par exemple au moyen d'un tirage au sort). Le module de construction 14 est adapté à recevoir, d'une part l'en-tête 5 de paquet H mentionné précédemment, et d'autre part l'ensemble formé par le vecteur d'identifiants sortant C' et le paquet de données utiles sortant Y' , et à construire à partir de ces éléments un paquet de données sortant. Enfin, le module de transmission 15 est adapté à recevoir le paquet de données sortant de la part du module de construction 14, et à transmettre ce 10 paquet de données sortant sur le réseau N. La figure 8 représente schématiquement un noeud destinataire D selon un mode de réalisation de l'invention. Le destinataire D comporte un module de réception 20, un module d'extraction 21, un module de construction 22, un module de second membre 23, 15 un module de test 27, un module d'inversion 26, un module de résolution 24 et un module de transmission 25. Le module d'extraction 21 est adapté à séparer, dans chaque paquet reçu, son en-tête (désigné par « H » sur la figure 8), son vecteur d'identifiants C, C, - - - , ) et son paquet de données utiles 1. 20 Le module de second membre 23 est adapté à recevoir de la part du module d'extraction 21, au fur et à mesure des réceptions de paquets par le module de réception 20, les paquets de données utiles R, et à ajouter des lignes égales à ces paquets de données utiles R au vecteur de second membre R2 25 De même, le module de construction 22 est adapté à recevoir de la part du module d'extraction 21, au fur et à mesure des réceptions de paquets par le module de réception 20, les vecteurs d'identifiants C, ,---,c,, ), et à 3064858 18 ajouter des lignes constituées de ces identifiants à une matrice servant à construire la matrice K. De même, le module de test 27 est adapté à recevoir, au fur et à mesure des réceptions de paquets par le module de réception 20, ladite matrice en 5 construction de la part du module de construction 22, et à déterminer si le déterminant de cette matrice est différent de zéro, c'est-à-dire si cette matrice est régulière (rang égal à k). Lorsque ce n'est pas le cas, le fonctionnement décrit ci-dessus continue. Lorsque c'est le cas, le module de réception 20 est adapté à arrêter de recevoir 10 des paquets, et le module d'inversion 26 est adapté à calculer l'inverse de la matrice K obtenue. Le module de résolution 24 est adapté à recevoir ledit vecteur de second membre de la part du module de second membre 23, ainsi que l'inverse de la matrice K de la part du module d'inversion 26, et à calculer le produit de ces deux grandeurs en mettant en oeuvre le procédé de multiplication 15 dans GF(2m) selon l'invention, de façon à retrouver les paquets d'information {Pi,- - -, Pk } initiaux. Enfin, le module de transmission 25 est adapté à recevoir les paquets d'information {F,. - - ,Pk } initiaux de la part du module de résolution 24, et à transmettre ces paquets d'information à l'utilisateur du noeud destinataire D. 20 Comme expliqué ci-dessus, le codage et le décodage considérés dans la présente invention sont réalisés dans un corps d'extension binaire GF(2m), où m > 1. On entend par là qu'a tout symbole donné composé de m bits xik , où i =0,- on associe l'élément de GF (2"), noté ,ck , dont les coordonnées binaires sur une base canonique {1, a, a2,---, a""} choisie sont précisément 25 lesdits bits xik ; autrement dit : m-1 x - - -Ixiiat, 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 dans GF(2m) uniquement au moyen d'additions binaires (XOR). 3064858 19 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+cr. Le résultat de la multiplication de l'élément X = X0 + X1 a + X2 a2 + X3a3, de coordonnées binaires X, E {0,1}, par l'élément a = ao+ al a + a2 a2 + a3a3, de 5 coordonnées binaires a, E IO», est l'élément y = y0 + y1 + y2 a2 + y3a3 dont les coordonnées binaires y , E {0,1} sont obtenues comme suit : y =ax= xoa+ xi(a a)+ x2 (a2 a) + x3(a3 a) Yo - - X0 = a a a a2a a3a x = M (a)x Y2 X2 X2 _Y3_ X _ 3_ _X3_ par définition de la matrice M(a), dont les colonnes successives sont constituées par les coordonnées binaires des éléments a , a a , da et a3 a de 10 GF (24) successivement. Pour calculer ces colonnes, on notera, par exemple, que a a = ao a + ai a2 + a2 a3 + a3a4 = ao a + ai a2 + a2 a3 + a3 (1+ a) = a3+ (a3 + ao)a + ai a2 + ct2 a3 On procède de la même façon pour a2a et a3a . Le résultat final est : Yo ao a3 a2 al X0 321 al a3 + a0 a3 + a2 a2 + al Xi Y2 a2 a1 a3 + a0 a3 + a2 X2 Y3 a3 a2 al a3 + a0 _X3_ 15 Dans le cas général d'un corps GF(2m) pour m quelconque, on calcule : Y = M (a)x X , (1) où : - X est le vecteur colonne contenant les m coordonnées binaires X, E {0,1} de x, 20 - Y est le vecteur colonne contenant les m coordonnées binaires y, E fo,(} de y , et 3064858 20 - la matrice M (a) , où a E GF (2"), est la matrice binaire mxm dont les colonnes contiennent les coordonnées binaires des éléments { a, a a, - - - , am-1a } de GF(2m) , soit - : M (a) = m-1 a aa --- a a 5 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 - ak ak+1 k+m-1 associées aux puissances consécutives de a. On notera que toutes ces matrices peuvent être obtenues en consultant une « grande » matrice binaire - 10 T= 1 a a2 crk+m-1 , n = 2m -1 15 de dimension mx(2m + m - 2) , construite préalablement, dont les colonnes 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 20 référence T, ce que l'on notera ainsi : M(d)=T(:, k +1: k + m) , pour k = 0,1,- - -,2m -2. 3064858 21 Par définition, le produit de deux éléments a = ak et b=cé est égal à a(") , où (1( +1) = (k +1) mod(r -1), de sorte que la matrice associée au produit ak X Cé est M (a(k+1)) , 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 5 M(ak) et m(oé) par : M(oek )xM(oel ) = M(oe'). De la même manière, la matrice associée à l'inverse d'un élément a = ak est [m(oek)T' =m(ari-k), puisque M(oek)xm(oen_k) m(a) m(c%0), qui est la matrice identité. 10 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 T= 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 de sorte que, par exemple : 1 0 0 1 1 0 1 1 1 1 0 0 4 1 1 0 1 1 1 1 0 0 0 1 0 15 M(cr ) , M(am) = M (6(14 ) 0 1 1 0 1 1 1 1 0 0 0 1 0 0 1 1_ 0 1 1 1 1 0 0 0 On vérifie facilement, par exemple, que le produit des matrices binaires M(a )XM(a 410) est bien égal à M(a14 ) comme prévu. En poursuivant le même exemple, on trouve : 0 0 1 1 1 0 0 0 m(a5) = 1 0 1 0 , et M (a5 )x M (al° ) = 0 1 0 0 = m(1), 1 1 0 1 0 0 1 0 0 1 1 0 0 0 0 1 20 de sorte que M (a5 ) =[M (a'° )]' , ou encore [M (a5 )1' = M (al° ) . 3064858 22 Comme autre exemple, la multiplication par a' = a + a3 dans GF (24) est donnée par le produit matriciel : 0 0 1 0 1 X0 x1+ X3 .Y1 1 1 1 1 X1 X0 + X1 ± X2 + X3 Y2 0 1 1 1 X2 X1 ± X2 + X3 _ Y3 _ 1 0 1 1 X X0 + X2 + X3 _ 3 _ On notera que cette expression n'utilise que des XORs des coordonnées 5 binaires x, E {0,1} 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 (2m) sur la base de l'équation (1) ci-dessus 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. 10 On va expliquer à présent comment on peut utiliser cette méthode pour effectuer la multiplication par tout élément a E GF (2m) au niveau des paquets. Le produit matriciel de l'équation (1) peut être aisément parallélisé lorsque chaque xi est un vecteur binaire de longueur L. Par exemple, la multiplication par un élément a dans GF (24 ) devient : 15 Y0,1, Y1,1, Y2,1, _ Y3,1, Y0,2 - - - YO,L Yi,L Y2,L Y3,L _ ao al a3 a2 al X01, X0,2, - - , X1,2 , - - - , X0,L Y1,2, - - - a2 a3 + a0 a3 + a2 a3 + a0 al a2 + al X2,1, X2,2, - - - , Y2,2 - - - a3 a1 a3 + a2 a3 + a 0 _ X3 1 , X3 2 , - - - X2 ,L Y3,2 - - - a2 _ , - , X3 L , _ 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 m x L ; le produit matriciel ci-dessus peut alors être commodément vu comme mettant en oeuvre des XORs de ces 20 lignes Par exemple, la multiplication par a' = + a3 présentée ci-dessus peut être commodément écrite sous la forme : 3064858 23 0 1 0 1 -x(0, x(1,:)+ x(34 - 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,:) 1 0 1 1 _ x(0, :)+ x(2,:)+ x(3,:) _ Les considérations ci-dessus exp iquent comment on peut, au cours du codage ou du décodage dans un corps de Galois GF (2"), où m > 1, défini au moyen d'un polynôme primitif prédéterminé, calculer un paquet Q= a - P, où le 5 nombre a appartient à GF (2") , et P est un paquet de données P = (xi,-- - ,x L), dans lequel x1, pour j avec L 1, est un symbole composé d'une suite de m bits xu , où i =0,- Selon le présent mode de réalisation, on met en oeuvre les sous-étapes suivantes. 10 a) On remplit une matrice binaire X de dimension mxL en plaçant les bits xu composant chaque symbole x le long de la j -ième colonne, comme illustré schématiquement sur la figure 9. On désigne par x(i,:) la i -ème ligne, où i =O. -m-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 : 15 )= PP +1+ / / = O. - - L -1 . 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. 20 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=(yi,---,yL), dans lequel 25 chaque symbole y, , pour j=1,2,--,L, est composé des m bits yu , où 3064858 24 i =0,- 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 5 quelle matrice A dont les éléments a1 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 a1 E GF(2m) par leurs équivalents binaires mxm définis ci- dessus. 10 L'invention peut être mise en oeuvre au sein des noeuds, par exemple un noeud relais ou un noeud destinataire d'un réseau 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 15 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 20 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 25 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 30 entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. 3064858 25 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. Le support d'informations peut être n'importe quelle entité ou dispositif 5 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 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 10 tel qu'un signal électrique ou optique, qui peut être acheminé via un câble é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 15 lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour ê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 dans un réseau (N), comprenant les étapes suivantes : - réception de 1 paquets de données utiles 17, constitué chacun par une combinaison linéaire yi cy) p j=1 j où les coefficients ci(t) sont pris dans un corps d'extension GF(r) défini au moyen d'un polynôme primitif choisi, des mêmes k 1 paquets d'information {Po P2, - - - , Pk} , dits paquets initiaux, chaque paquet d'information contenant L 1 symboles constitués chacun d'une suite de m > 1 bits ; - calcul d'un paquet de données utiles sortant Y' constitué par une combinaison linéaire Yl= lai Yi i=1 desdits paquets de données utiles 17, , où les coefficients a, sont pris dans ledit corps d'extension GF(r) ; et - émission dudit paquet de données utiles sortant Y' ; caractérisé en ce que ladite étape de calcul du paquet de données utiles sortant Y' 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 x3, pour j est un symbole composé d'une suite de m bits xu , où i =0,- par un même nombre a appartenant à GF (2') , et en ce que ladite multiplication est effectuée de la manière suivante : a) remplissage d'une matrice binaire X de dimension mxL en plaçant les bits xu composant chaque symbole xi le long de la j -ième colonne de ladite matrice X ; 3064858 27 b) calcul d'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 mxm dont les colonnes 5 respectives contiennent les coordonnées binaires des éléments respectifs {a, aa, Cela} ;et c) obtention du paquet de données Q = (yi,- - - , yL ), dans lequel chaque symbole y» pour j=1,2,---,L, est composé des m bits yu, où i =0,- situés sur la j -ième colonne de ladite matrice Y. 10 2. Procédé de codage selon la revendication 1, 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 (2,m +m-2). 15 3. Procédé de codage selon la revendication 1 ou la revendication 2, dans lequel chacun desdits paquets de données utiles 17, est contenu dans un paquet de données contenant en outre un vecteur d'identifiants C(1) (c(1) c(1) c(1)) , 2 ,---, k comprenant lesdits coefficients ci(t) , et dans lequel ledit paquet de données utiles 20 Y' est contenu dans un paquet de données contenant en outre un vecteur d'identifiants sortant C= (C,1 , C'k , OÙ CI] = C(i) J 1-1 caractérisé en ce que le calcul dudit vecteur d'identifiants sortant C' est effectué au moyen des mêmes opérations et simultanément au calcul dudit paquet de 25 données utiles sortant Y'. 4. Procédé de décodage de paquets de données, comprenant les étapes suivantes : 3064858 28 - réception de n >1 paquets de données codés R1, R2, , où, pour i chaque paquet de données codé Ri= ci, P1+ C42 P2 ± - - - ± Pk =1C, j j=1 est une combinaison linéaire des mêmes paquets d'information Pi 5 contenant chacun 1 symboles constitués d'une suite de m > 1 bits, et où les coefficients c sont pris dans un corps d'extension GF(2m) défini au moyen d'un polynôme primitif choisi, et - résolution du système formé par lesdites combinaisons linéaires, de manière à obtenir lesdits paquets d'information P3 , 10 caractérisé en ce que ladite étape de résolution d'un système de combinaisons linéaires 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 x3, pour j est un symbole composé d'une suite de m bits xi] , où i =0,- par un même nombre a appartenant à GF(2m), et en ce que 15 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 xi] composant chaque symbole xi le long de la j-ième colonne de ladite matrice X ; b) on calcule une matrice binaire Y, de dimension 111X L, définie par 20 le produit matriciel Y =M(a)xX, où la matrice M(a) est la matrice binaire de dimensions mxm dont les colonnes respectives contiennent les coordonnées binaires des éléments respectifs fa, aa, (rial; et 25 c) on obtient le paquet de données Q =(yi,--- ,yL), dans lequel chaque symbole y, pour j =1,2,--,L, est composé des m bits yu, où i =0,- situés sur la j-ième colonne de ladite matrice Y. 3064858 29 5. Procédé de décodage selon la revendication 4, 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 (2,m +m-2). 6. Dispositif de codage de paquets de données, comprenant des moyens pour : - recevoir r >1 paquets de données utiles 17, constitué chacun par une combinaison linéaire y cy) p j=1 j où les coefficients ci(t) sont pris dans un corps d'extension GF (r) défini au moyen d'un polynôme primitif choisi, des mêmes k 1 paquets d'information {Po P2, - - - , Pk} , dits paquets initiaux, chaque paquet d'information contenant L 1 symboles constitués chacun d'une suite de m > 1 bits ; 15 - calculer un paquet de données utiles sortant Y' constitué par une combinaison linéaire 171- ai Yi des paquets de données utiles 17, , où les coefficients a, sont pris dans ledit corps d'extension GF (2' ) ; et 20 - émettre ledit paquet de données utiles sortant Y' ; caractérisé en ce qu'il comprend en outre, dans le but d'effectuer au moins une multiplication Q = a - P, requise pour le calcul du paquet de données utiles sortant Y', de tous les symboles d'un paquet de données P = (xi,- - - , x L) dans lequel x1, pour j=1, ,L, est un symbole composé d'une suite de m bits xu , 25 où i =0,- par un même nombre a appartenant à GF (2') , des moyens 5 10 pour : 3064858 - remplir une matrice binaire X de dimension m x L en plaçant les bits composant chaque symbole x 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 5 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 10 - obtenir le paquet de données Q=(y1,...,yL), dans lequel chaque symbole yj, pour j=1,2,---,L, est composé des m bits yu, où i = 0,- situés sur la j-ième colonne de ladite matrice Y. 7. Dispositif de codage selon la revendication 6, caractérisé en ce qu'il 15 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). 8. Dispositif de codage selon la revendication 6 ou la revendication 7, 20 caractérisé en ce que, chacun desdits paquets de données utiles 17, étant contenu dans un paquet de données contenant en outre un vecteur d'identifiants Cl) = (c(1) c(1) c(1)) , 2 ,- - - k comprenant lesdits coefficients ci(t) , et ledit paquet de données utiles Y' étant contenu dans un paquet de données contenant en outre un vecteur d'identifiants 25 sortant C'= (c'1, C' 2 , k) , où CI =I ) J i=1 3064858 31 il comprend en outre des moyens pour effectuer le calcul dudit vecteur d'identifiants sortant C' au moyen des mêmes opérations et simultanément au calcul dudit paquet de données utiles sortant Y'. 5 9. Dispositif de décodage de paquets de données, comprenant des moyens pour : - recevoir n > 1 paquets de données codés R1, R2, , R', où, pour i = 1,- -,n , chaque paquet de données codé P1+ C 42 P2 ± - - - ± Pk =1C Pi j=1 10 est une combinaison linéaire des mêmes paquets d'information Pi contenant chacun symboles constitués d'une suite de m > 1 bits, et où les coefficients c sont pris dans un corps d'extension GF(r) défini au moyen d'un polynôme primitif choisi ; et - résoudre le système formé par lesdites combinaisons linéaires, de 15 manière à obtenir lesdits paquets d'information /33 ; caractérisé en ce qu'il comprend en outre, dans le but d'effectuer au moins une multiplication Q= a- P, requise pour la résolution dudit système de combinaisons linéaires, de tous les symboles d'un paquet de données P =(xi,--- ,xL) dans lequel x3, pour j est un symbole composé d'une 20 suite de m bits xu , 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 composant chaque symbole x le long de la j -ième colonne de ladite matrice X; 25 - calculer une matrice binaire Y, de dimension m x L, définie par le produit matriciel Y =M(a)xX, 3064858 32 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 - obtenir le paquet de données Q=(yi,---,yL), dans lequel chaque 5 symbole y» pour j =1,2,- est composé des m bits y, où situés sur la j -ième colonne de ladite matrice Y. 10. Dispositif de décodage selon la revendication 9, 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). 11. Noeud, dit noeud relais (R), d'un réseau de communication (N), caractérisé en ce qu'il comprend un dispositif de codage selon l'une quelconque 15 des revendications 6 à 8. 12. Noeud, dit noeud destinataire (D), d'un réseau de communication (N), caractérisé en ce qu'il comprend un dispositif de décodage selon la revendication 9 ou la revendication 10. 20 13. Réseau de communication (N), comprenant au moins un noeud relais (R) selon la revendication 11 et au moins un noeud destinataire (D) selon la revendication 12.