Brevet FR2037224A1 — publié le 19701231

La présente invention concerne un procédé de détection et/ou correction d'erreurs d'informations binaires transmises dans un code systématique, dans lequel chaque vecteur d'information _/ x_/ à k chiffres est complété par un vecteur de contrôle à m chiffres j_ y_J = ]_ a_/ . _/ x_/ puis 5 transmis sous forme d'un mode-code à n chiffres l_ x+_/, [_ a_/ étant la matrice H—h —■ de codage, dans lequel un mot à n chiffres J_ x _/ reçu à la suite de la mutilation d'un mode-code j_ x~*_/ sur la voie de transmission donne un vecteur d'erreur J_ F_/ = J_ b_/ „ J_ i= 0 et un mot-code correct ]_ x+_/ donne un vecteur d'erreur j_ F_/ = 0, ]_ b_/_ désignant la matrice de codage J_ a_/ complétée 10 par la matrice unitaire j_ I_/, et dans lequel, lors de l'apparition d'un vecteur d'erreur ]_ F_/ i= 0, un mot-addition est formé à l'aide du mot reçu ]_ '^+_l et un mot erroné de correction, changeant à chaque fois et pris parmi un nombre déterminé de tels mots, jusqu'à ce que le vecteur d'erreur j_ F_/d'un mût-addition soit nul, un mot erroné de correction étant une combinaison binaire 15 an chiffres dont l'addition modulo 2 terme à terme avec un mot-code ]_ x+_/ j j _ donne un mot reçu corrigible j_ x _/. Le procédé précédemment décrit donne satisfaction quant au temps-nécessaire lorsque les erreurs de transmission sont statistiquement indépendantes et la probabilité d'erreur ne varie pas en fonction du temps, car il 20 -est alors facile de calculer les mots erronés de correction en les classant d'après leur probabilité. Le mot erroné de correction aboutissant au vecteur d'erreur /F / = 0 est en effet trouvé relativement vite dans te cas, A titre d'exemple d'une telle erreur de transmission, on peut citer le bruit blanc apparaissant sur une voie. 25 Le procédé mentionné de correction d'erreurs doit alors utiliser des mots erronés de correction, choisis de façon pratiquement arbitraire. L'invention a pour objet un procédé de correction d'erreurs, ne présentant pas l'inconvénient mentionné et se prêtant ainsi particulièrement bien à la correction d'erreurs groupées, très fréquentespar exemple dans les 30 réseaux téléphoniques publics. Selon une particularité essentielle de l'invention, un détecteur de perturbation connu délivre un 1 pour chaque rang du mot-code ]_ x+_/ en présence d'une perturbation et un 0 dans les autres cas, de sorte qu'un mot perturbé ]_ st / est obtenu et constitue le premier mot erroné de correction j| j_ _. 35 J_ Pour l'addition modulo 2 au mot reçu J_ x _/. 70 09633 2 2037224 Les détecteurs de perturbation mentionnés sont connus et décrits par exemple dans le brevet allemand n° 1.200.348. Il est possible de constituer ces détecteurs de perturbation de façon qu'ils contrôlent les n chiffres des mots reçus j_ x _/ et délivrent un 1 en présence d'une perturbation et un 0 5 dans le cas contraire. On obtient ainsi des mots perturbés J_ st_7 comportant également n chiffres. Selon la particularité essentielle de l'invention, le mot perturbé J_ st_/ est utilisé comme premier erroné de correction J_ x / ^. Lorsque le résultat de l'addition modulo 2 du mot erroné de correction j_ x_/_1 au mot _ _| j_ *""" IJ. 10 reçu j_ x _/ montre que le vecteur d'erreur j_ F_/ ne s'annule pas, le mot erroné de correction suivant est formé à partir du précédent. Chaque mot erroné de correction J_ x_/^ doit être aussi semblable que possible au mot erroné de correction précédent J_ x__/ f(i-l) . Ce résultat s'obtient par exemple en transformant un 0 voisin d'un 1 en un 1 dans le mot perturbé /_ st_/ ou le 15 mot erroné de correction J_ x_/^ . Lorsque le résultat souhaité n'est pas obtenu, cette première transformation est annulée et un autre 0 voisin d'un 1 est transformé en un 1. Une autre possibilité consiste, en présence de groupes d'erreurs représentées par un 1, de transformer successivement chaque 1 en un 0. Dn 20 exemple de cette méthode est indiqué ci-dessous et présente les uns au-dessus des autres le mot-code J_ x+_/, le mot reçu j_ _l ^ une suite d'indications sur le détecteur par suite d'une perturbation sur la voie de transmission, le mot perturbé correspondant ]_ st_7" et les mots erronés de correction j_ x / 25 L KJ f 8 ' Indication de perturbation fl 30 35 L x+_/ 1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 1 0 L^J 1 0 0 0 A 1 0 1 1 /\ 0 ! 0 0 A ! 1 A 1 0 A 1 1 î 0 /V 1 1 0 0 1 0 1 1 0 L st_/ 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 -_X-^f3 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 Z_x_/f4 0 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 0 0 ^ 5 0 0 0 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 A_X-7f 6 0 0 0 1 0 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 /_*_/f7 0 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 0 0. 0 0 0 L X_/£8 0 0 0 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 70 09633 3 2037224 Dans cet exemple, la première méthode décrite - addition d'un 1 -est utilisée pour les mots erronés de correction J_ ~ L, x_/et ^a seconde méthode décrite - suppression successive des 1 à l'endroit des perturbations - est appliquée pour les mots erronés de correction j_ ^ - ]_ x_/£g-5 Le vecteur d'erreur ]_ F_/ = 0 est obtenu avec le mot erroné de correction J_ x_/£g Cet exemple suppose une voie à perturbations groupées, de sorte que la probabilité d'une erreur en dehors des perturbations indiquées décroît à chaque rang. Lorsque les perturbations sont très importantes, la probabilité 10 d'erreur tend vers 1/2 dans le domaine perturbé. La probabilité d'une indication de perturbation erronée est alors également voisine de 1/2 dans ce domaine. Avec cette hypothèse, une indication de perturbation erronée est plus probable qu'une indication de perturbation omise. Il est alors préférable de commencer la suppression des 1. 15 La structure de perturbation de la voie de transmission permet ainsi de déterminer une séquence particulièrement favorable pour la formation des / x /c.. — — fi Le procédé décrit est par principe applicable aussi aux autres corrections d'erreurs, utilisant un code systématique linéaire. Ï1 est avan- 20 tageux dans ce cas de déterminer , à partir du mot perturbé J_ st_/ le mot erroné de correction à probabilité maximale / x /r . On forme alors / x /. = _+_j ___ _ — — fw — —k l x _/ Q x_/^w, j_ x_/^ étant un mot reçu à corriger. La correction de ce mot reçu j_ x_/^ s'effectue de la façon habituelle, à l'aide de la redondance du code. Le (+) est le symbole de l'addition modulo 2. 25 Dans le cas des codes mentionnés, on sait que tous les mots reçus J_ x+ + _/ ayant une erreur binaire Bf 4 Cd - 1). ~ sont corrigibles, d étant la distance de Haming minimale du code utilisé. En l'absence d'un code dense ou quasi-dense, le procédé selon le brevet précité permet de corriger aussi des mots reçus pour lesquels Bf > (d - 1), y , en utilisant des mots-code spéciaux. 30 Le procédé selon l'invention permet par contre une correction quand le nombre des erreurs binaires est illimité. La correction par le code n'est en effet utilisée qu'après élimination de la grande majorité des erreurs binaires du mot reçu j_ x / par la correction précédemment décrite à l'aide de mots erronés de correction, 35 La formation du mot erroné de correction l_ x_/^ présentant la probabilité maximale s'effectue par exemple à partir des propriétés de trans-nibsi"n i o!in";jc de la voie considérée. Quand on sait par exemple que les 70 09633 4 2037224 perturbations diminuent vers les fréquences élevées, et dans le cas d'une transmission par déplacement de fréquence binaire, une indication de perturbation dans le domaine de fréquence inférieur est négligée quand on mesure simultanément dans le domaine de fréquence supérieur un niveau correspondant à la valeur probable en présence d'un caractère correct dans ce dernier domaine. Le 1 correspondant est alors transformé en un 0 dans le mot perturbé Jst/. Des variantes importantes du mot perturbé ]_ st_/ sont ainsi parfois nécessaires, selon les conditions différentes, pour obtenir le mot erroné de correction J_ x_/ présentant la probabilité maximale. 70 09633 5 2037224 REVENDICATIONS 1. Procédé de détection et/ou correction d'erreurs d'informations binaires transmises dans un code systématique, dans lequel chaque vecteur d'information J_ x_/ à k chiffres est complété par un vecteur de contrôle à m chiffres j_ y_/ = ]_ a_/ . ]_ x_/ puis transmis sous forme d'un mode-code à 5 n chiffres ]_ x+_/,JaJétant la matrice de codage, dans lequel un mot à n chif- _ _j j_ _j_ fres j_ x _/ reçu à la suite de la mutilation d'un mot-code j_ x _/ sur la voie de transmission donne un vecteur d'erreur /_ F / = / b_/ . / x*1"'" / #= 0 et un mot-code correct j_ x+_/ donne un vecteur d'erreur ]_ F / = 0, ]_ b_/ désignant la matrice de codage ]_ a_/ complétée par la matrice unitaire ]_ I_/, 10 et dans lequel, lors de l'apparition d'un vecteur d'erreur J_ F_/ # 0, un mot-addition est formé à l'aide du mot reçu J_ et un mot erroné de correction, changeant à chaque fois et pris parmi un nombre déterminé de tels mots, jusqu'à ce que le vecteur d'erreur J_ F_/ d'un mot-addition soit, nul, un mot erroné de correction étant une combinaison binaire à n chiffres 15 dont l'addition modulo 2 terme à terme avec un mot-code J_ x _/ donne un mot _ [ [ _ reçu corrigible / x _/, ledit procédé étant caractérisé en ce qu'un détecteur de perturbation connu délivre un 1 pour chaque rang du mot-code ]_ x+_/ en présence d'une perturbation et un 0 dans les autres cas, de sorte qu'un mot perturbé ]_ st / est obtenu et constitue le premier mot erroné de correction 20 j_ x_/.q pour l'addition modulo 2 au mot reçu j_ x"*"^/. 2. Procédé selon la revendication 1, caractérisé par la formation dans le cas ]_ F_/ f 0 d'autres mots erronés de correction j_ x_/£^3 avec i = 2, 3 à partir du mot erroné de correction J_ -q et Par mod:î-~ fication rang par rang de ce dernier, de façon que la modification affecte 25 toujours des rangs comportant un 1 ou voisin d'un 1. 3. Procédé selon la revendication 1 ou 2,caractérisé en ce que, dans le cas d'un code systématique linéaire, le mot erroné de correction / x / présentant la probabilité maximale est d'abord établi à partir du ^ | ] mot erroné de correction _/ x_/£^> puis ajouté modulo 2 au mot reçu _/ x _/, 30 après quoi une correction de l'erreur résiduelle est effectuée en utilisant la redondance.