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 Broadcast Multicast Services) en LTE (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 LTE) ou WebRTC (Web Real-Time Communication).

On notera que, dans certains de ces systèmes, les paquets sont appelés « blocs », mais on utilisera uniformément le terme de « paquets » ci-dessous.

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

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 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 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 » sont des paramètres importants du code ; en particulier, un code de distance minimale d permet de corriger

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 dite matrice de parité : un mot

de longueur n donné est un mot de code si, et seulement si, il vérifie la relation : (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 à pour une valeur correspondante de j, où et où a est une racine { primitive de l'unité dans GF{q) .

Lorsque, en particulier, 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 œuvre des procédés de codage/décodage opérant au niveau des paquets de données, notamment 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. 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 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 à (chaque symbole est donc composé de m bits).

En supposant que l'on utilise un code linéaire, le codage est effectué sur n paquets { } (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 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 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 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 « 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 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 (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 (2 ^m ) . En effet, de tels codes (où, rappelons-le, m > 1 ) sont plus avantageux que les codes binaires ( ) sur le plan du rendement et de la distance minimale relative ô

L'arithmétique de ces corps d'extension met en œuvre l'addition bit à bit, et la multiplication d'éléments dans G L'addition bit à bit est simple à mettre en

œuvre, mais la multiplication repose classiquement sur un mécanisme logiciel de consultation de table de multiplication, mécanisme typiquement complexe et lent.

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

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 c'est-à-dire des combinaisons linéaires de paquets avec des coefficients pris dans

Or, lorsqu'il faut multiplier tous les éléments d'un vecteur donné composé d'éléments de par un même élément a de

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.

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 k≥ 1 paquets de données utiles, chaque paquet de données utiles contenant L≥l symboles constitués chacun d'une suite de m > l 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 de longueur n et de dimension k opérant sur le corps d'extension binaire défini au 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 dans

lequel , pour est un symbole composé d'une suite de m bits où i 0 1 par un même nombre a appartenant à GF (2 ^m ) , et en ce que

ladite multiplication est effectuée de la manière suivante :

a) on remplit une matrice binaire X de dimension mxL en plaçant les bits χ _ϋ composant chaque symbole Xj le long de la j -ième colonne de ladite matrice X ;

b) on calcule la matrice binaire

de dimension mxL , où M (a) est la matrice binaire de dimensions mxm dont les colonnes respectives contiennent les coordonnées binaires des éléments respectifs en obtenant les lignes de ladite matrice Y au

moyen d'additions binaires de lignes de la matrice X selon des motifs déterminés par les lignes de la matrice ; et

c) on obtient le paquet de données dans lequel

chaque symbole y _{j t} pour est composé des m bits où situés sur la

j -ième colonne de ladite matrice Y .

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 symboles dudit paquet de données P . La présente invention est donc particulièrement avantageuse car, si elle permet une mise en œuvre 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 complètement à la place, de moyens logiciels.

Selon des caractéristiques particulières, lesdites matrices M (a) , pour sont extraites d'une matrice de référence T de dimension m ( )

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 œuvre 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 données codé contenant L≥ 1 symboles constitués d'une suite de m > l 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ù opérant sur le corps d'extension

binaire GF (2™ ) , et

- décodage desdits paquets de données codés de manière à obtenir k paquets de données utiles contenant chacun L symboles constitués d'une suite de m bits.

Ledit procédé de décodage est remarquable en ce que ladite étape de décodage des paquets de données codés comprend au moins une sous-étape de multiplication Q = a P de tous les symboles d'un paquet de données dans lequel _t pour est un symbole composé d'une

suite de m bits où par un même nombre a appartenant à

GF (2 ^m ) , et en ce que ladite multiplication est effectuée de la manière suivante : a) on remplit une matrice binaire X de dimension mxL en plaçant les bits composant chaque symbole X le long de la j -ième colonne de

ladite matrice X ;

b) on calcule la matrice binaire de dimension mxL, où la matrice M (a) est la matrice binaire de dimensions m x m dont les colonnes respectives contiennent les coordonnées binaires des éléments respectifs en obtenant les lignes de ladite matrice Y au moyen d'additions binaires de lignes de la matrice X selon des motifs déterminés par les lignes de la matrice ; et

c) on obtient le paquet de données dans lequel chaque symbole pour est composé des m bits _t où , situés sur la j -ième colonne de ladite matrice Y .

Les avantages offerts par ce procédé de décodage sont essentiellement les mêmes que ceux offerts par le procédé de codage corrélatif succinctement exposé ci-dessus.

Selon des caractéristiques particulières, lesdites matrices pour

sont extraites d'une matrice de référence T de dimension

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 œuvre 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 :

- recevoir k≥l paquets de données utiles, chaque paquet de données utiles contenant L≥ 1 symboles constitués chacun d'une suite de m > l 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 ^m ) défini au 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 = (x,,— ,x _L ) dans lequel X est un symbole composé d'une suite de m bits

χ , où par un même nombre a appartenant à GF (2 ^m ) , des

moyens pour :

- remplir une matrice binaire X de dimension mxL en plaçant les bits x _tj composant chaque symbole Xj le long de la j -ième colonne de ladite matrice

X ;

- calculer la matrice binaire

de dimension mxL, où M (a) est la matrice binaire de dimensions mxm dont les colonnes respectives contiennent les coordonnées binaires des éléments respectifs en obtenant les lignes de ladite matrice Y au

moyen d'additions binaires de lignes de la matrice X selon des motifs déterminés par les lignes de la matrice M ; et

- obtenir le paquet de données dans lequel chaque

symbole y _; , pour j est composé des m bits > , 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 d'une matrice de référence T de dimension

(

L'invention concerne aussi, deuxièmement, un dispositif de décodage de 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≥l symboles constitués d'une suite de m > l 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 h , où l≤k < n , opérant sur le corps d'extension binaire GF (2™ ) , et - décoder lesdits paquets de données codés de manière à obtenir k paquets de données utiles contenant chacun L symboles constitués d'une suite de m bits.

Ledit dispositif de décodage est remarquable en ce qu'il comprend en outre, dans le but d'effectuer une multiplication requise pour le décodage des paquets de données codés, de tous les symboles d'un paquet de données ( ) dans lequel x j l L est un symbole composé d'une

suite de m bits où par un même nombre a appartenant à

, des moyens pour :

- remplir une matrice binaire X de dimension mxL en plaçant les bits x _tj composant chaque symbole X _j le long de la j -ième colonne de ladite matrice

X ;

- calculer la matrice binaire

de dimension mxL, où M (a) est la matrice binaire de dimensions mxm dont les colonnes respectives contiennent les coordonnées binaires des éléments respectifs { } en obtenant les lignes de ladite matrice Y au

moyen d'additions binaires de lignes de la matrice X selon des motifs déterminés par les lignes de la matrice M et

- obtenir le paquet de données Q dans lequel chaque

symbole est composé des m bits

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 d'une matrice de référence T de dimension

Selon un troisième aspect, l'invention concerne :

- un nœud émetteur comprenant un dispositif de codage tel qu'exposé succinctement ci-dessus, et - un nœud récepteur comprenant un dispositif de décodage tel qu'exposé succinctement ci-dessus.

Les avantages offerts par ces dispositifs et ces nœuds 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 d'instructions logicielles et/ou dans le contexte de circuits électroniques.

Selon un quatrième aspect, l'invention concerne un système de transmission de données, comprenant au moins un nœud émetteur tel que décrit succinctement ci-dessus et au moins un nœud récepteur tel que décrit succinctement ci-dessus, mutuellement connectés par un canal sujet à des effacements de paquets.

On notera que dans un tel système de transmission, ledit nœud émetteur et ledit nœud récepteur doivent, pour être mutuellement compatibles, utiliser non seulement le même corps d'extension binaire , 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.

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- 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 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 :

- la figure 1, décrite ci-dessus, représente le codage de n paquets de données {ρ,, Ρ ₂ , ··· , où chaque paquet contient L symboles appartenant à GF (2 ^M ) , sous la forme de L mots de code, où chaque mot de code contient n symboles appartenant à GF (2 ^m ) ,

- la figure 2 représente schématiquement un système de transmission selon l'invention,

- la figure 3 représente schématiquement un nœud émetteur compris dans le système de transmission de la figure 2, selon un mode de réalisation de l'invention,

- la figure 4 représente schématiquement un nœud récepteur compris dans le système de transmission de la figure 2, selon un mode de réalisation de l'invention,

- la figure 5 représente la représentation d'un vecteur de L symboles appartenant à GF (2 ^m ) sous la forme d'une matrice binaire mx L ,

- la figure 6 représente une image binaire « en blocs » d'une matrice de parité d'un code opérant sur G et

- la figure 7 représente une image binaire « aplatie » de la même matrice de parité que pour la figure 6.

On va décrire à présent, en référence à la figure 2, un système R de transmission de données selon un mode de réalisation de l'invention.

Le système R de transmission de données comprend un nœud émetteur 1 , un canal de transmission à effacements de paquets T et au moins un nœud récepteur 2.

Le canal T est adapté pour transmettre des paquets de données émis depuis le nœud émetteur 1 au nœud récepteur 2. Le nœud récepteur 2 comprend des moyens (non-illustrés) pour effacer des paquets présentant des erreurs introduites au cours de la transmission, et des moyens pour générer des informations d'effacement identifiant les paquets effacés par le canal. Ces moyens, connus en eux-mêmes, ne seront pas détaillés dans la suite.

En référence à la figure 3, le nœud émetteur 1 comprend un module mémoire d'entrée 11 , un dispositif de codage de paquets 10 et un module d'émission 12 agencé en sortie du dispositif 10.

Le module mémoire 11 est raccordé à une entrée du nœud émetteur 1 par laquelle sont reçus des paquets de données. Le dispositif de codage de paquets 10 est configuré pour encoder les paquets mémorisés dans la mémoire 11 et délivrer des paquets codés au module d'émission 12.

Le module d'émission 12 est configuré pour générer un signal transportant les données codées et émettre ce signal sur le canal T. En particulier, le module d'émission 12 insère un numéro dans l'en-tête de chaque paquet transmis, ce qui permet de repérer les paquets non reçus, ou reçus dans le désordre.

En référence à la figure 4, le nœud récepteur 2 comprend un module de réception 21 , un dispositif de recouvrement de paquets effacés 20 et un décodeur 25 en sortie du dispositif de recouvrement 20.

Le dispositif 20 de recouvrement de paquets effacés comprend une première unité mémoire 22, une deuxième unité mémoire 23, et un module de correction de paquets 24.

La première unité mémoire 22 est configurée pour recevoir du module de réception 21 des paquets reçus correspondant à des paquets émis par le nœud émetteur.

La deuxième unité mémoire 23, également raccordée au module récepteur 21 , est configurée pour recevoir de celui-ci les informations d'effacement fournies par le canal T.

Le module 24 de correction comprend une unité d'identification 240 et une unité de reconstruction 241.

L'unité d'identification 240 est configurée pour identifier, dans les paquets reçus mémorisés dans la première unité mémoire 22, et à partir des informations d'effacement mémorisées dans la deuxième unité mémoire 23, un groupe de paquets non-effacés intervenant dans des équations de parité, chaque équation de parité faisant intervenir des paquets codés.

L'unité de reconstruction 241 est configurée pour reconstruire des paquets effacés à partir des paquets codés non-effacés stockés dans la première unité mémoire 22 et des informations d'effacement stockées dans la deuxième unité mémoire 23.

Le décodeur 25 est adapté pour recevoir des paquets traités par le dispositif 20 de recouvrement, et émettre en sortie des paquets décodés. On notera que le décodeur 25 peut former un module indépendant du dispositif de recouvrement 20, ou bien faire partie intégrante du dispositif de recouvrement 20.

Dans le cadre de la présente invention, le codage et le décodage sont réalisés dans un corps d'extension binaire , où On entend par là qu'à tout symbole donné composé de m bits on associe

l'élément de , noté _t dont les coordonnées binaires sur une base canonique choisie sont précisément lesdits bits

autrement dit :

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 uniquement au moyen d'additions binaires (on rappelle que l'addition binaire est également appelée « OU exclusif », et notée

Prenons un exemple dans le corps construit à partir du

polynôme primitif où a vérifie l'équation : Le résultat de la multiplication de l'élément de coordonnées binaires par l'élément , de

coordonnées binaires est l'élément dont

les coordonnées binaires sont obtenues comme suit :

20

par définition de la matrice dont les colonnes successives sont constituées par les coordonnées binaires des éléments d e GF(2 ⁴ ) successivement. Pour calculer ces colonnes, on notera, par exemple, que

On procède de la même façon pour Le résultat final est :

Dans le cas général d'un corps pour m quelconque, on calcule :

ou :

• X est le vecteur colonne contenant les m coordonnées binaires { } d

• Y est le vecteur colonne contenant les m coordonnées binaires de y , et

• la matrice est la matrice binaire

mxm dont les colonnes contiennent les coordonnées binaires des éléments

, soit

M

On dira que la matrice est « l'équivalent binaire » de l'élément a pour la

multiplication dans G .

Comme tous les éléments non-nuls de peuvent être écrits sous

la forme a = a ^k pour un certain entier on peut se contenter de

considérer les matrices

associées aux puissances consécutives de a .

On notera que toutes ces matrices peuvent être obtenues en consultant une « grande » matrice binaire

de dimension construite préalablement, dont les colonnes

contiennent les coordonnées de a pour Dans cette matrice T , que l'on appellera « matrice de référence », les dernières colonnes sont une simple copie des premières colonnes. est alors la sous-matrice

obtenue en extrayant les colonnes de la matrice de référence T , ce que l'on notera ainsi :

Par définition, le produit de deux éléments a est égal à de sorte que la matrice associée au

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

De la même manière, la matrice associée à l'inverse d'un élément est qui

est la matrice identité.

Si l'on prend le même exemple sur (construit à partir du

polynôme primitif la matrice de référence T est donnée

par :

de sorte que, par exemple :

On vérifie facilement, par exemple, que le produit des matrices binaires est bien égal à comme prévu.

En poursuivant le même exemple, on trouve :

de sorte que M ou encore [

Comme autre exemple, la multiplication par a dans

est donnée par le produit matriciel :

On notera que cette expression n'utilise que des XORs des coordonnées binaires x. e {0,1} de l'élément x .

On peut ainsi commodément effectuer la multiplication de tout élément x de par tout élément a 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 .

On va expliquer à présent comment on peut utiliser cette méthode pour effectuer la multiplication par tout élément au niveau des paquets.

Le produit matriciel de l'équation (1) peut être aisément parallélisé lorsque chaque x _{ est un vecteur binaire de longueur L . Par exemple, la multiplication par un élément a dans devient :

où, avantageusement, toutes les opérations sont effectuées dans GF(2) .

On utilisera ci-après la notation pour dénoter la

ligne n° i d'une matrice binaire X de dimension mxL ; le produit matriciel ci- dessus peut alors être commodément vu comme mettant en œuvre des XORs de ces lignes *(/ ^' ,:). Par exemple, la multiplication par présentée ci-

dessus peut être commodément écrite sous la forme :

Les considérations ci-dessus expliquent comment on peut, au cours du codage ou du décodage dans un corps de Galois où défini au

moyen d'un polynôme primitif prédéterminé, calculer un paquet , où le

nombre a appartient à et P est un paquet de données ( )

dans lequel pour avec L > 1 , est un symbole composé d'une

suite de m bits x

Selon le présent mode de réalisation, on met en œuvre les sous-étapes suivantes.

a) On remplit une matrice binaire de dimension en plaçant

les bits x _v composant chaque symbole le long de la j -ième colonne, comme

illustré schématiquement sur la figure 5. On désigne par la i -ème ligne, où de cette matrice X . Autrement dit, si l'on regarde le paquet P

comme une ligne de bits numérotés de 1 à mx L , la ligne *(*,:) est définie par :

b) On calcule la matrice binaire Y , de dimension mxL , au moyen du produit matriciel :

Y

où la matrice M (a) est l'équivalent binaire, défini ci-dessus, de l'élément a . 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 dans lequel

chaque symbole pour est composé des bits où 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 quelle matrice A dont les éléments a _{t j} appartiennent à G Î ) .

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 ( ) par leurs équivalents binaires définis ci- dessus. Cela est notamment le cas pour la matrice de parité d'un code linéaire.

Considérons par exemple un code de Reed-Solomon défini sur

(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 : On obtient une image binaire « en blocs » de la matrice H en remplaçant chaque élément a ^k par son équivalent binaire M (or*) de dimension 4x4, 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.

La forme de la figure 6 est plus adaptée au procédé selon l'invention, chaque opération a _{{ j} x _i dans l'arithmétique de GF(2 ^m ) étant remplacée par un produit d'une matrice binaire mxm par une matrice binaire mx L lorsque l'on parallélise les traitements sur des paquets de L symboles de GF(2 ^m ).

L'invention peut être mise en œuvre au sein des nœuds, par exemple un nœud émetteur ou un nœud 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 nœud de réseau. C'est pourquoi, comme 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 pour la mise en œuvre 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 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 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.

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 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 é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 ê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.