DE69220818T2 - Verfahren und Einrichtung zur Fehlererkennung in Recherspeichern versehen mit Mehrfach-bit-Ausgängen - Google Patents

Description

TECHNISCHE BESCHREIBUNG
• Die vorliegende Erfindung bezieht sich allgemein auf Fehlerkorrektur und -erkennung und insbesondere auf die Verwendung von Fehlerkorrektur- und Erkennungscodes bei Computerspeichern, die Speicherschaltkreise mit Mehrfachbit-Ausgängen benutzen.
HINTERGRUND DER ERFINDUNG
• Computerspeicher benutzen normalerweise dynamische Speicher mit wahlfreien Zugriff (DRAMs) für die Speicherung von Daten, die in der CPU des Computers verwendet werden. Diese Daten sind Gegenstand von Verfälschungen, was viele Ursachen haben kann. Aus diesem Grunde sind Speichersysteme verbessert und weiterentwickelt worden, so daß das Auftreten von zufälligen Fehlern relativ selten ist. Jedoch ist bei vielen Anwendungen die Unverfälschtheit der Daten so kritisch, daß sogar relativ selten auftretende Fehler nicht toleriert werden können. Verschiedene Fehlerkorrektur- und Fehlererkennungscodes wurden entwickelt, um solche Fehler zu erkennen und in bestimmten Situationen zu korrigieren. Am bekanntesten ist der Hamming-Code, der normalerweise eine Erkennung von Einzel- oder Zweifachbitfehlern und eine Korrektur von Einzelbitfehlern ermöglicht. Es sind Schaltkreise erhältlich, bei denen ein solcher Hamming-Code in Computerspeichersystemen implementiert werden kann. Die Technik des Hamming-Code ist bekannt und auf diesem Gebiet der Technik oft in der Literatur beschrieben.
• Die Verwendung des Hamming-Codes ist sehr wirksam bei herkönnlichen Speichersystemen, bei denen in jeder Speichereinrichtung ein Datenbit gespeichert wird. Große Speichersysteme enthalten normalerweise hunderte oder sogar tausende von einzelnen Speichereinrichtungen, von denen jede beispielsweise 1 Megabit, 4 Megabit oder 16 Megabit Daten enthalten kann. DRAM-Einrichtungen haben normalerweise einen Einzelbit-Ausgang pro Einrichtung, so daß ein Datenwort über die Anzahl von Speichereinrichtungen verteilt ist, die gleich der Anzahl von Bits in dem Wort ist. Zufällig auftretende Fehler, die normalerweise als weiche Fehler bezeichnet werden, sind am häufigsten Einzelbitfehler. Außerdem, wenn eine bestimmte Speichereinrichtung entweder dauerhaft oder vorübergehend ausfällt, wird in dem resultierenden Datenwort ein Einzelbitfehler erzeugt. Daher kann durch Verwendung eines Hamming-Code ein Einzelbitfehler erkannt und korrigiert werden. Es wurde angenommen, daß unter diesen Umständen keine Möglichkeit von Mehrfachbitfehlern besteht. Ein Hamming- Code kann normalerweise einen Zweifachbitfehler erfassen, aber nicht korrigieren. Es ist sehr schwierig, mit wirtschaftlich vertretbarem Aufwand eine größere Anzahl von Bitfehlern zu erkennen und zu korrigieren. Es ist daher eine akzeptierte Ansicht, daß kaum eine Möglichkeit des Auftretens von Mehrfachbitfehlern besteht, so daß sie sicher ignoriert werden kann.
• Mit der Einführung von sehr viel größeren Hauptspeicherkapazitäten, wie mehrere hundert Megabyte für einen einzelnen Computerhauptspeicher, wurde es erforderlich, Speicherschaltkreise zu verwenden, bei denen aus jeder Einrichtung Mehrfachbits ausgegeben werden, statt lediglich ein Einzelbit. Übliche DRAM-Speichereinrichtungen dieser Art können einen parallelen Vierfachbit-Ausgang für Speichereinrichtungs-Größen mit ein und vier Megabit haben. Es wird erwartet, daß sich diese Praxis fortsetzt und möglicherweise sogar größere Mehrfachbit-Ausgänge verwendet werden, wenn die Kapazität von Speicherschaltkreisen auf 16 und 64 Megabit ansteigt. Wenn aber eine einzelne Speichereinrichtung in einem einzelnen Datenwort vier Bits erzeugt, besteht eine viel größere Möglichkeit des Auftretens von Mehrfachbitfehlern, wenn bei dieser bestimmten Speichereinrichtung ein Fehler auftritt.
• Es wurden einige Computersystem-Anwendungen entwickelt, die eine sehr hohe Datenintegrität erfordern. Das Vorhandensein von nicht erkannten Fehlern, selbst in einer Größenordnung von nur ein oder zwei Fehlern pro Jahr, kann bei einem solchen Computersystem zu ernsten Folgen führen. Hinsichtlich der größeren Wahrscheinlichkeit des Auftretens von Mehrfachbitfehlern durch Verwendung von Speichereinrichtungen mit Mehrfachbit-Ausgängen und der erhöhten Forderung nach einer hohen Datenintegrität besteht die Notwendigkeit, ein Verfahren und eine Vorrichtung zu schaffen, um das Auftreten von Mehrfachbitfehlern bei Daten zu erkennen, die in einem derartigen Computerspeicher gespeichert sind.
• Die EP-A-0 166 269 offenbart ein Fehlerkorrekturverfahren für einen Computerspeicher. Bei diesem Verfahren wird für jedes Byte eines Mehrfachbit-Wortes ein Speicherparitätsprüfbit und ein Speicherprüfbit erzeugt, und die Speicherparitätsbits und die Speicherprüfbits, die zu einem Mehrfachbit-Wort gehören, werden in einer separaten Speichereinrichtung gespeichert. Beim Auslesen des Mehrfachbit-Wortes werden Verifizierungsprüfbits und ein Verifizierungsparitätsprüfbit erzeugt und mit den Speicherprüfbits bzw. dem Speicherparitätsprüfbit verglichen. Zum Beispiel können bei einem 4-Byte-Wort bzw. 32-Bit-Wort acht Bits zur Fehlerkorrektur verwendet werden, nämlich vier Paritätsbits und vier Prüfbits, um bis zu vier Fehler zu korrigieren, wenn die Fehler auf entsprechende Bits in den vier Bytes beschränkt sind. Wenn andererseits mehr als ein Fehler in einem Byte auftritt, ist keine Korrektur möglich. Dieses System ist nachteilig für Computerspeicher mit einer Anzahl von Speichereinrichtungen, die jeweils einen Mehrfachbit-Ausgang haben, bei denen aus jeder Speichereinrichtung Mehrfachbits, beispielsweise ein Byte, ausgelesen werden. Da der am häufigsten auftretende Fehler darin besteht, daß eine gesamte Speichereinrichtung ausfällt, sind alle Mehrfachbits, die aus dieser Speichereinrichtung ausgelesen werden, nicht zuverlässig, was zu einem nicht erkennbaren Fehler führt, da die Prüfbits nicht ausreichen, um alle Bits von einer Speichereinrichtung zu korrigieren.
• Die EP-A-0 401 994 zeigt ein Verfahren zum Speichern und Wiederauffinden von Mehrfachbit-Wörtern in einem Computerspeicher, der eine Anzahl von Speichereinrichtungen enthält. Das Mehrfachbit-Wort wird in Unterwörter unterteilt, und ein Fehlererkennungswert, vorzugsweise ein Paritätsbit, wird berechnet und an jedes Unterwort-Segnent angehängt. Jedes Unterwort wird dann in separaten Speichereinrichtungen gespeichert. Folglich kann das Wort bei diesem Speicherverfahren leicht rekonstruiert werden, wenn in einem Unterwort oder sogar in zwei Unterwörtern in einer Speichereinrichtung ein Einzelbitfehler auftritt.
ZUSAMMENFASSUNG DER ERFINDUNG
• Ein ausgewähltes Ausführungsbeispiel der vorliegenden Erfindung betrifft gemäß Anspruch 1 ein Verfahren zur Fehlerkorrektur und Fehlererkennung für in einem Computerspeicher gespeicherten Daten. Für ein Datenwort wird durch Verwendung eines ausgewählten Fehlerkorrekturcodes eine minimale Anzahl von Speicherprüfbits zur Fehlererkennung und Fehlerkorrektur erzeugt. Dieser Code erkennt und korrigiert Einzelbitfehler und erkennt Mehrfachbitfehler im Datenwort. Für die Gesamtheit des Datenwortes wird ein Paritätsspeicherprüfbit erzeugt. Das Datenwort, die Speicherprüfbits und das Speicherparitätsprüfbit werden in dem Computerspeicher gespeichert. Der Computerspeicher umfaßt eine Anzahl von Speichereinrichtungen mit Mehrfachbit-Ausgängen, wobei in jeder der Speichereinrichtungen mehrere Bits des Datenwortes gespeichert sind. In keiner der Speichereinrichtungen ist mehr als eines der Speicherprüfbits oder ein Speicherparitätsprüfbit gespeichert. Der Speicher wird ausgelesen, um das Datenwort, die Speicherprüfbits und das Speicherparitätsbit zu erzeugen. Infolge von Fehlerzuständen können in der Zusammensetzung aus dem Datenwort, den Speicherprüfbits und dem Speicherparitätsprüfbit, die aus dem Computerspeicher ausgelesen wurden, ein oder mehrere Bitfehler vorhanden sein. Der ausgewählte Fehlerkorrekturcode wird auf das Datenwort angewendet, das aus dem Computerspeicher ausgelesen wurde, um einen Satz von Verifizierungsprüfbits zu erzeugen. Ein Verifizierungsparitätsprüfbit wird durch Untersuchung des Datenwortes erzeugt, das aus dem Computerspeicher ausgelesen wurde. Die Speicherprüfbits, die aus dem Computerspeicher ausgelesen wurden, werden mit den Verifizierungsprüfbits verglichen, um ein Prüfbitsyndrom zu erzeugen. Das aus dem Computerspeicher ausgelesene Speicherparitätsprüfbit wird ebenfalls mit dem Verifizierungsparitätsprüfbit verglichen, um ein Paritätssyndrom zu erzeugen. Nachfolgend wird das Prüfbitsyndrom dekodiert, um:
• (a) entweder Einzelbitfehler zu erkennen und zu identifizieren oder um Dreifachbitfehler zu erkennen, die alle in den Datenbits und Prüfbits auftreten, die in einer der Speichereinrichtungen gespeichert sind, wobei bei einem solchen Auftreten eine erste Ausgabe erzeugt wird, oder
• (b) Doppelbitfehler zu erkennen, wobei bei einem solchen Auftreten eine zweite Ausgabe erzeugt wird, oder
• (c) Dreifachbitfehler zu erkennen, die alle in den Datenbits in einer der Speichereinrichtungen auftreten, um unter solchen Umständen eine dritte Ausgabe zu erzeugen, und um die erste Ausgabe, wenn eine solche erste Ausgabe erzeugt wurde, mit dem Paritätssyndrom zu vergleichen, um entweder eine vierte Ausgabe, die einen Einzelbitfehler anzeigt, oder eine fünfte Ausgabe zu erzeugen, die das Vorhandensein eines Dreifachbitfehlers in einer der Speichereinrichtungen angibt.
• Ein weiterer Aspekt der vorliegenden Erfindung betrifft eine Fehlererkennungsschaltung nach Anspruch 4.
• Weitere Ausgestaltungen sind Gegenstand der Unteransprüche.
KURZBESCHREIBUNG DER ZEICHNUNGEN
• Zum besseren Verständnis der vorliegenden Erfindung und von deren Vorteilen wird nun auf die nachfolgende Beschreibung in Verbindung mit den beiliegenden Zeichnungen Bezug genommen, wobei:
• FIGUR 1 ist eine Darstellung von einem Teil von einem Computerspeicher, der eine Anzahl dynamischer Speichereinrichtungen mit wahlfreiem Zugriff (DRAM) enthält, in denen eine Anzahl von Bits eines einzelnen Datenwortes zusammen mit Fehlerkorrektur- und Fehlererkennungsprüfbits gespeichert sind,
• FIGUR 2 ist ein Schaltkreisdiagramm für eine Fehlerkorrektur- und Fehlererkennungsschaltung gemäß der vorliegenden Erfindung, um Einzelbitfehler zu erkennen und zu korrigieren und um verschiedene Arten von Mehrfachbitfehlern zu erkennen, und
• FIGUREN 3A und 3B sind ein detailliertes Schaltkreisdiagramm für den in FIGUR 2 gezeigten Fehlergeneratorschaltkreis.
DETAILLIERTE BESCHREIBUNG
• Die vorliegende Erfindung enthält für das hier beschriebene Ausführungsbeispiel einen 8-Bit Fehlererkennungs- und Korrekturcode (EDC) zur Verwendung zusammen mit einem Speichersystem, bei dem jeweils mehrere Bits eines Datenworts in einzelnen Speichereinrichtungen gespeichert sind. Die augenblicklich am häufigsten verwendete Form von Speichereinrichtungen ist ein dynamischer Speicher mit wahlfreiem Zugriff (DRAM). Die Anordnung der derzeitigen DRAMs, die für das hier beschriebene Speichersystem verwendet werden können, werden als 256K mal 4 oder 1 Megabit mal 4 bezeichnet. Diese Bezeichnung bedeutet, daß beim Durchführen eines Speicherlese- oder Speicherschreibzyklus während eines Zyklus 4 Datenbits parallel geschrieben oder gelesen werden. Dies ist insbesondere bei großen Hauptspeichern üblich geworden, die derartige Speichereinrichtungen mit Mehrfachbit- Ausgängen verwenden. Ein typisches Datenwort kann 32 Bits enthalten, die über mehrere Speichereinrichtungen verteilt sind. Wenn Fehlerkorrektur- und Erkennungsprüfbits zusammen mit dem Datenwort verwendet werden, werden sie ebenfalls in dem Hauptspeicher gespeichert.
• Für ein 32-Bit Datenwort verwendet ein Hamming-Code, der einen Einzelbitfehler erkennen und korrigieren und das Vorhandensein eines Doppelbitfehlers erkennen kann, minimal 7 Bits.
• Ein Standard 7-Bit Hamming-Code kann durch Verwendung von im Handel erhältlicher Komponenten implementiert werden, wie den AMD Am2nc660, National Semiconductor 74F632 oder Texas Instruments SN74AS632. Für die vorliegende Erfindung werden das Erkennen und Korrigieren von Einzelbitfehlern und das Erkennen von Doppelbitfehlern durch das gleiche Verfahren durchgeführt, das in diesen erhältlichen Komponenten implementiert ist.
• Zusätzlich zu den Figuren, die hier zur Beschreibung der vorliegenden Erfindung verwendet werden, sind weiterhin vier Tabellen enthalten, die der detaillierten Beschreibung folgen. Auf diese vier Tabellen wird in der Beschreibung der Erfindung Bezug genommen.
• Ein Segrnent eines Hauptspeichers, wie in der vorliegenden Erfindung verwendet, ist in FIGUR 1 gezeigt. Ein Speicher 10, der ein kleiner Teil eines sehr viel größeren Hauptspeichers ist, hat zehn dynamische Speichereinrichtungen mit wahlfreiem Zugriff 12, 14, 16, 18, 20, 22, 24, 26, 28 und 30. Jede dieser Speichereinrichtungen erzeugt während eines Speicherzyklus eine 4-Bit Ausgabe. Typische Speichereinrichtungen können eine Anordnung von 256K mal 4 Bits oder 1 Megabit mal 4 Bits haben. Speichereinrichtungen dieser Art sind überall erhältlich und in der Literatur der Industrie detailliert beschrieben. Mehrfachbit- Speichereinrichtungen größerer Kapazität werden in naher Zukunft zweifellos verfügbar sein.
• Der Speicher 10 hat zehn Speichereinrichtungen, die zum Speichern eines Datenwortes verwendet werden. Im gesamten Hauptspeicher eines Computers wird eine große Anzahl der Speicher 10 verwendet. Die vorliegende Erfindung kann beschrieben werden, indem nur auf den Speicher 10 Bezug genommen wird.
• Ein wichtiger Aspekt der vorliegenden Erfindung sind die Speicherstellen für die Datenbits des Datenwortes und die entsprechenden Fehlerkorrekturprüfbits und Paritätsbits im Speicher 10. Jede der Speichereinrichtungen 12-30 enthält zumindest drei Datenbits, und in jeder der Speichereinrichtungen ist nicht mehr als ein Prüfbit gespeichert.
• Bei einem ausgewählten Ausführungsbeispiel der vorliegenden Erfindung sind in Speichereinrichtung 12 Datenbits 2, 3, 5 und 31 gespeichert. In Speichereinrichtung 14 sind Datenbits 14, 20 und 24 zusammen mit Prüfbit 1 gespeichert. In Speichereinrichtung 16 sind Datenbits 0, 4, 8 und 9 gespeichert. In Speichereinrichtung 18 sind Datenbits 11, 12 und 13 zusammen mit Prüfbit 6 gespeichert. In Speichereinrichtung 20 sind Datenbits 6, 10 und 17 zusammen mit Prüfbit 5 gespeichert. In Speichereinrichtung 22 sind Datenbits 15, 18 und 19 zusammen Prüfbit 7 gespeichert. In Speichereinrichtung 24 sind Datenbits 7, 21 und 22 zusammen mit Prüfbit 4 gespeichert. In Speichereinrichtung 26 sind Datenbits 16, 23 und 25 zusammen mit Prüfbit 2 gespeichert. In Speichereinrichtung 28 sind Datenbits 26, 27 und 30 zusammen mit Prüfbit 0 gespeichert. Und schließlich sind in Speichereinrichtung 30 Datenbits 1, 28 und 29 zusammen mit Prüfbit 3 gespeichert. Die Prüfbits 0 bis 6 enthalten die 7 Bits eines herkömmlichen 7-Bit Hamming-Codes, wie er in den beschriebenen erhältlichen Komponenten verwendet wird, die vorstehend genannt sind. Das achte Prüfbit ist ein Paritätsprüfbit, das für die gesamten 32 Bits des Datenwortes erzeugt wird.
• Nun wird auf FIGUR 2 Bezug genommen, in der eine weitere Einrichtung zur Verwendung gemäß der vorliegenden Erfindung dargestellt ist. Eine Fehlererkennungsschaltung 40 enthält 7 Syndromgeneratorschaltkreise 42, 44, 46, 48, 50, 52 und 54 zusammen mit einem Paritätsgeneratorschaltkreis 56. Jeder der Syndromgeneratorschaltkreise empfängt 16 Bits des 32-Bit Datenwortes, und erzeugt über eine EXKLUSIV-ODER-Funktion ein Fehlerkorrekturprüfbit. Die Syndromgeneratorschaltkreise 42-54 erzeugen jeweils Prüfbits 0 bis 6. Der Paritätsgeneratorschaltkreis 56 verwendet für alle 32 Bits des Datenwortes eine EXKLUSIV- ODER-Funktion, um ein Verifizierungsprüfbit zu erzeugen.
• Die Dateneingänge für jeden der Syndromgeneratorschaltkreise 42-54 ist ein Datenwort, das aus dem Speicher 10 ausgelesen wird. Diese Eingaben sind wie folgt:
• Alle 32 Datenbits (0..31) werden dem Paritätsgeneratorschaltkreis 56 zugeführt, um ein Paritätsbit zu erzeugen, das als Prüfbit 7 bezeichnet wird.
• Jeder der Syndromgeneratorschaltkreise 42-56 ist ein EXKLUSIV-ODER-Schaltkreis.
• Die Ausgaben von den jeweiligen Schaltkreisen 42-56 werden als erste Eingaben logischen EXKLUSIV-ODER-Gattern 70, 72, 74, 76, 78, 80, 82 und 84 zugeführt. Die Prüfbits 0-7, die aus dem Speicher 10 ausgelesen wurden, werden jeweils den zweiten Eingängen der logischen Gatter 70 bis 84 zugeführt. Die Ausgaben der logischen Gatter 70-84 sind die jeweiligen Syndrombits 0-7. Die Syndrombits 0-6 werden hier als ein Prüfbitsyndrom bezeichnet, und das Syndrombit 7 wird hier als ein Paritätsbitsyndrom bezeichnet.
• Das Prüfbitsyndrom (Bits 0-6) wird einem Dekodierer 100 zugeführt, der die 7 Eingaben in jede der möglichen 128 Kombinationen dekodiert, um dadurch einen ausgewählten Ausgang der 128 Ausgängen des Dekodierers 100 zu aktivieren. Der Dekodierer 100 hat ein übliches Logikdesign für eine solche Dekodierung.
• Die Ausgaben von dem Dekodierer 100 werden durch eine Gruppe von Leitungen 102 zu einer entsprechenden Gruppe von Eingängen eines Fehlergeneratorschaltkreises 104 übertragen. Das Prüfbitsyndrom (Bits 0-6) wird ebenfalls dem Fehlergeneratorschaltkreis 104 zugeführt. Das Paritätsbitsyndrom, Bit 7, das an dem Ausgang des Gatters 84 erzeugt wird, wird ebenfalls als eine Eingabe dem Fehlergeneratorschaltkreis 104 zugeführt. Nach Empfang der Eingaben am Schaltkreis 104 erzeugt dieser Schaltkreis eine von 4 möglichen Ausgaben auf Leitungen 106, 108, 110, 112. Auf der Leitung 106 wird für einen Einzelbitfehler, auf Leitung 108 für einen Mehrfachbitfehler, auf Leitung 110 für einen Dreifachbitfehler und auf Leitung 112 für ein Prüfbitfehler eine Ausgabe erzeugt.
• Der Fehlergeneratorschaltkreis 104 ist in FIGUREN 3A und 3B detailliert beschrieben. Die 128 Ausgänge des Schaltkreises 100 auf Leitungen 102 werden jeweils einem ODER-Schaltkreis 130, einem ODER-Schaltkreis 132 und einem ODER-Schaltkreis 134 zugeführt. Die Ausgabe von dem ODER-Schaltkreis 130 wird als erste Eingabe einem ODER-Gatter 136 zugeführt, das Leitung 108 als Ausgang hat, um einen Mehrfachbitfehler anzuzeigen.
• Die Ausgabe des ODER-Schaltkreises 132 wird als eine erste Eingabe einem ODER-Schaltkreis 138 zugeführt, dessen Ausgabe als eine zweite Eingabe dem ODER-Schaltkreis 136 und der Leitung 110 zuführt wird, um das Vorhandensein eines Dreifachbitfehlers anzuzeigen. Die Ausgabe des ODER-Schaltkreises 134 wird Leitung 112, um einen Prüfbitfehler anzuzeigen, und außerdem als eine Eingabe einem NICHT-Gatter 140 zugeführt, dessen Ausgabe als eine erste Eingabe einem UND-Gatter 142 zuführt wird. Die Ausgabe des UND-Gatters 142 wird als die zweite Eingabe dem ODER- Gatter 138 zugeführt. Die Syndrombits 0-7 von den Gattern 70-84 werden einem ODER-Gatter 150 zugeführt, dessen Ausgang mit dem dritten Eingang des UND-Gatters 142 verbunden ist. Das Syndrombit 7 wird über ein NICHT-Gatter 152 dem zweiten Eingang des UND-Gatters 142 zugeführt. Dieses Syndrombit 7 ist außerdem mit dem ersten Eingang eines UND-Gatters 154 verbunden, dessen zweiter Eingang mit dem Ausgang des ODER-Gatters 150 verbunden ist.
• Der Ausgang des UND-Gatters 154 ist mit dem dritten Eingang des ODER-Gatters 138 verbunden.
• Die Eingänge zu dem Fehlergeneratorschaltkreis 104 sind die 128 Elemente auf Leitungen 102 zusammen mit den 8 Syndromeingängen (Bits 0-7). Die in den FIGUREN 3A und 3B gezeigte Logik erzeugt auf den Leitungen 106, 108, 110 und 112 Fehlerausgangsanzeigen.
• Die Funktion der vorliegenden Erfindung wird nun unter Bezugnahme auf FIGUREN 1 und 2 beschrieben. Wenn ein Computerhauptspeicher, der den Speicher 10 enthält, ein 32-Bit Datenwort empfängt, so wird dieses Datenwort durch einen Syndromgenerator verarbeitet, der zu den Syndromschaltkreisen 42-54 äquivalent ist, um auf herkömmliche Art und Weise einen 7-Bit Hamming-Code zu erzeugen. Das 32-Bit Datenwort wird auf ähnliche Weise einem Paritätsgeneratorschaltkreis zugeführt, wie dem Schaltkreis 56, um ein Paritätsprüfbit zu erzeugen.
• Die 7 Prüfbits des Hamming-Codes werden dann zusammen mit dem Paritätsprüfbit in der speziellen Aufteilung, die unter Bezugnahme auf FIGUR 1 beschrieben und darin gezeigt ist, in den Speichereinrichtungen 12-30 gespeichert. Diese werden als Speicherprüfbits und als ein Speicherparitätsbit bezeichnet. Daher werden dort für jedes Datenwort 32 Bits für das Datenwort, 7 Bits für den Hamming-Code und 1 Bit für das Paritätsprüfbit gespeichert. Acht der Speichereinrichtungen speichern 3 Datenbits zusammen mit einem Prüf- oder Paritätsbit, und zwei der Speichereinrichtungen speichern nur 4 Datenbits.
• Wenn eine Anforderung empfangen wird, das bestimmte Datenwort zu lesen, das zuvor in dem Speicher 10 gespeichert wurde, wird dieses parallel zusammen mit den Prüfbits und dem Paritätsbit ausgelesen, wie für die Ausgänge der Speichereinrichtungen in FIGUR 1 gezeigt. Die aus dem Speicher 10 ausgelesenen Datenwörter werden in den Kombinationen den Syndromgeneratorschaltkreisen 42-54 zugeführt, die als Eingaben für diese Schaltkreise in FIGUR 2 gezeigt sind. Alle 32 Bits des Datenwortes, das aus dem Speicher 10 ausgelesen wurde, werden dem Paritätsgeneratorschaltkreis 56 zugeführt. Jeder der Syndromgeneratorschaltkreise 42-54 erzeugt ein jeweiliges Prüfbit, das als Verifizierungsprüfbit bezeichnet wird. Der Paritätsgeneratorschaltkreis 56 erzeugt auch etwas, das als ein Verifizierungsparitätsprüfbit bezeichnet wird. Jedes der Verifizierungsprüfbits wird zusammen mit seinem zugehörigen Speicherprüfbit, das aus dem Speicher 10 ausgelesen wurde, einem entsprechenden Gatter der Gatter 70-84 zugeführt.
• Die Logikgatter 70-82 erzeugen ein Prüfbitsyndrom, das eine Funktion der aus dem Speicher 10 ausgelesenen Speicherprüfbits und der durch die Syndromgeneratorschaltkreise 42-54 erzeugten Verifizierungsprüfbits ist. Wenn in den Datenwörtern oder Prüfbits oder bei der Erzeugung der neuen Verifizierungsprüfbits keine Fehler aufgetreten sind, haben alle Ausgänge der Logikgatter 70-84 eine gleiche logische (0). Durch diesen Sydromzustand wird auf einer der Ausgangsleitungen des Dekodierers 100 eine bestimmte logische Ausgabe erzeugt, wobei diese Ausgabe dem Fehlergeneratorschaltkreis 104 zugeführt wird. In diesem Zustand wird durch den Fehlergeneratorschaltkreis 104 keine der Leitungen 106-112 aktivieren, da kein Fehler aufgetreten ist.
• Wenn eine Fehlersituation aufgetreten ist, sind die Eingänge zu den Logikgattern 70-84 nicht alle gleich, und am Ausgang der Logikgatter 70-82 wird ein Prüfbitsyndrom erzeugt, das das Vorhandensein eines Fehlers anzeigt. Dieses 7-Bit Syndrom wird dem Dekodierer 100 zugeführt, der an einem seiner 128 Ausgänge einen aktiven Zustand erzeugt, was dem Eingangssyndrom entspricht.
• Diese Ausgabe wird dem entsprechenden Eingang des Fehlergeneratorschaltkreises 104 zugeführt. Weitere Eingaben zum Schaltkreis 104 sind das Paritätssyndrom, das durch das Logikgatter 84 erzeugt wird, und das Prüfbitsyndrom (0-6). Diese Eingänge werden logisch verglichen, um auf Leitungen 106, 108, 110 und 112 eine von vier Ausgaben zu erzeugen. Die Logik zur Erzeugung der speziellen Ausgabe wird nachfolgend beschrieben.
• Das Auftreten eines Einzelbitfehlers in dem Datenwort wird als ein "weicher Fehler" bezeichnet. Das Vorhandensein eines Einzelbitfehlers kann bestimmt werden, und die Stelle des fehlerhaften Bits in dem Datenwort kann ebenfalls bestimmt werden. Dieses Bit wird dann invertiert, um ein korrektes Datenwort zu erzeugen. Dies ist ein herkömmlicher Hamming-Fehlererkennungs- und Fehlerkorrekturvorgang. Wenn dieses stattfindet, wird auf Leitung 106 ein Ausgabesignal erzeugt, das das Auftreten eines Einzelbitfehlers (weicher Fehler) anzeigt.
• Wenn jedoch in dem Datenwort und in den Prüfbits ein Mehrfachbitfehler aufgetreten ist, kann irgendeine der beiden anderen Ausgaben erzeugt werden. Wenn ein Dreifachbitfehler erkannt wird, wobei alle Fehler in einer der Speichereinrichtungen 12-30 auftreten, wird auf Leitung 110 eine Ausgabe erzeugt. Wenn aber ein Mehrfachbitfehler aufgetreten ist und nicht bestimmt werden kann, ob alle diese fehlerhaften Bits in einer der Speichereinrichtungen 12-30 aufgetreten sind, wird eine Ausgabe auf Leitung 108 erzeugt, die das Vorhandensein eines solchen Mehrfachbitfehlers anzeigt.
• Wenn ein Fehler bei einem der Prüfbits aufgetreten ist, die aus dem Speicher 10 gelesen wurden, wird ein Fehlersignal auf Leitung 112 erzeugt.
• Tabelle 1 zeigt das 8-Bit Syndrom, das am Ausgang der Gatter 70-84 für jeden Einzelbitfehlerzustand erzeugt wird. Die Datenbits werden als DBO-DB31 bezeichnet, und die Prüfbits werden als CB0-CB7 bezeichnet. Für jeden Einzelbitfehler ist das entsprechende Syndrom als ein hexadezimaler Wert gezeigt.
• Unter Bezugnahme auf Tabelle 2 sind die 128 möglichen Syndrome für das 7-Bit Prüfbit gezeigt, das die Syndrombits 0-6 enthält. Für jedes Syndrom ist der entsprechende Fehlertyp gezeigt. Die möglichen Fehlerarten sind Einzelbit, Dreifachbit, Mehrfachbit und Vierfachbit. Der Dekodierer 100 empfängt die 7-Bit Syndrom-Eingabe und aktiviert in Reaktion darauf einen seiner 128 Ausgänge.
• 30 Tabelle 3 zeigt die Syndrome, die durch die Logikgatter 70-84 erzeugt werden. Für jeden der 3- und 4-Bit Fehlerzustände, die in jedem der DRAM-Speicherschaltkreise 12-30 auftreten können, ist ein Syndrom gezeigt. Die Syndrome sind wiederum als hexadezimale Werte aufgeführt. Diese geben alle 8 Bits des Syndroms wieder, die an den Ausgängen der Logikgatter 70-84 erzeugt werden.
• Tabelle 4 zeigt jede der logischen Beziehungen zwischen den möglichen Syndromwerten und den Ausgängen, die auf den Leitungen 106, 108, 110 und 112 erzeugt werden. Ein Einzelbitfehler ist durch den Buchstaben "S" bezeichnet, ein Zweifachbitfehler durch den Buchstaben "D", ein Dreifachbitfehler durch den Buchstaben "T" und ein Vierfachbitfehler durch den Buchstaben "Q". Die Ziffern, die auf die Buchstaben folgen, stellen die Anzahl der Fehlerzustände dar, die durch diesen Eintrag gezeigt sind.
• Die Datenlisten in der Tabelle 1-4 in Verbindung mit den in FIGUREN 2 und 3 gezeigten Schaltkreisen definieren eindeutig die Logik in dem Fehlergeneratorschaltkreis 104 zur Erzeugung der ausgewählten vier Ausgänge auf Leitungen 106, 108, 110 und 112.
• Die vorliegende Erfindung sieht die Erkennung von Dreifachbitfehlern vor, die so vorliegen, daß solche Fehler in einem einzigen der Speicherschaltkreise 12-30 auftreten. Dreifachbitfehler, die über mehrere der Speicherschaltkreise 12-30 auftreten, werden nicht notwendigerweise erfaßt. Da jedoch solche Fehler wahrscheinlich infolge eines vollständigen Ausfalls von einem der Speicherschaltkreise auftreten, ist es höchst wahrscheinlich, daß jeder Dreifachbitfehler erfaßt wird.
• Obwohl verschiedene Ausführungsbeispiele der vorliegenden Erfindung in den beiliegenden Zeichnungen dargestellt und in der vorhergehenden detaillierten Beschreibung beschrieben wurden, ist es selbstverständlich, daß die Erfindung nicht auf die offenbarten Ausführungsbeispiele beschränkt ist, sondern daß zahlreiche Neuanordnungen, Abwandlungen und Ersetzungen möglich sind, ohne den Schutzbereich der Erfindung zu verlassen. TABELLE 1 TABELLE 2 TABELLE 3 TABELLE 4

Claims (6)

1. Verfahren zur Fehlerkorrektur und -erkennung für Daten, die in einem Computerspeicher (10) gespeichert werden, mit den Schritten:

- Erzeugen eines Fehlererkennungs- und Fehlerkorrektursatzes von Speicherprüfbits für ein Datenwort durch Verwendung eines ausgewählten Fehlerkorrekturcodes, der Einzelbitfehler in dem Datenwort erkennt und korrigiert und Mehrfachbitfehler erkennt,

- Erzeugen eines Speicherparitätsprüfbits für das Datenwort,

- Speichern des Datenworts, des Speicherprüfbits und des Speicherparitätsprüfbits in einem Computerspeicher (10), der eine Mehrzahl von Multi-Bit-Speichereinrichtungen (12, 14, 16, 18, 20, 22, 24, 26, 28 und 30) aufweist, wobei in jeder Speichereinrichtung (12, 14, 16, 18, 20, 22, 24, 26, 28 und 30) mehrere Bits des Datenworts gespeichert sind und in keiner der Speichereinrichtungen (12, 14, 16, 18, 20, 22, 24, 26, 28 und 30) mehr als ein Speicherprüfbit oder Speicherparitätsprüfbit gespeichert ist,

- Lesen des Datenworts, des Speicherprüfbits und des Speicherparitätsprüfbits aus dem Computerspeicher (10), wobei das Datenwort einen oder mehrere Bitfehler enthalten kann,

- Erzeugen eines Fehlererkennungs- und Fehlerkorrektursatzes von Verifizierungsprüfbits für das Datenwort, das aus dem Computerspeicher ausgelesen wurde, unter Anwendung des ausgewählten Fehlerkorrekturcodes,

- Erzeugen eines Verifizierungsparitätsprüfbits für das Datenwort, das aus dem Cornputerspeicher ausgelesen wurde,

- Vergleichen der aus dem Speicher ausgelesenen Speicherprüfbits mit den Verifizierungsprüfbits, um ein Prüfbitsyndrom zu erzeugen,

- Vergleichen des aus dem Computerspeicher (10) gelesenen Speicherparitätsprüfbits mit den Verifizierungsparitätsprüfbits, um ein Paritätssyndrom zu erzeugen, und

- Dekodieren des Prüfbitsyndroms und des Paritätssyndroms,

(a) Einzelbitfehler in dem aus dem Computerspeicher ausgelesenen Datenwort zu erkennen und zu identifizieren, wobei eine erste Ausgabe (106) erzeugt wird, oder

(b) Mehrfachbitfehler, die nicht alle in einer einzigen Speichereinrichtung auftreten, zu erkennen, wobei eine zweite Ausgabe (108) erzeugt wird, oder

(c) Dreifachbitfehler, die alle in den Datenbits innerhalb einer der Speichereinrichtungen auftreten, zu erkennen, wobei eine dritte Ausgabe (110) erzeugt wird, oder

(d) einen Prüfbitfehler zu erkennen, wobei eine vierte Ausgabe (112) erzeugt wird.

2. Verfahren zur Fehlerkorrektur und -erkennung für Daten nach Anspruch 1, wobei das Datenwort 32 Bits hat, der Satz von Speicherprüfbits 7 Bits hat und jede der Speichereinrichtungen (12, 14, 16, 18, 20, 22, 24, 26, 28 und 30) 4 Bits speichert und wenigstens 3 der 4 Bits Datenbits des Datenworts sind.

3. Verfahren zur Fehlerkorrektur und -erkennung für Daten nach Anspruch 1, wobei der Satz von Speicherprüfbits eine Minimalzahl von Bits für das Datenwort hat, um einen Einzelbitfehler zu erkennen und zu korrigieren und einen Doppelbitfehler zu erkennen.

4. Fehlererkennungsschaltung (40) für einen Computerspeicher (10), in dem ein Datenwort mit jeweils mehreren seiner Bits in jeder aus einer Mehrzahl von Speichereinrichtungen (12, 14, 16, 18, 20, 22, 24, 26, 28 und 30) zusammen mit einem Satz von Syndromprüfbits und einem Paritätsprüfbit für das gespeicherte Datenwort gespeichert ist, mit:

- einer Mehrzahl von Syndromgeneratoren (42 - 54), die jeweils zur Aufnahme einer separaten Untermenge von Bits des Datenworts angeschlossen sind, das aus den Speichereinrichtungen (12, 14, 16, 18, 20, 22, 24, 26, 28 und 30) des Computerspeichers (10) ausgelesen wurde, wobei jeder der Syndromgeneratoren (42 - 54) ein korrespondierendes Prüfbitsyndrom erzeugt,

- einer Paritätsgeneratorschaltung (56) zum Erzeugen eines Paritätsbits für das aus dem Computerspeicher gelesene Datenwort,

- Logikschaltungen (70 - 82), die angeschlossen sind, um die gespeicherten Syndromprüfbits, die aus dem Speicher gelesen werden, und die erzeugten Syndromprüfbits aufzunehmen, um ein Syndrom an seinen Ausgängen zu erzeugen,

- einer Logikschaltung (84), die angeschlossen ist, um das gespeicherte Paritätsbit zu empfangen, das aus dem Computerspeicher ausgelesen wird, und angeschlossen ist, um das erzeugte Paritätsbit zu empfangen, um daraus ein Paritätssyndrombit zu erzeugen,

- einer Dekodierschaltung (100), die angeschlossen ist, um das Syndrom zu empfangen, das Syndrom zu dekodieren und daraus ein Logiksignal auf wenigstens einer aus einer Mehrzahl von seinen Ausgabeleitungen (102) zu erzeugen, und

- einer Fehlergeneratorschaltung (104), die mit den Ausgabeleitungen der Dekodierschaltung (100) verbunden ist, um das Logiksignal zu empfangen, und angeschlossen ist, um das Syndrom und das Paritätssyndrom zu empfangen, um eine Mehrzahl von Fehleranzeigesignalen (106 - 112) einschließlich eines Einzelbitfehlersignals (106) zum Anzeigen eines Einzelbitfehlers in dem Datenwort, eines Mehrfachbitfehlersignals (108) zum Anzeigen einer Mehrzahl von Bitfehlern verteilt über mehr als eine der Speichereinrichtungen, in denen das Datenbit und Prüfbits gespeichert wurden, und eines Dreifachbitfehlersignals (110) zu erzeugen, das wenigstens drei Bitfehler in einer der Speichereinrichtungen anzeigt.

5. Fehlererkennungsschaltung für einen Computerspeicher (10) nach Anspruch 4, wobei jede der Syndrorngeneratorschaltungen (42 - 54) ein ODER-Gate ist und die Logikschaltungen (70 - 82), die angeschlossen sind, um die gespeicherten Syndromprüfbits zu empfangen, ODER-Gates sind.

6. Fehlererkennungsschaltung für einen Computerspeicher (10) nach Anspruch 4, wobei die Fehlergeneratorschaltung auch ein Prüfbitfehlersignal (112) erzeugt, das das Vorhandensein eines Bitfehlers in den in der Mehrzahl von Speichereinrichtungen (12, 14, 16, 18, 20, 22, 24, 26, 28 und 30) gespeicherten Prüfbits anzeigt.