Brevet FR2062884A1 — publié le 19710702

la présente invention concerne un dispositif de codage et un dispositif de décodage à seuils multiples pour un système de transmission de données par impulsions codées. Grâce au choix du code et au principe de fonctionnement du dispositif de décodage, le système est auto-correcteur d'erreurs, c'est-à-dire qu'il permet ae détecter et de corriger une certaine proportion des erreurs ae transmission altérant la transmission des données. les codesconnus permettant l'autororrection d'rieurs présentent des difficultés lors du décodage En effet, pour obtenir de bons résultats, il faut utiliser des codes longs, et lors du décodage, on se trouve amené à choisir parmi un nombre de types d'erreurs possibles croissant exponentiellement avec la longueur du code.Selon la technique connue jusqu'à présent, cette complexité est évitée au prix d'une limitation du nombre de types d'erreurs possibles (par exemple erreurs en paquets) ou encore au prix d'un équipement complexe (par exemple décodage séquentiel avec emploi d'un calculateur)0 C'est pourquoi la présente invention propose un code et des dispositifs codeurs et décodeurs permettant de traiter tous les types d'erreurs avec une complexité croissant linéairement avec la longueur du code, et avec des performances du même ordre que celles du décodage séquentiel. le code proposé par l'invention est constitué par un signal formé de m impulsions identiques, de durée et d'amplitude prises pour unités, ces impulsions étant réparties dans un temps k supérieur à m. L'arrangement de ces impulsions est choisi de fa çon telle que la fonction d'autocorrélation est formée d'une pointe de valeur m et de m.(m-1) impulsions de valeur 1 réparties dans les 2.(k-1) cases situées de part et d'autre de cette pointe. Pour une valeur de m donnée, la valeur k peut être choisie selon la longueur de contrainte désirée du code. Dans 'hypothèse d'erreurs indépendantes, on a intérêt, pour des raisons ae simplicité de réalisation, à rendre k minimal (pour m donné), c'est-à-dire à rendre le taux de remplissage m(m-1) aussi voisin de l'unité que 2(E-l) possible. Ce choix n'est cependant pas essentiel pour le fonction nemen% du système. On voit immédiatement que dès que m est supérieur à 4 ce taux ne peut pas être maintenu égal à l'unité, et qu'il faut accepter des zéros dans les lobes latéraux de la fonction d'autocorrélation. Il n' existe actuellement pas de théorie mathématique permettant de connaitre, pour une valeur de m fixée, la meilleure séquence d'impulsions satisfaisant à la définition du code précité. La présente invention décrit toutefois un moyen qui, parmi plusieurs moyens possibles, est celui qui donnele meilleur résultat, sans qu'il soit toutefois possible d'affirmer que ce résultat obtenu soit le meilleur possible. Soit a. (avec i compris entre 1 et ~) les rangs des diverses impulsions, et soit dii = ai-aj (avec i compris entre 1 et m) les distances entre les impulsions de rang i et i. La matrice //dix// est antisymétrique, si bien qu'il suffit d'en construire la partie supérieure droite (i supérieur à i ). les valeurs des coefficients se déduisent de celles des coefficients de la diagonale di, (i+l) représentant les distances entre impulsions adjacentes. -Pour chaque valeur de m, il faut construire une matrice dont tous les dij soient différents entre eux. La méthode utilisée est la suivante : étant donné une matrice de rang m, on obtient celle de rang (m+1) en intercalant au milieu de la diagonale le plus petit nombre entier convenable non encore utilisé de façon définitive. Si m est pair, il n'y a qu'une place possible ; si m est impair, on essaye d'intercaler le nombre successivement dans les deux places les plus proches du milieu. En procédant de proche en proche, jusqu'à la valeur m=16, on obtient les codes schématisés dans le Tableau I ci-dessous, dans lequel chaque ligne donne la liste des intervalles successifs entre impulsions pour une valeur donnée du nombre m d'impulsions. Tableau I m=2 1 m=3 1 2 m=4 1 3 2 m=5 1 3 5 2 m=6 1 9 6 5 2 m=7 1 3 5 8 5 2 m=8 1 9 6 il 8 5 2 m=9 1 3 6 12 11 8 5 2 m=10 1 3 6 12 16 11 8 5 2 m=11 1 3 6 12 16 20 11 8 5 2 m=12 1 3 6 12 16 25 20 11 8 5 2 m=13 1 3 6 12 16 25 27 20 11 8 5 2 m=14 1 3 6 12 16 25 23 27 20 11 8 5 2 m=15 1 3 6 12 16 25 23 33 27 20 11 8 5 2 m=16 1 3 6 12 16 25 27 45 33 27 20 11 8 5 2 Selon l'invention, ce code est utilisé de la manière suivante : Pour la transmission, l'information devant être codée traverse de façon continue un registre à décalage E muni de m prises. On transforme le message à transmettre et qui contient k bits d'information en un message à 2k bits, en intercalant entre les k bits d'information k bits de redondance obtenus en faisant la somme modulo 2 des signaux prélevés sur les m prises du registre à décalage E. L'emplacement de ces m prises sur le registre à décalage E dont la longueur est de k cases est précisément déterminé par le code qui a été décrit ci-dessus. Pour la réception et le décodage, les bits d'information sont envoyés sur un premier registre à décalage R1 qui comporte m prises et un additionneur A modulo 2 branché sur ces m prises, l'en- semble fonctionnant de manière identique au registre à décalage E utilisé à l'émission. Toutefois, alors qu'à l'émission seuls les bits d'information étaient additionnés pour permettre de former les its de re'ondance, à la réception les bits de redondance sont traits corse les bits a'information et ils participent à l'addition moulu 2 dans l'additionneur. Le résultat des additions modulo 2 est envoyé sur un deuxième registre à décalage R2 qui comporte les mêmes prises que le registre à décalage R1, l'ordre de ces prises étant toutefois inversé et le début du code des localisations des prises correspondant à l'extrémité aval du registre à décalage R2, alors que dans les registres à décalage E et R1, on avait fait correspondre le début des localisations des prises avec l'extrémité amont du registre à décalage. les prises du registre à décalage R2 véhiculent les impulsions reçues vers un additionneur analogique B suivi d'un seuil (par exemple, la tension de sortie de cet additionneur est de la forme V, 2V, 3V ...nV, et le seuil est de la forme (n' + )V pour éviter toute ambigulté de fonctionnemen. L'ensemble de ces prises, de cet additionneur et du seuil est l'équivalent d'un corrélateur. En effet S'il n'y a pas d'erreur de transmission, le registre R2 ne contient que des zéros. Une erreur dans 18 redondance se traduit par un total 1 dans l'additionneur A, et une succession de m fois 1 dans l'additionneur B. Uneerreur dans l'information défilant dans R1 donne m fois 1 dans l'additionneur A et par conséquent m. (-1) fois 1 et une fois m dans l'additionneur B. Cette valeur de m dans l'additionneur B est utilisée pour causer le franchissement d'un seuil, un 1 est alors ajouté modulo 2 au bit d'information sortant, en même temps que l'erreur est rectifiée dans le registre R2. Selon l'invention, les performances du système peuvent être encore très améliorées Si l'on adjoint au dispositif décodeur décrit ci-dessus un dispositif décodeur additionnel, de façon qu'au lieu d'utiliser l'information émergeant on envoie cette information dans une ligne à retard qui lui permet de subir une nouvelle correction. Cette correction est élaborée dans un corrélateur formé d'un registre à décalage, d'un additionneur analogique et d'un seuil, ce corrélateur étant identique en son fonctionnement au corrélateur précédemment décrit, le réglage du seuil pouvant toutefois être différent. Une partie des erreurs ayant déjà été supprimée dans le premier corrélateur, le deuxième corrélateur fonctionne dans de meilleures conditions que le précédent et le seuil en est réglé en conséquence.On peut encore ajouter d'autres corrélateurs identiques en série, si cela est nécessaire ; l'étude des performances obtenues permet, pour un taux maximal d'erreurs prédéterminé, de calculer le nombre optimal de systèmes à mettre en série et les valeurs optimales de leurs seuils respectifs. On peut démontrer qu'en pratique un système à trois seuils donne des résultats suffisants : le premier seuil peut travailler avec une probabilité de fausse correction d'erreur relativement élevée, et les seuils ultérieurs permettent de rectifier les fausses corrections ainsi introduites, de sorte que les performances du système sont intéressantes et comparables à celles obtenues avec un décodage séquentiel, avec une bien plus grande simplicité de réalisation du dispositif exploitant le système de codage. La description qui va suivre et les dessins annexés, donnés à titre explicatif et nullement limitatif, feront mieux comprendre comment l'invention peut être réalisée. Sur les dessins an nexes - la fiffure 1 représente graphiquement la relation entre la longueur k du code selon l'invention et le nombre m a'impulsions dudit code - la figure 2 représente schématiquement un dispositif codeur pour la transmission d'un code selon l'invention - la figure 5 représente schématiquement un dispositif décodeur autocorrecteur d'erreurs pour la transmission d'un code selon l'invention ; et - la figure 4 représente graphiauement les résultats obte nus avec un nombre croissant de corrélateurs à seuils dans le dispositif autocorrecteur d'erreurs selon l'invention bur la figure 1, on a représenté en abscisses le nombre m 'impulsions utilisées dans le code selon l'invention, et en ordonnées la longueur k du cocue exprimée en unités d'intervalles entre impulsions. Ce code a été précécefliient résumé dans le Tableau I pour des valeurs de m comprises entre 2 et 16 : la longueur k du coue se àit du Tableau I en effectuant la somme des intervalles entre impulsions pour un nombre m donné. On obtient la courbe représentée sur la figure 1. Sur la figure 2 on a représenté schématiquement un dispositif de codage utilisable pour coder une information selon le code précédemment décrit. Une information est fournie en E à un e registre à décalage E contenant k cases. le registre à décalage E est aussi muni de m prises aboutissant à un additionneur g fonctionnant modulo 2. les m prises sont réparties le long des k cases du registre à décalage E selon une loi imposée par le code utilisé (code de répartition de m impulsions parmi k emplacements). Un commutateur électronique CE e fournit en Es une information codée à transmettre, contenant alternativement les bits provenant du registre à décalage E et les bits provenant de l'additionneur T, ces derniers constituant des bits de redondance tels que décrits précédemment. Sur la figure 3, on a représenté schématiquement un dispositif de décodage utilisable pour décoder une information précédemment codée selon le code décrit, par exemple au moyen du codeur décrit par référence à la figure 2. Sur la figure 3, on a représenté un registre à décalage R1 d'une longueur de k cases et muni de m prises aboutissant à un additionneur A fonctionnant modulo 2, la disposition des m prises parmi les k cases étant conforme au code utilisé. le registre à décalage R1, ses prises et l'addition neur A forment un ensemble de fonctionnement identique à l'ensemble du registre à décalage E, de ses prises et de l'additionneur T décrit par référence à la figure 2 L'information transmise est four nie en R à un commutateur électronique CE qui dirige alternative e r ment les bits reçus vers le registre à décalage R1 et vers l'additionneur A, le registre à décalage R1 recevant les bits d > infor- mation et l'additionneur A recevant les bits de redondance. Selon l'invention, les signaux de sortie de l'additionneur A sont dirigés vers un registre à décalage R2 à k cases muni de m prises reliees à un additiormeur analogique Bo La disposition des m prises parmi les k cases du registre à décalage R2 est symétrique ae la disposition des prises parmi les cases du registre à décalage R1 ; en d'autres tèrmes, la répartition des m prises parmi les k cases est déterminée par le même code que précédemment, mais ce code est lu "à l'envers" en commençant par la fin du code.L'additionneur B fournit ses signaux à un additionneur COR2 modulo 2 travers un dispositif à seuil S2 qui ne laisse passer que les signaux de valeur supérieure à une valeur de seuil prédéterminée. additionneur COR2 reçoit aussi les bits d'information ayant traversé le registre à décalage R1. Par ailleurs, les signaux sortant du dispositif à seuil sont aussi fournis aux cases du registre à décalage R2 correspondant aux m prises. Comme il a été dit pracédemment, s'il n'y a pas d'erreur de transmission, le registre R2 ne contient que des zéros. Une erreur dans l'information de redondance donne un total 1 dans l'additionneur A, et une succession de m fois 1 dans l'additionneur B, ce qui ne donne pas de signal traversant le seuil S2. Une erreur dans 1 lin- formation défilant dans le registre R1 donne m fois 1 dans l'addi- tionneur A et par conséquent m.(m-1)fois 1 et une fois m dans l'additionneur B : le signal sortant de l'additionneur B franchit le seuil 2, ce qui d'une part provoque l'addition d'un 1 modulo 2 dans l'additionneur COR2 au bit d'information sortant, ce qui a pour effet de corriger l'erreur d'information, et d'autre part les cases du registre à décalage R2 correspondant aux m prises reçoivent aussi l'addition modulo 2 d'un bit, ce qui remet leur contenu à zéro. Pour réduire le nombre d'erreurs restantes, dues d'une part aux erreurs non corrigées par le système décrit ci-dessus et, a'autre part aux fausses corrections qutil a introduites et qui sont dues à des perturbations particulières de l'information transmise, le dispositif de décodage selon l'invention comprend encore au moins un corrélateur tel que représenté entre les traits tiretés x-x' et y-y' sur la figure 3. Ce corrélateur comprend d'une part une ligne à retard W, à'autre part un ensemble d'un registre à décalage R3 à m prises, d'un additionneur analogique X, d'un seuil S3, atun additionneur COR3 et d'un circuit de remise à zéro des cases du registre R3 correspondant aux m prises, cet ensemble étant similaire à l'ensemble précédemment décrit et comprenant le re gisbre R2, le seuil 2, l'addtionneur B et l'additionneur COR2, le seuil S3 pouvant toutefois etre réglé à une valeur différente du seuil Au lieu d'être délivrée en C, l'information est alors envoyée dans la ligne à retard W qui lui communique un retard exactement égal à la durée du passage à travers les k cases d'un registre à décalage. Par ailleurs, le registre à décalage R2 est connecté au registre à décalage R3 Chaque fois qu'une information a été corrigée dans le premier corrélateur correspondant au registre à décalage R2, ce registre subit une remise à zéro des cases correspondant à ses prises, de sorte que l'information ne subit pas de nouvelle et indésirable correction à son passage dans le corrélateur correspondant au registre à décalage R3. En revanche, une correction non effectuée dans le premier corrélateur peut l'entre dans le second, en raison du taux d'erreur plus faible et du réglage différent des seuils S2 et S 3. Selon l'invention, l'information peut alors être soit délivrée en F, soit soumise à une nouvelle correction dans un corrélateur similaire à celui qui vient d'être décrit et qui est représenté entre les traits tiretés x-x' et y-y' sur la figure 3o L'intéret du dispositif provient de ce que le premier corrélateur peut travailler avec une probabilité de fausse correction d'erreur relativement élevée, puisque les corrélateurs ultérieurs permettent de rectifier les fausses corrections ainsi introduites. Sur la figure 4, on a représenté la probabilité d'erreur par bit du dispositif selon l'invention, après passage de l'information à travers le dispositif, et pour une probabilité d'erreur par bit p = 0,05 au niveau de la transmission de l'information. la probabilité P d'erreur par bit après passage dans le dispositif a été représentée en fonction du réglage s des divers seuils successifs des corrélateurs, en unités de hauteur d'impulsions. Le nombre m d'impulsions du code a été choisi avec une valeur typique de m = 8, ce qui donne un code de longueur k = 37, comme on peut le voir sur la figure 1. La courbe 1 représente la probabilité d'erreur résultant du passage de l'information à travers un seul corrélateur de cor rection d'erreur : on voit qu'un optimum est atteint pour un seuil réglé à 5 En reprenant cette valeur optimalede de la probabi- lité d'erreur et en traitant l'information dans un deuxième corrélateur, on obtient un optimum sur la courbe 2 pour un seuil réglé à 4 ; un troisième corrélateur (courbe 3) sera utilement réglé à un seuil ue 5 ; l'erreur est alors si réduite qu'en pratique, il n'est pas justifié de poursuivre les corrélations au prix d'une nouvelle complication du système électronique, dont le résultat est visible sur un tronçon de la courbe 4. La courbe asymptotique Z montre la limite des performances que l'on peut attendre du système selon l'invention, avec un grand nombre de seuils. Revendications lo Dispositif codeur et décodeur à seuil, autocorrecteur d'erreurs de transmission pqur un système de transmission et de réception d'information codée par impulsions avec redondance, l'information étant séparée de la redondance dans le système de réception et le code utilisé étant tel que les lobes latéraux de la fonction d'autocorrélation sont formés uniquement de O et de 1, ledit dispositif compre nant - dtune part un dispositif codeur lui-meme compor tant un registre à décalage, un additionneur modulo 2 et un moyen de transmissions successives des informations sor tant du registre et de l'additionneur, le registre à décalage étant muni d'un nombre k de cases correspondant à la lon gueur du code et d'un nombre m de prises réparties sur les dites cases selon une disposition ordonnée déterminée par le code, le registre à décalage étant parcouru par les si gnaux correspondant à l'information à transmettre, l'ordre de succession des prises du registre étant établi dans le sens même du parcours des signaux à travers le registre, les dits signaux d'information étant à leur sortie dudit re gistre fournis audit moyen de transmissions successives, l'additionneur modulo 2 additionnant modulo 2 lescsignaux provenant des m prises du registre à décalage du codeur, et fournissant des signaux au moyen de transmissions, lesdits signaux formant des signaux de redondance, - d'autre part un dispositif décodeur, lui-même comportant un moyen de réception permettant la séparation de l'information et de la redondance, un premier registre à décalage, un premier additionneur modulo 2, un deuxième re gistre à décalage, un additionneur analogique, un dispositif à seuil et' un deuxième additionneur modulo 2, -- le premier registre à décalage étant muni d'un nombre k de cases correspondant à la longueur du code et d'un nombre m de prises réparties sur lesdites cases se lon une disposition ordonnée déterminée par le code, ce re gistre à décalage étant parcouru par les signaux fournis par le moyen de réception, l'ordre de succession des prises dudit registre étant établi dans le sens m8me du parcours des signaux à travers le registre, lesdits signaux étant à leur sortie de ce registre fournis au premier additionneur modulo 2, -- le premier additionneur modulo 2 addition nant modulo 2 les signaux provenant d'une part du moyen de réception et d'autre part des m prises du premier registre à décalage, et fournissant des signaux à l'entrée du second registre à décalage, -- le second registre à décalage étant muni d'un nombre k de cases correspondant à la longueur du code et d'un nombre m de prises réparties sur lesdites cases selon une disposition ordonnée déterminée par le code, et étant parcouru par les signaux sortant du premier addition neur modulo 2, l'ordre de succession des prises du registre étant établi en sens inverse du sens de parcours des signaux de redondance à travers ledit registre, -- l'additionneur analogique étant relié aux prises du second registre de façon à additionner les signaux fournis par lesdites prises, -- le dispositif à seuil recevant les signaux de l'additionneur analogique et transmettant seulement ceux desdits signaux dont la valeur dépasse une valeur de seuil prédéterminée, lesdits signaux étant fournis d'une part au second additionneur modulo 2 et d'autre part aux cases du second registre à décalage de façon à s'y additionner modulo 2 avec les signaux contenus dans lesdites cases, -- le second additionneur modulo 2 qui reçoit les signaux provenant du dispositif à seuil, recevant égale ment des signaux véhiculant l'information transmise débar rassée de la redondance, de façon à additionner modulo 2 lesdits signaux et rectifier ainsi au moins une partie des erreurs éventuellement contenues dans l'information trans mise, de telle sorte que les signaux sortant du second ad ditionneur modulo 2 constituent l'information utilisable0 2o Dispositif codeur et décodeur selon la revendication 1, coflrXrenant en outre lan deuxième ensemble identique à l'en- semble selon la revendication 1, formé par le second re gistre à décalage, l'additionneur analogique, le dispositif à seuil et le deuxième additionneur modulo 2 ainsi qu'une ligne à retard, - le registre à décalage du deuxième ensemble étant alimenté à sa première case par les signaux sortant de la dernière case du registre à décalage du premier ensemble, - les dispositifs à seuil du premier et du deuxième ensemble étant indépendants et leurs seuils pouvant de ce fait Btre égaux ou différents, - l'additionneur modulo 2 du deuxième ensemble re cevant dtune part des signaux provenant du dispositif à seuil du deuxième ensemble et d'autre part, à travers la ligne à retard, les signaux d'information sortant de l'ad- ditionneur modulo 2 du premier ensemble, - la ligne à retard ayant pour effet de donner aux signaux d'information un temps de trajet entre les addition neurs modulo 2 respectifs des premier et deuxième ensembles égal au temps de trajet des signaux à travers le registre à décalage du deuxième ensemble, - 11 additionneur modulo 2 du deuxième ensemble four nissant ainsi des signaux d'information utilisables où au moins une partie des erreurs éventuellement encore présentes ont été rectifiées. 3o Dispositif codeur-décodeur à seuil selon la revendication 2 comprenant en outre un ou plusieurs ensembles successifs du type décrit dans ladite revendication, ainsi qu'un nombre égal de lignes à retard, l'additionneur modulo 2 du dernier ensemble fournissant des signaux d'information utilisables où au moins une partie des erreurs éventuellement encore présentes ont été rectifiées, le nombre d'erreurs restantes diminuant avec le nombre d'ensembles utilisés. 4. Dispositif codeur et décodeur à seuil selon l'une des re vendications 1 à 3, dans lequel le moyen de transmission permettant de mettre en série l'information sortant du re gistre à décalage et la redondance sortant de l'additionneur modulo 2, est formé d'un commutateur électronique diri geant vers des moyens de transmission situés entre le co deur et le décodeur et en eux-mêmes connus, alternativement les signaux d'information qu'il reçoit du registre à décalage du codeur et les signaux de redondance qu'il reçoit de l'additionneur modulo 2 du codeur, de façon que les signaux de redondance soient intercalés entre les signaux d'information pour être transmis du codeur au décodeur en succession alternée, et le moyen de réception permettant la séparation de 11 information et de la redondance est un commutateur électronique dirigeant l'information reçue alternativement vers la première case du premier registre à décalage et vers le premier additionneur modulo 20-