Brevet FR3013924A1 — publié le 20150529

Procédé et dispositif de codage de paquets de données numériques, et procédé et dispositif de correction d'effacements DOMAINE GENERAL L'invention se rapporte au domaine des codes correcteurs d'effacements. L'invention concerne plus particulièrement un procédé et un dispositif de codage de paquets de données numériques, ainsi qu'un procédé et un dispositif de correction des éventuels effacements affectant 10 les paquets codés suite à leur transmission dans un canal. ETAT DE L'ART On connait de l'état de l'art de nombreux procédés de transmission de données numériques identiques vers un nombre important de 15 récepteurs dans un canal sujet à des pertes ou des « effacements » de paquets. Dans le cas d'une diffusion de type « broadcast » ou « multicast » sur Internet, des pertes de paquets sont souvent causées par des congestions au niveau de routeurs. Dans le cas d'une diffusion de type « broadcast » ou « multicast » sur canaux radio (MBMS, eMBMS), 20 des pertes de paquets peuvent être dues à une mauvaise qualité de certains liens radio, provoquant des erreurs de transmission que le schéma de codage correcteur de couche physique ne peut corriger : les données correspondantes sont alors marquées comme effacées. Dans les deux cas, les différentes routes de transmission entre un émetteur et 25 plusieurs destinataires présentent des qualités de lien différentes et subissent des pertes de paquets différentes après émission de données par l'émetteur. Un schéma classique de retransmission des données non reçues, réalisée destinataire par destinataire, serait peu efficace car impliquerait 30 d'une part autant de voies de retour dans le canal qu'il y a de récepteurs, et d'autre part la retransmission des mêmes paquets à différents 3013 924 2 utilisateurs, provoquant un sur-débit conséquent dans le canal, et des délais de transmissions rallongés. Afin d'éviter la mise en place de telles voies de retour, il a été proposé d'introduire de la redondance dans les données transmises de 5 sorte que tout utilisateur puisse reconstituer les paquets qu'ils n'a pas reçus grâce à ceux qu'il a reçus, sans voie de retour ni retransmission. Cette introduction de redondance est typiquement mise en oeuvre au moyen d'un code correcteur d'effacements. Des codes correcteurs pour corriger des effacements sont connus 10 depuis longtemps, par exemple les codes de « Reed-Solomon », qui présentent cependant des contraintes : en effet, ces codes ont des longueurs peu flexibles, de la forme n = 2m -1, 2 , et font intervenir une arithmétique dans des corps d'extension GF(2m ), arithmétique qui devient difficile à mettre en oeuvre (du moins sous forme logicielle) pour 15 des valeurs de m dépassant 10, c'est-à-dire des longueurs de code n>_1023. Pour éviter les contraintes des codes de Reed-Solomon, il a été proposé une classe de procédés de codage de paquets (dénommés « procédés selon Arai » ci-après) fondés sur des codes convolutifs 20 opérant sur des paquets de données numériques (cf. M. Arai, A. Yamamoto, A. Yamaguchi, S. Fukumoto et K. Iwasak, « Analysis of using convolutional codes to recover packet losses over burst erasure channels », actes du « 2001 Pacific Rim international symposium on dependable computing (PRDC '01) », pages 258 à 265, et M. Arai, 25 S. Fukumoto et K. Iwasaki, « Extension of coefficients for (n,k,m) convolutional-code-based packet loss recovery », Computers and Mathematics with Applications, vol. 51, 2006, pages 247 à 256). Dans les procédés selon Arai, on transmet des données sous la forme de groupes de n paquets, chaque groupe 30 Vi = (V/ ,121,2 , - - - , Vi,n) contenant, d'une part, k paquets d'information (on a donc un codage systématique), et d'autre part (n-k) paquets redondants, ce qui est écrit sous la forme Vi = ; Pi = (ui,1 Ui,k où les Iiii sont les paquets d'information et les pii sont des paquets 5 redondants, obtenus de la manière suivante : (i) + g (i) (i) P1,1 = g 11 u11 - 21 1/1-1,1 + + gm+11 Ui-m,1 + (/) (/) + g(i) 1, + + g1,2 ui,2 g2,2 111-1,2 ,-,m+1,2 -i-m,2 + - - - 0.(l) gl,k ui,k + g2 - - k ui-1,k + - + 6 m+1,k ui-m,k Cette forme fait apparaitre les composantes des vecteurs 1.1; (première colonne), Ui_1 (deuxième colonne), et ainsi de suite jusqu'à 1.1i-m. Si on écrit ces équations pour j=1, 2, ... , n-k, l'équation ci-dessus prend la forme 10 matricielle suivante P, = G(1) U +G(2) U1-1+ . - . + G(m+1) U i-m où les G(t) sont des matrices binaires de dimensions (n-k) par k. Cependant, ces procédés selon Arai présentent plusieurs inconvénients. 15 Un premier inconvénient est qu'il requiert que les effacements se présentent sous forme d'une salve regroupée devant être impérativement précédée et suivie de ce que les auteurs appellent un intervalle de garde (« guard space » en anglais), c'est-à-dire une succession de paquets n'ayant subi aucun effacement sur une longueur supérieure à la mémoire 20 m du codeur. Cette contrainte sur l'intervalle de garde est rendue nécessaire notamment par l'utilisation de matrices génératrices dimensionnées pour corriger des salves de longueur prédéterminée. Par ailleurs, dans ces procédés selon Arai, la récupération des paquets effacés se fait par la résolution d'un système linéaire d'équations dont les inconnues sont les paquets effacés. Une telle résolution est toutefois complexe à mettre en oeuvre. Enfin, ces procédés selon Arai mettent en oeuvre un codage systématique, ce qui présente l'avantage d'obtenir directement (c'est-à- dire, sans opération de décodage) les paquets d'information suite au recouvrement des paquets effacés. Mais comme le codage systématique consiste par définition à transmettre dans le canal des paquets d'entrée en clair, les procédés selon Arai présentent l'inconvénient d'être inadaptés à la transmission d'informations confidentielles. PRESENTATION DE L'INVENTION Un but de l'invention est de mettre en oeuvre un codage de paquets et une correction d'effacements dans un canal sujet à des pertes ou effacements de paquets, qui soient chacun simples à mettre en oeuvre. Un autre but de l'invention est de pouvoir recouvrer des paquets codés effacés sans avoir à décoder au préalable un quelconque paquet codé. Selon un premier aspect, il est donc proposé un procédé de codage de paquets de données numériques, comprenant les étapes suivantes : - la mémorisation de N paquets d'entrée (P1, ...,PN), - la production de (N + K1) premiers paquets codés (A1, ...,AN+K3 définis, pour = 1, N + K1 , par Am = El(11-0 G1,113n1-1 où G1 est un premier polynôme générateur de degré K1, G1,, est le coefficient du terme de puissance i dudit premier polynôme générateur G1, et les paquets d'entrée d'indice inférieur à 1 ou supérieur à N sont identiquement nuls, la production de (N + K2) premiers paquets codés (B1, ...,BN+K2) définis, pour n = 1, N + K2, par Bn = 0 G 2,,Pn_ , où G2 est un second polynôme générateur de degré K2, G2 J est le coefficient du terme de puissance j dudit second polynôme générateur G2, et les paquets d'entrée d'indice inférieur à 1 ou supérieur à N sont identiquement nuls, et où les polynômes générateurs G1 et G2 sont premiers entre eux. Il est entendu que les étapes dudit procédé de codage ne se déroulent pas nécessairement dans l'ordre dans lequel elles sont présentées ci-dessus. On notera que la présente invention n'impose aucune contrainte sur 10 la nature des données numériques composant les paquets. Il peut s'agir par exemple d'éléments binaires (« bits »), ou d'éléments d'un corps d'extension GF (21n), avec m supérieur ou égal à 2. On notera également que, contrairement aux procédés selon Arai, le procédé de codage selon l'invention n'impose nullement le recours à un 15 codage systématique (même si l'invention n'exclut pas de choisir, comme cas particulier, soit G1 = 1, soit G2 = 1), et n'impose donc pas de transmettre dans le canal des paquets d'entrée en clair lorsque le contexte ne s'y prête pas. Comme expliqué en détail ci-dessous, le fait que les deux 20 polynômes générateurs G1 et G2 servant au codage soient premiers entre eux permet de décoder très simplement les paquets codés (suite au recouvrement des paquets codés effacés). Selon un deuxième aspect, il est aussi proposé un procédé de 25 correction d'effacements, ledit procédé comprenant les étapes de : mémorisation de (N K) premiers paquets à traiter (A1, , AN+K) et de (N K) deuxièmes paquets à traiter (B1 ...,BN+K), chaque paquet à traiter étant un paquet non-effacé ou un paquet nul représentatif d'un paquet effacé, 30 calcul de (N + 2K) syndromes (S1, ...,SN+2K) définis, pour n = 1, ...,N + 2K, par Sn = G2,jAn-i Gl,iBn-i i=0 i=0 où les G1,, sont K premiers coefficients prédéterminés et les G2,1 sont K deuxièmes coefficients prédéterminés, et où les paquets Am et Bm sont identiquement nuls pour m N K, recouvrement éventuel de paquets effacés à partir des syndromes, de telle sorte que, lorsque le calcul d'un syndrome fait intervenir un unique paquet nul représentatif d'un paquet effacé, alors le paquet recouvré correspondant à ce paquet effacé est égal à ce syndrome. Le procédé de correction d'effacements selon le deuxième aspect comprend une étape de recouvrement de paquets codés effacés, qui peut 10 être mise en oeuvre indépendamment du décodage des données reçues. Aucun paquet d'entrée n'a en effet à être généré pour reconstruire un quelconque paquet codé ayant été effacé suite à sa transmission dans le canal. Le procédé de correction d'effacements selon le deuxième aspect 15 fonctionne par ailleurs sans aucune contrainte algorithmique particulière sur le nombre de paquets codés reçus. Il autorise donc une grande flexibilité sur le nombre N de paquets d'entrée codés collectivement. On voit donc que le procédé de codage selon le premier aspect et le procédé de correction d'effacements selon le deuxième aspect sont très 20 flexibles en ce qu'ils peuvent s'adapter à un grand nombre de contextes de mise en oeuvre différents. Il est proposé selon un troisième aspect un dispositif de codage de paquets de données numériques comprenant : 25 un module mémoire adapté pour mémoriser N paquets d'entrée (P1, PN), et un module de traitement de paquets d'entrée, ledit module de traitement de paquets comprenant des première et deuxième unités de codage convolutif telles que : la première unité de codage convolutif est configurée pour produire (N + K1) premiers paquets codés (A1, ...,AN+K3 définis, pour m = 1, N + K1i par Am = Exi'o G1,ipm-i où G1 est un premier polynôme générateur de degré K1, G1,, est le coefficient du terme de puissance i dudit premier polynôme générateur G1, et les paquets d'entrée d'indice inférieur à 1 ou supérieur à N sont nuls, la deuxième unité de codage convolutif est configurée pour produire (N + K2) premiers paquets codés (B1, ...,BN+K2) définis, pour n = 1, N + K2, par Bn = 1( j0 G 2,,Pn_ où G2 est un second polynôme générateur de degré K2, G2,1 est le coefficient du terme de puissance j dudit second polynôme générateur G2, et les paquets d'entrée d'indice inférieur à 1 ou supérieur à N sont nuls, et les polynômes générateurs G1 et G2 sont premiers entre eux. Selon un quatrième aspect, il est en outre proposé un dispositif de 20 correction d'effacements, comprenant : un module mémoire adapté pour mémoriser (N + K) premiers paquets à traiter (A1, ...,AN+K) et (N + K) deuxièmes paquets à traiter (B1...,BN+K), chaque paquet à traiter étant un paquet non-effacé ou un paquet nul représentatif d'un paquet effacé, 25 un module de traitement de paquets mémorisés adapté pour : o calculer (N + 2K) syndromes (S1, ...,SN+2K) définis, pour n= 1, ...,N + 2K , par K Sn = G2 iAn_i + G iBn-i i=0 i=0 où les G1,, sont K premiers coefficients prédéterminés et les G2,1 sont K deuxièmes coefficients prédéterminés, et où les paquets Am et Bm sont identiquement nuls pour m N + K, et o lorsque le calcul d'un syndrome fait intervenir un unique paquet nul représentatif d'un paquet effacé, définir un paquet recouvré correspondant à ce paquet effacé comme étant égal à ce syndrome. Il est également proposé selon un cinquième aspect un système de transmission de données numériques comprenant au moins un noeud émetteur et au moins un noeud récepteur mutuellement connectés par un canal apte à effacer des paquets erronés, ledit noeud émetteur comprenant un dispositif de codage selon le troisième aspect, et ledit noeud récepteur comprenant un dispositif de correction d'effacements selon le quatrième aspect. Il est également proposé selon un sixième aspect 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, caractérisé en ce qu'il comprend des instructions pour l'exécution des étapes d'un procédé selon le premier et/ou le deuxième aspect, lorsqu'il est exécuté sur un ordinateur Selon un septième aspect, il est aussi proposé un moyen de stockage de données inamovible, ou partiellement ou totalement amovible, comportant des instructions de code de programme informatique pour l'exécution des étapes d'un procédé selon le premier et/ou le deuxième aspect. DESCRIPTION DES FIGURES D'autres caractéristiques, buts et avantages de l'invention 30 ressortiront de la description qui suit, qui est purement illustrative et non limitative, et qui doit être lue en regard des dessins annexés sur lesquels : La figure 1 représente schématiquement un système de transmission selon l'invention. La figure 2 représente schématiquement un noeud émetteur compris dans le système de transmission de la figure 1, selon un mode de réalisation de l'invention. La figure 3 représente schématiquement un noeud récepteur compris dans le système de transmission de la figure 1, selon un mode de réalisation de l'invention. La figure 4 est un organigramme comprenant les étapes d'un procédé de codage de paquets selon un mode de réalisation de l'invention. La figure 5 est un organigramme comprenant les étapes d'un procédé de traitement de paquets reçus depuis un canal selon un mode de réalisation de l'invention. La figure 6 est un organigramme comprenant les étapes d'un procédé de recouvrement de paquets effacés selon un mode de réalisation de l'invention. La figure 7 représente un diagramme fonctionnel d'un codage convolutif de paquets selon un mode de réalisation de l'invention. La figure 8 est un graphe de Tanner associé au code convolutif de la figure 7. La figure 9 représente un schéma d'un décodage du code convolutif de la figure 7. Chacune des figures 10 à 12 représente respectivement des courbes de performances associée à un procédé de recouvrement de paquets effacés, selon une variante respective de l'invention. Sur l'ensemble des figures, les éléments similaires portent des références identiques. DESCRIPTION DETAILLEE DE L'INVENTION 3013 92 4 10 En référence à la figure 1, un système R de transmission de données numériques comprend un noeud émetteur 1, un canal de transmission à effacements de paquets T et au moins un noeud récepteur 2. 5 Le canal T est adapté pour transmettre des paquets de données émis depuis le noeud émetteur 1 à chaque noeud récepteur 2. Le noeud 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 10 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 2, le noeud émetteur 1 comprend un dispositif de codage de paquets 10 et un module d'émission 16 agencé en sortie du dispositif 10. 15 Dans le présent mode de réalisation, le dispositif 10 est configuré pour mettre en oeuvre un codage convolutif selon l'invention. Il comprend un module mémoire d'entrée 11, deux unités de convolution 12 et 13, et un module de multiplexage 14. Le module mémoire 11 est raccordé à une entrée du noeud 20 émetteur 1 par laquelle sont reçus des paquets de données. Les deux unités de convolution 12, 13 sont configurées pour encoder des données en paquets mémorisées dans la mémoire 11 et délivrer des paquets codés au module de multiplexage 14. Le module de multiplexage 14 est par ailleurs configuré pour 25 délivrer des données codées au module d'émission 16, lequel est configuré pour générer un signal transportant les données codées et émettre ce signal sur le canal T. Optionnellement, le module de multiplexage peut en outre entrelacer ces données codées, afin de remédier aux erreurs de transmission se produisant par bouffées, car ce 30 type d'erreurs de transmission provoque des bouffées de paquets effacés au niveau du récepteur. En référence à la figure 3, le noeud récepteur 2 comprend un module de réception 21, un dispositif de recouvrement de paquets effacés 20 et un décodeur 26 en sortie du dispositif de recouvrement 20. Le dispositif 20 de recouvrement de paquets effacés comprend une 5 unité mémoire 22, une unité mémoire 23, et un module de correction de paquets 24. L'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 noeud émetteur. 10 L'unité mémoire 23, également raccordée au module récepteur 21, est configurée pour recevoir de celui-ci les informations d'effacement générées par le canal T. Le module 24 de correction comprend une unité de calcul de syndromes 240, un compteur 241, et une unité de reconstruction 244. 15 L'unité de calcul des syndromes 240 est configurée pour identifier, dans les paquets reçus et à partir des informations d'effacement mémorisées dans la deuxième unité mémoire, un groupe de paquets non-effacés intervenant dans des équations de parité, chaque équation de parité faisant intervenir des paquets codés mémorisés dans l'unité 20 mémoire 22. Le compteur 241 est configuré pour compter, à partir des informations d'effacement stockées dans l'unité mémoire 23, un nombre de paquets effacés intervenant dans une équation de parité associée à une paire de paquets codés stockée dans l'unité mémoire 22. 25 L'unité de reconstruction 244 est configurée pour reconstruire un paquet effacé par une convolution opérée sur les paquets codés non-effacés identifiés qui interviennent dans l'équation de parité associée à une paire mémorisée dans l'unité mémoire 22, si le nombre de paquets effacés décompté par le compteur 241 pour ladite paire est égal à un. 30 L'unité de reconstruction 244 est par ailleurs configurée pour accéder en écriture aux unités mémoire 22 et 23. Le décodeur 26 est adapté pour recevoir des paquets traités par le dispositif 20 de recouvrement. Le décodeur 26 peut former un module indépendant du dispositif 20 ou bien faire partie intégrante du dispositif 20 de recouvrement. Codage et émission En référence à la figure 4, un procédé de codage correcteur d'effacement comprend les étapes suivantes. Dans une étape 101, des données sont mémorisées par le module mémoire 11 sous la forme d'une suite de N paquets d'entrée P = (P1, ..., PN) à traiter, présentant tous une même longueur, c'est à dire le même nombre de données (bits ou autres) du paquet. A partir de cette suite P, on produit (N + K1) premiers paquets codés A, et (N + K2) deuxièmes paquets codés Bn. Dans une étape 102, les premiers paquets codés A, sont produits par le module 12 par la mise en oeuvre d'une première convolution opérée sur un premier ensemble de paquets d'entrée présent dans la suite. Dans une étape 103, les deuxièmes paquets codés Bn sont produits par le module 13 par la mise en oeuvre d'une deuxième convolution 20 opérée sur un deuxième ensemble de paquets d'entrée présent dans la suite. Chaque premier paquet codé A, et chaque deuxième paquet codé Bn sont donc de longueur égale à celle des paquets d'entrée. La convolution mise en oeuvre par l'unité de codage 12 est définie 25 par un premier polynôme générateur G1 de degré K1.. Similairement, la deuxième convolution mise en oeuvre par l'unité de codage 13 est définie par un deuxième polynôme générateur G2 de degré K2. On désigne par K le maximum des degrés K1 et K2 respectifs du premier et du deuxième polynôme générateur G1 et G2. Dans le mode de réalisation décrit ci-dessous, on supposera que les degrés K1 et K2 sont égaux (bien que des polynômes G1 et G2 de degrés différents puissent être utilisés, comme il sera présenté plus loin). Dans une étape 104, (N + K) premiers paquets codés et (N + K) 5 deuxièmes paquets codés sont mémorisés par le module de multiplexage 14 de façon à générer une suite C de paires (A,-'Bn) de premiers et deuxièmes paquets codés, de façon à pouvoir transmettre l'ensemble des paquets codées sur une unique route de communication comprise dans le canal T. Le module de multiplexage 14 peut par exemple piloter 10 l'exécution des unités de convolution 12 et 13 de façon à recevoir de ces deux unités de convolutions des premiers et deuxièmes paquets codés alternativement. Optionnellement, comme expliqué ci-dessus, le module de multiplexage 14 peut en outre entrelacer les données codées. La suite C de paires codées ainsi obtenue comprend par exemple 15 les paquets Ci suivants : C1 = A'C2=B'C3=A'C4 B2 - - - C2/-1 A C2 =B --- C = 2 (N+K )-1 = AN+K,C 2(N+K) BN+K Dans une étape 106, la suite C de paires codées est émise par le module d'émission du noeud émetteur 1 dans le canal de transmission T. Au cours de leur transmission dans le canal T, d'éventuelles erreurs 20 peuvent corrompre le contenu de certains paquets codés de la suite C de paires émise par le noeud émetteur 1. Lorsque le décodeur de la couche physique (chargé de corriger les erreurs dues à la transmission) n'arrive pas à corriger totalement ces erreurs, il donne une information qui permet de marquer le paquet comme effacé. 25 Les « informations d'effacement » permettent ainsi d'identifier l'ensemble des paquets effacés suite à leur passage dans le canal T. Réception, recouvrement des paquets codés effacés, et décodage En référence à la figure 5, le module de réception 21 du noeud récepteur 2 reçoit du canal T des données au cours d'une étape 201. Les données reçues comprennent des paquets reçus correspondant à la suite C de 2(N + K) paquets codés émis par le noeud 5 émetteur 1, et les informations d'effacement décrites ci-dessus. Ensuite, au cours de cette étape 201, le module de réception 21 met en oeuvre un démultiplexage des données reçues (et optionnellement désentrelace ces données si elles ont été entrelacées avant d'être émises par le noeud émetteur 1), et marque chacun des 2(N + K) paquets codés émis comme 10 présent dans les paquets reçus, ou bien manquant dans les paquets reçus. On admettra en effet dans ce qui suit que chacune des (N + K) paires de la suite émise par le noeud émetteur 1 est référencée dans les informations d'effacements reçues par le noeud récepteur 2. 15 Dans une étape 202, les paquets reçus dans l'unité mémoire 21, et dans une étape 202, les informations d'effacement sont mémorisées dans l'unité mémoire 23. Ces deux étapes de mémorisation 202, 203 peuvent être exécutées séquentiellement, ou bien simultanément de façon raccourcir le temps de traitement de ces données. 20 Les informations d'effacement et les paquets reçus sont ensuite traités par le dispositif 24 au moyen d'un procédé de recouvrement de paquets effacés représenté par une étape 204 sur la figure 5. Enfin, dans une étape 206, les paquets codés correctement transmis dans le canal T et les paquets recouvrés peuvent être décodés par le décodeur 26 (donc, 25 de façon indépendante du recouvrement de paquets effacés opéré au cours de l'étape 204). En référence à la figure 6, le procédé de recouvrement de paquets effacés 204 comprend les étapes suivantes mises en oeuvre pour les 2(N + K) premiers et deuxièmes paquets codés mémorisés au cours de 30 l'étape 203. Dans une étape 2040, l'unité de calcul des syndromes 240 calcule (N + 2K) syndromes à partir des paquets mémorisés. Chaque syndrome Si, d'indice n est le résultat de l'équation de parité suivante : Sn = G2 iAn_i Gli13,_i i=0 i=0 Dans une étape 2041, le compteur 241 compte, à partir des informations d'effacement, un nombre de paquets effacés intervenant dans chaque équation de parité ; dans ce qui suit, ce nombre compté sera dénommé « index » de l'équation de parité, ou index du syndrome résultant de cette équation de parité. Dans une étape 2042, la valeur de chacun des (N + 2K) index est 10 examinée. Si l'index In est égal à 0, cela veut dire qu'aucun paquet effacé n'intervient dans l'équation de parité donnant comme résultat le syndrome Sn ; aucun recouvrement n'est nécessaire. Si l'index In est égal à 1, alors un unique paquet nul représentatif 15 d'un paquet codé effacé intervient dans l'équation de parité. Dans ce cas, dans une étape 2044, la valeur du syndrome Sn est identifiée comme étant la valeur du paquet effacé. Si l'index In est différent de 1, l'index suivant /72+1 est examiné. Les étapes de calcul des syndromes 2040, de calcul des index 20 2041 et de recouvrement 2044 peuvent être répétées de façon à corriger un maximum d'effacements dans les paquets reçus correspondant à la suite de paires émise. Mode de réalisation à base d'opération XOR 25 Dans un mode de réalisation, chaque convolution opérée au cours des étapes 103 et 104 est une addition bit à bit modulo 2 (XOR) opéré sur les paquets d'entrée correspondants, et chaque convolution opérée par le au cours de l'étape de reconstruction 2044 est également une addition bit à bit modulo 2 (XOR) opéré sur les paquets codés correspondants. Dans le cas général d'un code de polynômes générateurs Gi(D) = = 1,2 , dont les coefficients Gii valent 0 ou 1, le premier paquet codé et le deuxième paquet codé correspondants sont calculés par les opérations de 5 convolution suivantes dans les unités de convolution 12 et 13 : de sorte que : Par conséquent, pour toute valeur de n, les paquets codés sont associés 10 à un syndrome Sn et obéissent à l'équation de parité suivante : K K Sn = G2,/ An-i + -0 . i=0 i=0 Ainsi, le groupe de paquets codés non effacés intervenant dans l'équation de parité associée à l'indice n comprend un premier ensemble comprenant au moins un premier paquet codé Ai retardé(s) ou non par 15 rapport au paquet An et un deuxième ensemble comprenant au moins un deuxième paquet codé Bi retardé(s) ou non par rapport au paquet Bn. Ledit premier ensemble de paquets codés est associé au deuxième polynôme générateur G2, tandis que ledit deuxième ensemble de paquets codés est associé au premier polynôme générateur G1. 20 Par convention, dans l'équation ci-dessus relative au syndrome Sn d'indice n, les paquets Am, B, dont les indices vérifient m (N+K) sont nuls. À titre d'exemple, on prendra dans la suite les polynômes générateurs suivants G1(D) =1+ D + D2 et G2 (D) =1+ D2 . Le premier paquet et le deuxième paquet d'indice n codés d'après ces polynômes sont alors définis comme suit : An = Pne Pn-1e Pn-2 Bn = Pne Pn-2 où le symbole désigne l'addition modulo 2 des bits de même position des paquets intervenant dans les expressions des paquets An, Bn. Le schéma de codage correspondant à cet exemple est illustré en figure 7. L'équation de parité d'indice n est alors la suivante : An e An_2 e Bne Bu_ie Bu_2 = 0 pour toute valeur de n. En effet, en considérant les termes successifs suivants : An = Pn 0 Pn 1 O Pn-2 An 2 Pn-2 O Pn-3 O Pn-4 Bn = Pn Pn-2 Bn-1 Pn-1 Pn-3 Bn-2 Pn-2 Pn-4 on vérifie aisément que : An e An_2$ Bne Bn_iO Bn_2 = 0 Chaque paquet d'entrée P apparaît un nombre pair de fois dans la somme An 42_2 O+ BnBn_1 Bn-2 qui est donc nulle (un paquet dont tous les bits sont égaux à 0). Dans ce qui suit, le symbole e est remplacé par le symbole 20 classique de l'addition (+) étant entendu qu'il s'agit de l'addition du corps à deux éléments GF(2). Cette suite d'équations de parité peut être représentée graphiquement sous la forme d'un graphe de Tanner, qui est un graphe biparti avec deux catégories de sommets : des noeuds représentants les paquets codés, et des noeuds représentants les syndromes (équations de parité), comme illustré sur la figure 8. Dans ce graphe, tous les noeuds Sn ont le même degré, c'est-à-dire le même nombre de branches incidentes, égal à : d =1(G1, + G2 qui n'est autre que la somme des nombres de coefficients non nuls des 10 deux polynômes générateurs G1(D) et G2(D). Les noeuds du graphe de Tanner qui correspondent aux paquets codés Ar, sont de degré db = Gi,/ et ceux correspondants aux paquets i>0 Bn sont de degré db = , les deux sommes étant calculées dans les entiers naturels (ce sont simplement les nombres de coefficients non nuls 15 de chacun des deux polynômes générateurs). Chaque paquet An intervient dans les syndromes Sn±'G20 et de la même manière chaque paquet Bn est relié aux syndromes S n+1 iP1,1 . Les équations de parité permettent de recouvrer des paquets 20 effacés ; en effet, si un seul paquet intervenant dans une équation de parité donnée est effacé, on peut le recalculer comme la somme (XOR) des autres paquets non effacés intervenant dans la même équation de parité. Le procédé de recouvrement de paquets effacés opère sur le 25 graphe de Tanner introduit plus haut. On introduit l'index d'une équation de parité comme étant égal au nombre de paquets effacés intervenant dans cette équation de parité. Le cas intéressant est bien entendu celui d'une équation de parité d'index égal à 1 car le paquet effacé est alors calculable comme la somme (XOR) des autres paquets (non effacés) qui interviennent dans cette équation de parité. Si, dans l'exemple qui précède, le paquet An est le seul paquet effacé dans l'équation de parité Sn = An O+ An_2 Bn C Bn_1^0 Bn_2 = 0 , on peut le reconstruire selon An = An 2GB'GB,,,1GBn . Une fois qu'un paquet est recouvré, l'index des équations de parité dans lesquelles il était impliqué est décrémenté d'une unité (le paquet n'est plus considéré comme effacé), et on cherche une nouvelle équation de parité d'index 10 égal à 1. On va montrer ci-dessous qu'il est possible d'éviter de mettre oeuvre le décodage des bits contenus dans les paquets An, Bn, pour remonter aux paquets d'entrée Pn. Selon la présente invention, les polynômes générateurs G1 et G2 15 sont premiers entre eux et vérifient donc l'équation de Bezout, c'est-à-dire qu'il existe deux polynômes U (D) ,V (D) tels que U (D) G i(D) + V (D) G 2 (D) =1 (l'arithmétique étant, dans le présent mode de réalisation, celle du corps à deux éléments, c'est-à-dire modulo 2). Par exemple, les deux polynômes Gl(D) =1 + D + D2 et G2 (D) =1 + D2 20 déjà pris en exemple respectent bien l'équation de Bezout, puisque D xG1(D)+ (1 + D)xG2(D) =1 , i.e. U(D)=D et V(D)=1 +D. Recouvrement de paquets effacés à base d'opération XOR Dans le mode de réalisation illustré en figure 6, le recouvrement de 25 paquets effacés peut être mis en oeuvre en deux phases : une phase d'initialisation, et une phase de bouclage, qui vont maintenant être détaillées dans le cas non-limitatif où l'opérateur XOR est choisi pour générer les premiers paquets codés et les deuxièmes paquets codés par convolution. A titre préliminaire, on suppose que les 2(N+K) paquets suivants ont mémorisés au cours de l'étape 203 de mémorisation : Cl= A1,C2=B1 ,C3= A2 C4 B2 - - - C21-1 A, C2, = B, - - - , C2 (N+K)-1 AN+K'C 2(N+K) B N+K Les paquets Ci sont supposés reçus sans erreur ou bien non reçus 5 (effacés). Les informations d'effacement sont un vecteur E = (El, E2, ...) tel que : 11, si le paquet i est effacé , i = 1,2, - - - ,2(N + K) 0, si le paquet i est reçu Avec ces notations, la suite des paquets mémorisés dans l'unité mémoire 10 23 est C0;, si le paquet i est reçu si le paquet i est effacé , i = 1,2, - - - ,2(N + K) L'unité mémoire 23 contient donc des paquets non effacés et des paquets nuls représentatifs chacun d'un paquet effacé. On définit également les deux ensembles 11= {iGt } et 15 I 2 =}i G2 =1}. Pour les polynômes générateurs G1 et G2 pris en exemple plus haut, on a I 1 = I 2 = {0,4. Phase d'Initialisation Au cours d'une étape préliminaire, les paquets reçus et les 20 informations d'effacements peuvent faire l'objet d'un démultiplexage mis en oeuvre par le module 21, de façon à séparer les paquets reçus relatifs aux premiers paquets codés et les paquets reçus relatifs aux deuxièmes paquets codés. Cette étape peut être mise en oeuvre par un passage série/parallèle des paquets Ri pour former les deux suites de (N+K) paquets Al =R1,A2 =R3,---, Ai = R21-1,--- et B1 = R2 B2 = R4, = R2/ De la même manière, le vecteur E = (E1,E2,- -) des effacements est converti en deux vecteurs stockant respectivement les informations d'effacements sur les premiers paquets codés A et sur les deuxièmes paquets codés Bi, c'est-à-dire : (a) = 2i-1 et Ei(b) Par « informations d'effacements », on veut dire que tous les paquets transmis sont numérotés (ou ont un identifiant), ce qui permet de savoir quels sont les paquets qui ont été perdus ou effacés (leur numéro 10 est manquant au niveau de la réception). L'étape de calcul des syndromes 2040 est ensuite mise en oeuvre pour les (N + 2K) syndromes par l'unité de calcul de syndromes 240. Au cours de cette étape, est initialisé un vecteur des syndromes S = (Si , S2 , S'2K chaque syndrome étant obtenu selon la 15 formule : Sn =1G21 An_+1G1,Bn, n = 1,2,--- i=o i=o Chaque premier paquet du premier ensemble de paquets codés intervenant dans cette équation de parité est multiplié par un coefficient non-nul du deuxième polynôme générateur G2, et chaque deuxième 20 paquet du deuxième ensemble de paquets codés intervenant dans cette équation de parité est multiplié par un coefficient non-nul du premier polynôme générateur G1. Si tous les paquets Ri était reçus, chaque syndrome Si, serait constitué de bits nuls (par définition du syndrome) ; la présence 25 d'effacements fait que certains Si, sont non nuls. L'étape de calcul des index 2041 est mise en oeuvre par le compteur 241 pour les mêmes (N + 2K) syndromes, de façon à initialiser 3013 924 22 un vecteur d'index I = (I1,/2,'''IN+2K), chaque index comptant le nombre de paquets effacés intervenant dans l'équation de parité associée au syndrome Sn. Les index (Il, , N +20 sont définis, pour n = 1, N 2K, par : G2 iE(a) (b) In = G E n_i i=0 n i=i3 = G 2 iE(a) G (b) iEn_i 1E12 " n " 5(a) où En_i est l'information d'effacement associée au premier paquet mémorisé d'indice i et E)i est l'information d'effacement associée au n- deuxième paquet mémorisé d'indice i. Phase itérative La phase itérative comporte une succession d'itérations, chaque itération étant réalisée après vérification d'une condition de bouclage 2042 évaluant s'il reste des paquets effacés pouvant être reconstruits. La condition de bouclage est vérifiée par l'unité de reconstruction 244, ou le compteur 241. Cette condition de bouclage 2042 est vraie s'il existe un indice j tel que l'index = 1, ce qui veut dire qu'il existe un unique indice i qui indique quel était le paquet effacé intervenant dans l'équation de parité d'indice j. En d'autres termes, cette condition de boucle 2042 est vraie si au moins un des (N + 2K) index calculés est égal à 1. La condition de bouclage 2042 peut donc être vérifiée dans deux cas : il existe, dans l'équation de parité d'indice j, un indice i de premier paquet Ai intervenant dans l'équation de parité tel que Ka )i = 1 (dans ce cas, le paquet effacé est un premier paquet codé), ou bien il existe, dans l'équation de parité d'indice j, un indice i de deuxième paquet Bi intervenant dans l'équation de parité d'indice j, tel que (b) = 1 (dans ce cas, le paquet effacé est un deuxième paquet codé). Tant que cette condition est vraie, une nouvelle itération de la boucle est exécutée, en prenant comme données d'entrées à traiter les 5 paquets mémorisés dans l'unité mémoire 23. Chaque itération comprend les étapes suivantes. Dans l'étape de reconstruction 2044, l'unité de reconstruction 244 remplace, dans les paquets mémorisés dans l'unité mémoire 23, un paquet nul d'indice i représentatif d'un paquet effacé, intervenant dans le 10 syndrome d'indice j, par la valeur Si de ce syndrome. Plus précisément, l'unique paquet effacé d'indice i intervenant dans l'équation de parité d'indice j est alors reconstruit par A=S; dans le premier cas décrit précédemment, ou bien par BFS; respectivement. L'étape de reconstruction réalise donc une simple écriture dans 15 l'unité mémoire 23, le syndrome Si ayant déjà été calculé au cours de l'étape 2040 mise en oeuvre préalablement, sans consommer de mémoire additionnel dans le dispositif de correction 20. Dans une étape 2046, les informations d'effacements sont mises à jour par l'unité de reconstruction 244 afin de marquer le paquet reconstruit 20 comme non-effacé. On positionne ainsi à zéro l'indication d'effacement correspondant Ei(a) = 0 ou bien ,(b) = 0 respectivement. L'unité de calcul des syndromes 240 met ensuite en oeuvre l'étape de calcul des syndromes S = (S1,S2,- - -SN+2K ) sur les (N + 2K) paquets mis à jour contenus dans l'unité mémoire 203. 25 L'étape de calcul des index 2041 est également exécutée de façon à mettre à jour le vecteur d'index I = (/1,/2,- - ./N+2K). Tous les index associés à des syndromes dont la valeur a été modifiée au cours de la mise à jour précédente sont alors décrémentés de 1. La condition de bouclage 2042 est ensuite à nouveau examinée. Ainsi, la phase itérative permet de reconstruire des paquets effacés intervenant dans des équations de parité d'index supérieur à 1 à l'issue de la phase d'initialisation. Dès que la condition de bouclage 2042 est fausse, plus aucun 5 paquet effacé ne peut être reconstruit : la phase itérative se termine alors. Deux cas de sortie de la phase itérative peuvent se présenter. Dans un premier cas de sortie, les (N + 2K) index sont nuls, ce qui veut dire que tous les paquets effacés ont été reconstruits, et l'étape de décodage 206 peut être ensuite mise en oeuvre par le décodeur 26. Dans un 10 deuxième cas de sortie (référencé « fin » sur la figure 6), il ne reste que des index strictement supérieurs à 1 ; la correction de tous les effacements n'est alors pas possible et il reste des effacements résiduels. Cas de polynômes générateurs de degrés différents 15 Le recouvrement est opéré à partir de 2(N + K) paquets mémorisés dans l'unité mémoire 23, chaque paquet mémorisé étant un paquet codé non-effacé (transmis avec succès dans le canal), ou bien un paquet effacé représenté par un paquet nul représentatif d'un paquet codé effacé par le canal. 20 On a considéré dans ce qui précède le cas d'un codage au moyen de deux polynômes générateurs G1 et G2 ayant un même degré K. Ces deux polynômes peuvent cependant avoir des degrés différents (l'un peut notamment avoir un degré nul ; les paquets en sortie de l'unité de convolution mettant en oeuvre un polynôme de degré nul sont alors en 25 clair). Si les degrés respectifs K1 et K2 des polynômes générateurs G1 et G2 sont différents (K étant alors défini comme le maximum de K1 et K2), alors seuls (N + K1) premiers paquets codés et (N + K2) paquets codés sont produits par les étapes de convolution 102 et 103. Des paquets nuls 30 de bourrage peuvent alors être générés, par le noeud émetteur, ou par le noeud récepteur, dans une étape de bourrage. 3013 924 25 Cette étape de bourrage produit : si K1 > K2, des deuxièmes paquets identiquement nuls 13,, où N + K2 REVENDICATIONS1. Procédé de codage de paquets de données numériques, ledit procédé comprenant les étapes de : - mémorisation (100) de N paquets d'entrée (P1, ...,PN), - production (101) de (N + K1) premiers paquets codés (A1, AN+Ki) définis, pour m = 1, N + K1, par Am = EK4 , où G1 est un premier polynôme générateur de degré K1, G1,, est le coefficient du terme de puissance i dudit premier polynôme générateur G1, et les paquets d'entrée d'indice inférieur à 1 ou supérieur à N sont identiquement nuls, - production (102) de (N + K2) deuxièmes paquets codés (B1, ...,BN+K2) définis, pour n = 1, N + K2, par = G2J13,_ij=o où G2 est un second polynôme générateur de degré K2, G2 J est le coefficient du terme de puissance j dudit second polynôme générateur G2, et les paquets d'entrée d'indice inférieur à 1 ou supérieur à N sont identiquement nuls, et où les polynômes générateurs G1 et G2 sont premiers entre eux. 2. Procédé de correction d'effacements, ledit procédé comprenant les étapes de : mémorisation (203) de (N + K) premiers paquets à traiter (A1, ...,AN+K) et de (N + K) deuxièmes paquets à traiter (B1 ...,BN+K), chaque paquet à traiter étant un paquet non-effacé ou un paquet nul représentatif d'un paquet effacé, calcul (2040) de (N + 2K) syndromes (S1, ...,SN+2K) définis, pour n= 1, ...,N + 2K, par 3013 924 Sn = G2,jAn-i Gl,iBn-i i=0 i=0 où les G1,, sont K premiers coefficients prédéterminés et les G2,1 sont K deuxièmes coefficients prédéterminés, et où les paquets Am et Bm sont identiquement nuls pour m N K, recouvrement (2044) éventuel de paquets effacés à partir des 5 syndromes, de telle sorte que, lorsque le calcul d'un syndrome fait intervenir un unique paquet nul représentatif d'un paquet effacé, alors le paquet recouvré correspondant à ce paquet effacé est égal à ce syndrome. 10 3. Procédé selon la revendication 2, comprenant en outre les étapes de : mémorisation (202) de 2(N + K) informations d'effacement, chaque information d'effacement indiquant si un paquet mémorisé respectif est un paquet non-effacé ou un paquet nul représentatif d'un paquet effacé, 15 calcul (2041) de (N + 2K) index /N+2K) à partir des informations d'effacement, l'index In décomptant le nombre de paquets nuls représentatifs de paquet effacés intervenant dans le calcul du syndrome Sn, ladite étape de recouvrement d'un paquet effacé pouvant être réalisée lorsque l'index In est égal à 1. 20 4. Procédé selon la revendication 3, comprenant plusieurs itérations successives, chaque itération comprenant : la mise à jour (2044) des paquets mémorisés, dans laquelle chaque paquet recouvré remplace le paquet nul correspondant dans les 25 paquets mémorisés, et le calcul des syndromes (2040) à partir des paquets mémorisés mis à jour, la mise à jour (2046) des informations d'effacement associées aux paquets mémorisés remplacés, de façon que chaque paquetrecouvert soit marqué comme non-effacé dans les données mémorisées, le calcul (2041) des index à partir des informations d'effacement, une nouvelle itération étant mise en oeuvre tant qu'au moins un des index 5 calculés au cours de l'itération précédente est égal à 1. 5. Procédé selon l'une des revendications 2 à 4, dans lequel, les premiers coefficients G1,, définissant un premier polynôme G1(D) = Ejiç_o GI_JDJ , 10 et les deuxièmes coefficients G2,1 définissant un deuxième polynôme G2(D) = Ejiç_o G2JD1 , les polynômes G1 et G2 sont premiers entre eux. 6. Procédé selon la revendication 5, comprenant en outre une étape de 15 décodage (206) mettant en oeuvre le calcul suivant pour obtenir des paquets Pn de données décodées : N+K P(D) = PnDn = U (D)A(D) + V (D)B(D) n=0 où : - A(D) est un polynôme représentatif de premier paquets non-effacés ou recouvrés, tel que (D) =IY+K A-Di 10 20 - B(D) est un polynôme représentatif de deuxièmes paquets non- effacés ou recouvrés, tel que B(D) = B; D , et - U(D) et V(D) sont deux polynômes tels que U(D)G1 (D) + V (D)G2(D) = 1. 25 7. Procédé selon l'une des revendications 2 à 6, dans lequel l'entier K est le maximum de deux entiers K1 et K2, et dans lequel les premiers coefficients G1,, sont identiquement nuls pour i > K1, et les deuxièmes coefficients G2,1 sont identiquement nuls pour i > K2, et comprenant enoutre les étapes suivantes mises en oeuvre avant l'étape de mémorisation : réception de (N + K1) premiers paquets transmis (A1, AN+Ki) et de (N + K2) deuxièmes paquets transmis (B1, si K1 > K2, production de deuxièmes paquets identiquement nuls 13,, où N + K2 8. Dispositif (10) de codage de paquets de données numériques comprenant : un module mémoire (11) adapté pour mémoriser N paquets d'entrée (Pl, PN), et un module de traitement de paquets d'entrée, ledit module de traitement de paquets comprenant des première et deuxièmes unités (12, 13) de codage convolutif telles que : la première unité (12) de codage convolutif est configurée pour produire (N + K1) premiers paquets codés (A1, ...,AN+K3 définis, pour m = 1, ..., N + K1, par Am = EK4 , où G1 est un premier polynôme générateur de degré K1, G1,, est le coefficient du terme de puissance i dudit premier polynôme générateur G1, et les paquets d'entrée d'indice inférieur à 1 ou supérieur à N sont nuls, la deuxième unité (13) de codage convolutif est configurée pour produire (N + K2) premiers paquets codés (B1, ...,BN+K2) définis, pour n = 1, N + K2, par Bn = G 2,,Pn_ j où G2 est un second polynôme générateur de degré K2, G2,1 est le coefficient du terme de puissance j dudit second polynôme générateur G2, et les paquets d'entrée d'indice inférieur à 1 ou supérieur à N sont nuls, et les polynômes générateurs G1 et G2 sont premiers entre eux. 9. Dispositif (20) de correction d'effacements, comprenant : un module mémoire (22) adapté pour mémoriser (N + K) premiers paquets à traiter (A1, ...,AN+K) et (N + K) deuxièmes paquets à traiter (B1 ...,BN+K), chaque paquet à traiter étant un paquet non-effacé ou un paquet nul représentatif d'un paquet effacé, un module (24) de traitement de paquets mémorisés adapté pour : o calculer (N + 2K) syndromes (S1, ...,SN+2K) définis, pour n = 1, ...,N + 2K, par Sn = G2,jAn-i Gl,iBn-i i=0 i=0 où les G1,, sont K premiers coefficients prédéterminés et les G2,1 sont K deuxièmes coefficients prédéterminés, et où les paquets Am et Bm sont identiquement nuls pour m N + K, et o lorsque le calcul d'un syndrome fait intervenir un unique paquet nul représentatif d'un paquet effacé, définir un paquet recouvré correspondant à ce paquet effacé comme étant égal à ce syndrome. 10. Dispositif (20) de correction d'effacements selon la revendication 9, 25 dans lequel les premiers coefficients G1,, définissent un premier polynôme, et les deuxièmes coefficients G2,1 définissent un deuxième polynôme, les deux polynômes étant premiers entre eux. 11. Dispositif (20) de correction d'effacements selon la revendication 10, comprenant en outre un décodeur (26) adapté pour mettre en oeuvre le calcul suivant obtenir des paquets Pn de données décodées : N+K P (D) = PnDn = U (D)A(D) + V (D)B (D) n=0 où A(D) est un polynôme représentatif de premier paquets non-effacés ou recouvrés, tel que A(D) = ADJ, B(D) est un polynôme représentatif de deuxièmes paquets non- effacés ou recouvrés, tel que B(D) = Bi D , et U(D) et V(D) sont deux polynômes prédéterminés tels que U (D)G i(D) + V (D)G2 (D) = 1. 12. Système de transmission (R) de données numériques comprenant au moins un noeud émetteur (1) et au moins un noeud récepteur (2) mutuellement connectés par un canal (T) apte à effacer des paquets erronés, ledit noeud émetteur (1) comprenant un dispositif de codage de paquets (10) selon la revendication 8, et ledit noeud récepteur (2) comprenant un dispositif de correction d'effacements (20) selon l'une quelconque des revendications 9 à 11. 13. 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, caractérisé en ce qu'il comprend des instructions pour l'exécution des étapes d'un procédé selon l'une quelconque des revendications 1 à 7, lorsqu'il est exécuté sur un ordinateur. 14. Moyen de stockage de données inamovible, ou partiellement ou totalement amovible, comportant des instructions de code de programmeinformatique pour l'exécution des étapes d'un procédé selon l'une quelconque des revendications 1 à 7.