FR 2030129 A1 19701030 FR 6942814 A 19691211 $9 42814 1 2030129 La présente invention concerne la correction d'erreurs, et, plus particulièrement, la correction d'erreurs multiples, au hasard de données parallèles. La conception de codage pour la correction d'erreurs dans des messages de données est exposée dans le brevetUS 2 552 629 "Error Detecting and Correcting •3* 5 Systems" par R.W. Hamming et al." La disposition de ces codages est généralement connue sous le nom de codes de Hamming» Ces cûdes nécessitent qu'un nombre minimal de bits de vérification ou de bits de parité soit ajouté aux bits du message pour produire alors un message codé qui peut être décodé de manière à corriger les erreurs introduites durant l'emmagasinage ou la transmission. 10 Par suite de récents développements, des erreurs multiples peuvent également être corrigées dans des codes cycliques en utilisant des circuits de complexité raisonnable. Cependant, l'agencement de ces codes fait intervenir normalement des retards importants lors du décodage. D'habitude les codes de correction d'erreurs ont des agencements de véri-15 fication de parité qui sont strictement fonction du nombre d'erreurs à corriger et du nombre de bits de données. De manière à pouvoir augmenter la possibilité de correction des erreurs d'un code spécifique il faut généralement avoir recours à une nouvelle conception. La présente invention fournit un agencement de circuits de vérification de parité construit sous forme modulaire de sorte 20 Que chaque module, en liaison avec les bits de vérification associés, va ajouter une possibilité de correction d'erreurs supplémentaire. Un objet de la présente invention consiste à fournir un nouveau système perfectionné de correction d'erreurs multiples. La présente invention s'applique à la transmission et à l'emmagasinage de données et, plus particulièrement, 25 aux systèmes de traitement de données en parallèle tels que des mémoires de calculateur de type numérique, des trajets de données et autres trajets importants qui nécessitent l'empêchement d'introduction d'erreurs à un niveau élevé. Par suite du prix réduit et de la vitesse accrue rendus possibles par le développement des circuits intégrés, l'addition de systèmes de correction d'erreurs 30 dans un calculateur est dévenue possible sur le plan pratique. Une forme simple de détection d'erreurs dans une mémoire, ou tout autre appareil de traitement de données, peut être assurée en doublant les positions d'emmagasinage pour chaque bit. Une erreur qui apparait dans une seule position peut être détectée en tant que non coïncidence des bits correspondants du mot. 35 Si trois positions, ou plus, sont fournies à chaque bit, il est possible de corriger les erreurs; si une erreur apparait dans une seule position, la valeur correcte peut être reconnue à partir de deux bits valables pour la même position. En règle générale, lorsqu'un bit est produit un nombre de fois impair, les erreurs qui apparaissent suivant un nombre inférieur à la moitié du nombre 40 de bits peuvent être détectées en acceptant la valeur majoritaire qui est cor 69 42814 2 2030129 recte. Bien entendu, lorsque plus de la moitié des bits est incorrecte, l'erreur ne va pas être corrigée. Tous- les systèmes de correction d'erreurs utilisent le principe d'engen- * ■ drer des bits de données redondants. Cependant, le-système qui consiste à y simplement transmettre sans fin le même bit, est rarement utilisé étant donné qu'il a été conçu des systèmes plus efficaces. Ces systèmes seront appelés codes car les bits de données d'origine sont codés pour engendrer un mot plus long (qui va être appelé message3 dans lequel quelques uns des bits sont fonction de plusieurs bits de données. L'information dé chaque bit de données 10 apparait en tant que fonction de plusieurs des bits de message. Le message est décodé pour former des bits de données d'une manière telle qu'une erreur dans un bit du message peut être détectée ou corrigée à partir de l'information dans d'autres bits du message. Les codes de correction d'erreurs sont communément identifiés par trois 15 nombres qui peuvent être généralisés comme étant (n, k,t, ). Ces termes définissent, respectivement le nombre de bits de message, le nombre de bits de données et le nombre d'erreurs qui peut être corrigé dans chaque bloc du message. Par exemple, dans le code (45,25,2) qui sera décrit un message de 45 positions binaires représente 25 bits de données, et les erreurs dans deux 20 quelconques des quarante cinq bits du message peuvent être corrigées. Beaucoup de codes de correction d'erreurs peuvent être expliqués en fonction du circuit de vérification de parité bien connu qui détecte mais ne corrige pas les erreurs. Dans un système de vérification de parité, un bit supplémentaire est ajouté au mot de données pour signifier qu'il y a un nombre impair (ou un 25 nombre pair) de "uns" dans le mot de données. Dans la présente invention, les circuits de vérification de parité sont utilisés pour engendrer les bits de vérification et pour régénérer les bits de données pour le décodage. Par exemple,l'équation suivante de bits de vérification peut être engendrée 30 dans le codage : c. = d. + d. k i J Dans le procédé de décodage, cette équation s'écrit de la façon suivante : d. = c, + d. i k - j- 35 où c, = Kième bit de vérification k d. = i ième bit de données i ' , d. = j ième bit de d + = fonction OU exclusif J __ • La procédure utilisée dans le décodage et la correction d'erreurs consiste à Bngendrsr les 2t copies indépendantes de a en transformant certaines des i 40 équations de bits de vérification où le mot indépendant implique que les ê9 42814 3 2030129 équations en 2t utilisées pour engendrer les 2t copies de d^ ne contiennent aucune autre donnée ou aucun bit de vérification en commun» Ces 2t copies de plus le bit de données d^ d'origine lui-même sont envoyés dans un circuit majoritaire pour corriger zéro jusqu'à t erreurs. 5 Un objet de la présente invention consiste à fournir un système de codage des données en parallèle dans un système de traitement de données et un agencement de décodage pour les données codées qui, à eux deux corrigent automatiquement les erreurs introduites dans les données. Un autre objet de la présente invention consiste à fournir un appareil de 10 codage et de décodage qui fonctionne à une très grande vitesse et qui peut être fabriqué de sorte que chaque possibilité de correction d'erreur successive puisse être additionnée en utilisant une technique de fabrication modulaire. Un autre objet de la présente invention consiste à fournir .une nouvelle 15 catégorie de codes de correction d'erreurs,. Un autre objet de la présente invention consiste à fournir une nouvelle catégorie de codes de correction d'erreurs qui soit capable de corriger t erreurs au hasard sur une longueur de données k avec pas plus de 2mt bit?, de 2 vérification où m est supérieur ou égal à k et où m est un nombre entier. 20 Un autre objet de la présente invention consiste à fournir un système de correction d'erreurs capable de corriger des erreurs introduites dans le circuit de décodage. Un autre objet de la présente invention consiste à fournir un procédé de 2 codage et de décodage d'un message ayant m bits de données. 25 En bref, un système de correction d'erreurs multiples au hasard est conçu pour corriger des messages de k D'autres objets, caractéristiques et avantages de la présente invention, ressortiront de la description qui va suivre, donnée à titre d'exemple non limitatif, en se reportant aux dessins annexés sur lesquels ; 40 La figure 1 représente un diagramme de fonctionnement général d'un sys êg 42814 4 2030129 tème de traitement de données comprenant un système de correction d'erreurs. La figure 2 représente un schéma d'un codeur pour obtenir les bits de vérification nécessaires. La figure 3 représente un schéma d'un décodeur pour le message codé en 5 provenance du circuit de la figure 2. La figure 4 représente deux groupes de quatre carrés latins orthogonaux pour cinq digits. La figure 5 représente un schéma montrant un décodeur pour le bit de données dQ capable de corriger trois erreurs et démontrant la conception de fabri-10 cation modulaire. La figure B représente un schéma montrant un codeur de longueur de données 23. La figure 7 représente un schéma montrant un décodeur de longueur de données 23. 15 La figure 1 représente un diagramme de fonctionnement général du codeur 12 et du décodeur 14 d'un système de traitement de données. Les données sont engendrées dans le processeur 16 et codées à sa sortie avant d'être mises dans la mémoire 10. Lorsque l'information doit être utilisée à nouveau, elle est décodée pour corriger toutes erreurs qui ont été' introduites durant la transmis-20 sion en direction ou à partir de la mémoire ou durant leur mise en mémoire. Les codes compris dans la présente invention sont ceux ayant une longueur 2 de donnée de K 1. S'il est souhaité coder un message de bits de données qui n'a pas une longueur de données égale à un carré parfait, un code carré latin de longueur 25 égale, au prochain carré supérieur est utilisé pour engendrer les équations de bits de vérification (ou de parité). Ensuite, le code peut être réduit à la longueur de données requise. Dans la description suivante,la procédure de construction est tout d'abord représentée pour des codes de carrés latins 2 de longueur m .Un latin de coté m est un agencement de m digits sous forme de 2 30 m sous carrés latin d'un carré latin d'une manière telle que chaque rangée et chaque colonne contiennent chaque digit rigoureusement une fois. En considérant le cas de correction d'erreur simple, qui est le cas le 2 plus simple les m bits de données représentés par les symboles d , d 0 1 d sont agencés dans un réseau de carrés latins ayant la forme suivante : K-1 35 °m+1 Cm+2 Cm+3 c2m C1 d0 d1 d2 dm-1 c„ d d „ d „ d 2 m m+1 m+2.... 2m~1 69 42814 5 2030129 ?3 2m 2irn-1 2m+2. 3m-1 C1Î m (m-1îm (m-1)to+1 d (m-1)m+2. d 2 . m -1 10 15 Les rangées de ce réseau sont consécutivement représentées par . c„ . Ainsi l'équation zm C.9 C0ICii«ii 1 2 m et les colonnes par c c - , m+1 m+2 du bit de vérification c^, i étant égal à 1, 2,.... 2m, est égale à la fonction OU EXCLUSIF des bits de données qui apparaissent dans sa rangée j il en est de même pour les colonnes du réseau. C'est-à-dire : °1 = m (m-1)m m+1 (m-1)m+1 Bd„ fid m+2 Sd [m-1)m+2 9.. « Sd m-1 9.. .Sd, 2m-1 fi.. .Sd m2-1 équations des rangées 20 25 m+1 ?m+2° '2m m-1 m+1 2m-1 6d 2m 6d, 2m+1 Bd. 3m-1 @... 8 d 3.. .Sd (m-1)m ) 8...Bd (m-1)m+1)équations ) des )colonnes ) ) m2-1 30 35 On peut voir que chaque bit de données apparait dans exactement deux de ces 2m équations de bit de vérification. En outre, les deux équations qui contiennent un bit de données commun ne contiennent aucun autre bit de données en commun. Ces deux observations sont des facteurs clés pour la formation du code. Par exemple, dg apparait dans l'équation pour c^ et cm+^« H est à remarquer que chacune de ces équations c^.... peut être simplement établie en réalisant les fonctions indiquées dans les équations. C'est-à-dire, chaque bit de données dans une équation est. envoyée .à un circuit OU EXCLUSIF. La sortie du circuit OU EXCLUSIF sera le bit de vérification correspon- 69 42814 6 2030129 dant c^... c^. Ceci forme la base du procédé de codage. Pour la compréhension du processus de décodage, il est à noter que les équations c^ et cm+^» par exemple, peuvent être écrites à nouveau sous la forme : dn = c. i d. i d. 8...8d „ 0 11 2 m-1 5 d„ 5 c . 8 d 1 d„ 8...8d, ... - 0 m+1 m 2m (in-1)m Il est à remarquer qu'aucune variable commune ne reste dans ces deux 'équations pour dQ. Ainsi, la présence d'une seule erreur dans les bits de données ou de vérification dn, d.,...d, c., c_,...C„ peut affecter au maximum une de ces 0 1 k-1 12 2m 1 q deux équations. En conséquence, dQ est donné de façon correcte par la fonction dn = Maj(dn,c.Sd Bd„B...Sd -,c .Sd Bd„ S...8dr ) u J 0 1 1 2 m-1 m+1 m 2m (m-1)m Cette dernière Équation est l'équation de majorité pour le décodage de majorité de la donnée dQ. Chaque bit de données qui a été codé peut être déterminé de la même façon. 15 La théorie fondamentale relative à la correction d'erreurs simple peut être étendue à la correction d'erreurs multiples à partir du groupe d'équations de bits de vérification pour une correction d'erreur simple. Cette extension s'applique également à la mécanisation ou à l'exécution des circuits de décodage. Les équations de bits de vérification supplémentaires sont engen- 20 drées conformément à la théorie des carrés latins orthogonaux. Les équations obtenues finalement ont la propriété que chaque bit de données apparait exactement dans les 2t équations de bits de vérification où t représente le nombre d'erreurs que le code est capable de corriger. Ces 2t équations contenant un bit de données commun ne contiennent aucun autre bit de données en commun. 25 Un carré latin d'ordre [dimension) m est une matrice carrée m x m des digits 0,1...,m-1 de sorte que chaque rangée et chaque colonne sont une permutation . de digits 0,1,...m-1 .jJn carré latin est utilisé pour engendrer le groupe de m équations de bits de vérification en superposant le carré latin au réseau de bits d'information donné dans l'équation (1). Ceci peut être considéré comme 30 "un masque" sur les bits de données. Les bits de données qui sont feecouverts" Par les mêmes digits du carré latin sont soumis ensemble à une condition OU EXCLUSIF afin de fournir l'équation de bits de vérification. Ceci fournit les m équations de bits de vérification. Si L^ et L2 représentés sur la figure 4 sont des carrés latins orthogonaux» le groupe de m équations de bits de véri- 35 fication produit de la manière mentionnée ci-dessus à partir de L^ et L2 va alors avoir la même propriété que les équations des rangées et des colonnes pour le cas de correction d'erreur simple. Cette propriété est que deux équations quelconques contenant un bit commun ne contiennent aucun autre bit commun et, en conséquence, peuvent être ajoutées aux équations de rangéee et 69 42814 7 2030129 de-colonnes pour le cas de correction d'erreur simple. Ainsi, chaque bit de données apparait dans quatre équations de bits de vérification et aucun autre bit de données commun n'apparait dans ces quatre équations et, en conséquence, un agencement du choix majoritaite de 3/5 peut être utilisé pour corriger toutes les erreurs doubles. En général, on peut utiliser un groupe de p (où p est égal à (m-1) si m est une puissance d'un nombre premier) carrés latins orthogonaux pour'engendrer mp équations de bits de vérification qui, lorsqu'elles sont ajoutées .aux ,2m équations de rangée et de colonne; fournissent m(p+2) équations de vérification de parité. Le code obtenu finalement peut corriger (p/2)+1 =t erreurs en utilisant t+1 parmi 2t+1 (ou portes de majorité). La construction modulaire du décodeur est déduite à partir d'extension exposée plus haut.Lorsqu'on passe de t corrections d'erreurs à t+1 corrections d'erreur il est seulement nécessaire d'ajouter 2m équations de bits de vérification au groupe déjà existant pour les t corrections d'erreurs. Ces équations supplémentaires sont obtenues à partir de deux carrés latins orthogonaux supplémentaires. La théorie des carrés latins orthogonaux est bien connue. Par exemple, on peut se reporter à l'ouvrage C.B. Mann, "Analysis and Design of- Experiments", Dover Publications, Inc., New York, 1949. Il y a des limites imposées sur le p-~£>re maximal de carrés latins orthogonaux d'ordre donné, (dimension). Ceci est fonction de m, la-dimension du carré latin. La description suivante est une application spécifique de la théorie dé- 2 crite ci-dessus a un code de latin .carré avec 5 = 25 bits de donnees. Ainsi, m = 5 et il y a quatre latins'orthogonaux d'ordre 5 comme le montre la figure 4. R, le nombre de bits de vérification est égal à 2mt, où t est égal au nombre d'erreurs à corriger. Ainsi, dans le cas d'un code de "correction unique," 2mt égal 10. Les bits de données dQ à dcomme cela a été décrit préalablement, sont agencés en réseau de carrés latins de la façon suivante. C en u7 B 9 10 C1 do d1 d2 d3 d4 C2 d5 d6 d7 dB d9 C3 d10 d11 d12 d13 d14 C4 d15 d16 d17 d18 d19 C5 d20 d21 d22 d23 d24 En soumettant ensemble à une condition OU EXCLUSIF les données dans les rangées c^... c,., et les données dans les colonnes correspondantes c^... 42814 B 2030129 ~ * j _ l'équation suivante, des bits de vérification c^...c^ peut s'écrire ; C1 = d0id1Sd2id3id4 3 équations de rangées C7 - dl9d68d119d1È,a21 o - d2Bd78d128d17»d22 équations de colonnes Le codeur des dix équations de bits de vérification peut être réalisé ên utilisant les entrées de portes OU EXCLUSIF représentées en 15,17 sur la figure 2. Bien entendu ces cinq portes OU EXCLUSIF peuvent être réalisées suivant de nombreuses façons différentes. La réalisation la plus directe bien connue se fait avec des portes ET et OU et des inverseurs. Les portes de majorité ou toutes autres portes bien connues peuvent être utilisées. Comme le montre un examen de ces équations de bits de vérification, d^ apparait dans les équations de bits de vérification c. et c„. De même, le bit de données 1 b d24 apparait uniquement dans les équations de bit de vérification c,. et Chaque bit de données d^... d^ apparait dans deux équations de bit de vérification. En conséquence, le décodeur peut être conçu de façon mécanique conformément à ces observations. En d'autres termes, les équations peuvent être transformées en équations dans lesquelles les données de digits communs sont égales au reste des données et des bits de vérification dans l'équation. Un exemple de codeur pour les données de digit dQ et est donné sur la figure 3. Les quatre bits de données de digits d^... d^ et le bit de vérification c^ sont envoyés en tant qu'entrées à la porte à cinq entrées OU EXCLUSIF 24. De même, les entrées dc, d.n, d.c, d_n et le bit de vérification c sont envoyés 3 lu 13 ZU u à une seconde porte à cinq entrées OU EXCLUSIF 2B. Il est à noter qu'aucun de ces bits numériques ne sort les mêmes que ce soit dans la porte OU EXCLUSIF particulière ou dans la porte OU EXCLUSIF associée. Ainsi, la sortie de chaque porte OU EXCLUSIF 24, 26 porte véritablement une détermination ou une copie du bit de données d^ qui est envoyé en tant qu'entrée distincte au circuit logique à seuil 2B. Ce bit de données d'origine d^ est également 69 42814 g 2030129 10 15 20 25 30 35 envoyé directement en tant que troisième entrée au circuit logique de seuil 28. Etant donné que trois entrées sont présentes, toutes les entrées représentant le bit de donnéedQ, toute erreur simple par rapport à dQ ou à l'une des entrées appliquées à la porte 24 ou à l'une des entrées appliquées à la porte 26, peut être corrigée par le fonctionnement du circuit logique de seuil 28. Le seuil du circuit logique 28 est fixé de sorte qu'il va donner la valeur prise par deux entrées quelconques choisies parmi les trois. Ainsi, si l'une des entrées a une erreur, l'erreur est corrigée. La sortie du circuit logique a seuil 28, qui est également connu comme circuit de choix majoritaire est le bit de données dQ en supposant que toutes les entrées appliquées à 28 sont correctes ou tout au moins deux entrées. L'art antérieur révèle un certain nombre de façons différentes d'exécuter les portes de majorité comprenant les circuits de seuil à transistors, les réseaux de résistances etc... Tous les digits de données d'origine dQ,... sont engendrés de la mime façon et avec les mêmes circuits que ceux indiqués sur la figure 3. De manière à étendre ce code à un code de correction d'erreur double, il est introduit la conception de "modularité" qui simplifie la réalisation. De manière à engendrer le codage supplémentaire nécessaire à la correction d'erreur double, il est nécessaire d'utiliser dix bits de vérification supplémentaires. Ceci peut être déduit de la caractéristique 2mt du code où m était 5 et t, le nombre d'erreurs pouvant être corrigée, est 2, donnant ainsi 20 bits de vérification dont 10 ont déjà été dérivés de la première description de correction d'erreurs donnée ci-dessus. Ces dix équations supplémentaires sont dérivées des carréslatins L^ et L2 qui sont représentés sur la figure 4. Ces carrés L^et L2 sont théoriquement utilisés en tant que masques du réseau de matrice carré d'origine de 25 digits de données. Les bits de données correspondant aux mânes digits du "Basque" de carrés latins sont soumis ensemble à une condition OU EXCLUSIF afin de donner l'équation de bits de vérification de la façon suivante : C11 = dOSd98d13®d170d21 o12- dl8d5®d148d18i d22 C13= d29d6ed10®d198d23 C14= d38d7®d11Sd158d24 C15 = d48d8Bd12id16id20 C16= dO8d8®d11®d190d22 C17= d18d98d128d159d23 40 "18 d28d59d13#d168d24 dérivéede L. dérivée de L, 69 42814 10 2030129 c19- d39d6ed148,i17,d20 | 1 dérivée de L„ o20= d48d7id1o8d188d21 ; Ces dix équations de bits de vérification supplémentaires c^....c2g fournissant deux moyens indépendants supplémentaires pour déterminer chaque bit de données. 5 Par exemple dQ peut maintenant être obtenu à partir des équations de bits de vérification supplémentaires c.„ et c„„. Ainsi, deux copies supplémentaires des 1 » 1o bits de données dQ peuvent être dérivées et utilisées en tant qu'entrées appliquées au circuit logique de seuil. Ainsi, la notion de choix de majorité peut 8tre un circuit de choix de majorité 3/5 où deux des entrées appliquées au cir-10 cuit de choix sont ceux dérivés du cas dserreur simple et où deux sont dérivés par les équations de bits de vérification supplémentaires pour le cas d'erreur double. Ces quatre entrées ainsi que le bit de données lui-même, constituent les cinq entrées appliquées au circuit de choix. La réalisation pour le premier bit de données dQ est représenté sur la figure 5. Il est à 15 noter que les deux premières portes OU EXCLUSIF 30, 32 et les entrées qui leur sont appliquées, comme celles représentées dans le bloc en pointillés I, correspondent au circuit de décodage de la figure 2 pour le cas de correction d'erreur simple. Les portes OU exclusif 34 et 36 ayant comme entrées les termes de l'équation dérivée des équations de bits de vérification c^„ et c„„ ont été 11 16 20 ajoutés au cas de correction d'erreur simple afin d'obtenir la possibilité de correction d'erreur double pour les données de digit dQ. En conséquence, la sortie des circuits OU EXCLUSIF 34 et 36 est dg. Ainsi, il y a cinq entrées dg ainsi que quatre déterminations supplémentaires de dQ, connectées en tant qu'entrées appliquées au circuit de choix majoritaire 38. Il est à noter que 25 le circuit 38 avec cinq entrées, est capable de corriger deux erreurs quelconques. En d'autres termes, le. circuit est capable de répondre avec la sortie dg correcte lorsque trois entrées quelconques des entrées appliquées à la porte 38 sont correctes, ce qui est le cas aussi longtemps que deux erreurs, ou moins, apparaissent dans les bits ds vérification et de données. Il est à 30 noter également que les circuits nécessaires pour corriger l'erreur supplémentaire, en d'autres mots la seconde erreur, peuvent être ajoutés aux circuits de correction de la première erreur en tant qu'agencement modulaire (voir le bloc II figure 5). Ceci est important étant donné qu'il n'est pas nécessaire d'intervenir sur la réalisation du circuit de correction de la première 35 erreur d'origine. Ceci introduit une souplesse considérable dans les circuits en ce sens que les circuits peuvent être conçus sous forme modulaire et facilement assemblés. En étendant l'exemple au cas de correctiond'erreurs triple, la conception modulaire peut en outre être donnée à titre d'exemple en dérivant les équa 69 42814 11 2030129 10 tions de bits de vérification supplémentaires c^, C22*'",03o des carrés latins Lg et L-4 représentés âur la figure 4. Les équations de bits de vérification 15 obtenues finalement sont c21- d0»d7»d14«d16«d23 c22- d18d6«d10ad1?«d24 c23- .yd^id 8d c24= d3Sd50d12Sd190d21 C25* C26= d08d68d12»d18ad24 °27- d1,d7*d139d1s'd20 C28* d2,dBSd14,d15Sd21 c29- d38dg8d1o0d160d22 c30= d4Sd50d110d170d23 es suivantes à partir deL„ à partir de L D'après les équations de bits de vérification données ci-dessus, on peut voir qu'il y a maintenant deux moyens supplémentaires pour déterminer chaque 20 bit de données. Par exemple, dQ peut être dérivé des équations de bits de vérification c^ et c2g. Ainsi la correction d'erreur peut être effectuée par un bhoix de quatre sur sept représenté par le circuit de la figure 5 pour d^. En comparant le bloc III de la figure 5 avec les blocs I et II il est à remarquer que les portes OU EXCLUSIF 40 et 42 ont été ajoutées au circuit de la 25 figure 5 afin d'obtenir les deux déterminations supplémentaires du bit de données dQ attribuant ainsi les sixième et septième entrées dQ au circuit de choix 38. Il est à noter que trois des entrées appliquées au circuit de choix 44 peuvent avoir une erreur et le circuit va toujours produire la sortie d'origine dQ j ainsi trois erreurs dans les données et les bits de vérification peu-30 vent être véritablement corrigées. La même théorie et les mêmes circuits seront nécessaires pour chacun des 24 bits de données. En bref, le bloc à ligne discontinue I correspond au circuit pour engendrer dQ de la figure 3 tandis que le bloc en ligne discontinue II contient les portes OU EXCLUSIF qui ont été ajoutées sur la figure 5 afin d'obtenir la correction d'erreur double. Les por-35 tes OU EXCLUSIF dans le bloc de ligne discontinue III sont celles qui ont été ajoutées afin d'inclure la correction d'erreur triple. D'après la description précédente, on peut voir que chaque augmentation du nombre d'erreurs t qui . peuvent être corrigées nécessite deux portes OU EXCLUSIF supplémentaires. Le nombre d'erreurs qui peuvent être corrigées est limité à la valeur m suivant 69 42814 12 2030129 l'équation suivante : t 2 Il faut également tenir compte qu'il est atteint une limite pratique où les circuits supplémentaires ne sont pas justifiés en raison'de la possibilité 5 d'apparition simultanée de nombreuses erreurs. La figure 5 illustre que le module I assure une correction d'erreur simple,. le module I et le module II une correction d'erreur double et l'addition du module III assure une correction d'erreur triple. II. est à remarquer que chaque module est identique. En conséquence, l'un quelconque des trois modu-1o les peut véritablement être utilisé pour, une correction d'erreur simple ; deux quelconques de ces modules peuvent être utilisés pour une correction d'erreur double, etc... En fait, la modularité s'étend au niveau du circuit OU exclusif dans le module. Par.exemple, une correction d'erreur simple peut être obtenue en utilisant deux circuits OU exclusif quelconques tels que les 15 circuits 30 et 42 représentés sur la. figure 5. De façon semblable, une correction d'erreur multiple peut être obtenue en.utilisant deux circuits OU EXCLUSIF quelconques pour chaque possibilité de correction d'erreur successive. La construction des modules est extrêmement importante lors de l'assemblage des circuits intégrés. 2 20 Un message de K bits de donnees inférieurs à m peut être codé et décodé 2 de la façon rigoureusement la même que pour les m bits de données. Un exemple de codeur et de décodeur pour 23 bits de données est représenté respectivement sur les figures B et 7. Les équations de bits de vérification sont dérivées en étendant les bits de données du code à la matrice carrée supérieure sui-25 vante. Dans le cas d'un code de 23 bits de données, le prochain carré supérieur est 25. Le code et la réalisation peuvent par la suite être réduits en éliminant les bits de données en extra. Par exemple, dans le codeur de 23 bits de données de la figure 6, les entrées des bits de données 23 et 24 ont été éliminées. En fait, deux quelconques des données pourraient avoir été 30 éliminées. En se reportant à nouveau aux équations de rangées et de colonnes, pourdes bits de vérification c^ à c10 dérivés de la description relative à l'exemple de 25 bits de données, on peut voir que les bits de données d^ et d apparaissent dans l'équation de bits de vérification c^, le bit de données d dans l'équation de bits de vérification c et d dans c .En £.ô y i u 35 conséquence, le codeur représenté sur la figure 6, pour engendrer les bits de vérification c^ à c q, a seulement trois entrées appliquées au circuit OU EXCLUSIF 50 pour engendrer le bit de vérification c_ et quatre entrées 5 appliquées aux circuits OU EXCLUSIF, 52, 54 pour engendrer respectivement les bits de vérification c^ et c^g- La logique linéaire des circuits de vérifica-40 tion de parité qui transforme les équations de bits de vérification suivant 69 42814 13 2030129 le bit de données commun correspondant va en conséquence avoir moins d'entrées. Par exemple, le bit de données d^ apparait dans les deux équations de bits de vérification c,. et cD. En conséquence, la porte OU exclusif 56 de la figure b o 7 va avoir uniquement trois entrées. En fait", le circuit régulier de 5 entrées 5 peut être utilisé avec les entrées non utilisées forcées pour produire un nombre fixe tel que zéro. Il est à remarquer que le décodeur, à l'exception du circuit de choix peut §tre utilisé pour détecter des erreurs. Le circuit logique linéaire accomplit une fonction de vérification de parité au moyen de laquelle l'erreur peut être 113 détectée. Une possibilité de détection d'erreur supplémentaire peut être incluse en ajoutant un circuit de vérification de parité globale. Ce circuit vérifierait la parité du message entier plutôt que les groupes de m bits de données comme cela était le cas avec les circuits logiques linéaires de vérification de parité utilisés préalablement. 15 II reste bien entendu que la description qui précède n'a été donnée qu'à titre d'exemple non limitatif et que de nombreuses variantes peuvent être envisagées sans pour autant sortir du cadre et de la portée de la présente invention. 69 42814 14 2030129 REVENDICATIONS 1. Système de correction d'erreurs multiples au hasard pour corriger le messa- 2 ge de k - un moyen de codage pour ajouter 2m bits de vérification ,aux -.dits bits de 5 données pour chaque possibilité de correction d'erreurs supplémentaire j - un moyen de décodage comprenant un circuit de correction d'erreurs pour chacun des dits bits de données et un module de circuit logique linéaire pour chaque possibilité de correction d'erreur afin ds réaliser des vérifications de parité pour chaque bit de données, les sorties de chaque module de circuit 10 logique linéaire formant les entrées appliquées audit circuit de correction d'erreurs. 2. Système selon la revendication 1, dans lequel chaque module de circuit logique linéaire comprend deux circuits OU EXCLUSIF chacun ayant m entrées formé de m-1 entrées de bits de données et une entrée de bit de vérification. 15 3. Système selon la revendication 2, dans lequel deux quelconques des dits circuits OU EXCLUSIF à partir de l'un quelconque,ou d'une combinaison, desdits modules de circuits logiques linéaires peuvent être utilisés pour produire une sortie représentant les mêmes bits de données. 4. Système selon la revendication 1, dans lequel ledit circuit de corraction 20 d'erreurs comprend un circuit logique de seuil pour chacun desdits bits de donnée où le seuil a été fixé de manière à choisir un signal de sortie représentant un bit de donnée -si la majorité des entrées de bits de donnée 5 qui lui sont appliquées sont les mêmes, et où chaque circuit logique ds seuil peut contenir une entrée supplémentaire pour un signal représentant le 25 bit de données lui-même que le circuit logique de seuil respectif corrige. 5.Système selon la revendication 1» dans lequel ledit moyen de codage comprend 2m circuits OU EXCLUSIF pour chaque possibilité de correction d'erreur, chaque circuit OU EXCLUSIF ayant m entrées pour recevoir différentes combinaisons des 2 dits m bits de données, des paires des dits 2m circuits OU EXCLUSIF ayant 30 une entrée de bits de données corrmuns et n'ayant aucun autre bit de données commun, la sortie provenant de chacun desdits circuits OU EXCLUSIF représentant un bit différent parmi les 2m bits de vérification. 6. Système selon la revendication 5, dans lequel les dites différentes « 2030129 42814 2 combinaisons des m bits de données appliqués aux entrées de chaque circuit OU EXCLUSIF sont déterminées conformément à la théorie des réseaux en forme de carrés latins. 7. Système selon la revendication 6, dans lequel les dites différentes combinai 2 sons des m bits de donnée pour chaque circuit OU EXCLUSIF pour la première possibilité de correction d'erreur sont obtenues en appliquant les bits de données contenus dans chaque rangée et chaque colonne d'un réseau fondamental de carrés latins des' données aux entrées des circuits OU EXCLUSIF respectifs. 8. Système selon la revendication 7, dans lequel les dites différentes combi- 2 - " naisons de m bits de données pour chaque circuit OU EXCLUSIF pour la seconde possibilité de correction d'erreur et des dites possibilités suivantes, sont obtenues en appliquant ces bits de données aux entrées des circuits OU EXCLUSIF respectifs dont la position correspond dans ledit réseau fondamental de car rés latins à la position des digits qui sont les mêmes dans chacun des deux carrés latins orthogonaux pour chaque possibilité de correction d'erreur. 2 9. Procédé de correction d'erreurs dans un message de K - addition de 2m bits de vérification audit message pour chaque possibilité t de correction d'erreurs afin de former 2 mt équations de bits de vérification dans lesquelles exactement 2t équations contiennent un bit de données commun, - transformation des dites équations de bit de vérification en des équations pour déterminer les bits de données communs, '- et utilisation des déterminations de bits de données communs afin de produire une sortie indiquant un - bit de données correct si il est obtenue une majorité des dits bits de données commun. 10. Procédé selon la revendication 9, dans lequel un bit de vérification est ajouté audit message pour chaque rangée et chaque colonne de carrés latins 2 de base des dits m bits de données pour la première possibilité de correction d'erreur, et où si néeessaire 2mt équations de bits de vérification sont formées pour deux ou plusieurs possibilités de correction d'erreurs en ajoutant un bit de vérification pour chaque groupe de bits de données qui dans ledit réseau fondamental de carrés latins correspond en position aux digits sembla- 2 bles dans l'un et l'autre de deux carrés latins orthogonaux pour m bits de données j une autre paire supplémentaire de carrés latins orthogonaux est utilisée pour chaque possibilité supplémentaire de correction d'erreur.