Brevet FR2103405A1 — publié le 19720414

La présente invention concerne un procédé pour la correction d'erreurs de transmission de messages, qui sont codés dans un code binaire linéaire et forment des mots à k caractères d'information et m caractères de redondance. Divers procédés ;sont-connus pour la correction d'erreurs résultant de perturbations pendant la transmission de messages. Dans tous ces procédés, on transmet, en plus de l'information proprement dite, une information appelée redondance et qui permet, en présence d'erreurs, de rétablir l'information initialement transmise, dans certaines limites. Chaque mot transmis ("bloc") contien-t ainsi des caractères d'information et des caractères de redondance. Soit k le nombre des caractères d'information et m le nombre des caractères de redondance. La longueur totale du mot est par suite m + k = n. Le codage s'effectue en-multipliant les'k caractères d'information par une matrice de codage [A].Pour le décodage, le mot reçu est multiplié par une matrice [B] S qui est la matrice de codage [A] complétée par la matrice unité [g], le résultat fournissant des renseignements sur les erreurs réelles. Dans la transmission d'information avec auto-correction à l'aide de codes-blocs systématiques redondants, le message reçu est contrôlé bloc par bloc pour déceler d'éventuelles mutilations; lorsque des erreurs sont constatées, une répétition du bloc mutilé est demandée ou une correction entreprise. Le procédé décrit concerne une correction d'erreurs sans répétition des blocs perturbés. La correction éventuelle n'est effectuée de préférence que sur la -p-artie-information du message-. Le procédé de correction est particulièrement simple en cas d'emploi de codes spéciaux, tels que des codes cycliques. On connatt par ailleurs un procédé de correction dans lequel le mot reçu est permuté (brevet allemand n 1 449 906). Dans ce procédé, les permutations décalent les erreurs des rangs d'information vers la partie redondante. Le poids du syndrome indique quand toutes les erreurs se--trouvent dans la partie redondante. Ce procédé de correction connu n'est toutefois applicable qu'aulx codes cycliques, qui présentent des symétries par nature. Les permutations ainsi applicables laissent le code invariant, c'est-à-dire que la permutation d'un mot-code donne de nouveau un mot du même code. L'invention a pour objet un procédé général de correction efficace de codes linéaires quelconques. Selon une caractéristique essentielle de l'invention, la correction d'erreurs individuelles réparties statistiquement s'effectue en permutant les caractères de chaque mot, de façon à le transformer en un mot d'un autre code binaire équivalant au code binaire initial ou en un autre mot du code binaire initial, chaque mot obtenu par permutation est contrôlé pour déterminer si le poids de son syndrome est inférieur ou égal au nombre maximal d'erreurs - corrigibles et, dans l'affirmative, les caractères du mot-sont modifiés afin d'annuler le poids du syndrome. :I1 est possible de représenter un code linéaire systématique par une matrice de codage {Aj. A l'aide de cette matrice, on calcule pour une suite de k caractères d'information des caractères de contrôle, qui sont émis à la suite de ces derniers. Dans le récepteur, les mots entrants;[X jsont multipliés par la matrice [B]. Cette dernière représente la matrice de codage complétée par la-matrice unité [E]. Le résultat de cette mul tiplication est le syndrome d'erreur [S]. [B] # [X]e = [A,E] # [X]e = [S] Les lignes de la matrice[B] sous-tendent l'espace orthogonal à l'espace- code. il en résulte que [S] = 0 pour tous les [X3e reçus non perturbés. Les erreurs du mot reçu sont interprétées comme un mot erroné, superposé au mot non perturbé [X]ew. [Xe] =[X]ew+[F] Comme [B][X]ew = 0, il reste : [B] # [F] = [S] Un mot erroné admissible, c'est-à-dire donnant une mutilation encore corrigible, est caractérisé par un poids maximal G(F) ' nombre d'erreurs que le code peut corriger. Lorsque le mot erroné contient toutes les erreurs dans la partie redondance, le poids du syndrome est G(S) # e. Il est alors possible de délivrer l'information direction au transposeur.L'opération de correction doit par contre être déclenchée quand le' poids du s'yndrome est G(S) > e. L'invention part en outre de l'idée suivante : il suffit, dans-le cas G(S) # e, de réfléchir la con figuration du syndrome sur la matrice unité dans [B] pour obtenir la con- figuration d'erreur IFS. La permutation ne modifiant pas le poids' de la configuration d'erreur, il suffit de regrouper toutes les erreurs dans la redondance. Le calcul'permet alors de retrouver la configuration d'erreur initiale. Soit-le système d@@quations suivant Partie infcrmation partie redondante t f1 f2 f3 fk+l i f k fnl fn mot erroné rllal2al3----ali----alk 1' 1 0 0 ~~~~0 s S a a a2k 0 1 0 ----0 521 a21a22a23-- --a2k a31 10010 0-0 S3 t' 1 ami a t O 0 0 1 S il ni a a 11 0 0 -----O ml mi at m IA3 tex [Si La permutation d'un caractère de la partie information du mot erroné et d'un caractère de la partie redondante ne modifie pas le système d'équations ci-dessus quand la permutation du caractère f. considéré s'accompagne de celle de la colonne correspondante de [B]. la multiplication-du mot per- muté par La matrice également permutée donnerait de nouveau le même syndrome [s]. La matrice unité est tout toits perdue dans la partie redondante du code permuté. Il est possible de l'obtenir de nouveau en permutant les lignes du système d'équations précédent et en les additionnant de façon que la matrice prenne d'abord la forme en triangle, puis la forme unité dans la partie redondante. Il est facile de montrer que ces opérations sur les lignes sont admissibles et agissent aussi sur le syndrome, de sorte qu'après le rétablissement de la matrice unité, on obtient un nouveau syndrome(S, fournissant les mêmes indications que le syndrome initial. Lorsque le poids du syndrome [s1J est G(S1) Ces considérations sont illustrées ci-dessous par l'exemple d'un code optimal, déterminé par un calculateur. On connatt la matrice [B] d'un code optimal, permettant de corriger e = 3 erreurs quelconques. Longueur du bloc n = 15, nombre des caractères d'information k = 5, nombre des caractères de redondance m = 10. 1 2 3 4 5 6 7 8 9 IO II I2 I3 I4 15 te mot-code [X] = 1 0 1 I 0;0 0 1 1 0 0 0 1 1 0 est émis. Un mot erroné [F] = 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 se superpose au canal. Le mot reçu est [Xe] = 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 et le syndrome est par suite [5o1 = 1011011010 et comporte plus de e uns. L'information est donc marquée comme perturbée. La matrice unité est ensuite décalée sur la matrice de codage. On retrouve ici la difficulté précitée, à savoir que la matrice ne doit pas devenir singulière. On évite cette difficulté en ne permutant pas les colonnes de façon rigoureusement cyclique5 mais en les plaçant sur les caractères de la matrice unité, de façon qu'elle demeure regulière.' puis les lignes sont transposées. Cette opération doit agir également sur le syndrome, ce'qui implique un décalage cyclique du syndrome. La ligne 10 est ensuite ajoutée aux lignes 3-, 5, 6, Sg-9 : Le syndrome correspondant est [S1] = 0 1 0 1 1 0 1 1 0 1 Un décalage cyclique de la matrice donne [S0] 1 0 1 1 0 1 1 0 1 0 Le syndrome [S1] comporte plus de trois uns : la correction doit donc etre poursuivie. La difficulté précitée apparait alors quand la colonne 4 est entrée dans la matrice unité et la colonne 14 sortie; on y remédie par exemple en délivrant la oolonne 13 au lieu de la colonne 14. - Les lignes sont d'abord permutées de nouveau. Le syndrome ett alors [S2] = 0 0 1 0 1.1 0 1 1 1. I1 peut être indiqué immédiatement, car l'addition de la ligne 3 aux lignes 1, 3, 4, 5, 6, 8 ne le modifie plus (l'élément additif du syndrome est nul). Une nouvelle phase de correction est par suite nécessaire car G(S2) = 6 > 3. On décale aussitot, sans transposer la matrice sous la forme unité. L'ordre initial des colonnes peut désormais être rétabli. La transposition des lignes donne L'addition de la ligne 10 à 2, 3, 5, 6, 8, 9 # donnent la matrice unité. l'addition de la ligne 1 à 2, 4, 5, 6, 7, 9 L'application au syndrome [S2]| donne [S3]: [S3] = 1 0 1'0 O p O O O O; le poids de [53] est inférieur à 3, de sorte que la configuration d'erreur est F = O 0 1 0 1 0 0 0 0 O 0 0 0 0 O, ce qui coïncide avec le mot erroné admis. L'exemple de réalisation ci-dessus montre que la permutation précédemment décrite des caractères du mot reçu et @a transformation correspondante de la matrice de décodage [B] et du syndrome sont équivalentes à une instruction de calcul, qui prévoit l'addition ligne par ligne de la matrice de décodage, cette addition aboutissant à un décalage de la matrice unité [E] à l'intérieur Je la matrice globale et agissant direc tement sur le syndrome. D'autres caractéristiques et avantages de l'invention seront mieux compris à l'aide de la description détaillée ci-dessous et des dessins annexés sur lesquels la figure 1 représente un montage effectuant la correction selon l'invention par addition ligne à ligne de la matrice de décodage; la figure 2 représente le circuit multiplicateur réalisé en réseau de calcul parallèle; et la figure 3 représente le schéma d'un controleur de poids. Le mot reçu entre dans une mémoire 1. Une mémoire tampon Il permet dans certaines conditions de conserver le mot reçu suivant jusqu'à la fin de l'opération de correction du mot précédent. Le contenu de la mémoire 1 est transféré dans un circuit multiplicateur 2, auquel est appliqué un second facteurs qui est la matrice de décodage [Bl contenue dans une mémoire de matrice 3. Le circuit multiplicateur 2 détermine > à partir du mot reçu et de la matrice de décodage [B], le syndrome [S], @qui est transféré dans une mémoire de syndrome 4 par une position correspondante d'un inverseur 5.Un contrôleur de poids 6 vérifie le poids du syndrome (s] et ne délivre une instruction d'arrêt que si le poids est inférieur ou égal au nombre maximal d'erreurs corrigibles du code. La matrice de décodage [B] et le contenu de la mémoire de syndrome 4 sont appliqués à une unité de calcul 7. A l'aide de la permutation prédéterminée dans la matriceÇB], l'unité de calcul forme un nouveau syndrome [Sî' qui est transmis à la mémoire 4 par une position appropriée de l'inverseur 5. Cette modification du syndrome se poursuit jusqu'à ce que le contrôleur de poids 6 délivre l'instruction d'arrêt, à l'aide-du critère précité, et immobilise l'unité de calcul 7. Cette dernière délivre une grandeur (indication d'un compteur), caractéristique de la permutation prédéter minée et commandant un registre 8 de mot erroné, qui est en outre commande par l'instruction d'arrêt du contrô-leur de poids 6 et fonctionne selon le contenu de la mémoire de-syndrome 4. Le registre de mot erroné-est réalisé par exemple sous forme de regist-re à décalage à réaction et délivre, à partir des g-randeurs caractéristiques mentionnée?s,-une-suite de bits telle que sa superposition au contenu du registre de mémoire 1 produit, selon les règles de l'addition modulo 2, un mot exempt d'erreur. les -éléments mentionnés': sont par exemple réalisés -comme suit. Les mémoires 1 et 11 sont des registres à décalage, de même que la mémoire de syndrome 4. Le circuit multiplicateur est réalisé par exemple sous forme de réseau de calcul parallèle (figure 2). Des portes ET, disposées suivant une matrice, comb-inent les valeurs a d'une matrice et les valeurs xl à \3 3 d'un vecteur. L'addition modulo 2 ligne par ligne des grandeurs de sortie des portes ET donne le syndrome La mémoire de matrice est réalisée en mémoire morte-(read only memory). De telles mémoires sont fournies sous forme de modules complets, par la Société Radiation par exemple, sous la désignation ROM-0512.; Le contrôleur de poids 6 est réalisé par exemple selon le. schéma de la figure 3, Des transistors sont branches en aval des étages du registre de syndrome 4. Les collecteurs sont reliés par des résistances R1 au potentiel +E et par- des résistances R2 à l'entrée + d'un comparateur X, dont l'entrée - peut être portée à un potentiel compris entre +E et -E afin de fixer le point de fonctionnement du comparateur.Le calcul des résistances R1, R2 et du point de fonctionnement est effectué de façon que le comparateur bascule dans le domaine de grande sensibilité, en distinguant certainement entre e et. e + 1, quand le poids du syndrome contenu dans le registre 4 est e. Le procédé selon l'invention a été décrit jusqu'àprésent à l'aide d'un mot mutilé par des erreurs --individuel'es-. putre ces-d'ernières, il apparaît très fréquemment aussi des erreurs en paquet, c'est-à-dire des configurations d'erreurs intéressant un domaine plus étendu du mot. Dans le cas de telles, erreurs, l'application du procédé selon l'invention fait apparaître des modifications caractéristiques du syndrome au cours des phases de calcul successives. Lorsque la "fenêtre" précitée est décalée bit par bit sur le mot-code, cycliquement par exemple, un paquet de longueur configurations de bits ayant la durée de séjour la plus longue-dans le syndrome, est identifiée comme configuration d'erreur du paquet; il est alors possible de corriger l'information. Un exemple est de nouveau fourni un un code optimal. Soit l'émission du mot-code 1 0 1 I 0#0 0 1 1 0 0 0 1 1 O; au canal se superpose un paquet longueur du paquet Le mot reçu est par suite 1 0 1 1 0#1 1 0 1 1 0 0 I 1 0; le syndrome correspondant est : 1 1 1 0 1 0 0 0 0 0. Le syndrome comportant plus de 3 uns, la matrice unité est décalée à travers le code (par des opérations sur lignes). La nouvelle matrice est alors Le nouveau syndrome [S1] ] est 0 1 I 1 0 1 0 0 0 O. La configuration de bits est conservée dans le syndrome; elle est simplement décalée d'un bit. La matrice unité est ensuite décalée d'un bit, avec permutation des colonnes 13 et I4. 1 2 3 4 5 6 7 8 9 10 11 12 14 13 15 I O O 1|1 1 1 1 ' ' O 'Q 1 2 I 1 1t0 0 1 ' ' ' O ' O 3 1 1 Otl O 1 ' ' ' O 'O O 4 1 1 111 0 1 ' ' ' O 'O 1 5 l O 111 0 1' 0 '0 O Permutation 6 10 011 0 1 ' ' 0 '0 1 des lignes 7 101 Q 1 ' 0 '0 1 8 0l1tl 0 1 0 '0 0 9 O I 011 0 0 0 '1 1 10 0 I 110 0 1 'O I 1 2 3 4 5 6 7 8 9 10 11 12 14 13 15 o 9 o 1 ol 0 r ! 1 t I 0 1 1 1 0 0 16 1 ' 0 r 1 I 2 111001 ' ' ' ' ' de ligne 00 3 1 1 011 0 1 ' ' ' ' ' 0 O Addition de la ligne 9 4 1 11110 1 ' ' ' ' ' O 1 aux lignes 5 1 0 111 0 1 ' ' ' ' 0 0 1, 3, 4, 5, 6, 8 6 10010 1 ' ' ' 0 1 7 1 o 110 0 1 ' ' 0 1 8 01 1(1 0 1 ' O O 10 I Le syndrome [S2] est : 0 0 1 I 1 0 1 0 0 0. La permutation ci-dessus des colonnes 13, 14 peut être supprimée Iors du décalage ultérieur de la matrice unité. 10 11 12 13 14 15 1 0 110 1 w lOr 2 O 111 0 1 ' 1 0 0 3 1110 1 1 O 4 1000 1 ' 10 1 Fermutatión 5 1 oiî 0 1 ' 1 0 0 des1ignes 6 1 1 1 0 '1 ' 1 0 1 7 1100 1 ' 10 0 8 1 011 0 1 ' O 0- 1 9 0 0 1 0 1' -1 0 1 10 O 1 1 0 ' O 1 1' 10 ' O 1ç-1 0 0 '.0 1 1 1 O 1 o 1 '' ,1 O' 1 2 O 1 1 0 1 ' 1 0 0 3 1 li 0 1 ' 0 O Q 4 1 0 0 0 1 ' 1 0- 1 Permutation 5 1 0 1 0 1 ' 1 0 O des lignes 6 l 111 0 1 ' 1 0 -l 7 1100 1 ' -1 0 0 8 1 O 1 0 1 r 0'0 1 9 o o1î 0 1' 1 0 1 Le syndrome [S3] est : 0 0 0 1 1 1 0 1 0 0. Il est inutile de produire la matrice sous forme unité, car cette opération ne modifie pas le syndrome. [S5]= 0 0 0 0 0 1 1 1 0 1 La configuration d'erreur 11101 est ainsi apparue dans six syndromes, décalée d'un bit à chaque fois. On constate en outre que cette configuration est celle ayant le plus long temps de séjour dans le syndrome. I1 est donc possible dlsffectuer la correction de cette configuration d'erreur. Lorsque la longueur du paquet apparaissant est supérieure à la longueur b garantie par le code5 lia. ptobabilité d'une correction correce par application du procédé ci-dessus diminue. Lorsque des erreurs individuelles et en paquets apparaissent dans un système de transmission, il est avantageux d'utiliser un dispositif commutable pour la correction des deux types d'erreurs. Le critère nécessaire peut entre obtenu à l'aide de détecteurs de perturbations qui contrôlent les niveaux de signal et, à partir des écarts de niveau, décèlent des erreurs individuelles et/ou en paquets, de sorte que le code est "soutenu" dans une certaine mesure. Bien entendu, diverses modifications peuvent être apportées par l'homme de l'art au procédé et aux dispositifs qui viennent d'étire décrits à titre d'exemples non limitatifs, sans sortir du cadre de l'invention. Revendications 1. Procédé pour la correction d'erreurs de transmission de messages, codés dans un code binaire linéaire et formant des mots à k caractères d'information et m caractères de redondance, ledit procédé étant caracté risé en ce que la correction erreurs individuelles réparties statistiquement s'effectue en permutant les caractères de chaque mot, de façon à la transformer en un mot d'un autre code binaire équivalant au code binaire initial ou en un autre mot du code binaire initial, chaque mot obtenu par permutation est contrôlé pour déterminer si le poids de son syndrome est inférieur ou égal au nombre maximal d'erreurs corrigibles et, dans l'affirmativeS les caractères du mot sont modifiés afin d'annuler le poids du syndrome. 2. Procédé selon revendication 1, caractérisé par son application à des paquets d'erreurs, dont la longueur est inférieure ou égale à la longueur b du code utilise, corrigible avec certitude. m 3. Procédé selon revendication 1, caractérisé par son application aux paquets d'erreurs, dont la langueur est supérieure à bm, mais inférieure à m, des possibilités de corrections erronées étant alors admises. 4. Procédé selon une quelconque des revendications 1 à 3, caractérisé en ce que le choix entre correction d'erreurs individuelles et correction d'erreurs en paquets est décidé à l'aide d'un détecteur qui décèle la présence de perturbations à partir des écarts de niveau ou du contrôle d'autres paramètres du canal.