Brevet FR2065561A1 — publié le 19710730

La présente invention se rapporte à un procédé de codage de segments de codes de contrôle à partir de données d'origine et, plus particulièrement, à un procédé et à un dispositif destinés à produire un certain nombre de segments de codes de contrôle à par-5 tir des données d'origine, dev manière qu'après l'introduction des segments de codes de contrôle dans les données d'origine, les erreurs puissent être détectées, et dans certains cas, corrigées. le cadre général de cette invention peut être mieux compris en considérant d'abord le procédé "Hamming" de détection d'errèurs 10 bien connu, décrit dans le brevet des Etats-Unis d'Amérique "Reis-sue" n° 23 601» Il y a lieu de noter que dans ce brevet, cette technique se rapporte à un procédé et à un dispositif destinés à ajouter "k" éléments binaires de contrôle à chaque groupe de codes de la donnée d'origine de "m" éléments binaires d'informations. le 15 code Hamming comportant les éléments binaires de contrôle contient par conséquent "n" éléments binaires avec n = m + k. Comme lrexpose clairement le brevet précité, la technique qu'il décrit est destinée, à la détection et à la correction dans un groupe de codes donné, c'est-à-dire que les "k" éléments binai-20 res sont ajoutés à chaque groupe de codes afin d'identifier spécifiquement celui des éléments du groupe qui est erroné. La présente invention, par ailleurs, concerne particulièrement 'la détermination du segment de données qui contient une erreur, si une erreur existe, dans le cas où ce segment de données 25 est contenu dans une donnée d'origine comportant un certain nombre de segments, plutôt que la localisation de la position d'une erreur dans un segment de données dans le cas où la donnée d'origine ne comporte qu'un seul segment. Il est donc important de noter les définitions totalement 30 différentes de "n", "m" et "k" selon la présente invention,- par rapport à celles de la description du brevet précité. Le terme "k" désigne dans le présent mémoire le nombre maximum de lignes du tableau ou sa dernière ligne. Le terme "n" désigne le nombre maximum d'éléments binaires d'un segment ou le dernier élément de ce segment, ou 35 il peut encore désigner le nombre maximum de colonnes ou la dernière colonne d'uryfcableau. La première détermination de l'invention consiste à établir s'il est possible, à la lecture de données précédemment codées avec des segments de contrôle, de déterminer le segment, s'il y en a, qui contient une erreur ou éventuellement un groupe d'erreurs. Cet- 70 36587 2065561 te détermination ne peut être faite de façon univoque que si "k" est inférieur ou égal à "n". Comme certains groupes d'erreurs peuvent contenir des sous-rgroupes répétitifs, la réalisation préférée de l'invention spécifie que "n" est un nombre premier. 5 la présente invention concerne un procédé de codage d'un ta bleau en codes de contrôle de façon à permettre la localisation de la position d'un segment de données dans le tableau, plutôt que de la position d'un élément dans le segment, d'augmenter l'efficacité du codage des codes de contrôle pour la détection d'erreurs éven-10 tuelles et leur correction, où l'efficacité est mesurée par le nombre d'éléments binaires de contrôle nécessaires par rapport au nombre des éléments binaires des données d'origine. La présente invention concerne un procédé de codage de segments de codes de contrôle à partir des données d'origine organi-15 sées en k segments de données de chaque n éléments binaires, .où chaque élément d'un segment de données a une position qui est rapportée dans deux directions à chaque autre élément binaire du môme segment, et où chaque position constitue une position de ..colonne dans un groupe k x n, le procédé comportant la production d'une 20 première série de n éléments binaires de contrôle comme série correspondant à une première suite de fonctions OU-exclusif le long des colonnes dudit tableau, et la production d'une seconde série de n éléments binaires de contrôle comme une série correspondant à des secondes séries de fonctions OU-exclusif le long des diagona-25 les dudit groupe, une diagonale étant définie comme/uae série de positions adjacentes dans des lignes successives du tableau, dans une direction qui est la même pour toutes les diagonales. L'inefficacité des éléments binaires de contrôle selon la technique Hamming a amené le développement de la technique de contrôle de code 30 cyclique» Pour appuyer la description ci-après, "concernant les *Co-des cycliques pour la Détection d'Erreurs" il est fait mention d'un article portant ce titre, publié dans les procédés de IBE, en Janvier 1961, par W.W. Peterson et H. T. Brown. Il faut noter que dans la définition du "Code Cyclique" don-35 née dans l'article précité, cette technique est un développement d& celle de Hamming permettant- une technique de codage plus efficace. C'est ainsi que l'article de Peterson concerne également la détec-* tion d'erreurs et leur correction éventuelle dans un segm&nt de données unique. En particulier, la technique de "Codage Cyclique" est 70 36587 3 2065561 destinée à produire un code qui est espéré unique pour ce segment de' données et qui est ensuite ajouté au segment de la façon décrite ' par Hamming-, , Pour cette raison, il est important de noter que les techni-5 ques de codages antérieures décrités ci-dessus se rapportent dans tous les cas à un segment de données unique, le but de la te clinique étant de détecter une erreur dans un segment et si possible de la corriger. Une étude plus approfondie des techniques antérieures de 'dé-10 tection d'erreurs se trouve dans le "Digital Computer Design Fun-damental-s" par Yaohan Chu, publié en 1962 par McGraw-Hill, particulièrement aux chapitres 2-8 commençant à la page 78 et continuant avec une liste d'autres références à la page 88. La technique logique d'expression d'un contrôle de parité \5 comme une succession, ou série, de fonctions OU-exclusif est décrite dans la référence de Yaohan Chu ci-dessus. Cette expression générale sera utilisée dans la présente description et complètement définie pour les buts actuels. Par conséquent, la référence ci-dessus n'est pas introduite dans la présente description, mais est 20 simplement mentionnée comme une technique antérieure. La caractéristique principale de la présente invention est l'utilisation d'une série de diagonales d'un tableau pour établir au moins un segment de codes de contrôle supplémentaire. Une fois que la donnée d'origine est mise sous forme de tableau n x k, selon 25 la présente invention, et que les segments de code de contrôle sont codés, un nouveau procédé de détection d'erreur et de correction devient, possible. Si la donnée précédé minent codée pour le contrôle doit être lue par le procédé selon l'invention, la technique de base du co-30 dage est répétée dans une phase finale qui est la formation d'au moins deux segments dferreur dont l'un doit être un segment d'erreur de diagonale. Le terme "segment d'erreur" tel qu'il est employé dans le présent mémoire, signifie un code comportant n éléments binaires, ne contenant aucun "UN" binaire si aucune erreur 35"- n'est détectée dans un groupe déterminé de lignes, tel qu'un groupe de colonnes ou de diagonales, la présenee de "US" indiquant la présence .d'erreurs dans ces lignes. 70 36587 4 2065561 Dans la présente. technique, les segments d'erreur sont analysés pour déterminer s'il y a des codes non-zéro. Bien que l'invention puisse n'être pratiquée qu'avec un seul code d'erreur de colonne et un .des deux codes possibles d'erreur de diagonale, une 5 amélioration importante est obtenue en ce qui concerne la sécurité de la correction ou la "confiance" grâce à l'utilisation des trois codes. En conséquence, dans la description qui suit, les trois codes : colonne, diagonale gauche et diagonale droite sont supposés être présents. 10 Selon le procédé de base, si deux ou trois des codes d'er reur contiennent tous les zéros, la donnée est désignée comme correcte. Dans ce cas, le code d'erreur de diagonale a servi à permettre une décision qui autrement ne serait pas possible. Si l'un seulement .des trois codes d'erreur contient tous les 15 zéros, le procédé décrit dans la présente invention spécifie que la donnée désignée est "impossible à corriger" ce qui implique" qu'une erreur est détectée mais qu'ëlle ne peut être corrigée. Si aucun des codes d'erreur ne contient tous les zéros, la nouvelle technique de localisation de segment selon l'invention se-20 ra mise en oeuvré, bien qu'il puisse toujours survenir des cas où une correction d'erreur ne sera pas possible. Il peut être noté à ce sujet que, si la localisation, sous forme de la ligne du tableau de données, peut être spécifiée de façon univoque eomme "contenant ■ toutes les erreurs possibles, celles-ci sont susceptibles d'être 25 corrigées. La présente invention a donc pour objet de permettre la correction d'un nombre d'erreurs atteignant n-1 dans un seul segment de données de n. éléments binaires. • La technique de la localisation des lignes selon l'invention fonctionne rd'après le nouveau principe selon lequel, si les trois 30 segments d'erreur peuvent se recouvrir par la combinaison correete t de modulo "n" décalages cycliques comme spécifié ci-dessous, le groupe d'erreurs ne doit exister que dans un seul segment de données et peut, alors, être corrigé par rapport au code d'erreur de colonne d'origine ....... 35 . Dans la pratique du recouvrement des codes, le code d'erreur de colonne. n'est pas décalé cyeliquement» Une première comparaison est faite e,ntre les trois, codes d'erreur. Si une triple égalité est trouvée, le groupe d'erreur doit- exister dans la première ligne (ligne N0 zéro). Lorsque cette première comparaison n'est pas va 70 36587 5 2065561 lable, le code d'erreur de diagonale gauche est décalé cycliquement (modulo n) à gauche, le code d'erreur de diagonale droite est décalé cycliquement à droite, et une triple comparaison est faite à nouveau. Ces comparaison et opération de décalage sont répétées 5 jusqu'à ce que la triple égalité soit trouvée, ou que n comparaisons soient effectuées sans égalité. le nombre des cycles est compté et donne l'indice de la ligne, si elle existe, dans laquelle l'erreur a été détectée. S'il n'y a pas d'accord, un signal "impossible à corriger" est délivré. 10 Lorsque le triple contrôle des codes d'erreur est terminé, selon la présente invention, un code de correction extrêmement sûr est disponible. Le signal "à corriger" signifie que toutes les erreurs se trouvent dans ce segment de données, ou ligne, qui est marqué par l'indice du compteur de décalages. De plus, le code 15 d'erreur de colonne définit précisément quelles sont les modifications qui doivent être faites pour corriger complètement toutes les erreurs. C'est ainsi que si "n" est choisi comme un grand nombre premier (la préférence pour un nombre premier apparaîtra clairement 20 après que les groupes d'erreurs auront été examinés) tel que 67, et qu'un tableau 67 x 67 est choisi, un total de 3 z 67 éléments binaires de contrôle permet selon l'invention, de corriger jusqu'à 66 éléments binaires dans un seul segment de données. Il ressort de cette description que la présente invention 25 est particulièrement avantageuse lorsqu'elle est utilisée avec une large bande ou une série de disques dans lesquels un segment de données peut constituer un enregistrement complet- de peut-être plusieurs centaines d'éléments binaires et les segments de contrôle sont alors destinés à indiquer l'erreur dans un enregistrement 30 unique. Une fois qu'il a déterminé qu'un groupe d'erreurs existe dans un segment de données prédéterminé, selon l'invention, un contrôle de code cyclique du type Hamming pourrait être utilisé si des éléments binaires de parité ou autres étaient déjà conte-35 nus dans les données d'origine. Bien que cette combinaison de. contrôle- soit suggérée ici afin de faire ressortir le-s fonctions différentes entre la technique antérieure et celle selon l'invention, il peut être souhaitable' d'appliquer la présente invention en se servant du code d'erreur de colonne comme code de correction plu 70 36587 & 2065561 tôt que d'utiliser ind ividue1le me nt les contrôles de code Hamming ou à décalage cyclique. D'autres caractéristiques et avantages de l'invention res-sortiront de la description qui va suivre,faite en regard des des-5 sins annexés donnés à titre d'exemples non limitatifs. Sur' ces dessins : La figure 1 représente le "format du tableau source n x k de base considéré dans la présente invention et la manière générale dont sont organisés trois segments de contrôle. 10 La figure 2 montre un exemple spécifique du tableau de la figure 1 dans lequel n = 4- et k = 3. La figuré. 3' représente un tableau d'éléments binaires réels introduits pour montrer comment sont déterminées les valeurs réelles des segments de contrôle. 15 La figure 4 est le diagramme schématique d'une forme de dis positif pouvant être utilisée pour produire les segments de contrôle. Les figures 5a. 5b et 5c montrent trois formats typiques de données pouvant être transformés en tableaux, sources n -x k selon 20 l1invention6 Les figures 6as 6b?6cs6d et 6e montrent différentes sortes d'erreurs pouvant se produire et justifient la préférence d'un nombre premier pour n® Dans la figure 1, la source de données est représentée comme 25 un tableau de k x n„ Chaque position d'élément binaire du tableau est désignée par\un symbole de référence de ligne et de colonne. En commençant par en haut et à gauche, la position B11 désigne la première/et la première colonne du tableau. En suivant la ligne, la seconde position est désignée par BÏ2. Le terme général désignant 30 les éléments binaires de la première ligne est Blm, oh m peut prendre ùne valeur *comprise entre 1 et n, et le dernier terme de la première rangée est désigné par Bln. Une case déterminée du tableau de la figure 1 se retrouve dans la figure 2 au-dessous. La lettre j est utilisée pour désigner l'une quelconque des 35 k Lignes et par'suite la'série B-jl,... Bjn représente l'une quelconque des lignes du tableau. La dernière ligne du tableau source de la figure î" est désignée par Bkl„.i Bkm».« Bkn car, dans la présente description-k désigne le nombre de -lignes et aussi la dernière ligne du tableau. 70 36587 7 2065561 10 Bien que la figure 1 représente des segments de contrôle avec trois séries de codes de contrôle, l'invention peut n'en comporter que deux. L'un des deux doit être une série de codes de contrôle de diagonale. La détermination d'une série de codes, de contrôle de colonne étant plus simple, elle sera examinée en premier. Chaque élément binaire de contrôle dans une colonne désigné de façon générale par Cm est déduit de la formule générale ci-après. Cm = 1ET© Bjm 3=1 Cette formule générale peut être mieux comprise grâce à un exemple particulier.. Dans ce but, un tableau 3 x 3 et un ensemble particulier de valeurs supposées est représenté ci-dessous. 15 Tableau 3 x 3 et valeurs affectées B11 B12 B13 1 0 1 B2î B22 B23 0 1 î B31 B32 B33 O 1 0 20 En écriture logiquerles trois éléments binaires de contrôle de colonne de l'exemple ci-dessus s'écrivent C1 « 'B11 @ B21 0 B31 25 C2 = B12 @ B22 @ B32 C3 = B13 (g B23 © B33 Le symbole plus entoure d'un cercle représente le "OU exclusif". A propos de la définition de C1 pour la première colonne, 30 il y a lieu de noter que l'élément binaire B11 est combiné avec B21 par un OU-exclusif et que le résultat de cette opération est ensuite combiné avec B31 par un QU-exclusif. Chaque opération OU-exclusif est effectuée selon la formule fondamentale ci-dessous. 35 A 0 B = A.B1 + A'.B La fonction ci-dessus .s '.interprèt§£omme. .suit : le OU-exclusif des signaux A et B a la valeur binaire DE ou 1 soit si A=1 et 70 36587 8 2065561 B=0 ce qui est représenté par le terme A.B', soit si A=0 et B=1 ce qui est représenté par le terne A'".B. Le signe prime (') désigne, l'état 0 d'une variable Booleene particulière. Par conséquent, le premier OU-exclusif de la définition de Cl peut s'exprimer : 5. . B11 0 B21 = B1 1 .B211 + B111 ,B21 Dans le tableau 3 x 3 de l'exemple ci-dessus, B11-1 et B21=0 ce qui entraine que le OU-exclusif qui en résulte a la valeur bï-10 naire 1. Dans cet exemple, le premier OU-exclusif doit ensuite être co'mbiné avec B31=0. La suite complète dés OU-exclusifs peut donc s'exprimer : . 15 (B11 @ B21) 0 B31 =. (B11 0 B21).B31' + (BU Q B21)I.B31 Avec les valeurs introduites dans le cas de llexemple particulier, la première fonction OU-exclusif a la valeur 1, et la valeur finale de Cl peut être déterminée en effectuant le second OU-exclusif entre,la valeur binaire. 1 et B31=.0« L*analyse précéden-20 .. te a montré que le résultat final, et par conséquent la valeur de CÎ est l'élément binaire 1. Un élément binaire dé contrôle du segment de contrôle de colonne a donc ainsi été déterminé dans un exemple particulier. De la même manière, il apparaît que l'élément binaire de contrôle C2 a la valeur binaire 0 et que l'élément bi-25 naire de contrôle C3 a également la valeur binaire 0. - L'élément binaire de contrôle de .colonne peut être considéré comme un élément binaire de parité de la colonne, car, selon la définition ci-dessus, il a la valeur binaire 1 si seulement une valeur ,1 est contenue dans la colonne, alors qu'il a la valeur O" 30 si deux valeurs 1 sont contenues dans la colonne. Bien entendu, cet-te analyse peut être étendue àu cas général dans lequel un élément binaire de contrôle de valeur 1'résulte d'un nombre impair de 1 dans une colonne, et un élément binaire de contrôle de valeur O. résulte d'un nombre pair de 1 dans une colonne. 35 Une expression de sommation permet une représentation concise de l'expression des différents éléments binaires de contrôle. Le signe : ' ' © ■ 70 36587 9 2065561 est introduit pour représenter une suite dradditions de OU-exclu-sifs. Les variables entières spécifiant la position de la ligne des éléments binaires sont additionnées pour donner la définition de l'élément binaire de contrôle de colonne : 5 j=k Cm = © B jm 3=1 L'expression générale à examiner ensuite est la définition .10 des éléments binaires de contrôle de diagonale. Pour une brève explication,. le cas examiné est celui de la diagonale gauche, représentée génériquement ici par DLm,.en se reportant de nouveau au cas particulier du tableau 3x3 considéré ci-dessus. Les définitions de DL1, DL2 et DL3 sont les suivantes ■ 15 • DL1 =-. B11 © B23 @ B32, DL2 = B12 Q' B21 Q B33, et DL3 = B13 Q B22 Q B31 20 II faut noter que dans le cas des définitions de DL1 et DL2f il y a Une permutation des éléments binaires. Dans le cas de DL1f le premier OU-exclusif est effectué entre B11 et B23. Le résultat de ce'tte opération est combiné par OU-exclusif avec B32La succession des colonnes' dans cette opération est : ï, 2, 3. Dans" ce cas, 25 „ la permutation est l'association de B11 autour du tableau. Cette association permettant le décalage peut être définie dans les termes de nombres modulo n qui vont être expliqués' maintenant» La règle générale d'utilisation d'un nombre de représenta-tioi^/modulo est que si„la somme ou la différence de nombres modulo 30 dépasse les limites de 1 à n, le résultat est corrigé en ajoutant ou en soustrayant n pour les valeurs qui sont 'respectivement au-dessous et au-dessus des limites. Ceci est illustré'par-les exemples suivants : (3+2)3 =(5)3=2 j (3-5l3=C-2)3='i r (1-1)3=(Q)3=3 35 Dans le premier cas, la limite n=3 est dépassée de 2 de sorte que n=3 est soustrait de 5 pour donner le nouveau nombre modulo 3 qui est 2. Dans l'exemple suivant, le résultat intermédiaire est (-2) qui est corrigé par addition de 3 pour donner 1 comme résul- 10 70 36587 2065561 -bat ;"et enfin la différence (1-1)5 donne 3" comme résultat. L'opération précédente peut être considérée également comme une fonction de décalage cyclique. L'opération (3+2)3 peut être considérée comme un décalage de deux à droite qui s'effectue : 3» 5 1,2. Le cas (3-5)3 est un décalage de 5 à gauche qui s'effectue î 3,2,1,3,2,1. Le cas (1-1)3 est un décalage de 1 à gauche qui s'effectue : 1*3. Après avoir défini les séries-fondamentales de Oïï-exclusifs et une technique pour spécifier les positions d'éléments binaires 10 dans un tableau sous forme modulo n, il est possible d'énoncer les expressions génériques -des diagonales gauche et droite. iï=k LLm = ^T~ 0 Bj(ni-j+l)n 3=1 15 ' \ ' La figure 2 montre la manière d'appliquer les définitions génériques des diagonales à Un cas particulier. Il faut noter que la figure 2 est représentée comme une. série de lignes; sans fin ou circulaires pour indiquer la nature modulo n de - chaque segment de 20 données dans son utilisation selon la présente invention. Pu fait que dans-la figure 2,--k est inférieur à n, il y a quatre diagonales bien qu'il n'y ait que 3 lignes. Il n'y a donc pas d'e diagonale d'extrémité à extrémité comma .dans le" cas où k=n« En se reportant à la formule générique de LLm définie ci-dessus, il 25 est possible de définir les séries de diagonales gauches en commençant pour" chaque définition de diagonale par l'un des éléments binaires de la première ligne.- Afin de formuler une technique précise de définition; il est supposé-que la première série de OU-exclusifs définissant DL1 commence par B11 ; la seconde série de OU-exclusifs 30 définissant DL2 commence par B12 ; la troisième BL3 commence par f B13'; 'et la quatrième DL4 commence par B14. Il est bien entendu qje l'invention n'est pas limitée à cette définition du commencement. après là formule générique de .DLra, il est possible- d'effectuer' les substitutions nécessaires" pour obtenir les séries de dia-35 gonales gauches. En partant dé l'élément binaire B11 il a été établi que' la valeur initiale de i est î et également que la valeur 'initiale pour la position de la colonne n est 1..La sommation spécifie 'qu'il faut augmenter la valeur de g' pour déterminer le terme suivant dans la série, tout en maintenant la valeur de m=1. Cette 70 36587 n 2065561 substitution donne B2(t-2+1)4=B24 où j=2. Le terme suivant est trouvé en faisant j=3 et en maintenant encore nt=l comme suit B3(1-3+1}4=B33 5 ' Par conséquent, la série BL1 peut être définie - DL1=B11+B24+B33 10 De manière similaire, les autres séries de diagonales à gauche peuvent être définies comme suit ï DL2 = B12 + B21 + B34 DL3 = B13 + B22 + B3.1 15 DL4 = B14 + B23 + B32 En utilisant la définition générique des séries de diagonales à droite il est possible d'énoncer les définitions particulières an cas de la figure 2 : DR1 = B11 + B22 + B33 DR2 = B12 + B23 + B34 DR3 II bd —J» + B24 + B31 DR4 = ' B14 + B21 + B32 25 ' Après avoir examiné la technique générale de codage des segments de contrôle selon l'invention, il y a lieu de se reporter à la figure 3 afin d'examiner une forme particulière de codage. Il faut noter que chaque élément binaire dans chaque segment de con-30 trôle peut être déterminé par un procédé manuel en parcourant les diagonales et les colonnes du tableau en passant par les éléments binaires appropriés. Si dans une diagonale ou une colonne le nombre d 'éléments binaires de valeur T est impair, l'élément binaire de contrôle correspondant qui est introduit est un 1, et si ce nom-35 bre est pair, l'élément binaire de contrôle correspondant est un 0. Bien entendu, une variante évidente consisterait à utiliser un 0 pour représenter un nombre impair d'éléments binaires 1 dans une diagonale ou une colonne, et un 1 pour représenter un nombre pair d'éléments binaires 1. L'une ou l'autre définition tombe dans le cap- 70 36587 12 2065561 dre général de l'invention. Avant d'examiner le dispositif destiné à effectuer le codage de l'élément binaire de contrôle décrit ci-dessus, il est utile d'examiner l'utilisation possible des segments de contrôle quand 5. ils sont codés. Dans un but explicatif, il est supposé qu'après que les données d'origine ont été analysées de la manière décrite ci-dessus, les trois segments de contrôle sont joints aux données d'origine . Ce nouveau groupe peut alors être traité comme le tableau d'origine, augmenté de trois lignes de segments de contrôle pouvant 10 indiquer si l'un des segments de données du tableau contient des erreurs. Ceci s'effectue de façon très simple. Lorsque les données d'origine sont lues dans le groupe après l'introduction des segments de contrôle, le codage des segments de contrôle est effectué à nouveau d'après la méthode décrite ei-dessus. 15 L'étape suivante du procédé de détection d'erreur consiste à comparer le nouvel ensemble de segments de contrôle avec l'ensemble initial de segments de contrôle qui a été joint au tableau d'origine. Cette comparaison peut s'effectuer par l'exécution d'une série de OU-exclusifs entre les positions des- éléments binaires des 20 anciens et des nouveaux segments. En supposant qu'une approche par OU-exclusifs soit faite, le résultat serait dans 1'exemple précédent trois segments d'erreur tels que EDLm, ECm et EDRm correspondant 'respectivement aux codes de contrôle d'origine de DLm, Cm et DRm et à leurs nouveaux codes de contrôle» 25 Des formes typiques d'erreurs peuvent être examinées en dé tails en se reportant aux figures 6. Dans ce cas, il y a au moins deux divergences entre les anciens et les nouveaux codes de contrôle. Par conséquent, des codes d'erreur doivent être produits pour être analysés selon une autre méthode faisant partie de l'invention 30 pour déterminer si ces erreurs se gont produites dans un seul segment de données. Lorsque cette seconde méthode selon l'invention a été appliquée, il est possible d'appliquer un troisième procédé capable de corriger une f orme c omplexe d'erreurs s'il est souhaité de déterminer avec un haut degré de confiance si toutes les erreurs 35 se trouvent dans un segment de données. La figure 4 montre comment la technique de codage selon l'invention peut être appliquée à l'aide d'un dispositif très simple. Le fonctionnement du dispositif est examiné dans son Utilisation-avec le format de données d'origine du type représenté par la fi- 70 36587 13 2065561 gure 5a, où il est supposé que tous les éléments binaires de. la donnée d'origine apparaissent successivement en commençant par B11 et en continuant avec le premier segment de données et ensuite de la même manière avec les segments de données successifs» 5 Selon la figure 4, un premier registre désigné par RO est utilisé pour recevoir les séries d'éléments binaires des données d'origine et pour les décaler successivement de la droite vers la gauche jusqu'à ce que tous les n éléments binaires d'un segment de données apparaissent dans le registre. 10 la figure 4 montre trois autres registres R1, R2 et R3 uti lisés pour produire les trois segments de contrôle mentionnés ci-dessus. Ces registres sont d'abord placés tout à zéro pour mettre en place la convention d'éléments binaires de contrôle d'après laquelle un élément binaire de contrôlé de valeur 1 résulte d'un nom-15 bre impair de 1 et un élément binaire de contrôle de valeur 0 résulte d'un nombre pair de 1. L'opération est donc effectuée d'après les formules de séries de OU-exclusifs décrites- précédemment. Les positions d'éléments binaires du registre RO sont désignées par Bj1... Bjm... Bjn pour marquer leur correspondance avec 20 les éléments binaires des segments de données successifs. Les positions. d'éléments binaires des registres RI, R2 et R3: sont repérées de façon à correspondre à la représentation de l'élément binaire de contrôle final devant y être contenu. _ Le fonctionnement" et la logique de la figure 4 seront décrits 25 en se reportant à l'organigramme de codage, et en supposant- que le format des données soit celui de la figure 5a. Comme il a déjà été indiqué,les registres sont mis à zéro au début de l'opération. Il faut noter dans l'organigramme de codage une fonction supplémentaire consistant en la_mise à zéro d'un compteur désigné par CNT, 70 36587 14 2065561 I. Organigramme de codage 70 36587 15 2065561 Au point la,la fonction est définie comme RO=Nouveau Segment de Donnée,qui est le segment d'origine B11... B1m... Bln, ou la . première ligne à la première entrée. Trois fonctions OU-exclusif sont reliées au point d'entrée 5 Ib î RI = R1 ©RO ; R2 = R2 ©RO ; et R3 = R30RO. A la fin de cela, RO est simplement introduit comme premier segment dans R1, R2 et R3 qui étaient initialement à zéro. A la suite de ces fonctions OU-exclusif, le registre Rt est décalé cycliquement à gauche d'une position (décalage modulo n) et 10 le registre R3 est décalé cycliquement à droite d'une position, le registre R2 correspondant à la série d'éléments "binaires de contrôle de colonne n'est pas décalé. Les décalages cycliques à gauche et à droite correspondent respectivement aux opérations nécessaires pour trouver DLm et DRm comme indiqué précédemment. 15 Après avoir terminé une opération logique indiquée ci-dessus, le dispositif augmente le compteur de : ONT = CHT + 1 et écrit ou transmet le contenu de RO dans une mémoire ou autre dispositif d'utilisation de données en vue d'une utilisation possible. Un essai est effectué par ONT = k, pour déterminer si tous 20 les segments ont été lpgiquement combinés. Il en résulte un retour à la si la réponse est SON, ou une entrée dans le du segment de contrôle écrit si la réponse est OUI indiquant la fin de l'opération' de codage. L'automatisation spécifique de la partie machine nécessaire 25 à la réalisation de la figure 4 découle de façon évidente de la description ci-dessus. Une première série.de portes OU-exclusif déjà définies sont commandées suivant la méthode de codage selon l'invention pour produire dans le registre R1 les éléments binaires de contrôle de diagonale DL1... DLn. Une deuxième série de por-30 tes OU-exclusif sont commandées pour produire les éléments binaires de contrôle de colonne CI... Ch., dans laquelle le registre R2 reçoit les éléments binaires intermédiaires et n'est pas décalé. Une troisième série de portes OU-exclusif sont utilisées pour produire les éléments binaires intermédiaires dans le registre R3 où le ré-35 sultat final est la série DRT-... DRn. Le mode de commande de la partie machine nécessaire pour accomplir les opérations représentées par 1'organigramme de codage apparaît également de façon évidente. Un premier mode est établi correspondant aux étapes initiales, un second mode est établi pour 70 36587 16 2065561 la commande de la boucle, à partir de la, et un troisième mode est établi après l'essai de non retour à la pour commander les opérations qui commencent en-le. * Une importante variante de' l'invention sera maintenant exa-5. minée en se reportant à la figure f. Il a été supposé, seulement dans un "but de simplification que," lorsque les éléments binaires de chaque segment de donnée qéont lus dans le format de la figure 5a, ils deviennent l'une des lignes du tableau défini par la figure 1. Par conséquent, n éléments binaires ont été supposéqéxister dans 10 chaque segment de données. Le concept élargi de l'invention ne^e limite pas à cela. Les segments de données peuvent aussi bien être considérés-comme s'étendant le long d'une colonne du tableau dans lequel il yak éléments binaires dans chaque segment et un total de n segments. 15 Par conséquent, il est important de noter ce qui -suit dans l'interprétation des sommations génériques déduites précédemment. Si un segment de données définit une colonne plutôt qu'une ligne, \ Bjm doit être interprété comme l'élément binaire de la" jeme colon-\ ne et de la meme ligne. La restriction suivant laquelle k doit être 20 inférieur ou égal à n doit encore s'appliquer car si k est plus grand que n, la position précise d'un segment de données dans lequel toutes les erreurs se trouvent, ne peut pas être- déterminée. 'La structure de la figure 4 ne fonctionne pas dans le cas qui vient d'être indiqué du concept par colonne des segments de données. 25 Dans ce cas, les éléments binaires de contrôle des colonnes sont produits comme des éléments binaires de. parité séparés de la même manière que les séries d'éléments binaires de parité conventionnels déjà connus. Bien que la méthode générique selon l'invention s'applique aussi bien aux segments de la ligne qu'aux segments de co^ 30 lonne, il faut noter la grande difficulté de la technique des dispositifs de codage des diagonales dans le cas de segments de colonne. Par conséquent, bien que le procédé selon l'invention n'y soit pas limité, la pratique d'utilisation du dispositif selon l'invention spécifie que les segments de données soient définis comme cor-35 respondant aux lignes du tableau. Les figures 5b et 5c montrent des caractères typiques et des formats de mots de données pouvant constituer les données d'origine. Le format de la figure 5b montre des caractères à 8 éléments binaires et un ensemble total de 8 caractères, bien que dans la pra 70 36587 " 2065561 tique réelle on utilise des longueurs différentes et le plus souvent "beaucoup plus de caractères par ensemble. Du fait que 8 caractères à 8 éléments binaires ne donnent que 64 éléments binaires au total, et que selon l'invention il est spé-5 cifié que n doit de préférence (comme il sera expliqué ci-dessous) contenir un nombre premier d'éléments binaires, trois éléments binaires de valeur Q sont supposés remplir largement lès conditions; Selon, l'invention, l'ensemble de 8 caractères et de 3 éléments binaires mis à 0 est défini comme un segment de données,'de 10 sorte que le tableau source complet peut contenir 67 ensembles de ces groupes de segments. Dans le cas du format supposé de la figure 5c, chaque'mot contient 32 éléments binaires et 2 mots sont supposés faire partie d'un segment de données,de sorte qu'à nouveau 3 éléments binaires Q 15 sont ajoutés pour obtenir le nombre premier n = 67. D'organigramme de détection montre la méthode de lecture du contrôle selon l'invention. Il faut noter que les étapes lia et Ilb correspondent respectivement aux étapes la et Ib de l'organigramme de codage. Il est à nouveau supposé dans cette explication que le 20 format utilisé est celui de la figure 5a, que les segments de données constituent les lignes du tableau et que la partie machine de la figure 4 peut être utilisée dans le fonctionnement automatique selon l'invention. 1 c^-° ) | RI- R2-R3-0 | I RO=Nouveàu segment de données ) (irâ X I RI 'm©RO 1 R2 - R2 © RO Decalage N cyclique a gauche RI | R3 « R30RO —x— | ÇNT»cKjf+ I ' 1 i I RQ-blm I [ RI » R10RO » EOLm ~1 | Ro'cm 1 t I' R2=R2©RO»Eem 1 ^ j RO=DRm 1 | R3=R3tf>RO = EORm | C— Décalage qycliqvue a droite ,B3 f CNT- k"? (lia v trni y ^ IX, Organigramme de détection „ ombien de registres\ ,, R1-R2-R5 contiennent F tous les zéros ? J 2 ou 3 ' ' ■ "q S - N OUI c î>k? y- " WÔN £773 Transmettre 1-indice de ligne "j" 2-contenu de R2 Décalage cyclique a gauche R1 u Décalage „ cyclique a droite R3 O U> O Cn 00 ^■4 oo K> O O-en en c- 70 36587 2065561 Après l'accomplissement de k cycles des étapes lia et 11b, les registres R1, R2 et R3 contiennent trois nouveaux segments de contrôle. L'étape Ile est abordée avec trois fonctions OU-exclusif sur les ancien et nouveau DLm pour obtenir EDLm, sur les ancien et 5 nouveau Cm pour obtenir ECm, et sur les ancien et nouveau DRm pour obtenir EDRm. Ces segments d'erreur peuvent être introduits dans les registres R1,.R2 et RJ exactement de la même manière dont toutes les autres fonctions OU-exclusif ont été formées. Ayant d'examiner le fonctionnement particulier de l'étape Ile, 10 il est utile d'étudier les cas d'erreurs représentés par la figure 6. L'analyse de ces cas d'erreurs explique également le choix préférentiel d'un nombre premier pour n. La figure 6a montre un tableau 5x5 avec un groupe d'erreurs dans la même colonne. La correspondance entre les erreurs de données 15 et les.éléments binaires de contrôle est déterminée par l'utilisation de ÈLO... E-L4 pour les éléments binaires d'erreurs à gauche, EC3 pour l'erreur de colonne (dans cet exemple toutes les erreurs sont supposées être dans la colonne 3) et ERO... ER4 pour les éléments binaires d'erreur à droite. . 20 II faut immédiatement préciser que s'il se présente plus d'une des erreurs montrées dans la figure 6a, la comparaison d'égalité des éléments binaires entre l'une quelconque des diagonales et le groupe d'erreur de colonne devient impossible car chacune des diagonales contient "deux éléments binaires 1 ou davantage représentant 25 les erreurs. Il est supposé dans la description ci-après que seulement une des erreurs de données EDO... ED4 peut exister à un moment donné de sorte que la localisation, selon l'invention, de ce segment de données est alors possible "ainsi qu'il va être examiné maintenant. 30 Si EDO est l'erreur présente, les trois segments d'erreurs sont tous les mêmes de sorte que la méthode de correction selon l'invention spécifie que la ligne 1 ou 0 (dans un but de désignation d'erreur .uniquement) contient l'erreur et que cette, dernière peut être corrigée selon la forme du code d'erreur de'colonne. 35 - Dans chacun des autres cas la valeur du décalage cyclique à gauche pour le code d'erreur de diagonale gauche et du décalage cyclique à droite pour le code, d'erreur de diagonale droite, nécessaire pour développer trois -codes identiques est également l'unique désignation de la ligne dans laquelle l'erreur se trouve. Done, EL3 Ito doit être décalé cycliquement trois fois vers la gauche pour être 70 36587 20 \ 2065561 aligné avec la position .de la colonne qui contient EC3, et ER3 doit être décalé de trois positions vers la droite,(dans ce cas, le décalage cyclique n'est pas nécessaire) pour obtenir l'alignement. Par conséquent, dans le cas où une seule ligne, ou segment 5.- de données, contient une erreur, le nombre de décalages uniquement désigne la position dans laquelle se trouve l'erreur. Jusqu'ici n'a été considéré que le cas d'une seule erreur dans un segment de données ou ligne. La même méthode s'applique à n'importe quel nombre d'erreurs jusqu'à n moins une (rt-1) erreurs 10 dans un segment de données ou une ligne. Dans la figure 6b, un groupe' d'erreurs est donc indiqué dans la quatrième ligne d'un tableau 7x4. Par conséquent, trois décalages à gauche des éléments binaires de EDL, et à droite des éléments binaires de EDR font apparaître un triple accord entre les trois registres et indiquent par 15 conséquent que la correction doit être faite dans la quatrième ligne du tableau. Si la longueur de registre contient un facteur tel que 2 et que le groupe d'erreurs dans un segment contient un sous-groupe répétitif comme le montre la figure 6c dans laquelle n est égal à 6 20 (3 x 2) et k est 6, .une indication unique du segment dans laquelle apparaît l'erreur est' impossible. Gela vient du.fait que la triple égalité apparaît un nombre de fois correspondant au nombre de fois dont'se répète le sous-groupe si n contient ce nombre comme facteur. •Par conséquent^ il est souhaitable que la correction d'erreurs se-25 Ion l'invention se fasse avec un nombre premier pour n de sorte - qu'il ne puisse y .avoir aucun facteur permettant une comparaison d'égalité pour, quelque sous-grou.pe que ce soit. Dans la figure 6e, les trois codes d'erreurs contiennent trois éléments binaires d'erreur mais line triple égalité est représentée 30 par les décalages 0 à 4. Cela illustrela technique d'essai de grau- ( pes selon l'invention grâce à laquelle un haut degré de confiance peut accompagner un signal ou décision désignant la donnée à corriger. - L' organigramme de détection fait apparaître, une étape parti-35 culière désignée par Ile. Le but de la séquence démarrant avec Ile est.de combiner par OU-exclusif les anciens segments qui étaient introduits d'après, la méthode de: codage, selon l'invention avec les nouveaux segments .qui se trouvent maintenant dans Rt, R2 et R3. Ceci s'effectue successivement par la lecture de DLm dans RO pour la 70 36587 21 2065561 combinaison pour OU-exclusif avec Ht, puis la lecture de Cm dans RO pour la combinaison par OU-exclusif avec R2, enfin par la lecture de DRm. dans RO pour la combinaison pour OU-exclusif avec R3. Le résultat final à la fin de la séquence commençant en Ile est que 5 trois codes d'erreurs-: EDIbl, ECm et EDRm se trouvent respectivement dans les registres R1, R2 et R3. l'analyse des codes d'erreurs ainsi produits commence à l'étape Ild dans laquelle il est déterminé d'abord si R2, qui correspond à ECm, contient tous les 1. Si la condition "tous les 1" se 10 présente, un branchement immédiat est fait sur la sortie "impossible à corriger" comme le montre l'organigramme de détection en Ile, Si au moins un élément binaire d'erreur est à 0 dans ECm, la recherche possible d'erreurs se poursuit avec la première comparaison de R1, R2 et R3 pour déterminer si tous les registres contiennent tous 15 les 0. Cette étape est désignée par Ile. Il y a trois sorties à partir de l'étape Ile ; si seulement l'un des registres contient tous les zéros, la sortie se fait en "impossible à corriger" car il est évident qu'aucune triple comparaison n'est possible. Si deux ou trois des registres sont tous à 0, 20 la donnée d'origine est considérée comme correcte et la sortie correspondante est faite. Si aucun des codes d'erreurs est tout à 0 la sortie se fait en Ilf pour effectuer la série des triples comparaisons expliquée ci-dessus dans quelques exemples par. les figures 6» L'étape'IIS ne comporte que la mise à 0 de l'indice de ligne 25 . par 3=0. La triple comparaison est faite en Hg par R1=R2=R3. Si la réponse est OUI à n'importe quel moment, la sortie se fait en "à corriger". Quand la réponse est HOU, l'entrée se fait au point Ilh avec j augmenté de t par 3=3+1 et ensuite le nouvel indice de ligne (j) est comparé avec la limite k par l'essai j > k» 30 Si l'indice de ligne augmenté j dépasse celui de la dernière ligne k, la sortie se fait en "impossible à corriger", car aucune triple égalité n'a été trouvée. Si la limite k n'est pas dépassée, le registre R1 est décalé à gauche et le registre R3 est décalé-à droite et le programme retourne au point Ilg pour une autre compa-35 raison. Il faut noter que la sortie "à corriger" entre au point Ili pour line fonction par laquelle l'information nécessaire à la correction réelle est sortie, c'est-à-dire : l'indice de ligne 3 qui désigne le segment de données dans lequel se trouve l'erreur, et le con-h 70 36587 22 2065561 ' RBYEBDICATIOKS 1. Procédé de codage de segments de codés de contrôle à partir de données d'origine organisées en k segments de n éléments binaires chacun, où chaque élément binaire d'un segment de données a 5 une position qui est rapportée dans deux directions à n'importe quel autre élément binaire du même segment, et ehaque position constitue une position de colonne dans un tableau à k par n, caractérisé en ce qu'il comporte la production d'une première série de n éléments binaires de contrôle constituant une série correspondante de pre- 10 mières suites de fonctions OU-exclusif suivant les colonnes dudit tableau, et la production d'une seconde série de n éléments binaires de contrôle constituant une série correspondante de secondes suites de fonctions OU-exclusif suivant des diagonales dudit tableau dans lequel une diagonale est définie comme une série de po- 15 sitions adjacentes dans des lignes successives du tableau suivant une direction constante pour toutes les diagonales. 2. Procédé selon là revendication î-, caractérisé en ce que lesdites données d'origine sont représentées par les séries (B1l..i B1m».. B1n)., ... (Bj1... Bjm... Bjn), ... (Bk1... Bkm... Bkn) où j 20 peut représenter l'une quelconque'des positions de ligne de 11 k et m peut représenter l'une quelconque des positions de colonne de 1 à n, et ladite première série d'éléments binaires de contrôle est définie par j=k ' " 25 . Cm = 2Z 0 Bjmr " 3=1 3* Procédé selon la revendication 2, caractérisé en ce que ladite seconde série d'éléments binaires de contrôle est définie 30 par - ' . > DLm "= ^EL 0 B3(m-j+1)n ' 35 4. Procédé selon la revendication 2j caraetérisré en ce que ladite seconde série d'éléments binaires de contrôle est définie par . 3=* . " DRm = @ B3(m+3-î)n 3=1 70 36587 23 2065561 5. Procédé selon la revendication 1, caractérisé en ce que n est un nombre premier, ce qui élimine toute possibilité d'ambiguïté dans'les codes de contrôle. 6. Procédé selon la revendication 2, caractérisé en ce que 5 deux formes de ladite 'seconde série d'éléments binaires de contrôle sont produites, étant définies par 3=k BLm = 0 Bj(m-3+t )n et j=î 10 BRm = V @ B3(nri-j-l)n 3=1 15 7. Procédé de détection d'erreurs dans des données d'ori gine où l'origine comporte au moins deux segments de données de contrôle contenant chacun n éléments binaires, l'un desdits segments de données de contrôle étant rapporté auxdites données d'origine comme une série de suites de fonctions OU-exclusif suivant des 20 diagonales d'un tableau déduit desdites données d'origine où une "diagonale est définie comme une série de positions adjacentes, dans des lignes successives du tableau dans une direction constante pour toute's les diagonales, caractérisé en ce qu'il comporte la production d'un groupe de nouveaux segments de données de contrôle cor-25 respondant respectivement auxdits segments de données de contrôle, l'accomplissement de la fonction OU-exclusif entre l'un desdits segments de données de contrôle et l'un desdits nouveaux segments de données de contrôle développé suivant les diagonales du tableau, l'accomplissement de la fonction OU-exclusif entre ledit autre seg-30 ment de données de contrôle et l'autre desdits nouveaux segments de données de contrôle, ce dont il résulte deux segments d'erreur dans lesquels l'existence d'éléments binaires non zéro représente la présence d'une erreur. 8. Procédé selon la revendication 7, caractérisé en ce qu'il 35 comporte des étapes de correction aussi bien que de détection, ladite origine comportant trois segments de données de contrôle", un segment de contrôle de diagonale gauche, un segment de contrôle de diagonale droite et un segment de contrôle de colonne, le procédé comportant trois étapes de production de code„ d-' erreur effectuant « 70 36587 24 2065561 le OU-exclusif nouveau et celui d'origine entre les deux segments de contrôle de diagonale gaucher les deux segments de contrôle de diagonale droite et les deux segments de contrôle de colonne pour déduire trois segments d'erreur,' erreur à gauche, erreur à droite 5 et erreur de colonne, les étapes de comparaison desdits segments d'erreurs avec les décalages cycliques successifs à gauche et à droite desdits segments d'erreur à droite et à gauche jusqu'à ce qu'une triple égalité se produise ou que k comparaisons soient effectuées sans qu'une triple égalité soit trouvée, et une étape de 10 comptage.des comparaisons faites avant qu'une triple égalité soit trouvée pour indiquer un indice de ligne. 9. Procédé selon la revendication 7, caractérisé en ce que ladite origine comporte trois anciens segments de données de contrôle D2m, Cm et DRm et dans lequel trois nouveaux segments de don- 15 nées de contrôle correspondânt respectivement auxdits anciens seg- - " - . / ments de données de contrôlé sont produits et désignés par HDLm, NCm et HDRm, le procédé comportant' les étapes d'accomplissement de fonctions OU-exclusif î EDLm = DLm Q NDLm, ECm = Cm KCm et EDRm = DRm HDRm, - 20 10. Dispositif pour coder des segments de codes de contrôle à partir de données d'origine organisées en k segments de données de n éléments binaires chacun, dans lequel la position cyclique dans un segment de données est représentée par un nombre modulo n, caractérisé en ce qu'il comporte un premier dispositif pour produi-25 re une série de n éléments binaires de contrôle sous forme d'une sommation de OU-eiclusifs .• ' 3=k ' - - Cm = @ Bjm ' 3=1 - 30 , et un second dispositif pour produire une série de-n éléments binaires de contrôle sous forme d'une sommation de 0U-ex;clusifs , 3=k ï)IiRm = @ BjCaffj+l)' • 35 " d=V' : ' ' : n 11. Dispositif selon la revendication 10, caractérisé en ce que n est un nombre premier. 70 36587 20Ô5S61 12. Dispositif selon la revendication 10, caractérisé en ce que ledit second dispositif comporte deux sous-ensembles de sommation de OU-^exclusif s, le premier produisant la série d'éléments binaires de contrôle définie par 5 ' ; j=k , . . . "DLm =: @ Bj(m-3+1)n j=î . et le second produisant la série d'éléments binaires de contrôle 10 définie par 3=k DRm. .= @ BjCmfj-l) • î "n 15 13. Dispositif pour détecter et corriger des erreurs dans un système dans lequel les données d'origine contenant k segments de données de n éléments binaires chacun sont enregistrées avec des segments de contrôle DLm, Cm et DRm., caractérisé en ce qu'il cgeh-porte un premier dispositif pour produire-des nouveaux segments de 20 contrôle NDLm, NCm et ÏÏDRm, un second dispositif pour produire des segments d'erreur EDLm, ECm et EDRm constituant des fonctions OU-exclusif respectives entre DLm et HDLmr Cm et NCm, et DRm et NDRrn, un troisième dispositif pour comparer EDLm, ECm et EDRm, un quatrième dispositif» pour décaler cycliquement à gauche EDLm et pour 25 décaler cycliquement à droite EDRm, et un cinquième dispositif pour compter le nombre de comparaisons effectuées par ledit troisième dispositif, ledit troisième dispositif fonctionnant de façon à répéter la comparaison entre les segments d'erreur après chaque décalage cyclique jusqu'à ce qu'une triple égalité soit trouvée ou que 30 k comparaisons aient été effectuées. 14. Dispositif selon la revendication 13, caractérisé en cô que'n est un nombre premier. 15» Dispositif selon la revendication 13, caractérisé en ce que le .second dispositif-comporte trois registres RI, R2 et R3 pour 35 produire EDLm, ECm et EDRm respectivement.