FR2556483A1 - Systeme de detection d'erreurs perfectionne - Google Patents

Abstract

LE SYSTEME DE DETECTION DES ERREURS CONTENUES DANS UN ENREGISTREMENT DE DONNEES CONSISTE A CODER LES DONNEES, DE MANIERE A PROPAGER UNE ERREUR CONTENUE DANS UN MULTIPLET DANS LES MULTIPLETS SUIVANTS ET, AVANTAGEUSEMENT, A LA DISTRIBUER DE MANIERE ALEATOIRE, DE FACON A ACCROITRE LENTEMENT LES PROBABILITES DE DETECTION DES ERREURS. A CETTE FIN, LE SYSTEME EFFECTUE UNE OPERATION OU EXCLUSIF ENTRE CHAQUE MULTIPLET I ET LE MULTIPLET PRECEDENT I-1, CE DERNIER AYANT ETE PREALABLEMENT PROBABILISE PAR APPLICATION D'UNE FONCTION PREDETERMINEE, DE MANIERE A OBTENIR UNE VALEUR RESULTANTE R QUI EST MISE EN MEMOIRE. POUR LA LECTURE, UNE OPERATION OU EXCLUSIF EST EFFECTUEE ENTRE CHAQUE VALEUR R EXTRAITE DE LA MEMOIRE ET LE MULTIPLET PRECEDEMMENT RECONSTITUE I-1 AUQUEL LA FONCTION PREDETERMINEE A ETE PREALABLEMENT APPLIQUEE POUR OBTENIR LE MULTIPLET RECONSTITUE I.

Description

i

La présente invention se rapporte au domaine de la dé-

tection des erreurs et plus particulièrement à des procédés

de détection des erreurs utilisés dans un ensemble de traite-

ment de l'information pour identifier les erreurs contenues dans des données mises en mémoire.

La complexité des ensembles de traitement de l'informa-

tion modernes nécessite que des moyens soient utilisés pour détecter les erreurs contenues dans les bits de données mis en mémoire, lus ou manipulés d'une autre manière. Par exemple, des erreurs peuvent être introduites dans les données par suite des variations mécaniques et/ou électriques qui se produisent dans l'ensemble de traitement de l'information,

telles que celles dues à la présence d'une matière étran-

gère sur les têtes de lecture/écriture d'un dispositif de mé-

moire de masse à bande ou à disque. D'autres sources suscep-

tibles d'introduire des erreurs ou de modifier d' une autre manière les bits de données sont notamment l'usure naturelle du support d'enregistrement, les variations de la tension de

la source d'alimentation en courant de l'ensemble de traite-

ment de l'information ainsi que les erreurs de "logiciel" induites par les impuretés radioactives contenues dans le

carter du dispositif de mémoire et par les rayons cosmiques.

Divers procédés ont été mis au point dans le but de détecter les erreurs introduites dans les données mises en

mémoire ou manipulées d'une autre manière. Un système cou-

ramment employé de détection des erreurs comprend l'emploi d'un simple code de total (ou somme) de contrôle. Typiquement, les données sont organisées en enregistrements qui comprennent une multiplicité de multiplets (ou mots). Chaque multiplet est, à son

tour, composé de plusieurs bits (typiquement 8). Un système qui uti-

lise un procédé à simple total de contrôle effectue une opé-

ration OU exclusif entre les multiplets consécutifs de l'en-

registrement. Ainsi, comme représenté sur la Fig. 1, les 8

bits qui constituent le multiplet A1 font l'objet d'une opé-

ration OU exclusif avec les 8 bits qui constituent le multi-

plet A2. De même, la quantité binaire résultant de l'opéra-

tion entre A et A2 fait l'objet d'une opération OU exclusif A 2 avec les bits qui constituent le multiplet A3 et ainsi de

suite. Le total de contrôle est défini comme étant la quanti-

té binaire nette résultante obtenue à partir de ces opér&-

tions OU exclusif. La quantité de total de contrôle résul-

tante est typiquement introduite à la fin de l'enregigstre-

ment comme représenté sur la Fig. 1 par le multiplet X Ai.

Dans de nombreux ensemble de traitement de l'informa-

tion, les données sont écrites sur un support d'enregistre-

ment magnétique,tel qu'un disque ou une bande magnétique.

Dans les ensembles qui utilisent un procédé de détection des erreurs employant un total de contrôle, les données sous la forme d'un grand nombre de multiplets constituant l'ensemble de l'enregistrement sont écrites séquentiellement sur le support magnétique, le multiplet A1 étant écrit le premier puis les multiplets suivants étant écrits et, enfin, un ou

plusieurs multiplets constituant le total de contrôle résul-

tant étant disposés à la fin de l'enregistrement. Lors de la lecture des données sur le support magnétique, l'ensemble

de traitement de l'information lit séquentiellement le conte-

nu de l'ensemble de l'enregistrement tout en recalculant la

valeur du total de contrôle. Après que la totalité de l'en-

registrement a été extraite du support d'enregistrement, la valeur du total de contrôle recalculée est comparée au total de contrôle précédemment enregistré en tant que partie de l'enregistrement. Si les deux totaux de contrôle ne sont pas

égaux à l'identique, il est admis que les données con-

tiennent une erreur.

L'emploi d'un procédé de détection des erreurs utilisant

un simple total de contrôle n'assure pas une protection aus-

si efficace qu'on pourrait le penser. Par exemple, le procé-

dé à simple total de contrôle présente une sensibilité inhé-

rente dépendant de la configuration binaire pour les courtes

salves d'erreurs, réparties au hazard dans tout l'enregistre-

ment. L'emploi d'une opération OU exclusif entre les multi-

plets consécutifs de l'enregistrement rend possible que des

erreurs s'annulent mutuellement et ne soient pas détectées.

Par exemple, si l'état binaire du bit n 2 d'un multiplet particulier de l'enregistrement est modifié par suite d'une défaillance mécanique et/ou électrique (par exemple,un 1 est modifié enun état binaire 0) et si le bit n 2 d'un autre

multiplet est modifié d'une manière semblable (un état bi-

naire 0 est accidentellement modifié enun état binaire 1)

les erreurs des deux multiplets s'annulent au cours de l'opé-

ration OU exclusif. Dans le cas de deux bits erronés au ha-

zard la probabilité d'une non détection de l'erreur est

d'approximativement un sur huit.

Un procédé pour améliorer la fréquence de détection des erreurs au moyen du simple total de contrôle consiste à ajouter une"imbrication' Par exemple, un total de contrôle à 3 multiplets engendre trois valeurs de total de contrôle

résultantes séparées pour un enregistrement. Comme représen-

té sur la Fig. 2, la première valeur de total de contrôle

peut être déterminée pour les multiplets A1, A2, A3 etc...

qui représententdes multiplets imbriqués séquentiels du to-

tal de contrôle. De même, un second total de contrôle sera

calculé pour les multiplets B1, B2, B3, etc... et un troi-

sième pour les multiplets C1, C2, C3, etc... Bien que l'im-

brication réduise de manière significative la probabilité de non détection des longues salves d'erreurs aléatoires, la probabilité de non détection des salves d'erreurs éparses

s'est avérée être d'une grandeur inacceptable.

Par conséquent, il est souhaitable de disposer de moyens

pour accroître la capacité de détection des erreurs conte-

nues dans des données mises en mémoire et manipulées. Comme on le décrira ci-après, la présente invention fournit des

appareils et des procédés pour améliorer la capacité de dé-

tection des erreurs en distribuant de manière aléatoire et er propaqeant une erreur dans l'ensemble de l'enregistrement de données. La probabilisation et la propagation d'une erreur accroît de

manière importante la probabilité de sa détection.

La présente invention fournit des procédés et appareils pour améliorer la détection des erreurs dans un ensemble de traitement de l'information. Les techniques de la présente invention assurent qu'il existe une forte probabilité qu'une erreur contenue dans un enregistrement de données (chaque

enregistrement comprenant une multiplicité de bits de don-

nées) soit détectée. Dans le cas d'une erreur, la présente invention applique une fonction de probabilisation à l'erreur qui modifie les bits suivant à l'intérieur de l'enregistre- ment puis propage et distribue alatoi:rement à noruveau l'erreur dans

tout l'enregistrement pour amplifier ses dimensions appa-

rentes. La distribution aléatoire et la propagation de 1 'erreur

abaisse de manière importante la probabilité de non détec-

tion des erreurs aléatoires contenues dans un enregistre-

ment en ce sens que la capacité de détection des erreurs

n'est plus sensible à la configuration binaire. L'utilisa-

tion des deux fonctions, de propagation et de distribution aléatoire, modifie considérablement les données contenant une erreur de sorte qu'il existe une forte probabilité de détection de l'erreur lorsqu'on utilise les techniques à total de contrôle. D'autres caractéristiques de l'invention apparaitront

à la lecture de la description qui va suivre et à l'examen

des dessins annexes dans lesquels:

la Fig. 1 est une illustration d'un système de détec-

tion d'erreurs à total de contrôle simple;

la Fig. 2 est une illustration d'un système de détec-

tion d'erreur à totaux de contrôle imbriqués;

La Fig. 3 est un schéma-bloc qui représente un ordina-

teur qui incorpore les enseignements de la présente invention;

les Fig. 4(a)-(b) illustrernt un procédé de mise en m6-

moire et de lecture utilisé par la présente invention; la Fig. 5 illustre la propagation d'une erreur qui se produit lorsqu'on utilise la technique des Fig. 4(a)-(b);

les Fig. 6(a)-(b) illustrent un procédé de mise en mé-

moire et de lecture pour la propagation et la distribution aléatoire d'une erreur utilisé par la présente invention; les Fig. 7(a)-(d) illustrent un autreprocédé de mise

en mémoire et de lecture pour la probabilisation et la pro-

pagation d'une erreur utilisant des totaux d'erreur imbri-

qués.

La description détaillée donnée ci-après est présentée

en grande partie à l'aide d'algorithmes et de représentations symboliques d'opérations effectuées sur des bits de données

à l'intérieur d'une mémoire d'ordinateur. Ces descriptions

algorithmiques et représentations symboliques sont les

moyens utilisés par les spécialistes des techniques de trai-

tement de l'information pour transmettre le plus efficace-

ment possible la substance de leurs travaux aux autres spé-

cialistes de ces techniques.

Dans le cadre de la présente description, et d'une ma-

nière générale, un algorithme est conçu comme étant une sé-

quence auto-cohérente d'étapes qui aboutissent à un résultat

désiré. Ces étapes sont celles qui nécessitent des manipula-

tions physiques de quantités physiques. Habituellement,mais non nécessairement, ces quantités se présentent sous la

forme de signaux électriques ou magnétiques qui sont ca-

pables d'être mis en mémoire, transférés, combinés, compares

et manipulés d'autres manières appropriées. Il s'avère com-

mode,de temps à autre, principalement pour des raisons d'u-

sage courant, d'appeler ces signaux des bits, des valeurs, des éléments, des symboles, des caractères, des termes, des nombres ou analogues. On doit cependant garder à l'esprit

que tous ces termes et autres termes et expressions simi-

laires doivent être associés aux quantités physiques appro-

priées et sont simplement des étiquettes commodes appli-

quées à ces quantités.

En outre, les manipulations effectuées sont souvent désignées par des termes, tels qu'addition ou comparaison, qui sont habituellement associés à des opérations mentales effectuées par un opérateur humain. Une telle capacité d'un opérateur humain n'est ni nécessaire ni désirable dans la plupart des cas dans aucune des opérations décrites ici qui

entrent dans le cadre de la présente invention; les opéra-

tions sont des opérations machine. Les machines utilisables pour effectuer les opérations de la présente invention sont notamment les ordinateurs numériques universels et

autres dispositifs analogues. Dans tous les cas, la distinc-

tion entre les opérations de procédé utilisées pour faire fonctionner un ordinateur et la méthode de calcul proprement dite devrait être notée. La présente invention se rapporte aux étapes de procédé utilisées pour faire fonctionner un ordinateur afin de traiter des signaux électriques ou autres signaux physiques(par exemple, mécaniques, chimiques) pour

engendrer d'autres signaux physiques désirés.

La présente invention se rapporte également à un appa-

reil approprié pour effectuer ces opérations. Cet appareil peut être spécialement construit aux fins requises ou il

peut être constitué par un ordinateur universel tel que sélec-

tivement commandé ou reconfiguré par un programme d'ordina-

teur enregistré dans l'ordinateur. Les algorithmes présentés

ici ne sont pas liés d'une manière inhérente à un ordina-

teur ou autre appareil particulier quelconque. En particu-

lier, diverses machines universelles peuvent être utilisées avec les enseignements donnés ici ou il peut éventuellement

s'avérer plus commode de construire un appareil plus spécia-

lisé pour exécuter les étapes de procédé requises. La struc-

ture requise pour diverses machines de ce type ressortira

de la description donnée ci-dessous.

La description détaillée donnée ci-après sera divisée

en plusieurs chapitres. Le premier de ces chapitres traitera d'un agencement de système général pour mettre en mémoire, lire et manipuler des données. Les chapitres suivant seront consacrés aux appareils et procédés utilisés pour obtenir une capacité de détection des erreurs améliorée dans un

ensemble de traitement de l'information.

En outre, dans la description qui va suivre, de nom-

breux détails seront donnés, par exemple, en ce qui concenre des conventions algorithmiques, des nombres spécifiques de bits,des opérations binaires, etc... afin de faciliter une pleine compréhension de la présente invention. Cependant, il apparaitra clairement aux spécialistes de la technique que la présente invention peut être mise en oeuvre sans ces détails spécifiques. Dans d'autres cas, on ne décrira pas en détail des circuits et structures bien connus pour ne pas

ubscurcir inutilement la présente invention.

CONFIGURATIOU. GENERALE DU SYSTEME

La Fig. 3 représente un systèx.e typique dordinateur pour la lecture, la mise en méroire et la manipulation de données. On a représenté sur cete figure, un ordinateur 20 qui coprend trois 6ments principaux. Le premier de ces 64é!ments estq le circuit d'entrée/zortie (E/IS) 22 qui est ut. iLis pour transiettre dâs infornations sous une forese structurée d'une manière appropriee i d'autres parties e l'ordinateur 20 ou pour en revoir des informations On a également repFrsenté conme faisaut partie de lt'ordinateur 20 une unLté de traitement centale (UTC} 24 et une mmoire 260 Ces deux derniers lè!nents sont ceus que l'on trou-e typi=

quemenc' dans la l!upart Ies ordinteurSo En fait, les di-

-vrs é eïlts iContenu ZL I e inetérier de. ordinateur 20 sont destings. rte repréesentatIfs de cette catégorie génerale

de processeurs s de données. Des ereîples particuliers de pro-

esseurs de onnéee so.cptibles e remp!ir le rôle de ltor-

dinateur 20 sont, nc'aueme-rt, lees machines fabriquées par Apple Computer, ncCu Certin Ca!ifornie (EUAJo D autres erdina-teurs possèdant des oap=ucits similaires peuvent natu relleent -tre adaptés facilemen' pour exécuter les diverses

fonctions décrites ci-desscus.

:On a également rerirsenhté sur la Figo 3 un dispositif d'entre 30 représent... das un C e.ya isatio 't'pique coIef costi- é par un clauier. X! d i cre ependant bien compris que le dispositif denre pourrait -tre un!ecteur de cartes, un l etur o bansde nac tise ou de bane papier, *u un autre dispositif o -,re qoelconrue Dienm co.%nnu { com pris, naturellement, n a te ori-na'eur, o Un dispositif de moir e masse 32 3, al e. circ ut Z/I 22 fournit une ca= pacit% de stocka, e s ria-ta l:l lGordinartcur 20o La mé=

eZoire de masse peut co porter d=au2res prograrles et ana-

loguns et peut être cons-itues p-r un lecteur de bande mag'né tique ou de bande pa.ier u uar,n autre disposit'if bien cc-nnu queiconque. OnCr coprenira que ltes donnes conenues dans la m.moire de masse 32 peuvent, dans des cas approprifs Otre incorporées d'une manière classique à l'ordinateur 20

en tant que partie de la mémoire 26.

En outre, on a représenté un écran de visualisation 34

qui est utilisé pour afficher les données qui sont manipu-

lées conformément à la présente invention. Un tel écran de visualisation peut être constitué par l'un quelconque de divers dispositifs d'affichage à tube cathodique bien connus.

Au cours du fonctionnement de l'ordinateur 20, des er-

reurs peuvent être introduites dans les données qui sont mises en mémoire dans la mémoire 26 et dans la mémoire de masse 32 ou extraites de ces mémoires. Le fait de ne pas

détecter les erreurs contenues dans les données mises en mé-

moire ou manipulées d'une autre manière peut engendrer des réponses erronées de l'ordinateur. Comme on le décrira, la présente invention fournit des procédés et appareils pour accrottre la capacité de détection des erreurs contenues dans des données mises en mémoire ou manipulées d'une autre manière, améliorant ainsi de manière importante la fiabilité

des opérations de l'ordinateur.

PROPAGATION DES ERREURS

Comme précédemment mentionné, l'emploi d'une technique d'imbrication diminue de manière importante la probabilité de non détection dans le cas des longues salves d'erreurs aléatoires à l'intérieur d'un enregistrement. Cependant,on a trouvé que la probabilité de non détection des erreurs dans le cas de salves d'erreurs éparses réparties au hazard dans l'ensemble de l'enregistrement reste d'une grandeur

inacceptable. Par conséquent, un aspect de la présente in-

vention a pour effet de propager une erreur dans la totalité

de l'enregistrement,accroissant ainsi la probabilité de dé-

tection des erreurs.

On décrira maintenant, en se référant à la Fig. 4, le

procédé de la présente invention pour la propagation des er-

reurs. Des multiplets individuels-de données A, B, C et D qui peuvent être des multiplets imbriqués séquentiels d'un enregistrement doivent être mis en mémoire ou manipulés d'une

autre manière dans un système d'ordinateur. La présente in-

vention met directement en mémoire le premier multiplet A, par exemple, dans la mémoire 26 ou dans la mémoire de masse

32 qui peut, par exemple, comporter un support d'enregistre-

ment magnétique ou analogue. Comme représenté, le contenu du

multiplet suivant, le multiplet B, fait l'objet d'une opéra-

tion OU exclusif avec le contenu du multiplet A précédent et la quantité binaire résultant de cette opération OU exclusif entre le multiplet B et A est mise en mémoire. De même, le contenu du multiplet B précédent fait l'objet d'une opération

OU exclusif avec le multiplet C et la quantité binaire résul-

tante est mise en mémoire. Ainsi, à la différence des procé-

dés de codage de la technique antérieure, la présente inven-

tion met en mémoire le résultat d'une série d'opérations OU exclusif entre les multiplets séquentiels (ou imbriqués)

d'un enregistrement.

On décrira maintenant,en se référant à la Fig. 4(b),la reconstitution des données mises en mémoire conformément au principe de la Fig. 4(a). Comme représenté, les données sont décodées à partir des quantités binaires résultantes mises en mémoire conformément au procédé que l'on a décrit en se référant à la Fig. 4(a) en utilisant de nouvelles opérations

OU exclusif. Comme représenté, les quantités binaires résul-

tantes extraites font l'objet d'une opération OU exclusif

avec les résultats décodés obtenus du multiplet immédiate-

ment précédent (ou imbriqué). Par exemple, l'extraction du

multiplet A de la mémoire de masse 32 ou de la mémoire 26 pro-

duit simplement une quantité binaire représentative du conte-

nu du multiplet A étant donné que le multiplet A a été ex-

trait sans modification des moyens de mémoire. Cependant, la quantitérésultante mise en mémoire suivante(B A) extraite ensuite des moyens de mémoire 32 ou analogues fait l'objet d'une opération OU exclusif avec le multiplet précédemment

décodé, à savoir le multiplet A, dans le présent exemple.

Il apparaitra clairement que l'opération OU exclusif entre les quantités résultantes mises en mémoire conformément à la Fig. 4(a) et les données précédemment décodées (par exemple,

le multiplet A) décode effectivement et reconstitue le mul-

tiplet B. De même, une opération OU exclusif entre le multi-

plet B reconstitué et la quantité codée (C B) permet de re-

constituer le multiplet C. Ainsi, le procédé représenté sur la Fig. 4 fournit un moyen grace auquel on peut coder et mettre en mémoire des données dans un dispositif de mémoire et les décoder ensuite en utilisant une série de simples

opérations OU exclusif.

Sur la Fig. 5 à laquelle on se référera maintenant, on a représenté la propagation d'une erreur aléatoire dans un enregistrement de données. Conformément aux enseignements de

la présente invention, le premier multiplet A de l'enregis-

trement est mis en mémoire dans les moyens de mémoire dési-

rés, tels que la mémoire de masse 32 ou la mémoire 26 de l'ordinateur 20. Le multiplet B (qu'il soit consécutif ou imbriqué) fait l'objet d'une opération OU exclusif avec le contenu du multiplet A, la quantité résultante étant mise en mémoire dans les moyens de mémoire désirés. Ensuite, chacun

des multiplets suivants C, D et E fait l'objet d'une opéra-

tion OU exclusif avec les multiplets de données précédents,

conformément au procédé de la Fig. 4(a).

Supposons, à titre d'exemple, qu'une erreur accidentelle

"e" soit présente dans le multiplet A d'un enregistrement.

Cette erreur peut être introduite au cours de la relecture ou lors du cycle d'écriture initial ou elle peut encore être

due à l'une quelconque des causes d'erreur possibles préc6-

demment décrites. Ainsi, la lecture du premier multiplet d'un

enregistrement produit une quantité représentative du multi-

plet A G>e. En utilisant les enseignements de la présente

invention, cette quantité (AG e) fait l'objet d'une opéra-

tion OU exclusif avec la quantité résultante suivante mise en mémoire (B A). Le résultat net de cette opération OU

exclusif estla quantité (B e). Ainsi, l'erreur a été pro-

pagée dans le multiplet B suivant et,comme il résulte claire-

ment de la Fig. 5, l'erreur "e" est ainsi propagée dans cha-

cun des multiplets successifs de l'enregistrement. En pra-

tique, un ensemble de traitement de l'information utilisant

un processus de simple total de contrôle comparerait la va-

l1 leur de total de contrôle recalculée basée sur les données lues représentées sur la Fig. 5 à la quantité de total de

contrôle précédemment mise en mémoire pour les données ini-

tialement mises en mémoire conformément au procédé de la Fig. 4(a). Du fait de la propagation de l'erreur conformé-

ment au procédéde la présente invention, les totaux de con-

trôles ne seraient pas égaux et la présence d'une erreur

serait admise.

PROPAGATION ET DISTRIBUTION ALEATOIRE

On décrira maintenant,en se référant à la Fig. 6, un procédé utilisant les enseignements de la présente invention qui propage et distribue aléatoirement également les erreurs contenues

dans un enregistrement de données. Comme dans l'exemple précé-

dent, A, B, C et D représentent des multiplets consécutifs

(qu'ils soient séquentiels ou imbriqués) d'un enregistrement.

La notation prime" ' " représente une fonction, fonction qui

est conçue pour être aussi aléatoire que possible. La nota-

tion seconde "" " représente la fonction appliquée deux fois

et ainsi de suite. Comme précédemment décrit, la présente in-

vention met directement en mémoire le premier multiplet A

dans les moyens de mémoire particuliers utilisés. Comme re-

présenté, le contenu du multiplet immédiatement suivant, le multiplet B, fait l'objet d'une opération OU exclusif avec le contenu du multiplet A précédent auquel une fonction de

probabilisation a été appliquée. La quantité binaire résul-

tant de cette opération OU exclusif entre les multiplets B

et A est alors mise en mémoire dans les moyens de mémoire.

De la même manière, le contenu du multiplet suivant C dans la séquence fait l'objet d'une opération OU exclusif avec le contenu du multiplet B précédent auquel la fonction a été appliquée et la quantité binaire résultante est alors également mise en mémoire. On comprendra que la fonction de

probabilisation utilisée peut être lun quelconque de nom-

* breux algorithmes de probabilisation bien connus; cependant,

dans la présente invention, on utilise une fonction de proba-

bilisation linéaire.

Sur la Fig. 6(b) à laquelle on se référera maintenant, on a représenté l'effet d'une erreur située au hazard dans un enregistrement de données. Supposons, à titre d'exemple,

qu'une erreur accidentelle "e" soit présente dans un multi-

plet "A" d'un enregistrement. Comme représenté sur la Fig. 6(b), l'extraction du premier multiplet d'un enregistrement produit une quantité représentative du multiplet A + e. En utilisant les enseignements de la présente invention, la fonction de probabilisation est appliquée à la quantité A G e ce qui produit la quantité (A e)1'. Cette quantité (A e)' fait alors l'objet d'une opération OU exclusif avec la quantité résultante suivante mise en mémoire B A'. Le résultat net de cette opération -OU exclusif est la quantité B e', dans laquelle e' est égale à A' (A' e)'. Ainsi, l'erreur a été propagée dans le multiplet B suivant et a

été probabilisée conformément à la fonction de probabilisa-

tion choisie. De la même manière, la fonction de distribution aléa-

toire est appliquée au multiplet B 6 e' résultant,ce qui pro-

duit la quantité (B e')' qui fait l'objet à son tour d'une opération OU exclusif avec la quantité C B' précédemment

mise en mémoire, ce qui produit la quantité C Ee", dans la-

quelle e" est égale à B' (B Oe')'. Ainsi, la fonction de

distribution aléatoire a été appliquée deux fois à l'erreur "e" distri-

buant aléatoirement de ce fait l'erreur précédenent distribuée aléatoi-

remant tandis qu'elle est propagée dans l'enregistrement. Ce processus

est répété tandis que les données sont séquentiellement ex-

traites de l'enregistrement, distribuant aléatoirement et propageant ainsi l'erreur dans la totalité de l'enregistrement et accroissant ainsi fortement la probabilité de détection des erreurs par

les techniques à total de contrôle.

Sur les Fig. 7(a) à 7(d), on a représenté un autre mode de réalisation de la présente invention. Bien que l'on ait décrit la présente invention en se référant à l'emploi de procédés de distribution aléatoire et de propagation d'erreur appliqués à des multiplets séquentiels ou imbriqués d'un enregistrement

de données, on a trouvé que l'on pouvait obtenir une probabi-

lité élevée de détection des erreurs en appliquant les ensei-

gnements de la présente invention directement aux quantités de total de contrôle elles-mêmes. Comme représenté sur la

Fig. 7(a), un enregistrement de données comporte des multi-

plets A, B, C, D, etc... Les quantités de total de contrôle Cl, C2 et C3 sont enregistrées à la fin de l'enregistrement de données. Comme représenté, le mode de réalisation préféré de la présente invention utilise un système à totaux de con-

trôle imbriqués de 3 multiplets, dans lesquels les multiplets

A, D, G etc... constituent les multiplets imbriqués séquen-

tiels du total de contrôle Cl. De la même manière, les multi-

plets imbriqués séquentiels B, E, H, etc... constituent les

multiplets qui servent à former le total de contrôle C2. En-

fin, les multiplets C, F, I, etc... constituent les multiplets

imbriqués séquentiels qui servent à former le total de con-

trôle C3. En outre, on notera que la lettre "c" désigne un

report d'une opération précédente.

Comme représenté sur la Fig. 7(b), la fonction de proba-

bilisation du mode de réalisation de la Fig. 7 comprend une "permutation circulaire" au cours de laquelle le contenu du total de contrôle C3 est décalé d'un bit à gauche (à savoir

le bit le moins significatif vers le bit le plus significa-

tif) et le bit le plus significatif vient occuper la place du bit le moins significatif. On a trouvé que l'emploi d'une permutation circulaire pour la probabilisation permettait une mise en oeuvre en temps réel dans une grande diversité

de systèmes d'ordinateur.

Comme représenté sur la Fig. 7(c), le codage de données

conformément aux enseignements de la présente invention com-

prend une permutation circulaire initiale du total de con-

trôle C3 (qui,au début du processus,se traduit simplement par la permutation circulaire de zéros binaires puisqu'aucune donnée n'a encore été enregistrée). Le total de contrôle Cl est alors mis égal au total de contrôle C1 plus le contenu

du multiplet A (plus tout report c). Lors de l'initialisa-

tion, C1 est simplement égal au contenu du multiplet A.Comme représenté, le premier multiplet est mis égal à la quantité binaire A ayant fait l'objet d'une opération OU exclusif avec le contenu du total de contrôle C3 et cette quantité binaire

est ensuite mise en mémoire dans des moyens de mémoire appro-

priés. Pour le premier multiplet d'un enregistrement, le con-

tenu du multiplet A est simplement mis en mémoire dans la mé-

moire de masse 32 ou dans la mémoire 26 de l'ordinateur 20 étant donné que C3 est initialement mis à zéro. La quantité de total de contrôle C2 est mise égale au contenu précédent de C2 plus la quantité binaire qui constitue le multiplet B ainsi que tout report éventuellement existant. Le multiplet B de l'enregistrement fait alors l'objet d'une opération OU exclusif avec le contenu du total de contrôle C1 et cette quantité résultante est mise en mémoire dans les moyens de mémoire appropriés. Le total de contrôle C3 est alors mis égal à soncontenu précédent plus le contenu du multiplet C

plus le report éventuel. Le contenu du multiplet C fait l'ob-

jet d'une opération OU exclusif avec le contenu du total de

contrôle C2 et cette quantité est alors mise en mémoire.

Une fois que les trois premiers multiplets A( C3, B( C1 et C C2 ont été mis en mémoire dans les moyens de mémoire,

conformément à la description qui précède, le contenu du to-

tal de contrôle C3 fait alors à nouveau l'objet d'une permu-

tation circulaire d'un bit, comme représenté sur la Fig. 7(a). Le contenu du total de contrôle Cl est alors ajouté au

contenu du multiplet D plus tout report résultant. Le conte-

nu du multiplet D fait l'objet d'une opération OU exclusif avec le contenu du total de contrôle C3 et cette quantité

résultante est alors mise en mémoire dans les moyens de mé-

moire. Comme représenté, le contenu du total de contrôle C2

est alors ajouté au contenu du multiplet E de l'enregistre-

ment plus tout report afin de redéfinir le contenu du total de contrôle C2. De la même manière, les multiplets suivant qui constituent l'enregistrement représenté sur la Fig. 7(a) sont mis en mémoire dans les moyens de mémoire appropriés et

les totaux de contrôle Cl, C2 et C3, sont mis à jour en con-

séquence.

On décrira maintenant en se référant à la Fig. 7(d) la

reconstitution des données conformément au processus de co-

dage représenté sur les Fig. 7(a) à 7(c). Avant la lecture,

les totaux de contrôle Cl, C2 et C3 sont définis dans la mé-

moire principale 26 de l'ordinateur 20 et sont mis égaux à

zéro. On rappelera que les quantités de total de contrôle ré-

sultantes en fin d'enregistrement C1, C2 et C3 sont enregis- trées à la fin de l'enregistrement représenté sur la Fig. 7(a). Comme représenté, la quantité extraite A C3 fait

l'objet d'une opération OU exclusif avec le contenu du to-

tal de contrôle C3 (qui est égal à zéro) ce qui a pour effet

la lecture vraie du contenu du multiplet A,si A C3 ne con-

tient pas d'erreur. Une fois le multiplet A lu, comme repré-

senté, la quantité CI est mise à jour par addition du conte-

nu de C1 au multiplet A plus le report éventuel (il n'y en a pas dans le présent exemple). De la même manière, la quantité binaire antérieurement mise en mémoire B C1 fait l'objet d'une opération OU exclusif avec la valeur de C1 qui vient d'être mise à jour, ce qui a pour effet le décodage et la lecture du multiplet B. La quantité C2 est alors mise à jour par addition à cette quantité du contenu du multiplet B (plus le report éventuel). Le multiplet C est alors extrait au moyen d'une opération OU exclusif entre la quantité C C2 précédemment mise en mémoire et la valeur de C2 qui vient d'être mise à jour. La quantité C3 est alors mise à jour par addition à cette quantité de la valeur du multiplet C

suivie d'une permutation circulaire comme précédemment dé-

crit. De cette manière, les multiplets séquentiels qui cons-

tituent l'enregistrement sont décodés et lus.

DETAILS DU CODAGE

Aucun langage de programmation particulier n'a été

indiqué pour exécuter les divers processus décrits ci-

dessus. Ceci est en partie dû au fait que les langages qui pourraient être mentionnés ne sont pas tous universellement disponibles. Chaque utilisateur d'un ordinateur particulier connaitra le langage qui est le plus approprié pour ses objectifs immédiats. En pratique il s'est avérê utile de mettre en oeuvre en grande partie la présente invention au moyen d'un langage assembleur qui fournit un code objet

exécutable par la machine.

Du fait que les ordinateurs et les systèmes moniteurs

qui peuvent être utilisés pour la mise en oeuvre de la pré-

sente invention sont composés de nombreux éléments diffé-

rents, on ne donnera pas ici une liste deprogramme détaillée.

On considère que les opérations et les autres processus ci-

dessus décrits et représentés dans les dessins annexés sont suffisamment explicites pour permettre à un spécialiste de la technique de mettre en oeuvre la présente invention ou

toute partie qui peut lui être utile.

Ainsi, on a décrit ci-dessus des procédés et appareils qui sont très avantageusement utilisés en combinaison avec un ordinateur numérique pour assurer une détection améliorée des erreurs. La distribution aléatoire et la propagation des

erreurs dans l'ensemble d'un enregistrement de données ef-

fectuées par la présente invention réduisent de manière très importante la probabilité d'une non détection des erreurs et accroît, de ce fait, la fiabilité d'un ensemble de traitement

de l'information.

Claims (25)

REVENDICATIONS

1 - Un procédé pour mettre en mémoire des données dans un ensemble de traitement de l'information (20, 30, 32, 34) et

les en extraire, ces données étant organisées en une multi-

plicité (N) de multiplets séquentiels, d'une manière telle qu'une erreur contenue dans un multiplet soit propagée dans chacun des multiplets suivants,ce procédé étant caractérisé en ce qu'il consiste: à effectuer une opération OU exclusif entre chaque multiplet (i) et le multiplet précédent (i-1)

afin d'obtenir une valeur résultante (Ri); à mettre en mê-

moire chacune des valeurs résultantes (Ri) dans un dispositif de mémoire (26, 32); à extraire les valeurs résultantes (Ri) du dispositif de mémoire; à reconstituer les multiplets de données à partir des valeurs résultantes en effectuant une opération OU exclusif entre chaque valeur résultante (Ri) et le multiplet de données précédemment reconstitué, de façon que: i =N multiplet = [ Ri multiplet i 1] i= formule dans laquelle: "N"est le nombre de multiplets que comportent les données, et j'désigne une opération OU exclusif; de telle sorte qu'une erreur contenuedans un multiplet est propagée dans tous les multiplets suivants cequi accroit

la possibilité de détection de cette erreur.

2 - Procédé selon la revendication 1, caractérisé en ce qu'il

comporte, en outre, l'étape qui consiste à calculer une pre-

mière quantité de total de contrôle pour les données avant l'étape e. mise en mémoire et à mettre en mémoire le total de contrôle avec les valeurs résultantes (Ri) dans les moyens

de mémoire.

3 - Procédé selon la revendication 2, caractérisé en ce qu'il

comporte, en outre, l'étape qui consiste à calculer une se-

conde quantité de total de contrôle pour les données recons-

tituées. 4 - Procédé selon la revendication 3, caractérisé en ce

qu'une erreur est détectée si les première et seconde quanti-

tés de total de contrôle ne sont pas égales.

- Procédé, selon la revendication 4, caractérisé en ce que les premier et second totaux de contrôle sont calculés en résolvant l'expression: N - 1 Total de contrôle = [ 7 multiplet i] Mod 2 i=0 dans laquelle multipleti désigne un multiplet à la position

i (i = 0, 1, 2,... N-1) desdites données.

6 - Procédé selon la revendication 5, caractérisé en ce que plusieurs premiers et seconds totaux de contrôle sont calculés pour les données, chacun des totaux étant calculés

pour un multiple imbriqué prédéterminé d'un multiplet spé-

cifié initial.

7 - Un système de détection d'erreurs perfectionné pour les données mises en mémoire dans un ensemble de traitement de l'information et extraites de cet ensemble, caractérisé en ce qu'il comporte: des moyens de mémoire (26, 32) pour mettre en mémoire une multiplicité (N) de multiplets séquentiels, des moyens de traitement couplés auxdits moyens de mémoire pour effectuer une opération logique sur les données, les moyens de traitement comprenant: des moyens d'écriture pour effectuer une opération OU exclusif entre chaque multiplet

(i) et le multiplet précédent (i-1) des données afin d'obte-

nir une valeur résultante (Ri) et pour mettre en mémoire la valeur résultante (Ri) dans les moyens de mémoire; et des moyens de lecture pour reconstituer les multiplets de données à partir des valeurs résultantes en effectuant une opération OU exclusif entre chaque valeur résultante (Ri) et le multiplet de données précédemment reconstitué (i-1) de façon que: multiplet = [Ri G multiplet i i 1] i1 formule dans laquelle: "N" est le nombre de multiplets que comportent les données, et "I "désigne une opération OU exclusif;

de telle sorte qu'une erreur dans un multiplet est pro-

pagée dans tous les multiplets suivants accroissant, de ce

fait, les possibilités de détection de l'erreur.

8 - Système de détection selon la revendication 7, caractéri-

sé en ce que les moyens de traitement comprennent des moyens pour calculer une première quantité de total de contrôle pour les données et pour mettre en mémoire cette première quantité de contrôle dans les moyens de mémoire avec lesdites

valeurs résultantes (Ri).

9 - Système de détection selon la revendication 8, caractéri-

sé en ce que les moyens de traitement comprennent des moyens pour calculer une seconde quantité de total d'erreur pour

les données reconstituées.

- Système de détection selon la revendication 9, caractéri-

sé en ce qu'une erreur est détectée si les premier et second

totaux d'erreur ne sont pas égaux.

11 - Système de détection selon la revendication 10, carac-

térisé en ce que les premier et second totaux de contrôle

sont calculés par les moyens de traitement en résolvant l'ex-

pression:

N-1

Total de contrôle = [ multipleti] Mod2 i= o dans laquelle multiplet i désigne un multiplet à la position

i (i = 0, 1, 2,... N-1) des données.

12 - Système de détection selon la revendication 11, carac-

térisé en ce que plusieurs premiers et seconds totaux de contrôle sont calculés pour les données, chacun des totaux étant calculé pour un multiple imbriqué prédéterminé d'un

multiplet spécifié initial.

13 - Un procédé pour mettre en mémoire des données dans un ensemble de traitement de l'information et les en extraire,

les données étant organisées en une multiplicité (N} de mul-

tiplets séquentiels, de façon qu'une erreur contenue dans

un multiplet soit distribuée et propagée dans chaque multi-

plet suivant, ce procédé étant caractérisé en ce qu'il con-

siste: à exécuter une opération OU exclusif entre chaque mal-

tiplet (i) et le multiplet précédent (i-1), le multiplet pré-

cédent ayant été distribué aldatoirement par une fonction prédéterminée

afin d'obtenir une valeur résultante (Ri); à mettre en mé-

moire la valeur de chacune des valeurs résultantes Ri dans un dispositif de mémoire (26, 32); à extraire les valeurs résultantes du dispositif de mémoire; à reconstituer les multiplets de données à partir des valeurs résultantes en

exécutant une opération OU exclusif entre chaque valeur ré-

sultante (Ri) et le multiplet de données précédemment recons-

titué, ladite fonction prédéterminée ayant été appliquée au multiplet de données précédemment reconstitué (i-1) avant ladite opération OU exclusif de façon que: r i =N multipleti = [Ri (multiplet i1] i=1i dans laquelle:

"N" est le nombre de multiplets séquentiels que com-

portent les données,

" " désigne une opération OU exclusif, -

n " représente la fonction prédéterminée; de telle sorte qu'une erreur contenue dans un multiplet

est distribuée et propagée dans chacun des multiplets sui-

vants,accroissant ainsi les possibilités de détection de l'erreur. 14 Procédé selon la revendication 13, caractérisé en ce qu'il comporte, en outre, l'étape qui consiste à calculer une première quantité de total de contrôle pour les données avant l'étape de mise en mémoire et à mettre en mémoire le total de contrôle avec les valeurs résultantes (Ri) dans les

moyens de mémoire.

- Procédé selon la revendication 14, caractérisé en ce qu'il comporte, en outre, l'étape qui consiste à calculer une seconde quantité de total de contrôle pour les données reconstituées. 16 - Procédé selon la revendication 15, caractérisé en ce

qu'une erreur est détectée si les première et seconde quan-

tités de total de contrôle ne sont pas égales.

17 - Procédé selon la revendication 16, caractérisé en ce que les premier et second totaux de contrôle sont calculés en résolvant l'expression: total de contrôle y. multiplet1] Mod2 i = 0 dans laquelle multipleti désigne un multiplet à la position i (i = 0, 1, 2,... N-1) desdites données. 18 - Procédé selon la revendication 17, caractérisé en ce que plusieurs premiers et seconds totaux de contrôle sont calculés pour les données, chacun des totaux étant calculé

pour un multiple imbriqué prédéterminé d'un multiplet spé-

cifié initial.

19 - Procédé selon la revendication 18, caractérisé en ce

que les multiplets sont imbriqués un par un.

- Procédé selon la revendication 18, caractérisé en ce

que les multiplets sont imbriqués 3 par 3.

21 - Procédé selon la revendication 18, caractérisé en ce que les données sont organisées en enregistrements,chacun des enregistrements comprenant unemultiplicité de multiplets

ayant 8 bits.

22 - Système de détection d'erreur perfectionné pour des don-

nées mises en mémoire dans un ensemble de traitement de l'in-

formation et extraites de cet ensemble, caractérisé en ce qu'il comporte: des moyens de mémoire (26, 32), pour mettre les données en mémoire sous la forme d'une multiplicité (N) de multiplets séquentiels; des moyens de traitement (24) couplés aux moyens de mémoire pour effectuer des opérations logiques sur les données, ces moyens comprenant des moyens d'écriture pour effectuer une opération OU exclusif entre

chaque multiplet (i) et le multiplet précedent (i-1), ce mul-

tiplet précédent ayant été distribué aléatoirement par une fonction prédéterminée afin d'obtenir une valeur résultante (Ri),et pour mettre en mémoire la valeur résultante (Ri) dans les moyens de mémoire; des moyens de lecture pour reconstituer les multiplets de données à partir des valeurs résultantes en exécutant une opération OU exclusif entre chaque valeur

résultante (Ri) et le multiplet de données précédemment re-

constitué, ladite fonction prédéterminée ayant été appliquée au multiplet de données précédemment reconstitué (i-1) avant ladite opération OU exclusif de façon que: multipleti =[ Ri i(multiplet_1)' =N dans laquelle "N" est le nombre de multiplets séquentiels que com- portent les données, " " désigne une opération OU exclusif, représente la fonction prédéterminée; de telle sorte qu'une erreur contenue dans un multiplet

est distribuée et propagée dans chacun des multiplets sui-

vants accroissant ainsi les possibilités de détection de l'erreur. 23 Système de détection d'erreur selon la revendication

22, caractérisé en ce que les moyens de traitement com-

prennent des moyens pour calculer une première quantité de total de contrôle pour les données et pour mettre en mémoire

cette première quantité de contrôle dans les moyens de mé-

moire avec lesdites valeurs résultantes (Ri).

24 - Système de détection d'erreur selon la revendication

23, caractérisé en ce que les moyens de traitement com-

prennent des moyens pour calculer une seconde quantité de

total d'erreur pour les données reconstituées.

- Système de détection d'erreur selon la revendication

24, caractérisé en ce que les moyens de traitement com-

prennent des moyens pour calculer plusieurs premiers et seconds totaux de contrôle pour les données, chacun des totaux de contrôle étant calculé pour un multiplet imbriqué

prédéterminé d'un multiplet initial spécifié.

26 - Système de détection d'erreur selon la revendication 25, caractérisé en ce que les multiplets sont imbriqués un

par un.

27 - Système de détection d'erreur selon la revendication , caractérisé en ce que les multiplets sont imbriqués trois

par trois.

28 - Un procédé pour mettre en mémoire des données dans un ensemble de traitement de l'information, ces données étant organisées en une multiplicité (N). de multiplets imbriqués

séquentiels, ce procédé étant caractérisé en ce qu'il con-

siste à définir des premier et second totaux de contrôle

correspondant à des multiplets imbriqués des données; à dis-

tribuer aléatoireent le contenu du second total de contr8le au moyen d'une fonction prédéterminée, à mettre le contenu du premier

total de contrôle égal au contenu du premier total de con-

trôle plus le contenu du premier multiplet; à effectuer une opération OU exclusif entre le contenu distribué aléatoirement du second

total de contrôle et le premier multiplet; et à mettre en mé-

moire la valeur résultante de l'opération OU exclusif dans

un dispositif de mémoire.

29 - Procédé selon la revendication 28, caractérisé en ce qu'il comporte, en outre, les étapes qui consistent: à mettre le contenu du second total de contrôle égal à la somme du contenu du second total de contrôle plus le contenu du second multiplet; à effectuer une opération OU exclusif entre le contenu du premier total de contrôle et le contenu

du second multiplet; et à mettre en mémoire la valeur résul-

tante de cette opération OU exclusif dans le dispositif de

mémoire.

- Procédé selon la revendication 29, caractérisé en ce qu'il comporte, en outre, l'étape qui consiste à définir un troisième total de contrôle correspondant aux multiplets

des données imbriquées trois par trois.

31 - Procédé selon la revendication 30, caractérisé en ceque la fonction de distribution aléatoire comprend une permutation

circulaire du contenu du second total de contrôle.

32 - Procédé selon la revendication 31, caractérisé en ce

que le procédé est appliqué à chacun des multiplets imbri-

qués séquentiels de sorte que des représentations de chacun

des multiplets sont mises en mémoire.

33 - Procédé selon la revendication 28, caractérisé en ce qu'il comporte, en outre, un procédé pour reconstituer les

données mises en mémoire, ce procédé de reconstitution com-

prenant les étapes qui consistent: à mettre les valeurs des

premier et second totaux de contrôle égales à zéro, à ex-

traire la première valeur résultante mise en mémoire obtenue par l'exécution de l'opération OU exclusif entre le second total de contrôle et le premier multiplet du dispositif de mémoire; à effectuer une opération OU exclusif entrela valeur

résultante et le second total de contrôle de façon à recons-

tituer le premier multiplet de données; et à mettre le conte- nu du premier total de contrôle égal à la valeur du premier

total de contrôle plus le premier multiplet.

34 - Procédé selon la revendication 33, caractérisé en ce que le procédé de reconstitution comprend, en outre, les

étapes qui consistent: à extraire la seconde valeur résul-

tante mise en mémoire obtenue par l'exécution de l'opération

OU exclusif entre le premier total de contrôle et le conte-

nu du second multiplet; à effectuer une opération OU exclu-

sif entre la valeur résultante et le premier total de con-

trôle de façon à reconstituer le second multiplet de con-

trôle; à mettre le contenu du second total de contrôle égal

à la valeur du second total de contrôle plus le second multi-

plet; et à distribuer aléatoirement le contenu du second total

de contrôle au moyen de la fonction prédéterminée.

35 - Procédé selon la revendication 34, caractérisé en ce qu'il comporte, en outre, l'étape qui consiste à définir un troisième total de contrôle correspondant aux multiplets

des données imbriquées trois par trois.

36 - Procédé selon la revendication 35, caractérisé en ce que le procédé de reconstitution est appliqué à chacun des

multiplets de la multiplicité (N) de multiplets pour recons-

tituer les données extraites du dispositif de mémoire.