Brevet FR2086007A1 — publié le 19711231

7.1 10274 1 2086007 L'invention concerne les systèmes de correction d"erreurs pour manipuler (p.ex. transmettre, traiter, mémoriser) des informations sous la forme de messages de bits de données, et particulièrement des systèmes de correction d'erreurs multiples, ayant leur utilité dans les systèmes de manipulation de données parallèles tels que les mémoires d'ordinateurs à grande vitesse, les canaux de données et autres canaux nécessitant un degré de protection élevé contre les erreurs. Les systèmes de codage pour la correction d'erreurs utilisent en général l'adjonction, aux bits de données du message, d'un certain nombre de bits de contrôle ce qui donne un message codé pouvant être décodé de telle sorte que les erreurs qui sont apparues au cours de la mémorisation ou de la transmission dudit message soient corrigées. Les premiers systèmes de codage, connus sous la nom de codes de Hamming, tout en utilisant qu'un nombrè minimum de bits de-contrâle n'en étaient pas moins lents et difficiles à décoder (ils nécessitaient notamment, pour chaque erreur, une opération de détection suivie d'une opération de correction ; de plus, ils mettaient en oeuvre des circuits complexes eux-mêmes sujets à erreurs. □ans les systèmes de codage décodables, à vote majoritaire, chaque bit de contrôle correspond à une équation comportant plusieurs bits de données, et toutes les équations de bits de contrôle sont indépendantes, c'est-à-dire qu'elles n'ont pas plus d'un seul bit de données en commun. Par exemple, lorsqu'il n'y a qu'une seule erreur à corriger, chaque bit de données a deux bits de contrôle sous sa dépendance, et ces bits de contrôle de même que le bit de données fournissent trois positions de bits ou voies (votes). Lorsqu'on utilise un système de décodage à vote majoritaire et qu'une erreur se produit dans une seule de ces trois positions, la valeur correcte sera identifiée à partir des deux autres positions. En ce qui concerne la correction des erreurs multiples en général, si t est le nombre d'erreurs à corriger (t >2), 2 + 1 positions devront être prévues pour chaque bit de données. La correction des erreurs affectant t positions ou moins peut donc se faire par acceptation de la valeur majoritaire qui est correcte. Les précédents codes de correction d'erreurs à vote majoritaire, particulièrement, ceux pour la correction des erreurs multiples, étaient basés sur les carrés latins. En général, k bits de données sont disposés selon 2 un carré latin de côté m, K étant inférieur ou égal à m s un carré latin de 2 m de côté est une configuration de m digits disposés en m scus-carres inscrits dans le carré, de telle sorte que chaque rangée et chaque colonne contienne une seule fois exactement chacun des caractères. Deux séries de bits de contrôle indépendants peuvent être générées à partir des carrés latins i l'une de ces séries contient les bits de contrôle correspondant à 71 10274 2 2086007 chaque rangée et l'autre série contient les bits de contrôle correspondant à chaque colonne. D'autres séries d'équations de bits de contrôle peuvent 8tre générées conformément à la théorie du carré latin orthogonal, les possibilités de correction du code étant donc limitées par le nombre d'équations 5 qu'il est possible de générer. Les équations de bits de contrôle résultantes sont caractérisées par le fait que chaque bit de données doit apparaître dans exactement 2t équations de bits de contrôle et ces 2t équations qui comportent un bit de données commun, ne contiennent pas d'autre bit commun. 10 Cependant, le nombre de bits de contrôle requis par le système du carré latin pour k bits de données, est soumis à la condition que k soit 2 inférieur ou égal à m .tandis que le nombre total de bits de contrôla r, sera égal à 2 mt. Si k n'est pas un carré parfait, il est nécessaire d'utiliser le carré latin immédiatement supérieur pour générer les équations de bits de 15 contrôle. Ainsi, dans le système à carré latin conventionnel, on aura donc pour une correction d'erreur double (t«2), k » 25, m ■ 5 et 2mt « 20 bits de contrôle. Mais si k » 26, il est nécessaire de prendre m * 6, de sorte que 2mt » 24, soit une adjonction de quatre bits de contrôle nécessaire pour accepter un seul bit de données supplémentaire. 20 Cette invention a donc pour objet de fournir des systèmes de codage décodage à votre majoritaire plus efficaces, dans lesquels le rapport des bits de données aux bits de contrôlé, k/r, k n'étant pas un carré parfait, soit supérieur à celui obtenu dans les systèmes de codage conventionnels basés sur le carré latin. 25 Un autre objet de l'invention est de fournir les moyens de développer les codes conventionnels basés sur le carré latin et donc d'améliorer leur efficacité. Dans un système manipulant des informations sous la forme de messages de bits de données, l'invention définit un système de correction d'erreurs 30 multiples permettant de corriger t erreurs dans des messages contenant 2 ,2 k bits de données, en supposant t > 2, m 71 10274 3 2086007 bit de données étant le bit de donnée lui-même et 2t combinaisons de bits de contrôle et d'autres bits de données ladite combinaison représentant le bit de données ; le circuit de correction d'erreurs sont capables de produire un signal de sortie correspondant exactement à un bit de données 5 lorsque pour le bit de données en question au maximum t entrées sont erronées. Dans les modes de réalisation préférés, le circuit de correction d'erreurs comprend un circuit logique à seuil pour chaque bit de donnée, le seuil étant fixé de façon à produire un signal de sortie de valeur correspondant à celle de la majorité des entrées franchissant ce circuit logique à 10 seuil , le circuit d'entrée comprend 2t circuits OU EXCLUSIFS pour chaque bit de données, les entrées de chacun de ces circuits comprenant au moins m et généralement plus de m bits de données ainsi qu'un des bits de contrôle. Dans un système préféré, le moyen d'encodage comprend un circuit qui 2 produit 2 mt des r bits de contrôle selon une configuration de m des k bits 15 de données, désignés respectivement par dQ, d .......dm2_^, ayant une forme d'une trame carrée. Quelques uns au moins 2m des bits de données . de ces r bits de contrôle sont les bits de données de chaque rangée et de chaque colonne de cette trame carrée, et quelques uns au moins des bits de données des 2(m-1)t ae ces bits de contrôle sont les bits de données dont la position 20 dans la trame carrée correspond à la position des caractères qui sont les mêmes dans chacune des paires de carrés orthogonaux pour chaque t. Le moyen d'encodage comprend en outre des circuits permettant d'ajouter à quelques „ 7 uns au moins de ces 2mt bits de contrôle k-m bits de donnees, désignes par d 2» d, „ ; chacun de ces bits de données étant ajouté à au moins m k-1 25 2t-1 et au plus 2t de ces bits de contrôle et tous les dits bits de contrôle n'ayant en commun qu'un seul de ces bits de données ajoutés. Le moyen d'encodage peut aussi inclure des circuits pour produire r-2mt bits de contrôle supplémentaire (r > 2mt), qui tous correspondent aux bits de données dm2""" dk-l" 30 D'autres objets, caractéristiques et avantages de l'invention ressorti- ront de la description d'un rncde de réalisation préféré, qui va être faite sn référence aux dessins annexés à es texte. Sur les dessins s La figura 1 esr. le schcnr-a d'un système ne irai'cernent os données comprenant un système de correction d'erreurs. 35 Les figures 2et 2a sont des schémas généraux de l'encodeur p&.mettam; de dériver les bits de contrôle nécessaires. La figure 3 est le schéma de l'encodeur [sous sa forme la plus générale) qui permet de traiter les messages codés par le système de la figure 2. La figure 4 représente la série de quatre carrés latins orthogonaux 40 pour cinq caractères. 71 10274 4 2086007 Les figures 5 et 5a sont les schémas des décodeurs pour les bits de données dn et d„, capables de corriger deux erreurs ; et U Zh Les figures 6,7,8 représentent des matrices de carrés latins développées. La figure 1 représente un encodeur 12 qui reçoit K bits de données 5 m » m .«.o.m produisant en sortie k bits de données plus r bits de contrôle ic. K c , c ....c . Un encodeur type est représenté à la figure 2 où chaque bit de contrôle m suit à la fois un canal direct et un canal de génération de bit de contrôle, où il est encodé sous la forme de deux bits de contrôle. Comme le montre la figure 2a, chaque bit de données peut être appliqué, ainsi que 10 d'autres bits de données, et conformément au système de codage, à un circuit OU EXCLUSIF, dont la sortie sera le bit de contrôle correspondant. Ainsi, à la figure 2a les bits de données tels que m^, sont appliqués au circuit OU EXCLUSIF 24 pour produire un bit de contrôle c^. Comme le montra la figure 1 les bits de données et les bits de contrôle sont ensuite traités 15 dans le processeur 18. Les informations peuvent alors, si on le désire être décodées dans le décodeur 14. Comme le montre la figure 3, le décodeur est constitué par un certain nombre de circuits de vote majoritaire 30, autrement dit, un circuit logique à seuil qui émet un signal de sortie représentant le bit de données 20 si la majorité des entrées sous forme de bits de données et de bits de contrôle qui lui ont été appliquées, sont correctes. Pour un bit de données m,, 1 la formule définissant les deux bits de contrôle et correspondants serait c„ » m. S 6 m„ 11 2 25 c2 - m 8 » 8 mg C1 8t °2 n'a^ant comme de donnée en commun que m^, et le symbole 8 représente une fonction OU EXCLUSIF. Ces deux formules peuvent aussi être 3- ni., « c, 8 ....... 8 m ni, * c S 9 m, 1 i 3 Comme aucune variable commune de demeure dans ces formules, la présence d^une erreur unique dans l'un des bits de données ou de contrôle constituant ces équations affectera au plus une formule, Ainsi donc, m^ sera donné par m^ " Maj. Cm1,c1 8 8 m2» c, S .... 8 m3) Pour produire des codes dans le cadre de la présente invention, la méthode préférée est celle de l'augmentation des codes basés sur le carré latin. En général un carré latin de m de côté est un ensemble de m digits dispesés selon une trame carrée semblable à celle représentée ci-dessous. Pour 71 10274 5 2086007 2 2 K =m , les m bits de données représentés par les symboles dQ, d^ ...... d sont disposés dans une trame carrée qui a le forme suivante : k-1 10 20 Cm+1 Cm+2 C m+3« « « B CM a C1 d 0 d1 ^2* * *" Vi C2 d m dm+1 dm+2**'' d2m-1 C3 • • d2m d2m+1 • d2m+2 • d3m-1 C1) • • c m ■ d(m«*1)m • d(m-1)m+1 d(m-1)m+2.. • d 2 m -1 Les rangées de cette trame sont désignées successivement par V V bit de ..c et les m contrôle c. colonnes c ., c _ m+1 m+2 (i étant égal à 1,2 , .... c2m. Ainsi, 1'équation pour ... 2m) est égale à la fonction OU EXCLUSIF des bits de données apparaissant dans sa rangée et il en va de mSme en ce qui concerne les colonnes de la trame. End'autres termes : O a il do «d1 *«d2 B...Bd . ) m-1 -j C2 " « ■ d m • 9 dm+1 ■ » 8 dm+2 ■ 8 ...,8d_ . ) ) ) i i \ * • cm * • d(m-1)m m • ■ • 8d[m-1)m+1 • • tm-1)m+2 • • 1 • * ^ m -1 cm+r do S d m Bd2m [m-1 )m . °m+2* d1 8 d m+1 ® d2m+1 (m-1)m+1 i 25 2m m-1 i d, 2m-1 e d 3m-l J d 2 , m -1 m O- m rn XI o c (-> a o «+ 3 H- 3 O (D 3 CD (0 CL m Qn voit donc que chaque bit de données apparaît exactement dans deux 30 de ces 2m équations de bits de contrôle. En outre, deux équations quelconques ne posséderont qu'un seul bit de données en commun. La série d'équations de bits de contrôle par rangée pour c^... cm sera désignée par S1, et la série d'équations de bits de contrôle par colonne pour cm+^' 35 c„_ sera désignée par S_. 2m 2 Pour générer d'autres séries, Sg, S^ d'équations de bits de 71 10274 6 2086007 Pour générer d'autres séries, Sg, d'équations de bits de contrôle, on a recours aux carrés latins orthogonaux. La théorie des carrés latins orthogonaux est bien connue. Se référer notamment à l'article "Analysis and Design of Experiments" de C.B. Mann, Dover Publications, Inc. New York 5 1949. Il y a des limites au nombre maximum de carrés latins orthogonaux possibles d'un ordre ou dimension donné. Cette limite supérieure est une fonction de m, qui est la dimension du carré latin. En général, un carré latin orthogonal d'ordre (de dimension) m est une trame carrée mXm composée des chiffres 0,1..... s m-1/ de sorte que chaque rangée et chaque colonne soit 10 une permutation des chiffres 0,1 ...., m-1. Pour générer la série de m équations de bits de contrôle, on superpose le carré latin sur la trame mXm de bits d'informations donnés dans l'équation (1). Cela revient à poser un masque sur les bits de données. Les bits de données qui sont "recouverts" par les mêmes digits de carré latin sont soumis ensemble à une fonction OU 15 EXCLUSIVE pour produire l'équation de bit de contrôle. Cette opération produit m équations de bits de contrôle. Si L^ et L2 représentés à la figure 4 sont des carrés latins orthogonaux, la série de 2m équations de bits de contrôle produite de la façon précédemment décrite à partir de L^ et L^aura la même propriété que les équations de rangées et de colonnes correspondant à 20 la correction d'erreur unique. Cette propriété veut que deux équations quelconques contenant un bit de donnée commun ne contiennent pas d'autres bits de données en commun, et en conséquence peuvent être ajoutées aux équations de rangées et de colonnes correspondant au cas de correction d'erreur unique. Ainsi donc, chaque bit de données apparaît dans quatre équations 25 de bits de contrôle, et aucun autre bit de donnée commun n'apparaît dans ces quatre équations. Pour comprendre le processus de décodage, nous observerons que les équations c^ et par exemple peuvent être récrites de la façon suivante : 30 dQ - °i • d, • d2 « ... e dm., d0 " °m.1 » dm ' d2m Les équations supplémentaires contenant des bits de contrôle dérivés de carrés latins orthogonaux peuvent être ré-écrites de la même manière. Comme aucun bit de donnée commun ni aucun bit de contrôle commun ne demeure dans ces deux 35 équations portant sur dQ, la présence d'une seule erreur dans les bits de données ou de contrôle d^, d^ ..... _.j* c-j» c2 •••■■ peut affecter au plus deux de ces quatre équations. En conséquence, dQ sera donné de façon correcte par la fonction : cL - Maj(d , c #d id„8 ... id ,, c . 8d 8d„ 8... fid. 0 0 112 m-1 m+1 m 2m (m-1)m, 40 équation S , équation S ). w *T 71 10274 7 2086007 L'équation pour est l'équation de vote majoritaire pour le décodage par vote majoritaire du bit de données dQ. On peut procéder de la même manière pour chacun des bits de données qui a été encodé. Pour augmenter ces codes basés sur le carré latin, on ajoute à chaque 5 série S d'équations de bits de contrôle, $ bits de données (soit 2t $ bits de données au message entier) sans ajouter de bits de contrôle, ou en ajoutant un nombre de bits de contrôle inférieur à celui qui serait nécessaire pour passer au carré latin immédiatement supérieur. Comme toutes les équations contenues dans chaque série sont indépendantes les unes des autres, et comme 10 aucune équation d'une série quelle qu'elle soit n'est combinée (à des fins de correction d'erreur) à aucune autre équation de la mime série, se trouvant dans le système conventionnel du carré latin, le même bit de donnée pourra être ajouté à plusieurs équations de la même série, sans détruire l'indépendance des équations de la série par rapport à leurs bits de données initiaux. 15 La valeur # est une fonction de t et de m, et cette notion sera éclaircie grâce aux exemples ci-après : 2 Dans un premier exemple, considérons un code carre de 5 =25 bits de données, en supposant t * 2. Ainsi, m * 5 et il y a quatre carrés latins orthogonaux d'ordre 5, comme l'indique la figure 4. Le nombre, r de bits 20 de contrôle est égal à 2mt, t étant égal au nombre d'erreurs à corriger j ainsi r, * 20. Les bits de données d^ à d^, comme indiqué précédemment, sont disposés selon la trame carrée représentée comme suit : CB C7 n CD o CD C10 C1 *0 d1 d2- d3 d4 CM U d5 dg d7 da d9 C3 dio d11 d12 d13 d14 C4 d15 1b *17 die *4 "10 C5 rL ~ so H A k'\7.2 d, _ ««o 2^ On obtient les séries 3, et S„ d5équations de bits de montrale an 30 soumettant ensemble à une fonction OU EXCLUSIF les données contenues dans Iss rangées c„ à c. et cfans les colonnes c et c respectivement. Les séries 15 6 lu S et S sont dérivées des carrés latins L et L représentés à la figure 4. 3 n T £. Ces carrés latins L., at L„ sont utilisés théoriquement comme masaues sur 12' la trame carrée originale de 25 caractères. Les bits de données correspondant 35 aux digits identiques du masque carré Latin sont soumis à ^r.s fonction OU EXCLUSIVE pour former les bits de contrôle c,^ à c2Q. Les séries à S^ sont les suivantes : 71 10274 8 2086007 10 S4 C1 * dQ ®d1 ®d2 ^3 ®d4 c2 - d5 SdB id? 8d0 8dg„ S1 " C3 « d 10 ad^ 11 8d12 ®d13 8d14 C4 " d15 id16 #d17 8d18 Sd19 5 °5 * d20 Sd21 Bd22 #d23 Sd24 c « d Sd Bd Sd ffld 6 O 5 10 15 20 c_, - d„ Sd„ id„„ Sd,,,, 8d„„ 7 1 6 11 16 21 S„ » c « d 8d 8d Sd 8d 2 8 2 ? 12 17 22 c - d Sd Sd Sd 8d 9 3 8 13 18 23 c " d Bd Sd 8d Sd 10 4 9 14 19 24 c > d Id Id Sd 8d 11 O *9 13 17 21 c » d Id Sd Sd 8d 12 1 5 14 18 22 S ■ c * d„ 8d Sd Sd„_ §d_„ 3 13 2 6 10 19 23 c., = d„ Sd 8d Id r 8d„. 14 3 7 11 15 24 15 c ■« d Sd Bd Sd id 1S 15 4 8 12 16 20 C16 m do 8dfi #d11 Sd 19 Sd 22 C17 m di 9d9 #d12 8d15 Sd 23 C18 M d2 8d5 #d13 9d16 Sd 24 O a CO ' d3 ®d6 14 Sd 17 Sd 20 C20 m d4 8d7 Sd 10 ffld 16 8d 21 20 Comme les équations cA à cc sont toutes indépendantes les unes des 13 £ titres, on peut ajouter un oit de données d?g, à 2t de ces équations de aorte C1 dQ 8cJ1 sd2 Sd3 ad4 id2S 25 c = dc 8d„ Sd., Bdn ®dn id„,, 4. bb/uiii.^ S1 * C3 d10 M11 4d12 "d13 «M 'd25 c4 " d15 «16 "ï 9d1fl ,d25 C5 " d20 *d21 id22 "d23 "d24 30 De même les bits de données d_,, d^_ et d-n peuvent ètr&. ajoutés 2o 27 28 71 10274 9 2086007 à 2t équations dans chacune des séries S3 et S^ respectivement. Ainsi par exemple : c » d Sd Bd Bd Sd Sd 6 0 5 10 15 20 26 C11 " d0 8d9 ®d13 ®d17 #d21 ®d27 5 °16 " d0 #d8 #d11 8d19 8d22 8d28 Comme chaque série peut accepter au plus un seul bitde données, # » 1 pour le code (m,2tî ici (5.4). Il y a donc à présent quatre équations de bits de contrôle pour chaque bit de données dg à d^, chacune provenant d'une série et quatre équations 10 de bits de contrôle pour chaque bit de données d„r à d„a qui appartiennent Z. b Ao toutes à la même série. Sur la figure 5, le circuit de correction d'erreur pour dg est constitué par quatre portes OU EXCLUSIVES 30, 32, 34 et 36 dont les entrées sont dérivées des équations correspondantes à c., c_, c.. et c„„ I O M 1 o respectivement, et un circuit de vote majoritaire 38. Sur la figure 5a, le 15 circuit de correction d'erreur pour d_c est constitué par quatre portes OU 2b EXCLUSIVES 40, 42, 44 et 46 dont les entrées sont dérivées des équations correspondant à c^, c^, c3 et c^ respectivement, et un circuit de vote majoritaire 48, qui à l'instar du circuit 38, est un circuit logique à seuil qui produira un signal de sortie représentatif du bit de données si la 20 majorité des entrées qui lui sont appliquées sous forme de bits de données et de bits de contrôle est correcte. 2 2 Ainsi donc k ■ 29, (qui est un k tel que (m ' 2 fallu 2(m+1)t bits de contrôle et, comme 29, 25 r « 2(m+1)t « 24. Par contre pour le code augmenté de l'exemple, r » 20 et 2mt « 20 La matrice H du code résultant est représentée à la figure 6 où la portion de "matrice I" indique les bits de contrôle, la portion les séries d'équations de bits de données et la portion "matrice-B" les bits 30 de données d_c à d„n ajoutés. 2b Zo En général, chaque fois que 2t 71 10274 10 2086007 TABLEAU-I m 2t $ 3 4 O 4 4 1 5 4 6 0 5 4 1 5 6 0 6 4 1 6 6 1 10 7 4 2 7 6 1 a 4 2 8 6 1 8 8 1 15 9 4 3 9 6 1 9 8 1 Dans chaque cas, le nombre total de bits de données pouvant être ajoutés est 2t #. 20 Lorsque 2t » m, la nombre de positions Indépendantes disponibles dans chaque série d'équations dérivées du carré latin est insuffisant (inférieur à 2t) pour accepter un bit de donnée supplémentaire. Cependant, conformément à un autre mode de réalisation de l'invention, il est possible d'ajouter quelques bits de contrôla aussi longtemps que les conditions précédemment. 25 décrites sont remplies, c'est-à-dire que 2mt 71 10274 n 2086007 La figure 7 est la matrice H de ce nouveau code (26,13). Les séries originales - S^ pour le code (21,9) avaient chacune trois équations indépendantes seulement, ce qui représente une de moins que le nombre 2t requis pour la correction d'erreur double. Ainsi donc, Userait inférieur à 1, 5 et semble-t-il aucun bit de données ne pourrait être ajouté. Cependant, si l'on ajoute un seul bit de contrôle, c , si c = d 8 d.n f d 8 d , la lO lO 3 1U 1 I iz quatrième équation indépendante pourra être écrite pour tous les quatre bits de données supplémentaires ce qui permettra de porter le code (21,9) à (26,13). Lorsque m est suffisamment élevé il est possible d'ajouter plus d'un 10 bit de donnée à chaque équation de bit de contrôle originale, cette adjonction n'étant limitée que par la nécessité de conserver 2t équations indépendantes par bit de données. Pour prendre un exemple spécifique d'une telle augmentation, supposons un code de carré latin (117,61) où t » 2, K (initial) ■ 81 et r * 36 qui deviendrait après expansion le code (169,129). Au total 15 48 bits de données ajoutées pour un nombre de bits de contrôle supplémentaires à peine égal à 4. Si on avait utilisé les codes de carré latin conventionnels, pour K « 129 il aurait fallu employer 4m soit 48 bits de contrôle tandis que grâce à la présente invention 40 bits de contrôle suffisent pour corriger les erreurs doubles affectant une quantité aussi élevée de bits de 20 données. Les matrices résultantes sont représentées à la figure 8. La matrice EL sert à ajouter les bits de données dn„ à d„„ j la matrice EL à ajouter les 1 81 92 2 bits dn„ à djr,„ et ainsi de suite. Les bits de données dD. à d„„, dn„ à dn_ 93 1u4 oi oo ao 9b etc... sont ajoutés à S^. En conséquence, si l'on considère les équations de bits de données 25 initiales pour c^ à cg (S^), les équations augmentées seront : C1 m * • m 8dn. 81 8d 93 Bd107 8d118 °2 as • • o 8d 81 ®d94 8d105 «119 C3 M • 1 0 9d81 id95 W106 Sd117 30 C4 m • » 0 idB2 8d93 ®d 107 ®diia r» ^5 « -- -ï "9 iU32 '""94 îdios " 1 1 3 C6 M i * V ®C32 SG103 !d.M ? C7 M O « O 8d83 ?a94 îd ,r.- 107 id 113 35 C8 m • • 9 ^33 S4 Sd105 C9 M • • • 8d83 8d95 ®d106 ®d117 Pour fournir une quatrième équation indépendante à chaque bit de données supplémentaire, on ajoute par série B de bits de données supplémentai-40 res, un seul bit de contrôle pour un total de quatre bits de contrôle, 71 10274 12 2086007 c à c représentant chacun 12 bits de données, et ne possédant aucun bit «j/ TU de données en commun. Ainsi donc ï C37 " d81 ®d82 ®d83 8 '"' ®d92 C30 d93id94id95® ®d104 5 °39 " d105 Sd106®di07 ® ",id116 C4CT * d117 ®d118 ®d119 ® ®d128. Ainsi, d'une manière générale, si $ est une partie entière de m 2t- 1 il est possible d'ajouter jusqu'à 2 $ t bits de données pour chaque bit de contrôle ajouté, et d'aller jusqu'au maximum de 2t bits de contrôle sup-10 plémentaires. Par exemple, si t « 2,$ sera égal à 3 pour m « 9, 10 ou 11. Ainsi il sera possible d'étendre un code de correctiond'erreur double (117,81), à (130,93) s (143,105) ; (156,117) et (169, 129) en ajoutant successivement 2t $ bits de données et un bit de contrôle, sans compter l'expansion (129,93) qui est possible sans aucune adjonction de bits de contrôle. 15 Bien que l'on ait décrit dans ce qui précède et représenté sur les dessins les caractéristiques principales de l'invention appliquées à un mode de réalisation préféré de celle-ci, il est évident que l'homme de l'art peut y apporter toutes modifications de forme ou de détail qu'il juge utiles sans pour autant sortir du cadre de ladite invention. 71 10274 13 2086007 REVENDICATIONS — — 1. Système de correction d'erreurs multiples applicable notamment aux systèmes manipulant de l'information, système du type pouvant corriger t erreurs (avec t > 2) dans des messages comprenant K bits de données, caractérisé ~ 2 2 en ce que K vérifiant la relation m 5 égal à 3, on forme r bits de contrôle pour les dits K bits de données, chaque bit de contrôle correspondant à un certain nombre de bits de données et chaque bit de donnée entrant dans la détermination de 2t bits de contrôle, les dits 2t bits ayant seulement ce bit de donnée comme élément commun de leur détermination, en ce que le nombre r de bits de contrôle vérifie la relation 10 2mt 2t + 1 signaux reçus comprennent le bit de donnée lui-même et les 2t bits résultant des combinaisons concernant cette donnée et formées par des bits de contrôle et des autres données, permettent de connaître la valeur correcte de la donnée si ces 2t + 1 signaux ne présentent pas plus de t erreurs. 15 2, Système de correction d'erreurs multiples conforme à la revendication 1, caractérisé en ce que pour former les r bits de contrôle on forme 2 mt de 2 ces bits conformément à m arrangements de m des K bits de données, désignés par dg, d^, ... dm2_^ selon une matrice carrée où au moins certains des 2m des r bits de contrôle sont des bits de chaque colonne et de chaque ligne 20 de la base carrée, où au moins certains des bits de données auxquels correspondent 2 (m-U des bits de contrôle sont des bits de données qui correspondent en position dans ladite matrice carrée aux position similaires dans chacune des deux matrices orthogonales et ceci pour chaque t, en ce que les 2 mt bits de contrôle sont augmentés d'au moins 2 t-1 et d'au plus 2t bits en 2 25 ajoutant à l'ensemble un bit de donnée du groupe dB'sk-m bits de donnees désignés par d 2.... d , tous ces bits de contrôle ajoutés ayant seulement rn K~1 ledit bit de donnéeajouté en commun pour leur formation. 3. Système conforme à l'une quelconque des revendications précédentes, caractérisé en ce que les circuits donnant la valeur exacte sont des circuits 30 majoritaires à seuil. 4. Système conforme à l'une quelconque des revendications précédentes, caractérisé en ce que les circuits d'entrée de réception comprennent 2t circuits OU Exclusifs pour chaque bit de donnée, chacun recevant un des bits de contrôle et au moins m bits de données.