Brevet FR2766036A1 — publié le 19990115

L'invention se rapporte à un procédé de détection et de correction d'erreurs introduites dans une information numérique lors de sa transmission entre un émetteur et un récepteur. L'invention concerne en particulier un procédé de détection et de correction d'erreurs pour des informations numériques transmises dans un réseau ATM, abréviation anglo-saxonne pour Asynchronous Transfer Mode. Elle permet d'améliorer efficacement la qualité des transmissions effectuées dans des environnements perturbés. Les études de systèmes de télécommunication font de plus en plus appel au mode de transfert ATM. Cette technique permet de véhiculer des informations numériques de nature et de débit aussi variés qu'irréguliers (par exemple voix, vidéo, fichiers). L'information est transportée à travers un réseau pouvant être de diverses topologies (par exemple maillage, anneau, étoile, etc.). Chaque noeud du réseau, appelé commutateur ATM, est relié au noeud adjacent par une artère de transmission acceptant tous types de technologies (câble, faisceau hertzien, fibre optique, etc.). Le mode de transfert ATM met en oeuvre une technique de commutation et une technique de transfert asynchrone pour la transmission d'informations par un réseau. Ces techniques sont basées sur le principe de transmission par paquets d'information de longueur fixe, appelé cellules ATM. Ce principe consiste à segmenter les données issues d'un émetteur en blocs de longueur fixe et à ajouter à chaque bloc un en-tête pour former une cellule ATM. Les cellules ATM provenant de différents émetteurs sont multiplexées et transmises de façon asynchrone par les artères du réseau vers leur destination. Le transfert est asynchrone car les cellules transmises sont repérées seulement par leur adresse logique et non par leur position temporelle ou leur rang à l'intérieur d'une trame périodique, comme c'est le cas dans un transfert synchrone. Les techniques de transfert asynchrone sont déjà adoptées dans des réseaux tactiques militaires fonctionnant dans un environnement perturbé. Les perturbations engendrent des erreurs au sein de l'information numérique transmise par des artères des réseaux. Pour lutter contre ces erreurs, il est connu un procédé d'entrelacement. Suivant ce procédé, une structure matricielle est mise en oeuvre. Elle consiste en deux champs. Un premier champ comprend des données, un deuxième champ comprend une information de redondance des données. Les données à transmettre par l'émetteur sont rangées dans une première matrice dont la structure est identique à celle précédemment décrite. Le rangement des données issues de l'émetteur se fait par colonne, colonne après colonne pour remplir le premier champ. Dès qu'une colonne du premier champ est complète, une information de redondance du contenu de cette colonne est rangée dans le deuxième champ dans le prolongement de cette colonne. Une fois la première matrice complète, I'information numérique constituée des données issues de l'émetteur et de l'information de redondance est transmise par ligne, pour réaliser un entrelacement des données et de l'information de redondance, ligne après ligne par des artères d'un réseau vers un récepteur. Lors de ia réception, les lignes reçues sont rangées dans une deuxième matrice, dont la structure est identique à celle précédemment décrite. Le rangement se fait par ligne, ligne après ligne. Lorsque la deuxième matrice est complète un système de décryptage en exploite le contenu pour corriger le premier champ contenant les données en fonction des erreurs détectées grâce à l'information de redondance. Ainsi par exemple, soit une structure matricielle contenant des symboles dont le premier champ comprend 24 lignes de X colonnes et dont le deuxième champ comprend 6 lignes de X colonnes. Les données à transmettre par un émetteur sont rangées sous forme de symboles dans le premier champ de la première matrice. L'information de redondance est obtenue par l'utilisation d'un code Reed Solomon. Après transmission deux types d'erreur peuvent être distingués. Un premier type d'erreur modifie l'information numérique et correspond à une erreur bit. Dans ce cas le symbole est erroné. Ce type d'erreur est qualifié d"'erreur". La mise en oeuvre de la structure matricielle précédente permet de détecter et de corriger au maximum trois "erreurs" par colonne et pour toute les colonnes de 24+6 lignes de la deuxième matrice. Un deuxième type d'erreur cause la perte de l'information numérique. Ce cas correspond à l'effacement d'un symbole, voire d'une ligne par exemple. Ce type d'erreur est qualifié d"'effacement". Suivant les règles de l'art un mécanisme déterminé de remplissage de la deuxième matrice est mis en oeuvre lors de la réception. II permet de respecter le cadrage de l'information numérique transmise. Ce mécanisme peut comporter, en particulier, un procédé de maintien de l'intégrité binaire. Le mécanisme peut fournir la position des symboles détectés perdus (pertes qui correspondent à des "effacements") et remplacés par des symboles de bourrage. Finalement, lors de la réception, I'utilisation d'un code Reed Solomon, renseigné de la position des "effacements", permet de corriger jusqu'à 6 "effacements" par colonne, pour toutes les colonnes de 24+6 lignes de la deuxième matrice pour l'exemple considéré. Ainsi, I'entrelacement des données réalisé par le procédé d'entrelacement facilite les corrections à mettre en oeuvre. En effet, suivant ce procédé toute perturbation apparaissant sur une artère est répartie dans l'ensemble de l'information numérique rangée dans la deuxième matrice. Mais les capacités de détection et de correction d'erreurs de ce procédé d'entrelacement ne permettent pas de répondre d'une manière satisfaisante aux différentes configurations d'erreurs engendrées par le fort taux de perturbation affectant les réseaux militaires actuels. En effet I'augmentation des capacités de détection et de correction d'erreurs de ce procédé nécessite d'augmenter la taille du deuxième champ. Ainsi en reprenant l'exemple précédent, pour détecter et corriger jusqu'à trois "erreurs" par colonne, il faut dimensionner l'information de redondance à six lignes. Dans le cas d'un réseau militaire, le taux de perturbation est élevé et conduit, par exemple, à devoir détecter et corriger jusqu'à vingt-quatre "erreurs". Dans ces conditions, le deuxième champ comprend quarante-huit lignes d'information de redondance. Ainsi, la taille du deuxième champ devient rapidement du même ordre de grandeur que la taille du premier champ voire supérieure. Ceci est tout à fait inacceptable d'un point de vue efficacité. Dans le cas de l'exemple précédent, le procédé selon l'invention doit pouvoir détecter et corriger jusqu'à trois colonnes totalement erronées et corriger jusqu'à six lignes effacées; ce qui est impossible avec le procédé d'entrelacement connu et préalablement décrit, quelque soit la taille du champ de redondance. Le but de l'invention est de pallier les inconvénients cités et de répondre au problème posé. A cet effet, I'invention a pour objet un procédé de détection et de correction d'erreurs introduites dans une information numérique, contenant des données issues d'un émetteur destinées à un récepteur, lors de sa transmission vers le récepteur par des supports de transmission soumis à des perturbations caractérisé en ce qu'il consiste: à définir une première matrice de taille déterminée formée d'un premier champ de taille déterminée et d'un deuxième champ de taille déterminée, à remplir chaque colonne de la première matrice, colonne après colonne, en rangeant sous forme de symboles dans le premier champ les données issues de l'émetteur et en rangeant dans le deuxième champ une première information de redondance, de taille déterminée, déterminée par l'application d'un premier code détecteur et correcteur d'erreurs sur le contenu du premier champ de la colonne à transmettre ligne par ligne le contenu de la première matrice, en associant à chaque ligne transmise une deuxième information de redondance, de taille déterminée, déterminée par l'application d'un deuxième code détecteur et correcteur d'erreurs sur le contenu de la ligne, à définir une deuxième matrice de même structure que la première matrice, à remplir chaque ligne,de la deuxième matrice, ligne après ligne, avec une ligne reçue, et corrigée au moyen d'un deuxième code détecteur et correcteur d'erreurs appliqué sur un ensemble formé de la ligne reçue et de la deuxième information de redondance associée à transmettre au récepteur le contenu du premier champ de chaque colonne de la deuxième matrice, colonne après colonne, en corrigeant le contenu du premier champ avant sa transmission, au moyen du premier code détecteur et correcteur d'erreurs appliqué sur la colonne. Ainsi, le procédé selon l'invention définit une nouvelle structure matricielle. Cette nouvelle structure comprend, en plus des champs de la structure matricielle connue, un troisième champ dans lequel est rangée une deuxième information de redondance. La disposition du deuxième champ de redondance au sein de la structure matricielle a pour effet d'augmenter considérablement la capacité de détection et de correction des erreurs. En effet, le deuxième champ permet de réaliser une première détection et correction d'erreurs sur les données mais aussi sur la première information de redondance. Ainsi le doublement de l'information de redondance permet de multiplier par plus de deux, la capacité de détection et de correction d'erreurs. D'autre part, ce gain important d'efficacité ne nécessite que très peu d'espace mémoire supplémentaire, tant à l'émission qu'à la réception, et il ne nécessite qu'une légère augmentation du débit sur les artères du réseau. L'invention sera mieux comprise et ses avantages et autres caractéristiques ressortiront lors de la description suivante présentée à titre d'illustration non limitative et faite en regard des figures annexées qui représentent: - la figure 1, une structure matricielle définie par le procédé selon l'invention, - la figure 2, un schéma des étapes du procédé selon l'invention. Sur les différentes figures, les éléments homologues sont représentés avec une même référence. La structure matricielle définie par le procédé selon l'invention consiste en une matrice de taille déterminée. Suivant une illustration, représentée sur la figure 1, la structure matricielle comprend L+RI lignes de C+R2 colonnes. Ceci revient à dire que la structure matricielle a une taille égale à (L+Rl)x(C+R2). L, R1, C, R2 sont des entiers naturels. La structure matricielle contient des symboles. Un symbole peut avoir selon les applications une dimension binaire variable, il peut correspondre à un bit, un octet, un mot de 16 bits ou une cellule ATM par exemple. Un premier champ de taille L lignes x C colonnes contient des données émises par un émetteur à destination d'un récepteur. Les données sont rangées sous forme de symboles. Un deuxième champ 2 de taille R1 lignes x C colonnes contient une première information de redondance Rc. La première information de redondance Rc est le résultat d'un premier code détecteur et correcteur d'erreurs appliqué sur les symboles correspondant aux données émises par l'émetteur. Le deuxième champ 2 donne ainsi une information de redondance du premier champ 1. Ainsi, chaque colonne de la structure matricielle est composée d'un premier champ de L symboles et d'un deuxième champ de RI symboles. Le premier champ contient des symboles correspondant à des données émises par l'émetteur. Le deuxième champ contient les symboles d'une information de redondance résultat d'un premier code détecteur et correcteur d'erreurs appliqué sur les symboles du premier champ. Les codes détecteur et correcteur d'erreurs sont parfaitement connus de l'homme du métier. Le code détecteur et correcteur d'erreurs peut être choisi en fonction des performances de capacité de détection et de correction d'erreurs à atteindre. Le code choisi peut être un code Reed Solomon qui a pour particularité d'être particulièrement efficace dans le cadre du procédé. Un troisième champ 3 de taille (L+R?) lignes x R2 colonnes contient une deuxième information de redondance RL. La deuxième information de redondance RL est le résultat d'un deuxième code détecteur et correcteur d'erreurs appliqué sur le premier champ 1 et sur le deuxième champ 2 de la structure matricielle. Le deuxième code choisi peut aussi être un code Reed Solomon pour la même raison que précédemment. Ainsi, chaque ligne de la structure matricielle est composée d'un premier champ de C symboles et d'un deuxième champ de R2 symboles. Le premier champ contient des symboles des données s'il s'agit d'une ligne parmi les L premières lignes, sinon il contient des symboles de la première information de redondance Rc. Le deuxième champ contient une information de redondance RL résultat d'un deuxième code détecteur et correcteur d'erreurs appliqué sur le contenu du premier champ de la ligne considérée. Lors d'une transmission d'informations numériques entre un émetteur et un récepteur par des artères d'un réseau soumis à des perturbations tel un réseau militaire, le procédé selon l'invention est mis en oeuvre pour lutter efficacement contre les perturbations. La figure 2 illustre différentes étapes du procédé selon l'invention. Un émetteur 4 émet des données vers un récepteur 5. Les données sont transmises par des artères d'un réseau non représentées. Dans une première étape, les données émises D1 par l'émetteur 4 sont rangées sous forme de symboles dans une première matrice 6. La première matrice 6 est formée du premier champ 1 et du deuxième champ 2 de la structure matricielle préalablement définie en regard de la figure 1. Ainsi chaque colonne C6 de la première matrice 6 comprend un premier champ formé de L symboles et un deuxième champ formé de RI symboles. Les symboles des données émises D1 sont rangés dans le premier champ 1 suivant un rangement par colonne. En parallèle du rangement des données une information de redondance Rc est rangée dans le deuxième champ 2. Dès que le premier champ d'une colonne C61 est plein, une information de redondance Rc formée de RI symboles, calculée de la manière préalablement expliquée en regard de la figure 1, est rangée dans le deuxième champ de la colonne C61. La première étape est achevée lorsque les deux champs 1, 2 de la première matrice sont pleins. Dans une deuxième étape, I'information numérique rangée dans la première matrice 6 est transmise par les artères, non représentées, du réseau. Le contenu D2 de la première matrice 6 est transmis par ligne, ligne après ligne. Etant donné le mode de remplissage par colonne de la première matrice 6, réalisé lors de la première étape, la transmission par ligne du contenu D2 de la première matrice 6 réalise un entrelacement des données rangées dans la première matrice 6. Chaque ligne L6j parmi les L+R1 lignes de la première matrice 6 est transmise avec une deuxième information de redondance RL qui lui est associée. La deuxième information de redondance RL est calculée de la manière préalablement expliquée en regard de la figure 1. Le calcul est réalisé au début de la transmission de la ligne L6j par les artères du réseau. Ceci permet de bénéficier du gain d'efficacité de détection et de correction d'erreurs de la nouvelle structure matricielle en augmentant très peu la taille mémoire disponible. En effet, le supplément de mémoire nécessaire correspond à la taille de l'information de redondance RL d'une ligne, soit R2 symboles. Cette caractéristique limite d'une manière évidente l'augmentation du débit sur les artères. La deuxième étape est achevée lorsque tout le contenu D2 de la première matrice 6 a été transmis. Dans une troisième étape, I'information numérique reçue D3 des artères du réseau est traitée au fur et à mesure de sa réception. L'information numérique reçue D3 se présente sous la forme de lignes reçues L'6j accompagnées chacune de leur information de redondance RL. Le résultat du traitement est stocké par ligne, ligne après ligne, dans une deuxième matrice 7. Le traitement de l'information numérique reçue D3 consiste à corriger l'information numérique en appliquant, sur l'ensemble formé d'une ligne reçue L'j et de son information de redondance RL, le deuxième code détecteur et correcteur d'erreurs. Le traitement donne un résultat de taille C symboles. Ce résultat est stocké dans la deuxième matrice 7 suivant un rangement par ligne. Ainsi, la taille et la structure de la deuxième matrice 7 sont exactement les mêmes que ceux de la première matrice 6. Ainsi, côté réception, le supplément de mémoire nécessaire est le même que côté émission. La troisième étape est achevée lorsque les deux champs 1, 2 de la deuxième matrice 7 sont pleins. Dans une quatrième étape, une partie de l'information numérique contenue dans la deuxième matrice 7 est transmise par colonne, colonne après colonne, au récepteur 5. Chaque colonne C71 de la deuxième matrice 7 est traitée avant d'être transmise au récepteur 5. Le traitement d'une colonne C7i consiste à corriger l'information numérique contenue dans la colonne C71 en applicant le premier code détecteur et correcteur d'erreurs sur la colonne C71. Seul le résultat du traitement, de taille L symboles, est transmis au récepteur. La transmission colonne après colonne permet de réaliser le désentrelacement des données contenues dans le premier champ de la deuxième matrice. Ainsi la capacité de détection et de correction des erreurs a été notamment augmentée grâce à la spécialisation des deux champs de redondance. Le deuxième champ de redondance permet la correction sur une ligne de symboles erronés. Le premier champ de redondance permet la correction sur une colonne d"'effacements" etlou d"'erreurs" résiduelles. La succession des étapes du procédé telle que décrite précédemment est la plus efficace car: - la correction des "erreurs" isolées réalisée dans un premier temps au moyen de la deuxième information de redondance RL permet d'exploiter au maximum la capacité de correction des "effacements", correction qui est réalisée dans un deuxième temps au moyen de la première information de redondance Rc, - la deuxième information de redondance RL protège la première information de redondance Rc, - les traitements liés à la deuxième information de redondance RL se font en temps réel et nécessitent très peu d'augmentation de mémoire. Dans un deuxième mode de réalisation du procédé, il est réalisé dans l'ordre: -le stockage par ligne, ligne après ligne, dans une première matrice des informations émises par l'émetteur, - la détermination de la première information de redondance Rc, calculée sur une colonne, colonne après colonne, après que la première matrice soit pleine, - la transmission du contenu de la première matrice tel que décrit préalablement dans la deuxième étape, - le stockage dans une deuxième matrice tel que décrit préalablement dans la troisième étape, - la transmission par ligne, ligne après ligne, vers le récepteur du contenu de la deuxième matrice après avoir corrigé le premier champ grâce à l'exploitation du deuxième champ en utilisant le premier code détecteur et correcteur d'erreurs. Le choix d'un code REED SOLOMON pour le premier code détecteur et correcteur d'erreurs ainsi que pour le deuxième code détecteur et correcteur d'erreurs est le choix le plus efficace. Les codes REED SOLOMON permettent en effet de détecter et corriger des symboles. En fonction de l'implémentation et des performances attendues un choix de la taille des symboles est effectué. Dans ces conditions, la deuxième information de redondance RL permet de détecter et corriger pour chaque information reçue (R2/2) symboles parmi (C+R2) symboles reçus. La première information de redondance Rc permet de corriger jusqu'à: - E symboles erronés parmi les (L+Rî) symboles de chaque colonne de la deuxième matrice, avec E - P symboles détectés perdus par le mécanisme de remplissage de la deuxième matrice parmi (L+Rî) symboles, avec comme relation entre E et P : 2E+P De plus, I'utilisation simultanée en réception d'un procédé permettant la détection précise des emplacements des symboles perdus, permet de doubler la capacité de correction du code REED SOLOMON. En fonction des performances à atteindre, d'autres choix peuvent être réalisés pour les codes détecteur et correcteur d'erreurs. En particulier, un code moins puissant convient généralement pour calculer la deuxième information de redondance RL. Ainsi, il est par exemple possible de choisir un autre code cyclique, tel un code de Hamming ou un code BCH. REVENDICATIONS 1. Procédé de détection et de correction d'erreurs introduites dans une information numérique, contenant des données issues d'un émetteur destinées à un récepteur, lors de sa transmission vers le récepteur par des supports de transmission soumis à des perturbations caractérisé en ce qu'il consiste: à définir une première matrice (6) de taille déterminée (L+R1 lignes x C colonnes) formée d'un premier champ (1) de taille déterminée (L lignes x C colonnes) et d'un deuxième champ (2) de taille déterminée (R1 lignes x C colonnes), à remplir chaque colonne (C6;) de la première matrice (6), colonne après colonne, en rangeant sous forme de symboles dans le premier champ (1) les données (Dl) issues de l'émetteur (4) et en rangeant dans le deuxième champ (2) une première information de redondance (Rc), de taille déterminée (R1), déterminée par l'application d'un premier code détecteur et correcteur d'erreurs sur le contenu du premier champ de la colonne (C6i), à transmettre ligne par ligne le contenu (D2) de la première matrice (6), en associant à chaque ligne (L6;) transmise une deuxième information de redondance (RL), de taille déterminée (R2), déterminée par l'application d'un deuxième code détecteur et correcteur d'erreurs sur le contenu de la ligne (Lij), à définir une deuxième matrice (7) de même structure que la première matrice (6), à remplir chaque ligne (L7),de la deuxième matrice (7), ligne après ligne, avec une ligne reçue (L'si), et corrigée au moyen d'un deuxième code détecteur et correcteur d'erreurs appliqué sur un ensemble formé de la ligne reçue (L'6;) et de la deuxième information de redondance (RL) associée, à transmettre au récepteur (5) le contenu du premier champ (1) de chaque colonne (C7j) de la deuxième matrice (7), colonne après colonne, en corrigeant le contenu du premier champ (1) avant sa transmission, au moyen du premier code détecteur et correcteur d'erreurs appliqué sur la colonne (C7;). 2. Procédé selon la revendication 1, caractérisé en ce que le premier et le deuxième code détecteur et correcteur d'erreurs sont des codes REED SOLOMON.