DE60001370T2 - Verfahren und vorrichtung zur erkennung von doppelbitfehlern und korrektur von fehlern durch bauelementfehler verursacht - Google Patents

Description

HINTERGRUND DER ERFINDUNG 1. Gebiet der Erfindung
• Die vorliegende Erfindung bezieht sich auf Fehlererfassung und -korrektur in elektronischen Systemen und, genauer gesagt, auf Systeme, die Fehlerkorrekturcodes verwenden, um die Erfassung und Korrektur von Bitfehlern zu ermöglichen.
2. Beschreibung des relevanten Standes der Technik
• Fehlercodes werden üblicherweise in elektronischen Systemen verwendet, um Datenfehler zu erfassen und zu korrigieren, wie z. B. Übertragungsfehler oder Speicherfehler. Beispielsweise können Fehlercodes verwendet werden, um Fehler in Daten, die über eine Telefonleitung, einen Radiosender oder einen Compact Disc-Laser übermittelt werden, zu erfassen und zu korrigieren. Fehlercodes können zusätzlich verwendet werden, um Fehler zu erfassen und zu korrigieren, die zu in dem Speicher von Computersystemen gespeicherten Daten gehören. Ein üblicher Gebrauch von Fehlercodes besteht in dem Erfassen und Korrigieren von Fehlern von Daten, die auf einen Datenbus eines Computersystems übermittelt werden. In solchen Systemen können Fehlerkorrekturbits oder Prüfbits für die Daten vor ihrer Übertragung oder Speicherung erzeugt werden. Wenn die Daten empfangen oder wieder aufgerufen werden, können die Prüfbits verwendet werden, um Fehler innerhalb der Daten zu erfassen und zu korrigieren.
• Der Ausfall einzelner Bauteile stellt eine übliche Fehlerquelle in elektrischen Systemen dar. Fehlerhafte Bauteile können fehlerhafte Speicherchips oder fehlerhafte Datenpfade umfassen, die zwischen den Geräten eines Systems vorgesehen sind. Fehlerhafte Datenpfade können beispielsweise von fehlerhaften Anschlüssen, fehlerhaften Datenbahnen oder fehlerhaften Drähten bzw. Kabeln herrühren.
• Hamming-Codes sind ein üblicherweise verwendeter Typ eines Fehlercodes. Die Prüfbits in einem Hamming-Code sind Paritätsbits für Teile der Datenbits. Jedes Prüfbit liefert die Parität für einen einzigartigen bzw. eindeutigen Teilsatz von Datenbits. Wenn ein Fehler auftritt (d. h. eines oder mehrere der Datenbits verändern unbeabsichtigt ihren Zustand), so verändern auch ein oder mehrere der Prüfbits bei der Wiedergewinnung ihren Zustand (unter der Annahme, daß der Fehler innerhalb der Klasse von Fehlern liegt, die durch den Code abgedeckt bzw. erfaßt wird). Indem die speziellen Bits der regenerierten Prüfbits bestimmt werden, welche ihren Zustand verändert haben, kann die Position des Fehlers innerhalb der Daten bestimmt werden. Wenn beispielsweise ein Datenbit seinen Zustand verändert, so bewirkt dieses Datenbit, daß eines oder mehrere der regenerierten Prüfbits ihren Zustand verändern. Da jedes Datenbit zu einer einzigartigen bzw. besonderen Gruppe von Prüfbits beiträgt, identifizieren die Prüfbits, welche modifiziert wurden, das Datenbit, welches seinen Zustand verändert hat. Der Fehler kann korrigiert werden, indem das als fehlerhaft identifizierte Bit umgekehrt wird.
• Eine übliche Verwendung von Hamming-Codes besteht darin, Einzelbitfehler innerhalb einer Gruppe von Daten zu korrigieren. Allgemein gesprochen muß die Anzahl von Prüfbits groß genug sein, so daß 2k - 1 größer oder gleich n + k ist, wobei k die Anzahl von Prüfbits und n die Anzahl der Datenbits ist. Dementsprechend sind typischerweise sieben Prüfbits erforderlich, um einen Hamming-Code für die Einzelfehlerkorrektur für 64 Datenbits zu implementieren. Ein Hamming-Code für Einzelfehlerkorrektur ist in der Lage, einen einzelnen Fehler zu erfassen und zu korrigieren.
• Die Fig. 1-3 veranschaulichen ein Beispiel eines Systems, welches einen Hamming- Code mit Einzelfehlerkorrektur (SEC) verwendet. In diesem Beispiel werden vier Datenbits (D4, D3, D2 und D1) unter Verwendung von drei Prüfbits (P1, P2 und P3) geschützt. Der Paritätserzeuger 10 (Fig. 1) wird verwendet, um den Datenblock zu codieren, der die Datenbits und die Prüfbits enthält. Der Codierungsvorgang wird vor dem Speichern oder Kommunizieren der Daten ausgeführt. Fig. 2 zeigt eine Zuordnung von Datenbits, um die Prüfbits zu berechnen. In diesem Beispiel wird das Prüfbit P1 durch ein XOR (ausschließlich ODER) der Binärwerte in D4, D3 und D1 erzeugt. In ähnlicher Weise wird das Prüfbit P2 durch ein XOR der Binärwerte in D4, D2 und D1 erzeugt, und das Prüfbit P3 wird erzeugt durch ein XOR der Binärwerte in D3, D2 und D1. Fig. 3 zeigt die Positionen und den entsprechenden Inhalt dieser Positionen innerhalb des codierten Datenblockes. Der Datenblock, welcher die Datenbits und die erzeugten Prüfbits enthält, kann dann in einem Speicherchip gespeichert oder über einen Datenkommunikationspfad kommuniziert werden.
• Am Empfangspunkt wird der Datenblock wiedergewonnen und decodiert. Der Decodierungsvorgang umfaßt das Ausführen einer Gültigkeitsüberprüfung mit dem empfangenen Wort und das Ausführen einer Fehlerkorrekturtechnik, wenn ein Fehler erfaßt wurde. Um zu prüfen, ob ein Fehler beim Speichern (oder bei der Übermittlung) des Datenblockes aufgetreten ist, werden die Prüfbits P1, P2 und P3 wirksam wiedererzeugt unter Verwendung der empfangenen Daten, und jedes wiedererzeugte Prüfbit wird durch XOR mit dem entsprechenden empfangenen Prüfbit verknüpft, um ein entsprechendes Syndrombit zu erzeugen. Fig. 4 ist eine Tabelle, welche eine Art und Weise zeigt, in welcher diese Syndrombits erzeugt werden können. Genauer gesagt kann das Syndrombit S1 durch XOR-Verknüpfung der empfangenen Binärwerte in P1, D4, D3 und D1 erzeugt werden. Wenn keines der empfangenen Datenbits (D4, D3, D1) fehlerhaft ist, so wird der Wert des empfangenen Prüfbits P1 effektiv mit sich selbst durch XOR verknüpft und das Syndrombit S1 ist dann 0 (unter der Annahme, daß das ursprüngliche Prüfbit P1 nicht fehlerhaft ist). Wenn eines der Datenbits (D4, D3, D1) oder das Prüfbit P1 fehlerhaft ist, so ist das Syndrombit S1 l (anstehend), und zeigt damit einen Fehler an. Die Syndrombits S2 und S3 können in ähnlicher Weise erzeugt werden. Zusammengenommen können die Syndrombits S1, S2 und 53 verwendet werden, um die Position eines fehlerhaften Bits zu identifizieren. Beispielsweise zeigt der binäre Wert der Syndrombits in der Reihenfolge [S3, S2, S1] die Position des fehlerhaften Bits innerhalb des 7-Bit-Datenblocks an, wie es in Fig. 3 gezeigt wird. Wenn der Syndromcode aus lauter Nullen besteht (d. h. "000"), so haben die Daten keinen Einzelbitfehler. Bei der Identifizierung der fehlerhaften Bitposition wird der Fehler korrigiert, indem der binäre Wert an dieser Position umgekehrt wird, d. h. von 0 nach 1 oder von 1 nach 0.
• Es ist eine übliche Praxis, Daten in mehreren Komponenten zu speichern oder über mehrere Komponenten zu kommunizieren. Beispielsweise kann ein Datenblock in einer Mehrzahl von Speicherchips gespeichert werden oder er kann über eine Mehrzahl von Geräten bzw. Kabeln kommuniziert werden. Ein Fehler kann eingeführt werden, wenn eine der Komponenten fehlerhaft ist. Ein Hamming-Code wie der oben beschriebene kann verwendet werden, um in solchen Systemen eine Fehlerkorrektur anzugehen.
• Man betrachte beispielsweise den Fall des Speicherns von D Datenbits, welche durch C Prüfbits unter Verwendung von M Speicherchips geschützt werden. Der Datenblock hält demnach D + C Bits. Wenn der Datenblock gleichmäßig auf die M Speicherchips aufgeteilt wird, so speichert jeder Speicherchip X Daten- und/oder Prüfbits des Datenblockes, wobei X = (D + C)/M ist. Der Standardansatz für die Bereitstellung einer Fehlerkorrektur bei Chipfehlern besteht darin, die D + C Daten- und Prüfbits in X logische Gruppen aufzuteilen, die jeweils M Bits enthalten, und ein Bit von jedem Chip zu jeder der Gruppen zuzuordnen. Die Prüfbits in jeder Gruppe bilden einen SEC- (Einzelfehlerkorrektur-) Code, wie z. B. einen Hamming-Code. Wenn irgendein Chip fehlerhaft ist, so führt er höchstens einen Fehler in jede Gruppe ein und diese Fehler werden unabhängig unter Verwendung der SEC-Codes korrigiert. Wenn in jeder Gruppe ein Hamming-Code verwendet wird, ist eine Gesamtzahl von C = X·L Prüfbits erforderlich, wobei L die kleinste ganze Zahl derart ist, daß 2L größer als M ist. Dieser Standardansatz ist ineffizient, weil jede Gruppe in der Lage ist, unabhängig herauszufinden, welches Bit (falls überhaupt irgendeines) innerhalb der Gruppe fehlerhaft ist. Jedoch sind, wenn die einzigen betrachteten Fehler Speicherchipfehler sind, die Fehler in verschiedenen Gruppen in hohem Maße korreliert.
• In einigen Systemen kann es zusätzlich zu der Korrektur von Einzelbitfehlern aufgrund von Komponentenfehlrn wünschenswert sein, auch irgendwelche Doppelbitfehler zu erfassen, die möglicherweise auftreten. Der Standardansatz besteht darin, den Datenblock auf die Speicherchips in der oben beschriebenen Weise gleichmäßig aufzuteilen und Prüfbits für jede Gruppe zu erzeugen, die einen SEC-DED- (Einzelfehlerkorrektur-, Doppelfehlererfassungs-) Code bilden, wie z. B. einen erweiterten Hamming-Code. Wenn irgendein Chip fehlerhaft ist, so führt er höchstens einen Fehler in jede Gruppe ein und diese Fehler werden unabhängig unter Verwendung der SEC-DED-Codes korrigiert. Wenn zwei beliebige Bits fehlerhaft sind, so werden sie entweder korrigiert (wenn sie in verschiedenen Gruppen liegen) oder sie werden erfaßt (wenn sie in derselben Gruppe liegen). Wenn ein erweiterter Hamming-Code in jeder Gruppe verwendet wird, so ist eine Gesamtzahl von C = X·L Prüfbits erforderlich, wobei L die kleinste ganze Zahl ist, so daß 2(L-1)> M ist. Ähnlich wie bei der vorherigen Diskussion ist jedoch die Verwendung von erweiterten Hamming-Codes in solchen Systemen ineffizient.
• In den IEEE Transactions on Computers, Band 42, Nr. 12, 1. Dezember 1993, New York, USA, wird von Mazumder P. ein fehlertoleranter DRAM mit On-Chip-ECC offenbart, der einen Schaltkreis umfaßt, welcher innerhalb des DRAM-Chips integriert ist, um Doppelbitfehler zu korrigieren.
• Es wäre wünschenswert, ein System und ein Verfahren bereitzustellen, welche die zuverlässige Speicherung oder Übermittlung von Daten in Umgebungen ermöglichen würden, in welchen Bauteilfehler möglich sind. Insbesondere wäre es wünschenswert, ein System und ein Verfahren bereitzustellen, welche die Erfassung beliebiger Doppelbitfehler erlauben, während sie eine Korrektur von Fehlern aufgrund von Bauteilfehlern durchführen, und bei welchen die Anzahl der erforderlichen Prüfbits möglicherweise reduziert ist.
ZUSAMMENFASSUNG DER ERFINDUNG
• Die oben dargelegten Probleme können zum großen Teil durch ein System und ein Verfahren zum Erfassen und Korrigieren von Fehlern in einem Datenblock gemäß der vorliegenden Erfindung gelöst werden, wie sie in den anhängigen unabhängigen Ansprüchen definiert sind.
• In einer Ausführungsform umfaßt ein System eine Einheit zur Erzeugung von Prüfbits, welche zu schützende Daten empfängt und codiert. Die Einheit zur Erzeugung von Prüfbits teilt in effektiver Weise die Daten in eine Mehrzahl logischer Gruppen auf. Die Prüfbiterzeugungseinheit erzeugt ein Paritätsbit für jede der logischen Gruppen und erzeugt zusätzlich ein Paar globaler Fehlerkorrekturcodes, die im allgemeinen als erster globaler Fehlerkorrekturcode und als zweiter globaler Fehlerkorrekturcode bezeichnet werden. In einer Implementierung werden Daten an entsprechenden Bitpositionen innerhalb der logischen Gruppe durch eine gemeinsame Komponente transportiert, wie z. B. durch denselben Draht bzw. dasselbe Kabel, oder sie werden in demselben Bauteil gespeichert, wie z. B. in demselben Speicherchip. Zusätzlich werden Datenbits an unterschiedlichen Bitpositionen innerhalb einer gegebenen logischen Gruppe nicht durch eine gemeinsame Komponente übermittelt oder in einer gemeinsamen Komponente gespeichert.
• In einer besonderen Ausführungsform werden die Daten in eine Gesamtzahl von X logischen Gruppen aufgeteilt. Der erste globale Fehlerkorrekturcode (der in dieser Ausführungsform auch als "unverdrehter" globaler Fehlerkorrekturcode bezeichnet wird) ist im Ergebnis der Erzeugung eines individuellen Fehlerkorrekturcodes für jede logische Gruppe und der gemeinsamen XOR-Verknüpfung der Sammlung von individuellen Fehlerkorrekturcodes äquivalent. Der zweite globale Fehlerkorrekturcode (der in dieser Ausführungsform auch als der "verdrehte" globale Fehlerkorrekturcode bezeichnet wird) ist äquivalent dem Ergebnis des (oder kann abgeleitet werden durch) Verschiebens (entweder linear oder zyklisch) des Fehlerkorrekturcodes für eine gegebene i-te Gruppe um i Bitpositionen, wobei i von 0 bis X - 1 sein kann, und durch gemeinsame XOR-Verknüpfung entsprechender Spalten der sich ergebenden verschobenen Fehlerkorrekturcodes. Die Daten- und Prüfbits (die gemeinsam durch das Paritätsbit für jede logische Gruppe und die ersten und zweiten globalen Fehlerkorrekturcodes gebildet werden) werden dann durch einen Kommunikationskanal transportiert oder in einem Speicher gespeichert. Das System umfaßt weiterhin eine Fehlerkorrektureinheit, die so angeschlossen ist, daß sie die Mehrzahl von Datenbits und Prüfbits im Anschluß an die Speicherung oder Übermittlung empfängt. Die Fehlerkorrektureinheit ist so ausgestaltet, daß sie ein Paritätsfehlerbit für jede der logischen Gruppen von Daten auf der Basis der empfangenen Datenbits und der ursprünglichen Paritätsbits erzeugt. Die Paritätsfehlerbits zeigen an, ob eine Änderung in der Parität für jede logische Gruppe aufgetreten ist.
• Die Fehlerkorrektureinheit ist weiterhin so ausgestaltet, daß sie einen wiedererzeugten ersten globalen Fehlerkorrekturcode in derselben Art und Weise erzeugt, in welcher der ursprüngliche erste globale Fehlerkorrekturcode abgeleitet wird, und zwar unter Verwendung der empfangenen Daten. Demnach ist in einer Ausführungsform der wiedergewonnene erste globale Fehlerkorrekturcode dem Ergebnis des Erzeugens eines individuellen Fehlerkorrekturcodes für jede logische Gruppe (der empfangenen Daten und ihrer gemeinsamen XOR-Verknüpfung) äquivalent. Ein erster globaler Syndromcode wird dann durch XOR-Verknüpfung des ursprünglichen ersten globalen Fehlerkorrekturcodes mit dem wiedergewonnenen ersten globalen Fehlerkorrekturcode erzeugt.
• Nachfolgende Vorgänge bzw. Operationen der Fehlerkorrektureinheit hängen davon ab, ob eine ungerade Zahl der Paritätsfehlerbits vorgebracht wird oder eine geradzahlige Anzahl der Paritätsfehlerbits vorgebracht wird bzw. ansteht. In einer besonderen Ausführungsform verwendet die Fehlerkorrektureinheit in Reaktion darauf, daß sie erfaßt, daß eine ungerade Zahl von Paritätsfehlerbits ansteht, einen Binärwert des ersten Syndromcodes, um die Bitposition von irgendwelchen Fehlern innerhalb irgendeiner der logischen Gruppen zu bestimmen. Unter Verwendung dieser Information kann die Fehlerkorrektureinheit die Fehler korrigieren, indem sie die Werte an den als fehlerhaft angezeigten Positionen umkehrt.
• In einem alternativen Betrieb bestimmt die Fehlerkorrektureinheit in Reaktion darauf, daß sie eine gerade Anzahl von Paritätsfehlerbits erfaßt, die anstehen, ob der erste Syndromcode einen Wert mit lauter Nullen hat. Falls nicht, erzeugt die Fehlerkorrektureinheit ein Fehlersignal, welches anzeigt, daß in den Daten ein nicht korrigierbarer Fehler vorliegt. Dieser Zustand tritt auf, wann immer ein nicht korrigierbarer Doppelbitfehler in dem Datenblock vorliegt (d. h., wenn zwei Bits an verschiedenen Positionen in irgendeiner der logischen Gruppen Fehler haben). Wenn andererseits der erste globale Syndromcode einen Wert mit lauter Nullen hat, so bestimmt die Fehlerkorrektureinheit, ob irgendeines der Paritätsfehlerbits ansteht. Falls nicht, so werden die Daten, so wie sie empfangne wurden, als korrekt bestimmt. Wenn irgendeines der Fehlerparitätsbits ansteht, so erzeugt die Fehlerkorrektureinheit einen regenerierten bzw. wiedergewonnenen zweiten globalen Fehlerkorrekturcode in derselben Art und Weise, in welcher der ursprüngliche zweite globale Fehlerkorrekturcode abgeleitet wurde. Demnach ist in einer Ausführungsform der regenerierte zweite globale Fehlerkorrekturcode dem Ergebnis äquivalent (oder kann abgeleitet werden durch) daß der wiedergewonnene Fehlerkorrekturcode für eine gegebene i-te Gruppe um i Bitpositionen verschoben wird, wobei i zwischen 0 und X - 1 liegt, und indem entsprechende Spalten der sich ergebenden verschobenen Fehlerkorrekturcodes gemeinsam durch XOR verknüpft werden. Ein zweiter globaler Syndromcode wird dann durch XOR-Verknüpfung des ursprünglichen zweiten globalen Fehlerkorrekturcodes mit dem wiedergewonnenen zweiten globalen Fehlerkorrekturcode erzeugt. Die Fehlerkorrektureinheit verwendet dann den binären Wert eines Reihensyndromcodes, der von dem zweiten globalen Syndromcode abgeleitet wurde, um die Position eines Fehlers in irgendeiner der logischen Gruppen zu bestimmen, für welche ein Fehler angezeigt wurde (gemäß den entsprechenden Paritätsfehlerbits), und korrigiert diese Fehler, falls sie vorhanden sind. In alternativen Ausführungsformen wird der zweite globale Syndromcode (anstelle des ersten Syndromcodes) auch verwendet, um die Position von korrigierbaren Fehlern zu bestimmen, wenn eine ungerade Anzahl der Paritätsfehlerbits gesetzt ist.
• Im allgemeinen wird der erste globale Syndromcode derart erzeugt, daß er Situationen anzeigt, in welchen zwei Bitfehler in verschiedenen Positionen innerhalb der logischen Gruppe in den empfangenen Daten vorhanden sind. In solchen Situationen unterscheidet sich der erste globale Fehlerkorrekturcode von dem regenerierten bzw. wiedererzeugten ersten globalen Fehlerkorrekturcode. In der oben beschriebenen Ausführungsform wird, wenn der erste Syndromcode kein Wert mit lauter Nullen ist, wenn eine gerade Anzahl von Paritätsfehlerbits gesetzt ist, ein Doppelbitfehler angezeigt. In anderen Ausführungsformen können andere vorbestimmte Werte des ersten Syndromcodes einen Doppelbitfehler anzeigen.
• Zusätzlich wird bei Kenntnis der spezifischen logischen Gruppen, die einen Einzelbitfehler haben, im allgemeinen der zweite globale Syndromcode in der Weise erzeugt, daß ein Wert, welcher die Position des Fehlers in solchen Gruppen anzeigt, aus dem globalen Syndromcode abgeleitet werden kann. Die Gesamtzahl von Bits, welche den globalen Syndromcode und die Paritätsbits für jede logische Gruppe bilden, ist kleiner als die Gesamtzahl von Bits, die erforderlich ist für die Fehlerkorrekturcodes, die den logischen Gruppen individuell zugeordnet werden.
• Das System gewährleistet die Erfassung von beliebigen Doppelbitfehlern in dem Datenblock, während es eine Korrektur von Fehlern aufgrund von Komponenten- bzw. Bauteilfehlern ausführt. In vorteilhafter Weise kann die Gesamtzahl der erforderlichen Prüfbits (der Paritätsbits für die logischen Gruppen und der Bits, welche die ersten und zweiten globalen Fehlerkorrekturcodes bilden) kleiner sein als die Gesamtzahl von Bits, die erforderlich sind, um ein System unter Verwendung erweiterter Hamming-Codes zu implementieren.
KURZE BESCHREIBUNG DER FIGUREN
• Andere Ziele und Vorteile der Erfindung werden offensichtlich beim Lesen der folgenden genauen Beschreibung unter Bezug auf die beigefügten Zeichnungen, von denen:
• Fig. 1 (Stand der Technik) ein Blockdiagramm ist, welches einen Paritätsgenerator zeigt, um Datenbits zu codieren unter Verwendung eines Hamming-Codes zur Fehlerkorrektur,
• Fig. 2 (Stand der Technik) eine Zuordnungstabelle ist, um einen Satz von Prüfbits zu berechnen,
• Fig. 3 (Stand der Technik) eine Darstellung von Bitpositionen und deren Inhalt für einen Datenblock ist, der durch den Paritätsgenerator nach Fig. 1 codiert wurde,
• Fig. 4 (Stand der Technik) eine Zuordnungstabelle für das Erzeugen eines Syndromcodes ist,
• Fig. 5 ein Blockdiagramm eines Systems einschließlich einer Fehlersteuereinheit gemäß einer Ausführungsform der vorliegenden Erfindung ist,
• Fig. 6A einen Codierungsvorgang veranschaulicht, einschließlich der Erzeugung von Reihenparitätsbits und Reihenfehlerkorrekturcodes,
• Fig. 6B eine Art und Weise veranschaulicht, in welcher ein globaler Fehlerkorrekturcode erzeugt werden kann,
• Fig. 7A und 7B gemeinsam ein Flußdiagramm bilden, welches den Betrieb einer Ausführungsform eines Fehlerkorrektursystems zeigt,
• Fig. 8A eine Art und Weise veranschaulicht, in welcher ein Satz von Reihenparitätsfehlerbits und ein wiedergewonnener, nicht verdrehter globaler Fehlerkorrekturcode erzeugt werden können,
• Fig. 8B eine Art und Weise veranschaulicht, in welcher ein nicht verdrehter globaler Syndromcode erzeugt werden kann,
• Fig. 9A, 9B, 9C, 10A, 10B, 11A, 11B, 12A, 12B, 12C und 12D weitere Beispiele der Erzeugung von Reihenparitätsfehlerbits, nicht verdrehten globalen Fehlerkorrekturcodes, verdrehten globalen Fehlerkorrekturcodes, nicht verdrehten globalen Syndromcodes und verdrehten globalen Syndromcodes zeigen,
• Fig. 13 ein Blockdiagramm eines Systems einschließlich einer linearen Verschiebeeinheit für das Decodieren eines Datenblockes ist,
• Fig. 14 ein Funktionsblockdiagramm einer linearen Verschiebeeinheit ist,
• Fig. 15-21 eine beispielhafte Erzeugung eines Reihensyndromcodes veranschaulichen,
• Fig. 22 und 23 ein Flußdiagramm zeigen, welches eine Ausführungsform eines linearen Decodierungsvorganges veranschaulichen,
• Fig. 24-31 Zuordnungstabellen sind, welche den Betrieb eines Satzes von Prüfbits gemäß einer weiteren Ausführungsform der Erfindung zeigen,
• Fig. 32-39 Zuordnungstabellen sind, welche die Erzeugung eines Satzes von Reihenparitätsfehlerbits und wiedergewonnenen verdrehten Prüfbits für die Ausführungsform nach den Fig. 20-27 zeigen,
• Fig. 40 einen linearen Decodierungsvorgang veranschaulicht und
• Fig. 41 ein Blockdiagramm eines Systems gemäß einer weiteren Ausführungsform der vorliegenden Erfindung ist.
• Während die Erfindung für verschiedene Modifikationen und alternative Formen empfänglich und geeignet ist, werden spezielle Ausführungsformen derselben beispielhaft in den Figuren dargestellt und werden nachstehend im einzelnen beschrieben. Es versteht sich jedoch, daß die Zeichnungen und die genaue Beschreibung hierzu nicht die Erfindung auf die speziell offenbarte Form beschränken sollen, sondern daß stattdessen der Schutzumfang der vorliegenden Erfindung durch die anhängigen Ansprüche definiert wird.
GENAUE BESCHREIBUNG DER FIGUREN
• Gemäß Fig. 5 ist ein Blockdiagramm eines Systems einschließlich einer Fehlerkontrolleinheit 105 gemäß einer Ausführungsform der vorliegenden Erfindung dargestellt. In dieser speziellen Ausführungsform ist die Fehlerkontrolleinheit 105 so angeschlossen, daß sie Daten von dem Speicher 110 transportiert und empfängt. Der Speicher 110 ist so ausgestaltet, daß er einen Datenblock (Datenbits und Prüfbits) speichert, welcher von oder zu der Fehlerkontrolleinheit 105 kommuniziert wird. Der Speicher 110 weist eine Mehrzahl von Speicherchips 110A-110M auf. Jeder der Speicherchips 110A-110M ist so ausgestaltet, daß er einen Teil des Datenblockes speichert. Die Speicherchips 110A-110M können von irgendeinem Typ von Speichereinrichtungen sein, die verwendbar sind, um Daten zu speichern.
• Wie unten noch genauer beschrieben wird, ist die Fehlerkontrolleinheit 105 so ausgestaltet, daß sie in dem Speicher 110 zu speichernde Daten codiert und empfangene codierte Daten im Anschluß an die Speicherung decodiert, um gewisse Kategorien von Bitfehlern zu korrigieren und/oder zu erfassen (wenn sie auftreten), und zwar unter Verwendung einer relativ geringen Anzahl von Prüfbits im Vergleich zu traditionellen Ansätzen.
• Die Fehlersteuereinheit 105 umfaßt eine Erzeugungseinheit 120 für Prüfbits, um den Codiervorgang auszuführen und eine Fehlerkorrektureinheit 130, um den Decodiervorgang auszuführen und um eine Fehlerkorrektur auszuführen. Datenbits werden über den Datenpfad 151 empfangen und durch die Erzeugungseinheit 120 für Prüfbits codiert, und zwar vor dem Speichern eines Datenblockes (Datenbits und Prüfbits) über den Datenpfad 152 in den Speicher 110. Nachfolgend kann der gespeicherte Datenblock durch die Fehlerkorrektureinheit 130 über den Datenpfad 153 wiedergewonnen bzw. wiedergeholt werden. Die Fehlerkorrektureinheit 130 decodiert den Datenblock, um Fehler in diesen Daten zu erfassen und zu korrigieren. Wenn einer oder mehrere korrigierbare Fehler erfaßt werden, so werden die Fehler korrigiert. Die Datenbits (falls erforderlich korrigiert) werden dann über den Datenpfad 155 ausgegeben. Falls ein nicht korrigierbarer Fehler erfaßt wird, wird ein Fehlersignal auf der Leitung 156 vorgebracht.
• Es sei angemerkt, daß die Erzeugungseinheit 120 für die Prüfbits und die Fehlerkorrektureinheit 130 in Hardware, Software oder in einer Kombination aus diesen implementiert werden können. Verschiedene spezielle Implementierungen sind möglich.
• Die Betriebsweise der Fehlerkontrolleinheit 105 wird nachstehend unter Bezug auf die Fig. 5-8 erläutert. Die Fig. 6A-8B veranschaulichen ein Beispiel, wobei insgesamt 20 Datenbits, die im Speicher 110 gespeichert werden sollen, geschützt werden.
• Fig. 6A und 6B zeigen einen Codierungsvorgang, der durch die Erzeugungseinheit 120 für Prüfbits vor der Speicherung der Datenbits ausgeführt wird. Die Erzeugungseinheit 120 für Prüfbits empfängt die 20 Datenbits (über den Datenpfad 151) und verarbeitet in diesem Beispiel die Daten entsprechend fünf logischen Gruppen, wobei jede Gruppe eine entsprechende Reihe R0-R4 bildet, wie es in Fig. 6A dargestellt ist. Ein Satz von Spalten, der mit D4, D3, D2 und D1 bezeichnet ist, wird durch entsprechende Bitpositionen jeder Reihe gebildet. Wie später noch genauer beschrieben werden wird, werden die Daten, welche jede Spalte bilden, in demselben Speicherchip gespeichert und verschiedene Bits jeder Reihe werden in unterschiedlichen Speicherchips gespeichert.
• Die Erzeugungseinheit 120 für Prüfbits ist so ausgestaltet, daß sie für jede der Reihen ein Paritätsbit (PPR) erzeugt. Der Satz von Paritätsbits kann berechnet werden entweder unter Verwendung der geraden oder der ungeraden Parität. Da pro Reihe logische Gruppe ein Paritätsbit berechnet wird, ist die Anzahl der PPR-Bits gleich der Anzahl der Reihen. In dem Beispiel nach Fig. 6A wird eine gerade Parität verwendet. Demnach ist für die beispielhaft dargestellten Daten jedes der Paritätsbits (PPR) für die Reihen R0-R3 1. Das Paritätsbit für die Reihe R4 ist 0.
• Die Erzeugungseinheit 120 für Prüfbits ist weiterhin so ausgestaltet, daß sie einen ersten globalen Fehlerkorrekturcode und einen zweiten Fehlerkorrekturcode erzeugt. Allgemein gesprochen ist der erste globale Fehlerkorrekturcode einer ersten vorbestimmten logischen Kombination von Fehlerkorrekturcodes äquivalent oder kann von dieser abgeleitet werden, wobei die Fehlerkorrekturcodes jeweils einer entsprechenden Reihe individuell zugeordnet sind. In ähnlicher Weise ist der zweite globale Fehlerkorrekturcode einer zweiten vorbestimmten logischen Kombination von Fehlerkorrekturcodes, die der entsprechenden Reihe jeweils individuell zugeordnet sind, äquivalent oder kann von dieser abgeleitet werden.
• Fig. 6A und 6B veranschaulichen eine besondere Art und Weise, auf welche die ersten und zweiten globalen Fehlerkorrekturcodes durch die Erzeugungseinheit 120 für Prüfbits erzeugt werden können. Es sei angemerkt, daß die ersten und zweiten globalen Fehlerkorrekturcodes in anderen Ausführungsformen auf andere Art und Weise erzeugt werden könnten.
• Fig. 6A veranschaulicht einen Fehlerkorrekturcode (ECC), der jeder Reihe zugeordnet ist. In dem Beispiel gemäß Fig. 6A wird der Fehlerkorrekturcode für jede Reihe entsprechend der Zuordnungstabelle berechnet, die in Fig. 2 dargestellt ist. Beispielsweise ist der für die Daten in Reihe R0 berechnete Fehlerkorrekturcode [111], und der Fehlerkorrekturcode, der für die Reihe R1 berechnet wird, ist [011] usw. Es versteht sich jedoch, daß andere spezielle Fehlerkorrekturcodiertechniken für die individuellen Reihen verwendet werden können und daß verschiedenen Reihen unterschiedliche Codiertechniken der Fehlerkorrektur zugeordnet werden können.
• Wie in Fig. 6A dargestellt, ist in dieser Ausführungsform der erste globale Fehlerkorrekturcode dem Ergebnis einer XOR-Verknüpfung dar Sammlung individueller Fehlerkorrekturcodes gemeinsam äquivalent. Der erste globale Fehlerkorrekturcode in dieser Ausführungsform wird als ein "unverdrehter" Fehlerkorrekturcode bezeichnet (UGECC), und zwar aufgrund der Tatsache, daß jedes Bit des UGECC einer Kombination von ausgerichteten (und unverschobenen) entsprechenden Bits individuellen Fehlerkorrekturcodes äquivalent ist oder von dieser abgeleitet ist.
• Wie in Fig. 6B dargestellt, wird in dieser Ausführungsform der zweite globale Fehlerkorrekturcode durch gezieltes Verschieben gewisser Reihen-ECCs relativ zueinander und durch XOR- Verknüpfung der sich ergebenden, vertikal ausgerichteten Bits erzeugt. Da einige der Reihen-ECCs mehr als andere verschoben werden, werden die Bits, welche den zweiten globalen Fehlerkorrekturcode bilden, als "verdrehte" Prüfbits bezeichnet, und der zweite globale Fehlerkorrekturcode wird als ein "verdrehter" globaler Fehlerkorrekturcode (TGECC) bezeichnet. In der Ausführungsform nach Fig. 6B wird der zweite globale Fehlerkorrekturcode durch lineares Verschieben des Fehlerkorrekturcodes für eine gegebene i-te Gruppe um i Bitpositionen abgeleitet, wobei i = 0 bis X - 1 ist, und wobei X die Gesamtzahl von Reihen oder logischen Gruppen ist. Die Bits in jeder sich ergebenden vertikal ausgerichteten Spalte werden dann gemeinsam mit XOR verknüpft, um daraus den globalen Fehlerkorrekturcode zu erzeugen (führende oder angehängte Nullen können den Einträgen jeder Reihe der verdrehten ECCs vor dieser XOR-Operation, soweit erforderlich, hinzugefügt werden).
• Es versteht sich, daß, während die ersten und zweiten globalen Fehlerkorrekturcodes berechnet werden können, indem zuerst die individuellen Fehlerkorrekturcodes für jede Reihe berechnet werden, in anderen Ausführungsformen die ersten und zweiten globalen Fehlerkorrekturcodes direkt aus den Datenbits erzeugt werden können (d. h. ohne Erzeugen individueller Korrekturcodes für jede Reihe). Beispielsweise könnten die ersten und zweiten globalen Fehlerkorrekturcodes, die in den Fig. 6A und 6B dargestellt sind, direkt aus den Datenbits erzeugt werden unter Verwendung vorbestimmter Funktionen, ohne für jede Reihe individuelle Fehlerkorrekturcodes zu erzeugen.
• Beim Berechnen der unverdrehten und der verdrehten globalen Fehlerkorrekturcodes (UGECC und TGECC), wobei der Datenblock 20 Datenbits enthält, werden die Paritätsbits (PPRs) und die globalen Fehlerkorrekturcodes an den Speicher 110 geleitet. Es versteht sich, daß die Bits, welche jede Spalte (D4, D3, D2 und D1) von Daten in dem Datenblock bilden, in einem gemeinsamen Speicherchip gespeichert werden, und daß keine zwei Datenbits in verschiedenen Bitpositionen einer bestimmten Reihe in demselben Speicherchip gespeichert werden. Es versteht sich weiterhin, daß die Paritätsbits und die unverdrehten und verdrehten globalen Fehlerkorrekturcodes in zusätzlichen Speicherchips gespeichert werden können. Ein weiteres Beispiel der Art und Weise, in welcher die Paritätsbits und Bits, welche die unverdrehten und verdrehten globalen Fehlerkorrekturcodes bilden, für die Speicherung innerhalb verschiedener Speicherchips verteilt werden können, wird nachstehend noch in Verbindung mit den Fig. 22-37 geliefert.
• Es versteht sich weiterhin, daß in dem Beispiel nach den Fig. 6A und 6B insgesamt 15 Prüfbits (die Paritätsbits (PPRs) und die Bits der ersten und zweiten globalen Fehlerkorrekturcodes) für die Speicherung zusammen mit den 20 Datenbits erzeugt werden. Diese Gesamtzahl von Prüfbits ist in vorteilhafter Weise kleiner als die Anzahl von Prüfbits, die unter Verwendung konventioneller Verfahren erforderlich wären.
• Gemäß den Fig. 7A-13B wird als nächstes der Decodiervorgang für den Datenblock im Anschluß an die Speicherung erläutert. Fig. 7A und 7B bilden gemeinsam ein Flußdiagramm, welches die Betriebsweise des Fehlerkorrektursystems zeigt. Wie in Fig. 7A dargestellt, wird der Datenblock, nachdem die Erzeugungseinheit 120 für Prüfbits Daten in Schritt 202 empfangen hat, die Paritätsbits (PPRs) der ersten und zweiten globalen Fehlerkorrekturcodes (UGECC und TGECC) in Schritt 204 erzeugt hat und den Datenblock in Schritt 206 speichert oder sendet, wiedergewonnen oder empfangen durch die Fehlerkorrektureinheit 130 (Schritt 208). An diesem Punkt beginnt der Decodiervorgang.
• Wie in Fig. 8A dargestellt, verarbeitet die Fehlerkorrektureinheit 130 die Daten entsprechend denselben logischen Gruppen, wie sie durch die Erzeugungseinheit 120 für Prüfbits gebildet wurden. Die Fehlerkorrektureinheit 130 kann so ausgestaltet sein, daß sie ein regeneriertes Paritätsbits pro Reihe (PPR') unter Verwendung der empfangenen Daten erzeugt. Während der Codierung und Decodierung wird derselbe Paritätstyp (gerade oder ungerade) verwendet. In dem Beispiel nach Fig. 8A sind drei Fehler in den empfangenen Datensatz eingefügt worden, die alle in der Spalte D2 auftreten, wie es durch Unterstreichungen in den Reihen R0, R1 und R3 dargestellt ist (d. h. die Bits in den Reihen R0, R1 und R3 der Spalte D2 sind verändert worden, um Beispiele für Fehler darzustellen). Solche Fehler können das Ergebnis beispielsweise eines fehlerhaften Speicherchips sein, der die Sequenz des Datensatzes in Spalte 2 speichert. Demnach verändern für dieses Beispiel die wiedererzeugten Paritätsbits für die Reihen R0, R1 und R3 ihren Zustand. Ein Bit für jede Reihe, welches anzeigt, daß ein Paritätsfehler vorliegt, das als ein Reihenparitätsfehlerbit (RPE) bezeichnet wird, kann durch XOR-Verknüpfung der ursprünglichen Paritätsbits mit den wiedererzeugten Paritätsbits (Schritt 210) erzeugt werden. Es sei angemerkt, daß die Erzeugung von Reihenparitätsbits (RPEs) stattdessen auch direkt durch XOR-Verknüpfung entsprechender Bits der empfangenen Datenbits mit den ursprünglichen Paritätsbits (PPRs) erfolgen kann (ohne getrennte Erzeugung der wiedererzeugten Paritätsbits (PPRs)). Die Reihenparitätsbits RPEs, die in Fig. 8A dargestellt sind, geben die Einzelbitfehler in den Reihen R0, R1 und R3 wieder.
• Die Fehlerkorrektureinheit 130 erzeugt außerdem einen wiedererzeugten ersten globalen Fehlerkorrekturcode in derselben Art und Weise, auf welche auch der ursprüngliche erste globale Fehlerkorrekturcode erzeugt wurde, wobei die empfangenen Datenbits verwendet werden. Demnach ist, wie in Fig. 8A dargestellt, in der gezeigten Ausführungsform der wiedererzeugte erste globale Fehlerkorrekturcode dem Ergebnis einer XOR-Verknüpfung eines Satzes von individuellen Fehlerkorrekturcodes äquivalent, die auf den empfangenen Datenbits beruhen. Der wiedergewonnene erste globale Fehlerkorrekturcode dieser Ausführungsform wird als der wiedergewonnene unverdrehte globale Fehlerkorrekturcode (oder der wiedergewonnene UGECC) bezeichnet.
• In Schritt 214 nach Fig. 7A bestimmt die Fehlerkorrektureinheit 130, ob eine gerade Anzahl oder eine ungerade Anzahl von Reihenparitätsfehlerbits (RPEs) vorgebracht wird bzw. ansteht. Für das in Fig. 8A dargestellte Beispiel verwendet die Fehlerkorrektureinheit 130, da eine Gesamtzahl von drei Reihenparitätsfehlerbits vorgebracht wird (eine ungerade Anzahl) den Binärwert des unverdrehten globalen Syndromcodes UGSC (und zwar bezüglich des in Fig. 8B dargestellten Wertes in umgekehrter Reihenfolge), um die Position eines Fehlers in irgendeiner der logischen Gruppen (beispielsweise irgendwelchen Reihen) zu bestimmen, welche Fehler haben, und zwar gemäß den Reihenparitätsfehlerbits. Daher hat in diesem Beispiel der unverdrehte globale Syndromcode einen Wert von "110" (rückwärts gelesen), was eine binäre 6 ist. Dieser Wert entspricht der Bitposition D2, wie sie in Fig. 3 wiedergegeben ist, was der Position von Fehlern entspricht, die in dem Beispiel nach Fig. 8A eingeführt wurden.
• Die Fehlerkorrektureinheit 230 ist derart ausgestaltet, daß sie nach der Bestimmung der fehlerhaften Bits in dem empfangenen Datensatz die Datenbits korrigiert, soweit erforderlich (Schritt 213). Beispielsweise sind in dem Beispiel nach Fig. 8A die Bits in Spalte D2 der Reihen R0, R1 und R3 als fehlerhaft identifiziert worden. Dementsprechend kehrt die Fehlerkorrektureinheit 230 diese Bits um und nimmt die Daten als korrigiert an oder gibt sie über den Datenausgang 155 aus (Schritt 217).
• Fig. 9A zeigt ein ähnliches Beispiel, bei welchem zwei Fehler (statt drei) in den empfangenen Datensatz eingefügt wurden, die beide in der Spalte D2 auftreten, wie es durch Unterstreichungen in den Reihen R1 und R3 gezeigt ist. In dieser Situation erzeugt die Fehlerkorrektureinheit 130 wiederum einen Satz von Reihenparitätsfehlerbits (RPEs) und einen wiedererzeugten "unverdrehten" globalen Fehlerkorrekturcode (wiedergewonnener UGECC) während des Schrittes 210. Wie in Fig. 9B dargestellt, erzeugt die Fehlerkorrektureinheit 130 auch einen unverdrehten globalen Syndromcode (UGSC) durch XOR-Verknüpfung des ursprünglichen UGECC mit dem wiedergewonnenen UGECC (Schritt 212). In diesem Beispiel besteht der erzeugte "unverdrehte" globale Syndromcode (UGSC) aus lauter Nullen.
• Da in dem Beispiel nach Fig. 9A eine gerade Anzahl von Reihenparitätsfehlerbits vorgebracht wird (Schritt 214), bestimmt die Fehlerkorrektureinheit 130, ob der unverdrehte globale Syndromcode (UGSC) ein Wert mit lauter Nullen ist (Schritt 216). Wie in Fig. 9B dargestellt, bestimmt die Fehlerkorrektureinheit 130, da der UGSC ein Wert mit lauter Nullen ist, anschließend, ob irgendeines der Reihenfehlerparitätsbits (RPEs) ansteht (Schritt 220). In diesem Beispiel stehen die Reihenparitätsfehlerbits für die Reihen R1 und R3 an. Demnach erzeugt die Fehlerkorrektureinheit 130 einen wiedergewonnenen zweiten globalen Fehlerkorrekturcode in derselben Art und Weise, in welcher der ursprüngliche zweite globale Fehlerkorrekturcode erzeugt wurde, wobei die empfangenen Datenbits verwendet werden. Demnach wird in dieser Ausführungsform ein wiedergewonnener verdrehter globaler Fehlerkorrekturcode erzeugt (Schritt 222), indem der Fehlerkorrekturcode für eine gegebene i-te Gruppe um i Bitpositionen verschoben wird, wobei i = 0-X - 1 und indem die Bits in den sich ergebenden vertikal ausgerichteten Spalten durch XOR verknüpft werden, wie es in Fig. 9C dargestellt ist. In ähnlicher Weise wie bei der vorangehenden Diskussion kann der wiedergewonnene globale verdrehte Fehlerkorrekturcode in anderen Ausführungsformen direkt aus einer vorbestimmten Funktion der empfangenen Datenbits abgeleitet werden, ohne für jede Reihe einen individuellen Fehlerkorrekturcode zu erzeugen. In solchen Ausführungsformen ist jedoch der verdrehte globale Fehlerkorrekturcode einer vorbestimmten Kombination eines Satzes von Fehlerkorrekturcodes äquivalent, die jeweils individuell einer entsprechenden Reihe zugeordnet werden.
• Wie in Fig. 10A dargestellt, kann nach Erzeugung des wiedergewonnen verdrehten globalen Fehlerkorrekturcodes (des wiedergewonnen TGECC) ein zweiter globaler Syndromcode durch XOR-Verknüpfung des ursprünglichen zweiten globalen Fehlerkorrekturcodes mit dem wiedergewonnenen zweiten globalen Fehlerkorrekturcode (Schritt 224) erzeugt werden. In dieser Ausführungsform wird der zweite globale Syndromcode als ein verdrehter globaler Syndromcode (TGSC) bezeichnet. Der zweite globale Syndromcode ist kennzeichnend für einen Unterschied zwischen dem ursprünglichen zweiten globalen Fehlerkorrekturcode und dem wiedergewonnenen zweiten globalen Fehlerkorrekturcode. In Ausführungsformen, in welchen die Fehlerkorrekturcodes für verschiedene logische Gruppen effektiv in einer verdrehten Art und Weise verschoben und durch XOR verknüpft werden, beinhaltet der zweite globale Syndromcode ein Bit, welches jeder ausgerichteten Spalte der wiedergewonnenen verschobenen Fehlerkorrekturcodes entspricht, welches anzeigt, ob ein Paritätsfehler für diese Spalte vorliegt. Beispielsweise werden in dem Beispiel nach Fig. 10A die Bits in dem globalen verdrehten Syndromcode (TGSC) für die Positionen 2, 3, 4 und 5 gesetzt. Dies ist das Ergebnis der Tatsache, daß die Parität in jeder der Spalten 2, 3, 4 und 5 der verschobenen wiedergewonnenen Fehlerkorrekturcodes nach Fig. 9C sich von der Parität jeder der entsprechenden Spalten der ursprünglichen verschobenen Fehlerkorrekturcodes unterscheidet, wie in Fig. 6B dargestellt. Dementsprechend weist in dieser Ausführungsform der verdrehte globale Syndromcode ein Bit auf, welches jeder ausgerichteten Spalte der wiedergewonnen verschobenen Fehlerkorrekturcodes entspricht, und welches anzeigt, ob ein Paritätsfehler für diese Spalte vorliegt. Da die wiedergewonnenen Fehlerkorrekturcodes für die logischen Gruppen, welche Fehler haben (unter der Annahme, daß der unverdrehte globale Syndromcode ein Wert mit lauter Nullen ist), Veränderungen an genau denselben Bitpositionen erzeugen, kann durch Verschieben der verschiedenen Fehlerkorrekturcodes und durch XOR-Verknüpfung der resultierenden bitausgerichteten Spalten die Korrelation, die bezüglich Änderungen in den Fehlerkorrekturcodes für logische Gruppen vorliegt, welche Fehler haben, ausgewertet werden, um dadurch Information zu extrahieren, welche die speziellen Informationen der Fehler anzeigt.
• Beispielsweise veranschaulicht Fig. 10B eine Art und Weise, in welcher ein Satz von Reihensyndromcodes, von denen jeder eine Kennzeichnung der Position eines Fehlers in einer gegebenen Reihe ist, unter Verwendung des verdrehten globalen Syndromcodes und der Reihenparitätsfehlerinformation erzeugt werden kann (Schritt 226). Wie in Fig. 10B dargestellt, werden (anfänglich nicht gefüllte) Einträge für jeden Reihensyndromcode bereitgestellt, indem die Einträge in derselben Art und Weise verschoben werden, wie die Fehlerkorrekturcodes verschoben wurden, um den verdrehten globalen Fehlerkorrekturcode zu erzeugen. Zunächst können die Reihensyndromcodes für irgendwelche Reihen, die keine Fehler haben, mit Werten aus lauter "Nullen" gefüllt werden (weil Reihen ohne Fehler nicht zu einem Paritätsfehler in irgendeiner gegebenen Reihe beitragen können, wie es durch den verdrehten globalen Syndromcode angegeben wird). Demnach können die Reihensyndromcodeeinträge für die Reihen R0, R2 und R4 mit lauter "0"-Werten gefüllt werden. Wie in Fig. 10B gezeigt, ist die erste Reihe mit einem Fehler die Reihe R1. Da das erste Bit des Reihensyndromcodes für die Reihe R1 sich in der Spaltenposition 1 befindet, und da der globale Syndromwert für diese Bitposition Null ist und der einzige sonstige beitragende Wert für diese Bitposition des verdrehten globalen Syndromcodes aus dem Reihensyndromcode für die Reihe R0 abgeleitet wird (von dem bereits bekannt ist, daß er "0" ist), kann für den Wert des ersten Bits des Reihensyndromcodes für die Reihe R1 eine "0" eingesetzt werden. Zusätzlich kann, da der Reihensyndromcode für jede Reihe mit einem Fehler bekanntermaßen identisch ist, das erste Bit des Reihensyndromcodes für die Reihe R3 auch mit einer "0" gefüllt werden. Anschließend kann das zweite Bit des Syndromcodes für die Reihe R1 in ähnlicher Weise bestimmt werden durch Betrachten des Wertes in der Bitposition 2 des globalen Syndromcodes und der Werte der Bits in Position 2 der Reihen 0 und 2 (d. h. das letzte Bit des Reihensyndromcodes für die Reihe R0 und das erste Bit des Reihensyndromcodes für die Reihe R2). In dieser Situation kann für den Wert des zweiten Bits des Reihensyndromcodes für die Reihe R1 eine "1" eingesetzt werden. Dieser Wert wird wiederum in dem zweiten Bit des Reihensyndromcodes für die Reihe R3 wiedergegeben. Das letzte Bit der Reihensyndromcodes kann in ähnlicher Weise bestimmt werden.
• Der Binärwert der Reihensyndromcodes (genommen in umgekehrter Reihenfolge bezüglich der gezeigten Werte in Fig. 10B) zeigt die Position des Fehlers für logische Gruppen an, welche Fehler haben. Demnach korreliert in diesem Beispiel der Wert "110", der eine binäre 6 ist, mit der Bitposition D2, wie in Fig. 3 dargestellt. Diese Position entspricht der Position der Fehler, die in dem in Fig. 9A dargestellten Beispiel eingefügt wurden.
• Die Fehlerkorrektureinheit 230 ist so ausgestaltet, daß sie nach der Bestimmung der fehlerhaften Bits in dem empfangenen Datensatz die Daten nach Bedarf korrigiert. Beispielsweise sind in dem Beispiel nach Fig. 9A die Bits in Spalte D2 der Reihen R1 und R3 als fehlerhaft identifiziert worden. Dementsprechend kehrt die Fehlerkorrektureinheit 230 diese Bits um und gibt die Daten als korrigiert über den Datenausgang 155 aus.
• Fig. 11A veranschaulicht ein weiteres Beispiel, bei welchem zwei Fehler in eine einzige logische Gruppe eingefügt wurden (d. h. in eine Reihe). Genauer gesagt haben in Fig. 11A die Bits in den Positionen D3 und D2 der Reihe R1 Fehler. In diesem Fall sind alle Reihenparitätsfehlerbits 0, da innerhalb derselben Reihe R1 ein Doppelbitfehler auftritt. Zusätzlich ist in diesem Fall der wiedergewonnene unverdrehte globale Fehlerkorrekturcode "000". Wie in Fig. 11B dargestellt, bestimmt die Fehlerkorrektureinheit 130, nachdem der unverdrehte globale Syndromcode während des Schrittes 212 erzeugt wurde, daß eine gerade Anzahl (0) von Reihenparitätsfehlerbits in diesem Fall ansteht, und zwar während des Schrittes 214. Demnach bestimmt die Fehlerkorrektureinheit 130, ob der unverdrehte globale Syndromcode ein Wert mit lauter Nullen ist, wie in Fig. 11B angezeigt. Da der unverdrehte globale Syndromcode kein Wert mit lauter Nullen ist, wird während des Schrittes 230 ein Fehlersignal erzeugt, um das Vorliegen des Doppelbitfehlers anzuzeigen.
• Fig. 12A zeigt ein weiteres Beispiel, in welchem ein Doppelbitfehler eingefügt wurde, wobei einer in der Spalte D2 der Reihe R0 und der andere in Spalte D4 der Reihe R4 auftritt. Wie in diesem Beispiel dargestellt, sind die Reihenparitätsfehlerbits für die Reihen R0 und R4 gesetzt. Zusätzlich ist der wiedergewonnene, unverdrehte globale Fehlerkorrekturcode "010". Da eine gerade Anzahl von Reihenparitätsfehlerbits ansteht (Schritt 214), bestimmt die Fehlerkorrektureinheit 130, ob der unverdrehte: globale Syndromcode ein Wert aus lauter Nullen ist. Wie in Fig. 12B dargestellt, erzeugt die Fehlerkorrektureinheit 130, da der unverdrehte globale Syndromcode kein Wert mit lauter Nullen ist, während des Schrittes 230 ein Fehlersignal, um das Vorhandensein des Doppelbitfehllers anzuzeigen.
• Gemäß Fig. 12 ist schließlich ein Beispiel dargestellt, wobei keine Fehler in den Datensatz eingefügt wurden. Demnach ist in diesem Beispiel keines der Reihenparitätsfehlerbits gesetzt und der wiedergewonnene, unverdrehte globale Fehlerkorrekturcode ist "110". Wie in Fig. 12D dargestellt, ist der unverdrehte globale Syndromcode daher "000". Da die Fehlerkorrektureinheit 130 feststellt, daß eine gerade Anzahl von Reihenparitätsfehlerbits während des Schrittes 214 ansteht, bestimmt die Fehlerkorrektureinheit 130, ob irgendeines der Reihenparitätsfehlerbits während des Schrittes 220 gesetzt ist. Da in diesem Fall keines gesetzt ist, nimmt die Fehlerkorrektureinheit 130 die Daten als korrekt an.
• Gemäß den Fig. 13-23 wird als nächstes eine Art und Weise betrachtet, in welcher die Reihenparitätsinformation und der verdrehte globale Fehlerkorrekturcode decodiert werden können, um den Reihensyndromcode zu erzeugen. Genauer gesagt kann, wie in Fig. 13 dargestellt, die Fehlerkorrektureinheit 130 eine Erzeugungseinheit 131 für einen RPE/globalen Syndromcode und eine lineare Verschiebungseinheit 132 für die Decodierung eines empfangenen Datenblockes verwenden, welcher unter Verwendung der linearen Verschiebungsmethode codiert wurde, wie sie oben beschrieben wurde. Ein Funktionsblockdiagramm, welches funktionelle Aspekte der linearen Verschiebeeinheit 132 veranschaulicht, ist in Fig. 14 dargestellt. Wie gezeigt, umfaßt die lineare Verschiebeeinheit 132 eine Steuereinheit 135, die mit einem Paar von Verschieberegistern 133 und 134 verbunden ist. Die unterschiedliche Funktionalität, die in den Fig. 13 und 14 dargestellt ist, kann in Hardware, Software oder in irgendeiner Kombination hieraus implementiert werden.
• Die Erzeugungseinheit 131 für RPE/globalen Syndromcode erzeugt die Reihenparitätsfehlerbits (RPEs), den unverdrehten globalen Syndromcode (UGSC) und den verdrehten globalen Syndromcode (TGSC) gemäß der vorstehenden Beschreibung unter Verwendung des empfangenen Datenblockes. Wenn eine gerade Anzahl der Reihenparitätsfehlerbits (RPEs) gesetzt ist, werden die Reihenparitätsfehlerbits und der globale Syndromcode für die lineare Verschiebungseinheit 132 bereitgestellt, um den Reihensyndromcode zu bestimmen.
• Die Betriebsweise der linearen Verschiebeeinheit 132 wird unter Bezug auf die Fig. 15- 21, zusammen mit den Flußdiagrammen der Fig. 22 und 23 erläutert. Wie in Fig. 15 dargestellt, umfaßt das Schieberegister 131 eine Mehrzahl von Zellen RPE[0:4], um die Reihenparitätsfehlerbits (RPEs) für die Reihen 0-4 jeweils zu speichern. In ähnlicher Weise umfaßt das Schieberegister 132 eine Mehrzahl von Zellen TGSC[0:6] zum Speichern des verdrehten globalen Syndromcodes. Wie aus den Fig. 15 und 22 gemeinsam zu erkennen ist, werden anfänglich die Reihenparitätsfehlerbits RPEs in das Schieberegister 133 geladen und die Steuereinheit 135 bestimmt, ob das Schieberegister nur "Nullen" enthält (Schritte 310 und 330). Wenn das Schieberegister 133 ausschließlich Nullen enthält und damit anzeigt, daß kein Einzelbitreihenfehler vorliegt, so wird gemeldet, daß kein Datenfehler vorliegt und die Daten werden aus der Fehlerkontrolleinheit (Schritt 340) ausgegeben. Wenn andererseits eines oder mehrerer Paritätsfehlerbits gesetzt sind, so wird der verdrehte globale Syndromcode in das Schieberegister 134 geladen (Schritt 350). Fig. 16 zeigt den Inhalt der Schieberegister 133 und 134 an diesem Punkt des Verfahrens für die beispielhaften RPEs und den verdrehten globalen Syndromcode, die für das zu Fig. 10B gehörige Beispiel erzeugt wurden.
• Der Inhalt der am weitesten rechts liegenden Zelle des Schieberegisters 133 (Zelle RPE[0]) wird dann während des Schrittes 360 bestimmt. Wenn der Wert der am weitesten rechts liegenden Zelle RPE[0] des Schieberegisters 133 "0" ist, so werden die Inhalte sowohl des Schieberegisters 131 als auch des Schieberegisters 134 um eine Bitposition nach rechts verschoben (Schritt 370). Die am weitesten links angeordnete Parität in jedem dieser Register wird durch eine "0" ergänzt bzw. "unterfüttert" und die Werte, die von den am weitesten rechts liegenden Positionen verschoben werden, werden verworfen. Dieser Vorgang wiederholt sich, bis der Wert in der am weitesten rechts liegenden Zelle RPE[0] des Registers 133 eine "1" ist. Fig. 17 zeigt die resultierenden Werte in den Schieberegistern 133 und 134 im Anschluß an diesen Betrieb für die beispielhaften Codes.
• An diesem Punkt wird der Bitwert in der am weitesten rechts liegenden Zelle des Registers 134 als ein Reihensyndromcodebit RSC[0] aufgezeichnet, wie es auch in Fig. 17 dargestellt ist (Schritt 380). Wenn noch nicht alle Reihensyndromcodebits bestimmt worden sind (Schritt 390), wird die Feststellung getroffen, ob das zuletzt aufgezeichnete Reihensyndromcodebit eine 1 war. Falls nicht, so werden die Inhalte des Schieberegisters 134 erneut um eine Position nach rechts verschoben (Schritt 44), und der Vorgang wiederholt sich. Wenn andererseits das letzte Reihensyndromcodebit als eine 1 aufgezeichnet worden war, werden die ausgerichteten Bitpositionen der ersten und zweiten Schieberegister durch XOR miteinander verknüpft und das Ergebnis wird in dem zweiten Schieberegister 134 gespeichert (Schritte 420 und 430). In dem dargestellten Beispiel war das zuletzt aufgezeichnete Reihensyndromcodebit eine "0" und demnach werden die Inhalte der zweiten Schieberegister 134 um eine Position nach rechts verschoben (Schritt 440), und der Vorgang wiederholt sich durch Aufzeichnen des Wertes in der am weitesten rechts liegenden Position des Registers 134 als nächstes RSC-Bit, wie es in Fig. 18 dargestellt ist.
• Während der nächsten Iteration wird, da das zuletzt aufgezeichnete RSC-Bit eine "1" war, der Wert in dem Schieberegister 133 durch XOR mit dem Wert in dem Schieberegister 134 verknüpft (Schritt 420) und das Ergebnis wird in dem Schieberegister 134 gespeichert, wie es in Fig. 19 dargestellt ist. Der Inhalt des Registers 134 wird erneut um eine Position nach rechts verschoben, wie es in Fig. 20 dargestellt ist (Schritt 440) und das resultierende Bit in der am weitesten rechts liegenden Position des Schieberegisters 134 wird als das nächste RSC-Bit aufgezeichnet, wie es in Fig. 21 wiedergegeben ist (Schritt 380). Wenn alle Bits des Reihensyndromcodes bestimmt worden sind, so endet der Vorgang (Schritt 400).
• Der Reihensyndromcode ist kennzeichnend für die Position des Fehlers für jede Reihe mit einem Fehler. In dem dargestellten Beispiel ist der binäre Wert des Reihensyndromcodes 6. Gemäß Fig. 3 entspricht die Bitposition 6 der Spalte D2, welches die Position der in dem Beispiel nach Fig. 9A eingeführten Fehler ist.
• Es versteht sich, daß alternative Ausführungsformen des Decodierverfahrens mit linearer Verschiebung, welches in Verbindung mit den Fig. 13-23 beschrieben wurde, möglich sind. Beispielsweise könnten, anstatt die Werte in den Schieberegistern 133 und 134 nach rechts zu verschieben, diese Werte in ähnlicher Weise auch nach links verschoben werden, um den Reihensyndromcode abzuleiten.
• Es versteht sich weiterhin, daß die empfangenen Prüfbits unter Verwendung irgendeines anderen Mechanismus decodiert werden könnten. Beispielsweise könnten Mechanismen, welche eine Gauß'sche Eliminierung verwenden, benutzt werden, um die Reihenparitätsfehlerbits und den verdrehten globalen Syndromcode zu decodieren, um einen Reihensyndromcode abzuleiten.
• Es sei außerdem angemerkt, daß in verschiedenen Ausführungsformen eine der Reihen (oder logischen Gruppen) bei der Berechnung des verdrehten globalen Fehlerkorrekturcodes und des wiedergewonnenen verdrehten globalen Fehlerkorrekturcodes fortgelassen werden könnte. Beispielsweise kann in der Darstellung nach den Fig. 6A und 6B die Information des Fehlerkorrekturcodes, die sich auf die Reihe R4 bezieht, bei der Erzeugung des verdrehten globalen Fehlerkorrekturcodes fortgelassen werden. In solchen Ausführungsformen können der verdrehte globale Fehlerkorrekturcode, der wiedergewonnene verdrehte globale Fehlerkorrekturcode und der verdrehte globale Syndromcode jeweils durch ein Bit weniger ausgedrückt werden. Wenn ein Einzelbitfehler in der logischen Gruppe auftritt, die bei der Berechnung der verdrehten und unverdrehten globalen Fehlerkorrekturcodes fortgelassen wurde, so kann die Position des Fehlers dennoch unter Verwendung des unverdrehten globalen Syndromcodes bestimmt werden.
• Die Fig. 34-39 sind Tabellen, die eine weitere Ausführungsform eines Systems veranschaulichen, welches die lineare Verschiebetechnik für die Erzeugung des globalen Syndromcodes verwendet, wie sie oben beschrieben wurde. In der durch die Fig. 24-39 dargestellten Ausführungsform werden 262 Datenbits durch 26 Prüfbits geschützt. Der Code ist definiert in Form von Blöcken aus 288 Bits. Die Datenbits innerhalb eines Blockes sind mit D[261:0] bezeichnet. Die 26 Prüfbits innerhalb eines Blockes bestehen aus 8 Paritätsbits P[7:0], einem unverdrehten globalen Fehlerkorrekturcode, der aus 6 regulären (unverdrehten) Prüfbits R[5:0] besteht, sowie einem verdrehten globalen Fehlerkorrekturcode, der aus 12 verdrehten Prüfbits T[11:0] besteht.
• Der 288-Bit-Block ist in 8 Gruppen aufgeteilt, die als G[0] bis G[7] bezeichnet sind, und von denen jeder 36 Bits enthält. Dieser Code kann einen Fehler pro Gruppe G[0] bis G[7] korrigieren, vorausgesetzt, daß all diese Fehler innerhalb derselben Position innerhalb einer Gruppe auftreten. Der Code kann weiterhin beliebige Doppelbitfehler erfassen, wie es oben beschrieben wurde.
• Die Paritätsbits P[7:0], die regulären Prüfbits R[5:0] und die verdrehten Prüfbits T[11:0] werden entsprechend den Tabellen der Fig. 24-31 berechnet. Jede Tabelle listet die 36-Bit- Positionen innerhalb der Gruppe und die Inhalte jeder Bitposition auf. Beispielsweise stellt G[0][0] P[0], G[0][29] enthält D[27], und G[1][0] enthält T[2], usw. Die verbleibenden Reihen in jeder Tabelle liefern die Regeln für das Berechnen der Prüfbits. Jedes Prüfbit ist das Ergebnis der XOR- Verknüpfung gewisser Werte. Genauer gesagt werden die Werte, welche zu einem bestimmten Prüfbit beitragen, unter Verwendung einer "1" an den passenden Positionen in den Tabellen angezeigt. Beispielsweise ist das Paritätsbit P[0] das Ausschließlich-Oder-Ergebnis von G[0][35:1]. Da die Paritätsbits P[7:0] von gewissen Prüfbits R[5:0] und T[11:0] abhängen, können die Prüfbits R[5:0] und T[11:0] berechnet werden, bevor die Paritätsbits P[7:0] berechnet werden. In ähnlicher Weise können, da die regulären Prüfbits R[5:0] von gewissen der verdrehten Prüfbits T[11:0] abhängen, die verdrehten Prüfbits T[11:0] zuerst berechnet werden und anschließend die regulären Prüfbits R[5:0]. Alternative Regeln für das Berechnen der Paritätsfehlerbits und der Prüfbits direkt aus den Daten und in irgendeiner beliebigen Reihenfolge können ebenfalls abgeleitet werden.
• Es versteht sich, daß es in diesem Beispiel insgesamt 36 Einträge in jeder Gruppe gibt. Dementsprechend kann das System so konstruiert werden, daß insgesamt 36 Speicherchips verwendet werden, die jeweils ein Bit von einer entsprechenden Position jeder Gruppe speichern.
• Wenn die Daten empfangen werden, werden Paritätsfehlerbits Q[7:0] und wiedergewonnene Prüfbits S[5:0] und V[11:0] (die wiedergewonnenen unverdrehten und verdrehten globalen Fehlerkorrekturcodes) berechnet durch XOR-Verknüpfung der empfangenen Werte entsprechend den Zuordnungstabellen der Fig. 32-39. Zusätzlich kann ein globales Paritätsfehlerbit Q berechnet werden durch XOR-Verknüpfung von Q[7 : 0].
• In bestimmten Fällen ist es notwendig, ein Reihensyndrom U[5:0] zu erzeugen (d. h. den Reihen- oder Gruppensyndromcode). Dieses unverdrehte Syndrom ist eine Funktion von V[11:0] und Q[7:0]. Wie in Fig. 40 dargestellt und wie in dem vorherigen Beispiel, kann das unverdrehte Syndrom U[5:0] unter Verwendung paralleler Schieberegister 333 und 334 berechnet werden, die ähnlich den in Fig. 15 dargestellten Registern 133 und 134 sind.
• Das Schieberegister 333 enthält 7 Zellen, A[6:0], das Schieberegister 334 enthält 12 Zellen B[11:0]. Jede Zelle hält ein einzelnes Bit. Die Schieberegister 333 und 334 werden getrennt gesteuert bzw. kontrolliert. Wenn ein Schieberegister eine Verschiebung ausführt, überträgt es den Inhalt jeder Zelle um eine Position nach rechts, gibt den Wert aus, der sich in der am weitesten rechts liegenden Zelle befunden hat und lädt eine "0" in seine am weitesten links liegende Zelle. Ähnlich wie bei der vorangehenden Beschreibung ist es auch möglich, das durch XOR-Verknüpfung erzeugte Ergebnis des Schieberegisters 333 und des Schieberegisters 334 zu berechnen und den Inhalt in dem Schieberegister 334 zu speichern (das Schieberegister 333 wird logisch mit "Nullen" in den Positionen 11:7 unterfüttert, wenn das XOR bereitgestellt wird).
• Das unverdrehte Reihensyndrom U[5 : 0] wird folgendermaßen berechnet:
• 1. Lade Q[i] in die Zelle A[i], 0 i 6 und lade V[i] in Zelle B[i], 0 ≤ i ≤ 11.
• 2. Wenn A[0] 0 enthält:
• a. Schiebe beide Schieberegister 333 und 334 um eine Position nach rechts und verwirf die dabei herausgeschobenen Werte.
• 3. Für i = 0 bis 5:
• a. Setze U[i] = B[0].
• b. Wenn B[0] = 1, so berechne die XOR-Verknüpfung der Schieberegister 333 und 334 und ordne das Ergebnis in Schieberegister 334 an (d. h. B[j] = A[j] XOR B[j], 0 ≤ j ≤ 6).
• c. Verschiebe das Schieberegister 334 um eine Position nach rechts und verwirf den herausgeschobenen Wert.
• Wenn Q, Q[7:0], S[5:0] und U[5:0] gegeben sind, so werden die Fehler folgendermaßen korrigiert. Die Beschreibung, welche Art von Fehler aufgetreten ist, geht von der Annahme aus, daß die Fehler innerhalb des betrachteten Typs liegen (nämlich 1 oder 2 Fehler an beliebigen Stellen oder 0 bis 8 Fehler, die sich alle in derselben Position innerhalb ihrer Gruppe befinden).
• 1. Falls Q = 0:
• a. Falls S[5:0] = 00000000:
• i. Falls Q[7:0] = 00000000, kein Fehler ist aufgetreten.
• ii. Falls Q[7:0] ≠ 00000000, so ist ein korrigierbarer Fehler aufgetreten. Ergänze die Bits an allen Stellen der Form G[i][j], 0 ≤ i ≤ 7, 0 ≤ j ≤ 35, wobei Q[i] = 1 und j = U[5:0] (betrachtet als Binärzahl). (Falls U[5:0] > 35, so ist ein korrigierbarer Fehler aufgetreten, der nicht in der betrachteten Klasse von Fehlern liegt.)
• b. Falls S[5:0] ≠ 00000000, so ist ein nicht korrigierbarer Fehler aufgetreten.
• 2. Falls Q = 1: Ein korrigierbarer Fehler ist aufgetreten. Man ergänze die Bits an allen Stellen der Form G[i][j], 0 ≤ i ≤ 7, 0 ≤ j ≤ 35, wobei Q[i] = 1 und j = S[5:0] (betrachtet als Binärzahl). (Falls S[5:0] > 35, so ist ein nicht korrigierbarer Fehler aufgetreten, der nicht in der Klasse der betrachteten Fehler liegt.)
• Es versteht sich, daß kein Fehler aufgetreten ist, falls Q[7:0] = 00000000 und S[5:0] = 000000. Es versteht sich außerdem, daß U[5:0] nur in dem Fall 1.a.ii berechnet werden muß (was anzeigt, daß ein korrigierbarer Fehler aufgetreten ist).
• In der durch die Fig. 22-37 dargestellten Ausführungsform wird der verdrehte globale Fehlerkorrekturcode, der durch verdrehte Prüfbits T[11:0] gebildet wird, direkt aus einer vorbestimmten Kombination der Datenbits erzeugt. Jedes verdrehte Prüfbit T[11:0] wird in einer Position innerhalb jeder Gruppe gespeichert, so daß es das einzige Prüfbit ist, welches diese Position abdeckt. Beispielsweise wird, wie in Fig. 32 dargestellt, das verdrehte Prüfbit T[0] an einer Position G[0][01] gespeichert und es ist das einzige Prüfbit, welches zu dem wiedergewonnenen verdrehten Prüfbit V[0] beiträgt, usw. Zusätzlich sei angemerkt, daß die Paritätsbits T[7:0] für jede Datengruppe gewisse verdrehte Prüfbits umfassen, die innerhalb dieser Gruppe gespeichert sind. Da die Paritätsbits innerhalb der Position [00] der verschiedenen Gruppen gespeichert sind, kann eine weitere Effizienz erzielt werden.
• Alternative Ausführungsformen sind ebenfalls möglich. Beispielsweise werden in einer anderen Ausführungsform, die man sich vorstellen kann, die Fehlerkorrekturcodes, welche für die logischen Gruppen erzeugt werden, "zyklisch" verschoben (anstatt linear verschoben) und sie werden durch XOR miteinander verknüpft, um den verschobenen globalen Fehlerkorrekturcode ebenso wie die wiedergewonnenen verschobenen Fehlerkorrekturcodes zu erzeugen.
• Außerdem sei angemerkt, daß in anderen Ausführungsformen der Pfad "C" des Flußdiagramms nach Fig. 7B fortgelassen werden kann. In solchen Ausführungsformen kann, wenn eine ungerade Anzahl von Paritätsfehlerbits ansteht, die Position eines Fehlers unter Verwendung des verdrehten globalen Syndromcodes bestimmt werden.
• Schließlich zeigt Fig. 41 eine Ausführungsform, in welcher ein Datenblock, der gemäß den vorstehenden Techniken geschützt ist, durch eine Mehrzahl von Kommunikationskanälen 410A ... 410M übertragen wird. Jeder Kommunikationskanal 410A-410M steht beispielhaft für einen Draht bzw. ein Kabel oder ein anderes Übertragungsmedium. Ähnlich wie bei den vorherigen Ausführungsformen werden unterschiedliche Bits in jeder logischen Gruppe über unterschiedliche Kommunikationskanäle transportiert.
• Während die vorliegende Erfindung unter Bezug auf bestimmte Ausführungsformen beschrieben wurde, versteht es sich, daß die Ausführungsformen anschaulich und beispielhaft sind und daß der Schutzumfang der Erfindung nicht auf diese Weise beschränkt ist. Irgendwelche Variationen, Modifikationen, Additionen oder Verbesserungen der beschriebenen Ausführungsformen sind möglich. Diese Variationen, Modifikationen, Additionen und Verbesserungen können in den Schutzumfang der Erfindung fallen, so wie sie in den folgenden Ansprüchen im einzelnen angegeben ist.

Claims (27)

1. System zum Erfassen und Korrigieren von Datenfehlern, mit:

einer Einheit (120) zum Erzeugen von Prüfbits und für den Empfang einer Mehrzahl von Datenbits, wobei die Prüfbit-Erzeugungseinheit dafür ausgelegt ist, ein Paritätsbit zu erzeugen, welches jeweils einer aus einer Mehrzahl von Gruppierungen der Datenbits entspricht, und wobei die Prüfbit-Erzeugungseinheit dafür ausgelegt ist, einen ersten allgemeinen Fehlerkorrekturcode zu erzeugen, der eine erste vorbestimmte Kombination eines Satzes von Fehlerkorrekturcodes anzeigt, die jeweils einzeln einer entsprechenden aus der Mehrzahl von Gruppierungen zugeordnet sind, und wobei die Prüfbit- Erzeugungseinheit dafür ausgelegt ist, einen zweiten allgemeinen Fehlerkorrekturcode zu erzeugen, der eine zweite vorbestimmte Kombination des Satzes von Fehlerkorrekturcodes anzeigt,

einer Fehlerkorrektureinheit (130), die so angeschlossen ist, daß sie die Mehrzahl von Datenbits, das Paritätsbit für jede der Mehrzahl von Gruppierungen, den ersten allgemeinen Fehlerkorrekturcode und den zweiten allgemeinen Fehlerkorrekturcode empfängt, wobei die Fehlerkorrektureinheit dafür ausgelegt ist, ein Paritätsfehlerbit für jede der Mehrzahl von Gruppierungen und der Datenbits zu erzeugen, wenn sie empfangen werden, und wobei die Fehlerkorrektureinheit dafür ausgelegt ist, einen ersten allgemeinen Syndromcode zu erzeugen, und zwar auf der Basis des ersten allgemeinen Fehlerkorrekturcodes, um die Existenz von Doppelbitfehlern an verschiedenen Positionen in irgendeiner aus der Mehrzahl von Gruppierungen festzustellen, wenn eine geradzahlige Gesamtzahl von Paritätsfehlerbits der Mehrzahl von Gruppierungen vorgebracht wird, und wobei die Fehlerkorrektureinheit dafür ausgelegt ist, einen zweiten globalen Syndromcode zu erzeugen, und zwar auf der Basis des zweiten allgemeinen Fehlerkorrekturcodes, um eine Position eines Fehlers festzustellen, wenn eine geradzahlige Gesamtzahl von Paritätsbits aus der Mehrzahl von Gruppierungen vorgebracht wird.

2. System nach Anspruch 1, wobei der erste allgemeine Fehlerkorrekturcode einem "exklusiven ODER" (XOR) des Satzes von Fehlerkorrekturcodes äquivalent ist.

3. System nach Anspruch 2, wobei der erste allgemeine Syndromcode von einem Unterschied zwischen dem ersten allgemeinen Fehlerkorrekturcode und einem neu erzeugten, ersten allgemeinen Fehlerkorrekturcode beruht.

4. System nach Anspruch 3, wobei der zweite globale Syndromcode von einem Unterschied zwischen dem zweiten globalen Fehlerkorrekturcode und einem erneuerten bzw. wiedergewonnenen zweiten globalen Fehlerkorrekturcode abhängt.

5. System nach Anspruch 4, wobei, wenn eine gerade Anzahl von Paritätsfehlerbits aus der Mehrzahl von Gruppierungen gesetzt worden ist, und wenn der erste globale Syndromcode nicht gleich einem vorbestimmten Wert ist, die Fehlerkorrektureinheit so ausgestaltet ist, daß sie in Reaktion darauf ein Fehlersignal erzeugt.

6. System nach Anspruch 5, wobei der vorbestimmte Wert ein nur aus Nullen bestehender Wert ist.

7. System nach Anspruch 6, wobei, wenn eine gerade Gesamtzahl von Paritätsfehlerbits der Mehrzahl von Gruppierungen gesetzt ist und wenn der erste Syndromcode gleich dem aus lauter Nullen bestehenden Wert ist, die Fehlerkorrektureinheit so ausgestaltet ist, daß sie in Reaktion darauf einen Wert eines Reihensyndromcodes benutzt, um eine Position eines Fehlers innerhalb jeder der Mehrzahl von Gruppierungen von Datenbits zu bestimmen, wobei die Fehlerkorrektureinheit dafür ausgelegt ist, den Reihensyndromcode aus dem zweiten allgemeinen Syndromcode abzuleiten.

8. System nach Anspruch 7, wobei, wenn eine ungeradzahlige Gesamtzahl von Paritätsfehlerbits aus der Mehrzahl von Gruppierungen gesetzt ist, die Fehlerkorrektureinheit so ausgestaltet ist, daß sie in Reaktion darauf einen Wert des ersten Syndromcodes benutzt, um die Position eines Fehlers zu bestimmen.

9. System nach Anspruch 1, wobei der erste allgemeine Fehlerkorrekturcode einer vorbestimmten Funktion des Satzes von Fehlerkorrekturcodes äquivalent ist.

10. System nach Anspruch 9, wobei jedes Bit des ersten allgemeinen Fehlerkorrekturcodes einem "ausschließlich ODER" eines vorbestimmten Satzes von Bits aus dem Satz von Fehlerkorrekturcodes äquivalent ist.

11. System nach Anspruch 1, wobei der erste allgemeine Fehlerkorrekturcode durch bitweises Verschieben von zumindest einem Teil der Fehlerkorrekturcodes und durch XOR-Verknüpfung ausgerichteter Bits einer Mehrzahl der sich ergebenden verschobenen Fehlerkorrekturcodes abgeleitet wird.

12. System nach Anspruch 11, wobei die Mehrzahl von Datenbits insgesamt X Gruppierungen enthält und wobei der erste allgemeine Fehlerkorrekturcode abgeleitet wird durch Verschieben des Fehlerkorrekturcodes für eine gegebene i-te Gruppe durch i Bitpositionen, wobei i = 0 bis X - 1, und durch XOR-Verknüpfung einer Mehrzahl von resultierenden verschobenen Fehlerkorrekturcodes gemeinsam.

13. System nach Anspruch 12, wobei der zweite allgemeine Fehlerkorrekturcode abgeleitet wird durch lineares Verschieben des Fehlerkorrekturcodes für die gegebene i-te Gruppe um i Bitpositionen.

14. System nach Anspruch 12, wobei der zweite allgemeine Fehlerkorrekturcode abgeleitet wird durch zyklisches Verschieben des Fehlerkorrekturcodes für die gegebene i-te Gruppe um i Bitpositionen.

15. System nach einem der vorstehenden Ansprüche, wobei die Fehlerkorrektureinheit weiterhin so ausgestaltet ist, daß sie Fehler in irgendeiner der Mehrzahl von Gruppierungen aufgrund des Versagens einer einzelnen Komponente korrigiert.

16. System nach einem der vorstehenden Ansprüche, welches weiterhin eine Komponente (110) aufweist, in welche die Mehrzahl von Datenbits, das Paritätsbit für jede der Mehrzahl von Gruppierungen und die ersten und zweiten allgemeinen Fehlerkorrekturcodes übermittelt werden, bevor sie für die Fehlerkorrektureinheit bereitgestellt werden.

17. System nach Anspruch 16, wobei die Komponente eine Mehrzahl von Speicherchips (110A- 110M) aufweist.

18. System nach Anspruch 16, wobei die Komponente eine Mehrzahl von Kommunikationspfaden aufweist.

19. System nach Anspruch 17, wobei jedes Bit innerhalb einer bestimmten Gruppierung von Datenbits in einem getrennten Speicherchip gespeichert wird, wodurch keine zwei Bits irgendeiner gegebenen Gruppierung innerhalb desselben Speicherchips gespeichert werden.

20. System nach Anspruch 19, wobei Bits an entsprechenden Positionen innerhalb der Mehrzahl von Gruppierungen innerhalb desselben Speicherchips gespeichert werden.

21. System nach einem der vorstehenden Ansprüche, wobei der Fehlerkorrekturcode für jede aus der Mehrzahl von Gruppierungen ein Einzelfehlerkorrektur-Hamming-Code ist.

22. System für das Erfassen und Korrigieren von Datenfehlern, mit:

einer Erzeugungseinheit (120) für Prüfbits, um eine Mehrzahl von Datenbits zu empfangen, wobei die Prüfbit-Erzeugungseinheit so ausgestaltet ist, daß sie ein Paritätsbit erzeugt, welches einer aus einer Mehrzahl von Gruppierungen der Datenbits entspricht, und wobei die Prüfbit-Erzeugungseinheit dafür ausgelegt ist, einen unverdrehten allgemeinen Fehlerkorrekturcode zu erzeugen, der für eine erste Kombination von Fehlerkorrekturcodes kennzeichnend ist, die jeweils individuell einer entsprechenden aus der Mehrzahl von Gruppierungen zugeordnet ist, und wobei die Prüfbit-Erzeugungseinheit so ausgestaltet ist, daß sie einen verdrehten allgemeinen Fehlerkorrekturcode erzeugt, welcher für eine zweite Kombination von Fehlerkorrekturcodes kennzeichnend ist, die jeweils individuell einer entsprechenden aus der Mehrzahl von Gruppierungen zugeordnet ist,

einer Fehlerkorrektureinheit (130), die so angeschlossen ist, daß sie die Mehrzahl von Datenbits, das Paritätsbit für jede der Mehrzahl von Gruppierungen, und die unverdrehten und verdrehten allgemeinen Fehlerkorrekturcodes empfängt, wobei die Fehlerkorrektureinheit dafür ausgelegt ist, ein Paritätsfehlerbit für jede aus der Mehrzahl von Gruppierungen der Datenbits zu erzeugen, so wie sie empfangen wurden, und wobei die Fehlerkorrektureinheit dafür ausgelegt ist, einen unverdrehten allgemeinen Syndromcode zu erzeugen, und zwar auf der Basis des unverdrehten allgemeinen Fehlerkorrekturcodes, um die Existenz von Doppelbitfehlern an unterschiedlichen Positionen in irgendeiner aus der Mehrzahl von Gruppierungen festzustellen, wenn eine gerade Gesamtzahl von Paritätsfehlerbits aus der Mehrzahl von Gruppierungen vorgebracht wird, und wobei die Fehlerkorrektureinheit dafür ausgelegt ist, auf der Basis des verdrehten allgemeinen Fehlerkorrekturcodes einen verdrehten normalen Syndromcode zu erzeugen, um eine Position eines Fehlers zu bestimmen, wenn eine gerade Gesamtzahl von Paritätsbits aus der Mehrzahl von Gruppierungen vorgebracht wird.

23. Verfahren zum Korrigieren von Datenfehlern, mit:

Empfangen einer Mehrzahl von Datenbits,

Erzeugen eines Paritätsbits, welches jeweils einer aus einer Mehrzahl von Gruppierungen der Datenbits entspricht,

Erzeugen eines unverdrehten allgemeinen Fehlerkorrekturcodes, der für eine erste Kombination von Fehlerkorrekturcodes kennzeichnend ist, die jeweils einzeln einer entsprechenden aus der Mehrzahl von Gruppierungen zugeordnet sind,

Erzeugen eines verdrehten allgemeinen Fehlerkorrekturcodes, der kennzeichnend für eine zweite Kombination von Fehlerkorrekturcodes ist, die jeweils einzeln einer entsprechenden aus der Mehrzahl von Gruppierungen zugeordnet ist,

Empfangen der Mehrzahl von Datenbits, des Paritätsbits für jede der Mehrzahl von Gruppen und der unverdrehten und verdrehten allgemeinen Fehlerkorrekturcodes,

Erzeugen eines Paritätsfehlerbits für jede der Mehrzahl von Gruppierungen von Datenbits, wie sie empfangen wurden, und

falls eine gerade Gesamtzahl von Paritätsfehlerbits der Mehrzahl von Gruppierungen gesetzt ist, Erzeugen eines unverdrehten allgemeinen Syndromcodes auf der Basis des unverdrehten allgemeinen Fehlerkorrekturcodes, um die Existenz von Doppelbitfehlern an verschiedenen Positionen in irgendeiner der Mehrzahl von Gruppierungen zu bestimmen, und

falls eine geradzahlige Gesamtzahl von Paritätsfehlerbits der Mehrzahl von Gruppierungen vorgebracht wird, Erzeugen eines verdrehten allgemeinen Syndromcodes auf der Basis des verdrehten allgemeinen Fehlerkorrekturcodes, um eine Position eines Fehlers zu bestimmen.

24. Verfahren nach Anspruch 23, wobei der unverschobene allgemeine Fehlerkorrekturcode einem "ausschließlich ODER" (XOR) der Fehlerkorrekturcodes äquivalent ist.

25. Verfahren nach Anspruch 24, wobei der verschobene allgemeine Fehlerkorrekturcode durch bitweises Verschieben von zumindest einem Teil der Fehlerkorrekturcodes und durch XOR- Verknüpfung ausgerichteter Bits aus einer Mehrzahl von sich ergebenden verschobenen Fehlerkorrekturcodes abgeleitet wird.

26. Verfahren nach Anspruch 25, wobei die Mehrzahl von Datenbits insgesamt X Gruppierungen enthält, und wobei der allgemeine Fehlerkorrekturcode abgeleitet wird durch Verschieben des Fehlerkorrekturcodes für eine gegebene i-te Gruppe durch i Bitpositionen, wobei i = 0 bis X - 1, und weiterhin durch gemeinsame XOR-Verknüpfung einer Mehrzahl von sich ergebenden verschobenen Fehlerkorrekturcodes.

27. Verfahren nach Anspruch 26, welches weiterhin das Erzeugen eines Reihensyndromcodes aufweist, abhängig von dem verdrehten allgemeinen Syndromcode, wenn eine geradzahlige Gesamtzahl von Paritätsfehlerbits gesetzt ist, wobei der Reihensyndromcode ein Wert ist, welcher die Position des Fehlers anzeigt.