DE3443272A1

DE3443272A1 - Verfahren und anordnung zur fehlererkennung in datenverarbeitungsanlagen

Info

Publication number: DE3443272A1
Application number: DE19843443272
Authority: DE
Inventors: Neal Broomfield Col. Glover; Richard San Jose Calif. Williams; Richard N. Mountain View Calif. Woolley
Original assignee: Apple Computer Inc
Current assignee: Apple Inc
Priority date: 1983-12-08
Filing date: 1984-11-28
Publication date: 1985-06-13
Anticipated expiration: 2004-11-29
Also published as: JPS60124735A; GB2181581A; FR2556483B1; CA1208794A; GB2151052B; GB2151052A; US4564941A; GB2181581B; DE3443272C2; GB8417671D0; FR2556483A1; JPH0690672B2; AU574714B2; GB8628271D0; HK77188A; AU3289484A; HK76788A

Description

PATENTANWÄLTE ZENZ & HELBER D 43G0 ESSEN 1 · Αλί .RUHRSTEIN 1 · TEL.: (0201) 412687

A 85

APPLE COMPUTER, INC. 20525 Mariani Avenue,- Cupertino, Kalifornien 95014, V.St.A.

Verfahren und Anordnung zur Fehlererkennung in Datenverarbeitungsanlagen

Die vorliegende Erfindung betrifft das Gebiet der Fehlererkennung und insbesondere Fehlererkennungsverfahren zur Anwendung in einer Datenverarbeitungsanlage zur Identifizierung von Fehlern in gespeicherten Daten.

Die Komplexität moderner Datenverarbeitungssysteme erfordert, daß gewisse Mittel angewendet werden, um Fehler in gespeicherten, abgerufenen und auf andere Weise verarbeiteten Datenbits zu erkennen. Z.B. können als Folge von mechanischen und/oder elektrischen Veränderungen im Datenverarbeitungssystem, die durch auf den magnetischen Lese-Schreibköpfen der Band- oder der Platten-Massenspeichereinrichtung abgelagertes Fremdmaterial verursacht sein können, Fehler in Daten entstehen. Andere potentielle Fehlerquellen, die Datenbits verändern können, sind die natürliche Abnutzung des Speichermediums, Veränderungen in der Versorgungsspannung des Datenverarbeitungsanlages, sowie "Sof f'Fehler, die durch radioaktive Verunreinigungen im Gehäuse der Speichereinrichtung und durch kosmische Strahlen induziert werden.

Es wurde eine Reihe von Verfahren entwickelt, um in gespeicherten oder auf andere Weise verarbeiteten Daten eingeführte Fehler zu erkennen. Ein übliches Fehlererkennungssystem ver-

2"

wendet einen einfachen Prüf- bzw. Check-Summen-Code. Typisch werden Daten in Datensätzen organisiert, die eine Mehrzahl von Bytes enthalten. Jedes Byte enthält der Reihe nach eine Mehrzahl von Bits (typisch 8). Ein das einfache Check-Summen-Verfahren anwendendes System führt eine Exklusiv-ODER-Operation zwischen jedem folgenden Byte des Datensatzes durch. So ist, wie in Fig. 1 dargestellt, das 8 Bits aufweisende Byte A^ mit dem 8 Bits aufweisenden A₂ Exklusiv-ODER-verknüpft. Ähnlich ist die aus dieser Operation zwischen A. und A₂ resultierende binäre Größe mit den Bits des Bytes A^ exklusiv ODER-verknüpft und so weiter. Die Check-Summe ist definiert als die aus den wiederholt durchgeführten Exklusiv-ODER- -Operationen resultierende binäre Netto-Größe. Die resultierende Check-Summen-Größe wird typischerweise an das Ende des Datensatzes angefügt, wie in Fig. 1 mit £ A. dargestellt.

In vielen Datenverarbeitungsanlagen werden Daten auf magnetische Datenträger, wie magnetische Platten oder Bänder geschrieben. In solchen, ein Check-Summen-Fehlererkennungsverfahren anwendenden Systemen werden die Daten in Form von den gesamten Datensatz enthaltenden zahlreichen Bytes so aufeinanderfolgend auf den magnetischen Datenträger geschrieben, daß zunächst Byte A. und dann nachfolgende Bytes eingeschrieben und zum Schluß ein oder mehrere die resultierende Check-Summe enthaltende Bytes an das Ende des Datensatzes gesetzt werden. Wenn die Daten von dem magnetischen Datenträger abgerufen werden, liest das Datenverarbeitungssystem nacheinander den Inhalt des gesamten Datensatzes aus, während es eine erneute Berechnung des Wertes der Check-Summe vornimmt. Nachdem der gesamte Datensatz von dem Datenträger ausgelesen wurde, wird der neu errechnete Check-Summenwert mit der vorher als Teil des Datensatzes abgespeicherten Check-Summe verglichen. Wenn die zwei Check-Summen nicht identisch übereinstimmen, wird ein Fehler in den Daten unterstellt.

Die Verwendung eines einfachen Check-Summen-Fehlererkennungsverfahrens gibt nicht den Schutz, den man natürlicherweise annimmt. Zum Beispiel·haftet dem einfachen Check-Summenverfahren eine Musterempfindlichkeit gegenüber kurzen, geballt auftretenden Fehlern an, die statistisch auf den Datensatz verteilt sind. Die Anwendung einer Exklusiv-ODER-Operation zwischen aufeinanderfolgenden Bytes innerhalb des Datensatzes macht es möglich, daß sich Fehler gegenseitig auslöschen und dadurch nicht erkannt werden. Wenn z.B. der Bitzustand des Bits Nr. 2 innerhalb eines speziellen Bytes eines Datensatzes als Ergebnis einer mechanischen und/oder elektrischen Fehlfunktion verändert wird (z.B. eine 1 in einen O-Bitzustand verschoben wird) und Bit Nr. 2 eines anderen Bytes ähnlich verändert wird (ein O-Bitzustand irrtümlich in einen 1-Bitzustand verschoben wird), löschen sich die Fehler in den Bytes während der Exklusiv-ODER-Operation aus. Für den Fall von zwei fehlerhaften statistischen Bits ist die Wahrscheinlichkeit der Nichterkennung des Fehlers angenähert 1:8.

Ein Verfahren zur Verbesserung der Fehlererkennungsrate für die einfache Check-Summe ist die Hinzufügung einer "Verschachtelung". Zum Beispiel erzeugt eine 3-Byte-Check-Summe drei separate resultierende Check-Summenwerte für einen Datensatz. Wie in Figur 2 dargestellt, kann der erste Check-Summenwert für die Bytes A₁, A₂, A₃ usw. bestimmt werden, die verschachtelte Check-Summen-Bytes einer Folge repräsentieren. Ähnlich wird eine zweite Check-Summe für die Bytes B₁, B-, B^ usw. und eine dritte für die Bytes C₁, C_?, C^_n usw. errechnet. Obwohl die Verschachtelung die Fehlerkennungswahrscheinlichkeit für lange statistische Fehlerstöße bzw. -ballungen (bursts) wesentlich verringert, wurde die Fehlerkennungswahrcheinlichkeit für seltene Fehlerstöße oder -anhäufungen als unakzeptabel hoch gefunden.

Demgemäß besteht ein Bedarf an Mitteln, welche die Erkennbarkeit von Fehlern in gespeicherten und verarbeiteten Daten erhöhen. Wie beschrieben werden wird, schlägt die vorliegende Erfindung ein System und Verfahren für eine verbesserte Fehlererkennbarkeit durch statistische Verteilung und Ausbreitung eines Fehlers über den Datensatz vor. Die statistische Verteilung und Ausbreitung eines Fehlers erhöht wesentlich die Wahrscheinlichkeit seiner Erkennung.

Die vorliegende Erfindung gibt ein Verfahren und System zur verbesserten Fehlererkennung in einem Datenverarbeitungsanlage an. Die Techniken der vorliegenden Erfindung sichern, daß ein Fehler in einem Datensatz (jeder Datensatz weist eine Mehrzahl von Datenbits auf) mit hoher Wahrscheinlichkeit erkannt wird. Für den Fall eines Fehlers unterwirft die vorliegende Erfindung den Fehler einer statistischen Verteilungsfunktion, die die nachfolgenden Bits innerhalb des Datensatz ändert, breitet den Fehler aus und verteilt ihn statistisch überall in dem Datensatz, um seine scheinbare Größe zu verstärken. Die statistische Verteilung und Ausbreitung des Fehlers verringert wesentlich die Fehl- oder Nichterkennungswahrscheinlichkeit für einen statistischen Fehler innerhalb eines Datensatz und ist nicht länger musterempfindlich. Die Verwendung sowohl von Ausbreitungs- als auch statistischen Verteilungsfunktionen verändert wesentlich die Fehler enthaltenden Daten, so daß mit Check-Summenmethoden eine hohe Erkennungswahrscheinlichkeit besteht.

Im folgenden wird die Erfindung anhand der Zeichnung näher erläutert. Es zeigen:

Fig. 1 ein einfaches Check-Summen-Fehlererkennungssystem;

Fig. 2 ein verschachteltes Check-Summen-Fehlererkennungssystem;

Fig. 3 ein Blockschaltbild eines Computers, der mit dem System nach der Erfindung versehen ist;

Fig. 4(a)-(b) ein Speicher- und Abrufverfahren, das die Erfindung anwendet;

Fig. 5 die Ausbreitung eines Fehlers unter Anwendung des Verfahrens nach Figur 4(a)-(b);

Fig. 6(a)-(b) ein Speicher- und Abrufverfahren für die

Ausbreitung und die statistische Verteilung eines Fehlers gemäß der Erfindung; und

Fig. 7(a)-(d) ein anderes Speicher- und Abrufverfahren

der Erfindung für die statistische Verteilung und Ausbreitung eines Fehlers unter Verwendung verschachtelter Check-Summen.

BEZEICHNUNG UND NOMENKLATUR

Die nachfolgende ausführliche Beschreibung wird weitgehend unter Verwendung von Algorithmen und symbolischen Darstellungen der Operationen an in einem Computerspeicher enthaltenden Datenbits vorgenommen. Diese algorithmischen Beschreibungen und Darstellungen sieht der Datenverarbeitungsfachmann als die wirksamste Art an, um seine Arbeit anderen Fachleuten zu vermitteln.

Ein Algorithmus wird hier und im allgemeinen als eine selbständige Folge von Schritten, die zu einem gewünschten Ergeb-

nis führt, angesehen. Diese Schritte erfordern physikalische Bearbeitungen von physikalischen Größen. Gewöhnlich, aber nicht notwendigerweise, haben diese Größen die Form von elektrischen oder magnetischen Signalen, die gespeichert, übertragen, kombiniert, verglichen und auf andere Weise verarbeitet werden können. Es erweist sich zeitweilig als zweckmäßig, bei diesen Signalen von Bits, Werten, Elementen, Symbolen, Ziffern, Termen, Zahlen oder ähnlichem zu sprechen. Es sollte beachtet werden, daß alle diese und ähnliche Ausdrücke mit entsprechenden pyhsikalischen Größen verbunden sind und lediglich auf diese angewendet zweckmäßige Bezeichnungen darstellen.

Ferner sind die durchgeführten Bearbeitungen häufig mit Ausdrücken, wie addieren oder vergleichen, bezeichnet, die gewöhnlich geistigen Operationen einer Bedienungsperson zugeordnet sind. In den meisten Fällen sind für der hier beschriebenen Operationen, die Teil der Erfindung sind, derartige Fähigkeiten eines menschlichen Bedieners nicht erforderlich oder erwünscht; die Operationen sind Maschinenoperationen. Brauchbare Maschinen zur Durchführung der Operationen der vorliegenden Erfindung weisen im allgemeinen digitale Computer oder andere ähnliche Einrichtungen auf. In allen Fällen sollte zwischen den Verfahrensschritten zur Betätigung des Computers und den Berechnungsverfahren selbst unterschieden werden. Die vorliegende Erfindung bezieht sich auf Verfahrensschritte zum Betreiben eines Computers bei der Verarbeitung elektrischer oder anderer (z.B. mechanischer, chemischer) physiklischer Signale, um andere gewünschte physikalische Signale zu erzeugen.

Die vorliegende Erfindung bezieht sich auch auf eine Anordnung zur Durchführung dieser Operationen. Diese Anordnung kann speziell für die erforderlichen Zwecke ausgebildet sein oder

kann einen Universalcomputer aufweisen, der selektiv angesprochen oder über ein im Computer gespeichertes Computerprogramm rekonfiguriert wird. Die hier verwendeten Algorithmen sind nicht an einen besonderen Computer oder eine besondere Anordnung gebunden. Insbesondere können verschiedene allgemeine Maschinen mit den Lehren der Erfindung betrieben werden oder, wenn es zweckmäßig erscheint, eine spezielle Anordnung zur Durchführung der erforderlichen Verfahrensschritte aufgebaut werden. Der erforderliche Aufbau für eine Mehrzahl dieser Maschinen wird durch die im folgenden gegebene Beschreibung klar werden.

Die folgende ausführliche Beschreibung ist in unterschiedliche Abschnitte aufgeteilt. Der erste Abschnitt behandelt einen allgemeinen Systemaufbau zur Speicherung, Abrufung und Bearbeitung von Daten. Nachfolgende Abschnitte behandeln Anordnungen und Verfahren zur Erzielung verbesserter Fehlererkennungsfähigkeiten in einem Datenverarbeitungsanlage.

Zusätzlich sind in der folgenden Beschreibung zahlreiche Einzelheiten, wie algorithmische Konventionen, spezielle Zahlen von Bits, binäre Operationen usw. erwähnt, um die Erfindung besser verständlich zu machen. Es ist jedoch klar, daß der Fachmann die Erfindung ohne diese speziellen Einzelheiten anwenden kann. Andererseits sind bekannte Schaltungen und Aufbauten nicht in Einzelheiten beschrieben, um die Beschreibung der vorliegenden Erfindung nicht unnötig zu belasten.

ALLGEMEINER SYSTEMAUFBAü

Figur 3 stellt ein typisches Computerbasisanlage zum Lesen, Speichern und Verarbeiten von Daten dar. Es ist ein Computer 20 gezeigt, der drei Hauptkomponenten aufweist. Die erste Komponente ist die Eingangs/Ausgangs (I/O)-Schaltung 22, die

verwendet wird, um Informationen in angemessen strukturierter Form von und zu anderen Teilen des Computers 20 zu übermitteln. Als Teil des Computers 20 ist die Zentraleinheit (CPU) 24 und ein Speicher 26 dargestellt. Die letzten zwei Komponenten werden typischerweise bei den meisten Computern gefunden. Die verschiedenen im Computer 20 enthaltenen Elemente sollen repräsentativ für die weite Kategorie von Datenverarbeitungsmaschinen sein.

In Figur 3 ist auch eine Eingabeeinrichtung 30 in typischer Ausführung als Tastatur gezeigt. Es versteht sich, daß die Eingabeeinrichtung tatsächlich auch ein Kartenleser, ein Leser für Magnet- oder Papierbänder oder eine andere bekannte Eingabeeinrichtung (einschließlich eines anderen Computers) sein kann. Eine mit der I/O-Schaltung 2 2 verbundene Massenspeichereinrichtung ergibt für den Computer 20 eine zusätzliche Speicherfähigkeit. Der Massenspeicher kann andere Programme und ähnliches enthalten und die Form eines Lesers für Magnet- oder Papierbänder oder einer anderen bekannten Einrichtung annehmen. Es ist klar, daß die im Massenspeicher 32 aufgenommen Daten in geeigneten Fällen in üblicher Art in den Computer als Teil des Speichers 26 einbezogen sein können.

Zusätzlich ist ein Wiedergabemonitor 34 dargestellt, der zur Wiedergabe der durch die Erfindung bearbeiteten Daten verwendet wird. Als Wiedergabemonitor können verschiedene der bekannten CRT-Displays verwendet werden.

Während der Operation des Computers 20 können Fehler in die im Speicher 2 6 und Massenspeicher 32 gespeicherten und abgefragten Daten eingeführt werden. Die Nichterkennung von Fehlern in gespeicherten oder auf andere Weise bearbeiteten Daten kann falsche Computerantworten ergeben. Wie beschrieben werden wird, stellt die Erfindung Verfahren und Anordnungen zur Erhö-

hung der Erkennbarkeit von Fehlern in gespeicherten oder auf andere Weise bearbeiteten Daten zur Verfügung, wodurch die Zuverlässigkeit von Computeroperationen wesentlich verbessert wird.

AUSBREITUNG VON FEHLERN

Wie vorher erläutert, verringert die Anwendung von Verschachtelungen die Nichterkennungswahrscheinlichkeit in Datensätzen wesentlich für den Fall von langen statistischen Fehleranhäufungen. Es wurde jedoch gefunden, daß die Wahrscheinlichkeit einer Nichterkennung eines Fehlers bei seltenen Fehleranhäufungen, die statistisch auf den Datensatz verteilt sind, unakzeptabel hoch bleibt. Daher ist nach einem Aspekt der Erfindung vorgesehen, einen Fehler überall in einen Datensatz auszubreiten, wodurch die Wahrscheinlichkeit der Erkennung erhöht wird.

Unter Bezugnahme auf Figur 4 wird das erfindungsgemäße Verfahren für die Ausbreitung von Fehlern erläutert. Individuelle Datenbytes A, B, C und D, die aufeinanderfolgende verschachtelte Bytes in einem Datensatz aufweisen können, werden gespeichert oder auf andere Weise in einer Computeranlage verarbeitet. Die Erfindung speichert das erste Byte A direkt ab, z.B. im Speicher 26 oder im Massenspeicher 32, der ein magnetisches Speichermedium oder ähnliches aufweisen kann. Wie dargestellt, wird der Inhalt des nächsten Bytes B mit dem Inhalt des vorhergehenden Bytes A Exklusiv-ODER-verknüpft und die aus dieser Exklusiv-ODER-Verknüpfung zwischen den Bytes B und A resultierende binäre Größe gespeichert. Ähnlich wird auch der Inhalt des vorhergehenden Bytes B und die resultierende binäre Größe gespeichert. So wird, abweichend von bekannten Kodierverfahren für die Speicherung von Daten in Speichereinrichtungen, nach der vorliegenden Erfindung das Resul-

tat einer Serie von Exklusiv-ODER-Operationen zwischen aufeinanderfolgenden (oder verschachtelten) Bytes eines Datensatzes gespeichert.

Unter Bezugnahme auf Figur 4(b) wird die Rückgewinnung von Daten beschrieben, die gemäß dem Schema der Figur 4(a) gespeichert wurden. Wie dargestellt, werden die Daten von den resultierenden binären Größen dekodiert, die in Übereinstimmung mit dem in Verbindung mit Figur 4(a) beschriebenen Verfahren durch die Anwendung zusätzlicher Exklusiv-ODER-Operationen abgespeichert wurden. Wie gezeigt, sind die abgefragten resultierenden binären Größen mit dem dekodierten Resultat aus dem unmittelbar vorhergehenden (oder verschachtelten) Byte Exklusiv-ODER- -verknüpft. Zum Beispiel ergibt die Abfrage des Bytes A aus dem Massenspeicher 32 oder dem Speicher 26 nur eine binäre Größe, die den Inhalt des Bytes A repräsentiert, da Byte A ohne Veränderung innerhalb des Speichers gefunden wurde. Der Rückgewinnungswert der nachfolgend gespeicherten resultierenden Größe (b(+)A) aus dem Speicher 32 o. dgl., ist Exklusiv- -ODER-verknüpft mit dem vorhergehenden dekodierten Byte, nämlich mit A in diesem Beispiel. Es wird ersichtlich, daß die Exklusiv-ODER-Operation zwischen den gespeicherten resultierenden Größen gemäß Figur 4(a) und den zuvor wiedergewonnenen Daten (z.B. Byte A) Byte B effektiv dekodiert und rückgewinnt. Ähnlich ergibt eine Exklusiv-ODER-Operation zwischen dem wiedergewonnenen Byte B und der kodierten Größe (c(+)B) die Rückgewinnung des Bytes C. So stellt das in Figur 4 erläuterte Verfahren ein Mittel dar, mit dem Daten kodiert und in einer Speichereinrichtung abgespeichert und später unter Verwendung einer Serie von einfachen Exklusiv-ODER-Operationen dekodiert werden können.

Im folgenden wird unter Bezugnahme auf Figur 5 die Ausbreitung eines statistischen Fehlers in einem Datensatz dargestellt.

Gemäß der Lehre der Erfindung wird das erste aufgezeichnete Byte A in den gewünschten Speichermitteln, wie einem Massenspeicher 32 oder einem Speicher 26 des Computers 20 abgespeichert. Nachfolgend (entweder nacheinander oder verschachtelt) wird Byte B mit dem Inhalt des Bytes A Exklusiv-ODER-verknüpft und die resultierende Größe in den gewünschten Speichermitteln abgespeichert. Ähnlich werden in Übereinstimmung mit dem Verfahren nach Figur 4(a) die nachfolgenden Bytes C, D usw. mit den vorhergehenden Datenbytes Exklusiv-ODER-verknüpft.

Als Beispiel sei angenommen, daß ein zufälliger Fehler "e" innerhalb des Bytes A eines Datensatzes vorhanden ist. Dieser Fehler könnte eingeführt worden sein während des Zurückleseoder während des ursprünglichen Schreibzyklus oder als Folge eines der vielen vorher beschriebenen möglichen Gründe. So ergibt die Rückgewinnung des ersten Bytes eines Datensatzes eine Größe, die das Byte A0e repräsentiert. Unter Benutzung der Lehre der vorliegenden Erfindung wird diese Größe (A^^e) mit der nachfolgend gespeicherten resultierenden Größe (Β0Α) Exklusiv-ODER-verknüpft. Das Netto-Resultat dieser Exklusiv- -ODER-Operation ist die Größe (B(+)e). So wurde der Fehler e in das nachfolgende Byte B ausgebreitet und, wie aus Figur 5 deutlich wird, der Fehler e ähnlich überall in jedes Byte des Datensatz ausgebreitet. Im Betrieb wird ein Datenverarbeitungsanlage mit einem einfachen Check-Summenverfahren den neu errechneten auf den wiederaufgefundenen Daten (Figur 5) basierenden Check-Summenwert mit der vorher gespeicherten Check- -Summengröße für die ursprünglich gespeicherten Daten entsprechend dem Verfahren nach Figur 4(a) vergleichen. Wegen der Ausbreitung des Fehlers nach dem Verfahren der Erfindung werden die Check-Summen nicht stimmen und es wird ein Fehler angenommen.

AUSBREITUNG UND STATISTISCHE VERTEILUNG

Im folgenden wird unter Bezugnahme auf Figur 6 ein Verfahren beschrieben, das erfindungsgemäß sowohl die Ausbreitung als auch die statistische Verteilung von Fehlern innerhalb eines Datensatzes anwendet. Wie vorher repräsentieren A, B, C und D aufeinanderfolgende Bytes (entweder sequentiell oder verschachtelt) innerhalb eines Datensatzes. Das Apostroph '"" repräsentiert eine Funktion, wobei die Funktion so konzipiert ist, daß sie so statistisch wie möglich ist. Ein Doppelstrich ¹¹¹¹¹¹ repräsentiert die zweimalige Anwendung der Funktion usw. Wie vorher erläutert, speichert die vorliegende Erfindung das erste Byte A direkt in den speziellen benutzten Speichermitteln. Wie dargestellt, ist der Inhalt des nächstfolgenden Bytes B mit dem Inhalt des vorhergehenden Bytes A Exklusiv- -ODER-verknüpft, wobei das Byte A einer statistischen Funktion unterworfen wurde. Die sich aus dieser Exklusiv-ODER-Operation zwischen den Bytes B und A¹ ergebende binäre Größe wird dann in den Speichermitteln gespeichert. Ähnlich wird der Inhalt des nachfolgenden Bytes C mit dem Inhalt des vorhergehenden Bytes B, das der Funktion unterworfen wurde, Exklusiv-ODER- -verknüpft, und die resultierenden binären Größen werden dann ebenfalls gespeichert. Es ist klar, daß die besondere statistische Verteilungsfunktion eine Vielzahl von bekannten statistischen Verteilungs-Algorithmen enthalten kann. In der vorliegenden Erfindung wird eine lineare statistische Verteilungsfunktion angewendet.

Im folgenden wird unter Bezugnahme auf die Figur 6(b) die Auswirkung eines statistisch in einem Datensatz befindlichen Fehlers dargestellt. Als Beispiel sei angenommen, daß ein zufälliger Fehler "e" innerhalb des Bytes A eines Datensatzes vorhanden ist. Wie in Figur 6 (b) gezeigt, ergibt die Rückgewinnung des ersten Bytes eines Datensatzes eine repräsentative

Größe des Bytes A(*+)e. Unter Anwendung der Lehre der Erfindung wird die statistische Verteilungsfunktion auf die Größe Ä@e angewendet und ergibt eine Größe (A^e)¹. Die Größe (A@e)' wird dann mit der nachfolgend gespeicherten resultierenden Größe B^^A' Exklusiv-ODER-verknüpft. Das Nettoresultat dieser exklusiven ODER-Operation ist die Größe B@e'; wobei e¹ gleich A¹ 0 (A(^e)¹ ist. Der Fehler e wurde so in das nachfolgende Byte B ausgebreitet und gemäß der gewählten statistischen Funktion statistisch verteilt. Ähnlich wird die statistische Funktion auf das Resultat B^^e' angewendet, wodurch (B(+)e')' erhalten wird. Diese Größe wird in der weiteren Folge mit der vorhergehend gespeicherten Größe c(+) B' Exklusiv-ODER-verknüpf t, wodurch sich als Resultat die rückgewonnene binäre Größe C(^e' ' ergibt; wobei e¹ ' gleich B¹(+)(B(+)e¹)' ist. Die statistische Funktion ist so zweimal auf den Fehler e angewendet worden, wodurch der vorher statistisch angeordnete Fehler bei seiner Ausbreitung auf den Datensatz statistisch verteilt wurde. Dieser Vorgang wird beim nachfolgenden Lesen des Datensatzes wiederholt, wodurch der Fehler auf den ganzen Datensatz statistisch verteilt und ausgebreitet und so bei der Anwendung von Check-Summenmethoden die Wahrscheinlichkeit der Erkennung wesentlich erhöht wird.

Im folgenden wird unter .Bezugnahme auf die Figuren 7(a)-7(d) ein anderes Ausführungsbeispiel der Erfindung beschrieben. Die Erfindung wurde zuvor anhand eines eine statistische Verteilung und eine Ausbreitung verwendenden Verfahrens erläutert, die auf aufeinanderfolgende oder verschachtelte Bytes in einem Datensatz angewendet wurden. Es wurde aber gefunden, daß durch Anwendung der Lehren der Erfindung direkt auf die Check-Summengrößen selbst eine hohe Erkennungswahrscheinlichkeit erzielbar ist. Wie aus Fig. 7(a) ersichtlich ist, weist ein Datensatz Bytes A, B, C, D usw. auf. Check-Summengrößen C1, C2 und C3 sind am Ende eines Datensatzes angeordnet. Wie darge-

V4 *'

stellt, verwendet das bevorzugte Ausführungsbeispiel der Erfindung ein 3 Byte verschachteltes Check-Summensystem, wobei die Bytes A, D, G usw. aufeinanderfolgende verschachtelte Bytes der Check-Summe C1 aufweisen. Ähnlich weisen aufeinanderfolgende verschachtelte Bytes B, E, H usw. Bytes der Check- -Summe C2 auf. Schließlich weisen die Bytes C, F, I usw. aufeinanderfolgende verschachtelte Bytes der Check-Summe C3 auf. Zusätzlich sei darauf hingewiesen, daß "c" einen Übertrag von einer vorhergehenden Operation anzeigt.

Wie in Fig. 7(b) dargestellt, enthält die Zufallsverteilungsfünktion des Ausführungsbeispiels nach Fig. 7 eine "Drehung" (rotate), wobei der Inhalt der Check-Summe C3 um ein Bit nach links verschoben wird (insbesondere das am niedrigsten bewertete Bit zum am höchsten bewerteten Bit) und das am höchsten bewertete Bit wird auf die Position des am niedrigsten bewerteten Bits gedreht. Es wurde gefunden, daß die Anwendung einer Drehung für die Zufallsverteilung eine Echtzeitimplementierung in einer Vielzahl von Computeranlagen erlaubt.

Wie in Fig. 7(c) gezeigt, weisen die gemäß der Lehre der Erfindung kodierten Daten eine anfängliche Drehung der Check- -Summe C3 auf (die bei Beginn des Verfahrens eine einfache Drehung binärer Nullen bewirkt, da vorher noch keine Daten gespeichert wurden). Die Check-Summe C1 wird dann der Check- -Summe C1 plus Inhalt des Bytes A gleichgesetzt (plus irgendeinem Übertrag c). Bei Beginn wird Cl dem Inhalt des Bytes A einfach gleich sein. Wie gezeigt, wird das erste Byte der binären Größe A gleichgesetzt, Exklusiv-ODER-verknüpft mit dem Inhalt der Check-Summe C3 und dann diese binäre Größe in geeigneten Speichermitteln abgespeichert. Für das erste Byte eines Datensatzes wird nur der Inhalt des Bytes A im Massenspeicher 32 oder im Speicher 26 des Computers 20 gespeichert, da C3 anfangs auf 0 gesetzt ist. Die Check-Summengröße C2 ist

dem vorherigen Inhalt von C2 plus der binären Größe, die Byte B sowie einen etwaigen Übertrag enthält, gleichgesetzt. Byte B des Datensatzes wird dann mit dem Inhalt der Check-Summe C1 Exklusiv-ODER-verknüpft und die resultierende Größe in geeigneten Speichermitteln abgespeichert. Die Check-Summe C3 wird dann mit ihrem vorherigen Inhalt plus dem Inhalt des Bytes C plus einem Übertrag gleichgesetzt. Der Inhalt des Bytes C wird mit dem Inhalt der Check-Summe C2 Exklusiv-ODER-verknüpft und dann diese Größe abgespeichert. Nachdem die ersten drei Bytes a(+)C3, b(+)C1 und C(+)C2 gemäß der vorstehenden Erläuterung in den Speichermitteln abgespeichert sind, wird dann durch Verschieben um ein Bit, wie in Fig. 7(a) gezeigt, der Inhalt der Check-Summe C3 nochmals gedreht.

Der Inhalt der Check-Summe C1 wird dann zu dem Inhalt des Bytes D des Datensatzes plus einem resultierenden Übertrag addiert. Der Inhalt des Bytes D wird mit dem Inhalt der Check- -Summe C3 Exklusiv-ODER-verknüpft und diese resultierende Größe in den Speichermitteln abgespeichert. Wie gezeigt, wird der Inhalt der Check-Summe C2 dann zu dem Inhalt des Bytes E des Datensatzes plus einem Übertrag addiert, um den Inhalt der Check-Summe C2 neu zu definieren. Ähnlich werden nachfolgende Bytes, die den in Fig. 7(a) dargestellten Datensatz bilden, in geeigneten Speichermitteln abgespeichert und die Check-Summen C1 , C2 und C3 entsprechend aktualisiert.

Im folgenden wird unter Bezugnahme auf Fig. 7(d) die Datenrückgewinnung gemäß dem in Figuren 7(a)-7(c) beschriebenen Kodierschema erläutert. Vor der Rückgewinnung werden die Check-Summen C1, C2 und C3 innerhalb des Computerspeichers 26 des Computers 20 definiert und gleich 0 gesetzt. Es wird daran erinnert, daß das resultierende Ende der Datensatz-Check-Summengrößen C1, C2 und C3 am Ende des in Fig. 7(a) dargestellten Datensatzes abgespeichert ist. Wie gezeigt, wird die regene-

rierte Größe A(+)C3 mit dem Inhalt der Check-Summe C3 (die gleich O ist) Exklusiv-ODER-verknüpft, wodurch sich eine echte Wiedergewinnung des Inhalts des Bytes A ergibt, wenn A(^C3 keine Fehler enthält. Wenn Byte A, wie gezeigt, rückgewonnen ist, wird C1 durch Addition des Inhalts von C1 mit dem Byte A plus irgendeinem Übertrag aktualisiert (keiner in dem vorstehenden Beispiel). Ähnlich wird die vorhergehende binäre Größe B (+)C1 mit dem neu aktualisierten Wert von C1 Exklusiv-ODER- -verknüpft, wodurch sich eine Dekodierung und Rückgewinnung des Bytes B ergibt. C2 wird dann durch die Addition des Inhalts des Bytes B (plus irgendeinem übertrag) aktualisiert. Byte C wird durch Exklusiv-ODER-Operation der früher gespeicherten Größe c(^ C2 mit dem neu aktualisierten Wert von C2 wiedergewonnen. C3 wird dann durch Addition des Wertes von Byte C aktualisiert und dann, wie vorher beschrieben, eine Drehung durchgeführt. In dieser Art werden aufeinanderfolgende, den Datensatz bildende Bytes dekodiert und rückgewonnen.

KODIERANGABEN

Es wurde keine spezielle Programmiersprache für die Durchführung der verschiedenen oben beschriebenen Vorgänge angegeben. Dies ist teilweise dadurch bedingt, daß nicht alle Sprachen, die erwähnt werden könnten, universell anwendbar sind. Jeder Benutzer eines speziellen Computers ist über die Sprache unterrichtet, die am besten für seinen augenblicklichen Verwendungszweck geeignet ist. In der Praxis hat es sich als nützlich erwiesen, die vorliegende Erfindung im wesentlichen in einer Assemblersprache zu implementieren , die einen maschinenausführbaren Objektcode liefert.

Da die Computer und die Monitoranlagee, die bei der Anwendung der Erfindung eingesetzt werden, viele unterschiedliche Elemente enthalten, wurde kein detailliertes Programmlisting

vorgeschlagen. Es wird davon ausgegangen, daß die Operationen und andere in der Zeichnung dargestellte Verfahrensschritte
ausreichend erläutert wurden, um einem Fachmann die Benutzung der Erfindung oder für ihn nützlicher Teile derselben zu ermöglichen.

Es wurden Verfahren und Anordnungen erläutert, die am vorteilhaftesten in Verbindung mit einem digitalen Computer für eine verbesserte Fehlererkennung anwendbar sind. Die erfindungsgemäße statistische Verteilung und Ausbreitung von Fehlern innerhalb eines Datensatzes reduziert wesentlich die Fehlerverkennungswahrscheinlichkeit und erhöht dadurch die Zuverlässigkeit eines Datenverarbeitungsanlages.

Claims

PATENTANWÄLTE ZENZ & HELBER · D 43OO ESSEN 1 AM RUHPiSFEIN 1 · TEL.: (02 01) 412687 Seite A_85 Apple Computer, Ine· Patentansprüche

1. Verfahren zur Speicherung und Wiedergewinnung von Daten in einer Datenverarbeitungsanlage, wobei die Daten in einer Mehrzahl (N) von aufeinanderfolgenden Bytes organisiert sind, dadurch gekennzeichnet,

daß ein Fehler in einem Byte in jedes nachfolgende Byte ausgebreitet wird,

daß eine Exklusiv-ODER-Operation zwischen jedem Byte (i) und dem vorhergehenden Byte (i-1) durchgeführt wird, um einen resultierenden Wert (R.) zu gewinnen,

daß jeder der resultierenden Werte (R.) in einem Speicher abgespeichert wird,

daß die resultierenden Werte (R.) aus dem Speicher ausgelesen werden,

daß die Datenbytes aus den resultierenden Werten dadurch wiedergewonnen werden, daß zwischen jedem Wert (R.) und dem zuvor wiedergewonnenen Datenbyte (i-1) eine Exklusiv-ODER-Operation durchgeführt wird, wobei

i = 1

ist, mit

"N" = Anzahl der Bytes in den Daten und "©" ⁼ Exklusiv-ODER-Operation,

wodurch ein Fehler in einem Byte in nachfolgende Bytes ausgebreitet und dadurch die Erkennbarkeit des Fehlers erhöht wird.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß die vorhergehenden Bytes (i-1) und die zuvor wiedergewonnenen Bytes (i-1) jeweils vor ihrer Exklusiv-ODER-Operation einer vorgegebenen Zufallsverteilungsfunktion unterworfen werden, und daß die Datenbytes aus den resultierenden Werten unter Ausführung einer Exklusiv-ODER-Operation derart wiedergewonnen werden, daß

ist, wobei

"N" = Anzahl der sequentielen Bytes in den Daten, ¹¹ φ " = eine Exklusiv-ODER-Operation bezeichnet und "'" = die vorgegebene Funktion repräsentiert, wodurch ein Fehler in einem Byte über jedes nachfolgende Byte verteilt und ausgebreitet wird.

3. Verfahren nach Anspruch 1 oder 2, dadurch gekennzeichnet, daß vor dem Abspeicherungsschritt eine erste Check-Summengröße für die Daten berechnet wird und daß die erste Check-Summe mit den resultierenden Werten (R.) im Speicher abgespeichert wird.

4. Verfahren nach Anspruch 3, dadurch gekennzeichnet, daß eine zweite Check-Summengröße für die wiedergewonnenen Daten berechnet wird.

5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, daß zur Erkennung eines Fehlers die ersten und zweiten Check-Surnmengrößen verglichen werden und ein Fehler festgestellt wird, wenn die beiden Check-Summengrößen nicht übereinstimmen.

6. Verfahren nach Anspruch 5, dadurch gekennzeichnet, daß die ersten und zweiten Check-Summen errechnet werden durch

Verwendung der Formel:

Check-Summe

Mod₂ i=0

wobei Byte, ein Byte in der Position i (mit i = O, 1, 2 ... N-1 ist) in den Daten bezeichnet.

7. Verfahren nach Anspruch 6, dadurch gekennzeichnet, daß eine Mehrzahl von ersten und zweiten Check-Summen für die Daten berechnet wird, wobei jede der Check-Summen für ein vorgegebenes verschachteltes Vielfaches eines anfangs spezifizierten Bytes berechnet wird.

8. Verfahren nach Anspruch 7, dadurch gekennzeichnet, daß die Bytes einfach verschachtelt werden.

9. Verfahren nach Anspruch 7, dadurch gekennzeichnet, daß die Bytes dreifach verschachtelt werden.

10. Verfahren nach Anspruch 7, dadurch gekennzeichnet, daß die Daten in Datensätzen organisiert sind, wobei jeder Datensatz mehrere jeweils 8 Bits enthaltende Bytes hat.

11. Verfahren zur Speicherung von Daten in einer Datenverarbeitungsanlage, wobei die Daten in einer Mehrzahl (N) von aufeinanderfolgenden verschachtelten Bytes organisiert sind, dadurch gekennzeichnet,

daß verschachtelten Bytes der Daten entsprechende erste und zweite Check-Summen definiert werden;

daß der Inhalt der zweiten Check-Summe einer Zufallsverteilung nach einer vorgegebenen Funktion unterworfen wird;

daß der Inhalt der ersten Check-Summe dem Inhalt der ersten Check-Summe plus dem Inhalt des ersten Bytes gleichgesetzt

daß zwischen dem der Zufallsverteilung unterworfenen Inhalt der zweiten Check-Summe und dem ersten Byte eine Exklusiv-ODER-Operation durchgeführt wird; und

daß der resultierende Wert der Exklusiv-ODER-Operation in einem Speicher abgespeichert wird.

12. Verfahren nach Anspruch 11, dadurch gekennzeichnet, daß der Inhalt der zweiten Check-Summe der Summe des Inhalts der zweiten Check-Summe plus dem Inhalt des zweiten Bytes gleichgesetzt wird, daß zwischen dem Inhalt der ersten Check-Summe und dem Inhalt des zweiten Bytes eine Exklusiv-ODER-Operation durchgeführt wird, und daß der resultierende Wert der Exklusiv-ODER-Operation im Speicher abgespeichert wird.

13. Verfahren nach Anspruch 12, dadurch gekennzeichnet, daß eine dritte Check-Summe entsprechend dreifach verschachtelten Bytes der Daten definiert wird.

14. Verfahren nach Anspruch 13, dadurch gekennzeichnet, daß die Zuteilverteilungsfunktion eine lineare Drehung des Inhalts der zweiten Check-Summe enthält.

15. Verfahren nach Anspruch 14, dadurch gekennzeichnet, daß das Verfahren auf jedes der aufeinanderfolgenden verschachtelten Bytes angewendet wird und daß Darstellungen jedes dieser Bytes abgespeichert werden.

16. Verfahren nach einem der Ansprüche 11 bis 15, dadurch gekennzeichnet, daß zur Wiedergewinnung der gespeicherten Daten die Werte der ersten und zweiten Check-Summe gleich Null gesetzt werden, daß der erste gespeicherte resultierende Wert, der aus der Exklusiv-ODER-Operation zwischen der zweiten Check-Summe und dem ersten Byte erhalten wurde, aus dem Spei-

eher ausgelesen wird, daß zwischen dem resultierenden Wert und der zweiten Check-Summe eine Exklusiv-ODER-Operation durchgeführt wird, so daß das erste Datenbyte rückgewonnen wird, und daß der Inhalt der ersten Check-Summe dem Wert der ersten Check-Summe plus dem ersten Byte gleichgesetzt wird.

17. Verfahren nach Anspruch 16, dadurch gekennzeichnet, daß der zweite gespeicherte resultierende Wert, der durch die Exklusiv-ODER-Operation zwischen der ersten Check-Summe und dem Inhalt des zweiten Bytes erhalten wurde, gelesen wird, daß eine Exklusiv-ODER-Operation zwischen dem resultierenden Wert und der ersten Check-Summe durchgeführt wird, so daß das zweite Datenbyte zurückgewonnen wird, daß der Inhalt der zweiten Check-Summe dem Wert der zweiten Check-Summe plus dem zweiten Byte gleichgesetzt wird, und daß der Inhalt der zweiten Check-Summe nach der vorgegebenen Funktion einer Zufallsverteilung unterworfen wird.

18. Verfahren nach Anspruch 17, dadurch gekennzeichnet, daß als weiterer Schritt eine dritte Check-Summe entsprechend den Bytes der dreifach verschachtelten Daten definiert wird.

19. Verfahren nach Anspruch 18, dadurch gekennzeichnet, daß das Verfahren auf jedes der Mehrzahl (N) von Bytes zur Wiedergewinnung der Daten von der Speichereinrichtung angewendet wird.

20. Fehlererkennungssystem für gespeicherte und wiedergewonnene Daten in einer Datenverarbeitungsanlage, mit Speichermitteln zur Speicherung von Daten, als Mehrzahl (N) von aufeinanderfolgenden Bytes und mit einer mit den Speichermitteln verbundenen Verarbeitungseinrichtung zur Durchführung logischer Operationen an den Daten,

dadurch gekennzeichnet,

daß die Verarbeitungseinrichtung aufweist:

Schreibmittel zur Durchführung einer Exklusiv-ODER-Operation zwischen jedem Byte (i) und dem vorhergehenden Byte (i-1) der Daten, um einen resultierenden Wert (R.) zu gewinnen und zur Speicherung desselben in den Speichermitteln;

Lesemittel zur Wiedergewinnung der Datenbytes aus den resultierenden Werten, die eine Exklusiv-ODER-Operation zwischen jedem Wert (R.) und dem zuvor wiedergewonnenen Datenbyte (i-1) derart durchführen, daß

Byte

ist, mit

"N" = der Anzahl der Bytes in den Daten, und " (+) " ss Exklusiv-ODER-Operation,

wobei ein Fehler in einem Byte über nachfolgende Bytes ausgebreitet wird, wodurch die Erkennbarkeit des Fehlers erhöht wird.

21. Fehlererkennungssystem nach Anspruch 20, dadurch gekennzeichnet, daß die Verarbeitungseinrichtung so ausgebildet ist, daß die vorhergehenden Bytes (i-1) und die zuvor wiedergewonnen Bytes (i-1) jeweils vor ihrer Exklusiv-ODER-Operation einer vorgegebenen Zufallsverteilungsfunktion unterworfen sind, wobei die Wiedergewinnung nach der folgenden Beziehung erfolgt:

"N" = Anzahl der aufeinanderfolgenden Bytes in den Daten,

" (+) " = Exklusiv-ODER-Operation
" ' " = Darstellung der vorgegebenen Funktion.

22. Fehlererkennungssystem nach Anspruch 20 oder 21, dadurch gekennzeichnet, daß die Verarbeitungseinrichtung Mittel zur
Berechnung einer ersten Check-Summengröße der Daten und zur
Abspeicherung der ersten Check-Summe mit ihren resultierenden Werten (R.) in der Speichereinrichtung aufweisen.

23. Fehlererkennungssystem nach Anspruch 22, dadurch gekennzeichnet, daß die Verarbeitungseinrichtung Mittel zur Berechnung einer zweiten Check-Summengröße für die wiedergewonnenen Daten aufweist.

24. Fehlererkennungssystem nach Anspruch 23, dadurch gekennzeichnet, daß Mittel zur Fehlererkennung durch Vergleich der
ersten und zweiten Check-Summen vorgesehen sind.

25. Fehlererkennungssystem nach Anspruch 24, dadurch gekennzeichnet, daß die Verarbeitungseinrichtung so ausgebildet ist, daß sie die erste und zweite Check-Summe nach folgender Beziehung berechnet:

Check-Summe » Ij ^Byte.]

Mod₂
i=0

wobei Byte_i ein Byte in der Position i (mit i=0, 1 ,2...
N-1) in den Daten bezeichnet.

26. Fehlererkennungssystem nach Anspruch 25, dadurch gekennzeichnet, daß die Verarbeitungseinrichtung so ausgebildet ist, daß sie eine Mehrzahl von ersten und zweiten Check-Summen der Daten berechnet, wobei jede Check-Summe für ein vorgegebenes
verschachteles Vielfaches eines anfangs spezifizierten Bytes
berechnet ist.