Brevet FR2000680A1 — publié le 19690912

i 2000680 L*invention, relative au secteur des calculateurs numériques, concerne un procédé et un dispositif pour calculer un nombre arbitraire prédéterminé de caractères de contrôle ou d'essai à partir de données d'information et pour contrôler des données 5 d'information en dérivant, dont les caractères individuels sont rangés suivant un système de classes résiduelles modulo M. En général, les données sont constituées par une série de caractères d'une collection de caractères donnée (chiffres décimaux, alphabet, etc.) dont sont également prélevés les chiffres 10 de contrôle* La détermination des caractères de contrôle s'effectue d'une manière systématique à partir de caractères d'information et ce, de façon qu'elle permette de déceler le plus grand nombre possible d'erreurs. A cet effet, chaque caractère est majoré d'un nombre d'un système à classe résiduelle modulo M 15 approprié (M nombre premier collection de caractères). Les caractères individuels individuels peuvent évidemment être aussi codés dans le mode binaire ou, dans le cas de données binaires, plusieurs systèmes binaires peuvent être groupés en un seul caractère. Les caractères de contrôle peuvent alors être groupés, par 20 formation de sommes transversales pondérées dans le système de classe résiduelle choisi. Un choix judicieux du poids permet alors d'obtenir une, fiabilité optimale. On a déjà proposé un procédé dans lequel de telQiéaractères de contrôle sont obtenus avec une succession de poids appropriée. 25 Toutefois, comparativement au système conforme à l'invention, il présente l'inconvénient de requérir un nombre de composants notablement plus élevé pour la réalisation des caractères de contrôle. Dans l'invention une mémoire est utilisée pour chaque chif-30 fre de contrôle, et après chaque inscription d'un caractère, le nombre correspondant est ajouté modulo M au contenu de la première mémoire ; le résultat ainsi obtenu est ajouté au contenu modulo M de la mémoire suivante, et ainsi de suite, et après l'inscription et le traitement du dernier caractère d'informa-35 tion, l'ordre de traitement étant inversé, le contenu de la mémoire penultième est ajouté à la mémoire antépénultième, et ainsi de suite, et au cours de cette première phase, après la fin de l'inscription, le contenu de la permière mémoire est enregistré ; ensuite au cours de la seconde phase correspondante, le kO contenu de la seconde mémoire est enregistré et ainsi de suite 6901369 2000680 jusqu'à l'enregistrement du contenu de la mémoire antépénultième et le dernier contenu de mémoire obtenu donne les caractères de contrôle. Le procédé décrit ci-dessus ne requiert pas de stockage 5 explicite des séquences de poids et n'utilise qu'un seul endroit de stockage pour chaque caractère de contrôle. 11 offre donc l'avantage de permettre la détermination du caractère de contrôle ou le contrôle lui-même, avec un très petit nombre de composants . 10 La mise en oeuvre du procédé sera décrite à l'aide d'un exemple comportant un système à p = 5 caractères de contrôle, permettant de contrôler m = 7 caractères d'information dans le système à classes résiduelles modulo M s 11. Les caractères d'in formation seront désignés, dans l'odre de succession, par a^ à 15 a_,. Avant d'entamer le processus, le contenu de toutes les mémoi res est ramené à zéro. Au cours de la première phase, a^ 0St ajouté au contenu de la première mémoire Sp^, le résultat ainsi obtenu est ajouté au contenu delà seconde mémoire Sp^, et ainsi de suite de sorte" que, finalement, le contenu a^ se trouve dans 20 toutes les mémoires. Au cours de la seconde phase, a^ est ajouté au contenu a^ de la première mémoire, ce qui fournit, dans cette dernière, la valeur a^ + a^. Ce contenu est ajouté au contenu de la seconde mémoire Sp2 et fournit dans celle-ci le résultat 8a^ + a^. De ce 25 fait, on obtient comme contenu des mémoires après la 2ème phase (SPl) ; at + a2 (Sp2).,: 2&1 + a2 (Sp^) : 3»^ + ag (Sp^) * + a2 30 (Sp5> : 5a1 + ag La 3ème phase fournit la situation suivante : (Spt) al + a2 + a3 (Sp2} 3al + 2; + a3 (Sp3) 6al +3a2 + a3 (Sp^) 10a1 o (8 + + a3 (Sp5> 15at +5a2 + a3 Après la 4ème phase on obtient : (Spj^) : + a2 + a^ + a^ (Sp2) : ia^ + 3ag + 2a^ + a^ *i0 (Sp^) : 10a^ + 6a2 + 3a^ + a^ 6901369 3 2000680 (Sp4) s aOat + 10*2 (Sp,.) : 35aA + 15aa après la 5we phase, (SpA) : at + a2 + a^ + a4 + a5 (Spa) : 5a1 + 4a2 + 3a^ + 2a^ + a5 aB *v"o •*" "Iai. i- ai 35a_ +15a| + 5a£ + a| (SP,) î 15at + 10a + 6a, + 3a. + aK (Spl) : 35a* + 2Qaj* +10a^ + 4a? + a£ (Sp/) : 70aJ + 35a? + 15a| + 5a? + a| après là 6èae phase, + *a3 + a4 + 5a3 + *4 + a3 + a + 3a- + 2a + 6a- + 3a + 10a. + + i5a| + 5aJ (SpA) s ai + aa + a3 + a4 + a5 + a6 10 (Sp2) : ôaj, + 5a2 + 4a3 + 3a^ + 2a^ + afi (Sp^) ï 21a^ + 15a2 + 10a^ + ôa^ + 3a^ + ag (Sp^) : 56ax + 35aa + 20a^ + 10a^ +. 4a5 (Sp5) : 126a^ + après la 7ème phase, (Sp±) î al + (Spa) î 7a, + (Sp^) : 28at + (Sp^) s 84a1 + + a/ 70ag + 35a^ + 15a^ + 5a^ + 15 (Sp, ) Î a« + a2 6a2 21a2 56aa + a3 + a4 + a5 + a6 + a7 + 5a3 + 4a4 + 3a5 + 2a6 + a7 + 15a3 + lOa^ + 6a5 + 3a6 + a7 + 35a3 + 20a4 + 10a5 + 4a6 + a7 + 7°a3 + 35a4 + 15af + "6 + 4 (Spg) : 210a1 +126aa 20 ou, sous fora* de formule, le contenu de la mémoire Sp , après la phase jxt est : £ /T + 11 - 1 - lv ( \ - 1 >*1 i=l - Après la 7ème phase (inscription du dernier caractère d'informais tion) on a obtenu les deux caractères de contrôle P^ et P^ qui se trouvent dans les deux dernières mémoires Sp^ et Sp^* Pour déterminer les autres caractères de contrôle, le sens du traitement est inversé et on part de la mémoire pénultième Sp^# Après la 8ème phase, on obtient alors les nouveaux conte-30 nus de mémoire -suivants : (Sp^) : 112a^ + -77aa + 50a^ + 30a^ + l6a^ + 7ag + 2a», (Spa) : 119*^ + 83a2 + 55a^ + 3^a^ + 19a^ + 9ag + 3a^ (Spj) : 120a^ + 84aa + 56a^ + 35a^ + 20a,. + 10ag + 4a^ 0e ce fait, la dernière mémoire mentionnée (Sp^) contient le 35 caractère de contrôle P^. 4 la 9ème phase, on répète le traitement, mais cette fois uniquement jusqu'à la mémoire Sp2, dans laquelle s'obtient un autre caractère de contrôle Pg. Les nouveaux contenus de mémoire après la 9ème phase sont : 40 ^*>3^ : *96a^ + 133aa + 85a^ + 50a^ + 26a^ + + 3a^ (Spa) : 315aa + 2l6a2 + l40a3 + 84a4 + 45a5 + 20ag + 6a? Enfin, au cours de la dernière phase, on obtient le caractère de contrôle encore manquant : 6-901369 ^ 2000680 (Sp3) Î a80at + 189*2 + 120«3 + 70a% + 36«5 + 15ag + 4a? Les caractères de contrôle obtenus peuvent s'exprimer par la formule générale : PV = (v-1) 1 • (p-v-l) 1 -2 a* ^J~U+i~>l) mod M (1) ji=l p. i,J1 5 i=v (v = 1| 2t • • • • p) p étant le nombre désiré p de caractère de contrôle et ■ a M+l-p étant le nombre de caractères d'information, comme on peut le vérifier facilement par induction» 10 Si le nombre réel de caractères d'information est plus petit, il est complété par des caractères fixes, par exemple des O, jusqu'au nombre désiré. Comme poids, on obtient suivant ce procédé, les valeurs : 15 V " (v-ih • (p-t-ih • if" -oa * -ial i=v (v = 1, 2,.... p) (jb = 1, 2, «... m) Une fiabilité optimale s'obtient lorsque tous les détermi— 20 nants et sous-déterminants issus de la matrice des poids sont différents de 0. La formule (2) des poids satisfait à cette condition, ce qui assure le maximum de fiabilité. La désertion qui va suivre en regard du dessin annexé, le tout donné à titre d'exemple non limitatif, fera bien comprendre 25 comment l'invention peut être réalisée, les particularités qui ressortent tant du texte que du dessin faisant, bien entendu, partie de ladite invention. La fig. la est un agencement comportant un additionneur et un commutateur double. 30 La fig. lb est un agencement comportant un commutateur sim ple et une mémoire intermédiaire. La fig. 2 représente l'utilisation de compteurs montés en série. Sur la fig. la, le caractère arrivant est stocké dans la 35 ' mémoire d'entrée Spfl. Les mémoires Sp^ à Sp^ sont destinées à enregistrer les caractères de contrôle et, au début, toues ces mémoires sont mises à zéro. Les mémoires peuvent être constituées par des étages 6901369 2000680 basculeurs bistables et être montées par exemple en registres à décalage* Au cours de chaque phase d'inscription ou "pas", le commutateur S connecte les mémoires Sp et Sp^ à l'entrée de l'additionneur Ad modulo M et le résultat est stocké dans Sp^. 5 Ensuite, le contenu de (Sp^) et de (Sp^) parvient dans l'additionneur Ad modulo M et le résultat est stocké dans Sp , et ain-al de suite. L'inscription d'informations terminée, le contenu de l'avant dernière mémoire (Sp^) et celui de la mémoire pénultième 10 (Sp^) sont additionnés dans Ad et le résultat est stocké dans la mémoire (Sp^). Ensuite, on forme la somme du contenu de (Sp^) et de (Spg) et cette somme est transmise à Sp^, tout comme la somme des contenus de (Spg) et de (Sp^) est transmise à (Sp^)• Au cours du pas suivant, la même opération s'effectue 15 jusqu'au stockage dans (Sp^) et, au cours du dernier pas jusqu'au stockage dans (Sp^). En vue de simplifier le commutateur S, on peut en outre utiliser une mémoire intermédiaire Sp^ qui stocke temporairement le résultat de l'additionneur et/ou fait office de mémoire 20 d'inscription d'un des termes de somme de l'additionneur* Ce dernier cas est représenté en détail sur la fig. lb* Lorsqu'un commutateur impulsionnel T occupe la position 1, il se forme la somme du contenu de la mémoire intermédiaire et de celui de la mémoire connectée par le commutateur S^ et cette somme est stoc-25 kée provisoirement, avec un retard donné, dans la mémoire intermé diaire Sp . Ensuite, dans la position 2, il se produit un stocka ge en retour dans la mémoire connectée, de sorte qu'ensuite la somme figure dans les deux mémoires et que le commutateur S^ pas se dans la position suivante : 30 . En principe, les nombres de contrôle ne sont pas utilisés en parallèle, mais l'un après l'autre, de sorte que les mémoires doivent être interrogées successivement. Dans ce cas, on peut tirer parti du fait que les caractères de contrôle sont constitués par succession dans le temps et peuvent être chaque fois 35 utilisés au moment de la formation définitive. A cet effet, la valeur de sortie de l'additionneur Ad modulo M est chaque fois prélevée lorsque les contenus de mémoire finaux sont fixés. Si les mémoires Sp^ à Sp^ sont réalisées sous forme de compteurs modulo M, ZI à Z5, l'additionneur utilisé avec la mé-40 moire intermédiaire peut être omis. Après un nombre d'impulsions 6901369 2000680 ^ correspondant aux caractères d'entrée a , le compteur ZI est dé-placé de a positions* Après M autres Impulsions, le compteur ZI parviei^t à nouveau dans la même position, tandis qu'après le passage par zéro du compteur ZI, les impulsions traversent égale-5 ment le compteur Zg et réalisent ainsi une addition* Par M impulsions dans le compteur Zg et la connexion du compteur Z^, il se produit, après le passage par zéro, une addition dans le compteur Zyt et ainsi de suite. On peut alors se contenter d'un agencement selon la fig. la dans lequel Ad et SpQ sont omis, le commuta-10 teur S étant actionné de la même manière* On peut cependant aussi recourir à un agencement tel que représenté sur la fig. 2. A chaque caractère entrant a^, + K.M impulsions parviennent dans le compteur Z^ et toutes les impulsions après le premier passage par zéro de ce compteur, par-15 viennent dans le compteur Z^, toutes les impulsions après le 1er passage de ce dernier compteur parviennent aussi dans le compteur-Z^, et ainsi de suite. K est un nombre entier qui est à nouveau déterminé par le fait qu'il se produit au moins un passage par zéro de l'avant-dernier compteur qui est choisi fixe et égal à 20 K = p-1. Après inscription et traitement du dernier caractère d'information, on dispose de deux caractères de contrôle dans les deux derniers compteurs* Pour déterminer les autres caractères de contrôle (non représentés sur le dessin) K.M impulsions par-25 viennent dans l'avant-dernier compteur, et après le passage par zéro de celui-ci, toutes les impulsions parviennent également dans le compteur antépénultième et ainsi de suite. K est à nouveau un nombre entier qui est fixé par la progression après un passage à zéro du premier compteur ou du deuxième ou par K = 30 p-2. Après ce pas, le premier caractère de contrôle se trouve dans le compteur 1. Pour déterminer le second caractère de contrôle (dans le cas où p 3), K.M impulsions traversent l'avant-dernier compteur et, de la même manière, une partie correspondante des compteurs précédents, mais uniquement jusqu'au 2ème comp— 35 teur. Le compteur Z^ est ainsi déjà isolé. Au cours du pas suivant, le compteur Zg est isolé , de sorte qu'il ne se produit plus de changement dans la position de comptage des compteurs Z^ et Zg et ainsi de suite. L'opération se termine par l'isolement du compteur antépénultième ou immédiatement avant* 40 Les caractères de contrôle peuvent être obtenus directe- 6901369 2000680 ■«t à partir des positions finales des coapteurs, mais aussi par décodage, par exemple par formation du complément. Si l'on désire que trois caractères de contrôle, on peut renoncer à l'inversion de l'opération de traitement. Après ins— 5 cription et traitement du dernier caractère d'information, on peut prélever deux caractères de contrôle des deux dernières mémoires, et dans le présent cas le troisième caractère de contrôle peut être prélevé après un pas ultérieur, qui correspond à l'introduction supplémentaire d'un O à partir du centre de la 10 mémoire. Toutefois, les caractères de contrôle ne sont alors pas dispoiuLbles simultanément en ce sens que la mémoire centrale contient d'abord le second caractère de contrôle et, après un nouveau pas, le troisième caractère de contrôle, ce qui y entraîne l'effacement du second caractère de contrôle. .6901369 2000680 REVENDICATIONS : 1.Procédé pour calculer un nombre arbitraire prédéterminé de caractères de. contrôle à partir de données d'information et paur contrôler des données d'information en dérivant, dont les carac-5 tères individuels sont rangés suivant un système de classes résiduelles modulo M, caractérisé en ce qu'une mémoire est utilisée pour chaque chiffre de contrôle et qu'après chaque inscription d'un caractère, le nombre correspondant est ajouté modulo M au contenu de la première mémoire, le résultat ainsi obtenu est 10 ajouté au contenu modulo M de la mémoire suivante, et ainsi de suite, et après l'inscription et le traitement du dernier caractère d'information, l'ordre de traitement étant inversé, le contenu de la mémoire pénultième est ajouté à celui de la mémoire antépénultième, et ainsi de suite, et au cours de cette première 15 phase, après la fin de l'inscription, le contenu de la première mémoire est enregistré, puisegun|our« de la seconde phase correspondante, le contenu de la/mémoire est enregistré et ainsi de suite jusqu'à l'enregistrement du contenu de la mémoire antépénultième, le dernier contenu de mémoire obtenu donnant les caractères 20 de contrôle. 2*Procédé selon la revendication 1, caractérisé en ce que les nombres de contrôle sont prélevés à partir des contenus des mémoires, par exemple par formation du complément* 3«Procédé selon la revendication 1 ou 2, caractérisé en ce 25 que les nombres de contrôle sont obtenus successivement dans le temps à partir des résultats des additions correspondantes fournies pour les contenus finaux des mémoires* 4. Procédé pour déterminer -trois caractères de contrôle selon la revendication 1 ou 2, caractérisé en ce qu'après l'inscrip-30 tion du dernier caractère d'information, deux des caractères de contrôle sont prélevés à partir des deux dernières mémoires et qu'ensuite le troisième caractère de contrôle est prélevé de la mémoire pénultième après une phase ultérieure correspondant à l'inscription supplémentaire d'un zéro sans inversion du sens de 35 traitement. 5«Procédé selon les revendications 1 à 4 pour contrôler des groupes de données comportant déjà les caractères de contrôle, caractérisé en ce que les caractères de contrôle sont à nouveau 6901369 2000680 déterminés à partir de donné'es d* information et sont comparés avec les digits de contrôle et que la non-concordance provoque un signal d'erreur ou une indication d'erreur. 6.Dispositif pour la mise en oeuvre du procédé selon les 5 revendications 1 à 4, caractérisé en ce qu'une mémoire d'inscription est prévue pour les nombres entrants consécutifs, associés aux données d'information individuelles, et qu'un commutateur connecte la sortie de la mémoire d'inscription à l'entrée de la première mémoire du caractère de contrôle ou la sortie de 10 chaque mémoire de caractère de contrôle à l'entrée de la mémoire de caractère de contrôle suivante ou précédente par l'intermédiaire d'un additionneur modulo M. 7-Dispositif selon la revendication 6, caractérisé en ce qu'il comporte une mémoire intermédiaire qui stocke le résultat 15 de l'additionneur modulo M et/ou fournit chaque fois un terme d'addition pour l'additionneur modulo M. ô.Dispositif pour la mise en oeuvre du procédé selon les revendications 1 à 4, caractérisé en ce que les mémoires de caractères de contrôle sont réalisées sous forme d'additionneurs 20 modulo M, que les nombres additionnés aux données d'information individuelles sont représentés par un nombre correspondant d'iaqpulsions et qu'jin commutateur connecte les entrées de compteurs voisins. 9«Dispositif selon la revendication 8, caractérisé en ce 25 que pour lraddition du contenu de deux compteurs modulo M, le premier compteur reçoit M impulsions de comptage et après le passage peur zéro de ce premier compteur, les entrées de deux compteurs modulo M sont connectées en parallèle, de sorte que le second compteur reçoit les impulsions de comptage entrantes res-30 tantes. 10.Dispositif selon les revendications 8 et 9j caractérisé en ce que tous les compteurs sont montés en série et qu'après le passage par zéro d'un compteur modulo M, selon le sens du traitement, le compteur modulo M précédent ou le compteur modu— 35 lo M suivant, reçoit les impulsions de comptage entrantes suivantes, tandis que pour l'inscription d'un nombre le premier compteur reçoit un même nombre d'impulsions plus un multiple entier de M impulsions ou le pénultième compteur reçoit, après la fin de l'inscription dans le compteur pénultième, un multi-kO pie entier de M impulsions pour calculer les digits de contrôle.