DE2260850C2

DE2260850C2 - Schaltungsanordnung zur Erkennung von Einzel- und Mehrfachfehlern und zur korrektur von Einzel- und bestimmten Mehrfachfehlern

Info

Publication number: DE2260850C2
Application number: DE2260850A
Authority: DE
Inventors: Donald Walter Lake Katrine N.Y. Price
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1971-12-14
Filing date: 1972-12-13
Publication date: 1982-06-09
Also published as: GB1366013A; FR2165408A5; US3755779A; JPS4866952A; DE2260850A1; JPS535099B2

Description

d<Ja)i = äUah * dUt)i

auf /Spalten erweitert wurde, wobei

+ a(j,)i ein Element dieses Codes in der Zeile / sowie

d(jb)i Elemente des erweiterten Codes in den beiden Spalten ja, jb eines Bitpaares sind, und #Modulo-2-Addition bedeutet,

und daß gemäß der //-Matrix ein weiteres Prüfbit (CT) als Paritätsbit über alle Daten- und Prüfbits gewonnen wird, so daß ein Bitpaarfehler aus dem Wert CT=O und den Werten des Syndromvektors der zweiten Gruppe der Prüfbits (C 7 bis C12) erkannt und korrigiert werden kann (Tabelle IV).

2. Schaltungsanordnung nach Anspruch 1, dadurch gekennzeichnet, daß beim Vorliegen eines Einzelfehlers ein Teil (CT, CS) der Prüfbits der zweiten Gruppe anzeigt, welches Bit eines Paares fehlerhaft ist

3. Schaltungsanordnung nach Anspruch 1, dadurch gekennzeichnet, daß die erste und die zweite Gruppe von Prüfbits jeweils gleich viele Prüfbits enthalten.

4. Schaltungsanordnung nach Anspruch 1, dadurch gekennzeichnet, daß das erste Bit eines Bitpaares in den numerisch aufeinanderfolgenden Datenbitpositionen (0 bis 63) jeweils aus der unteren Hälfte (d0 bis c/31) und das zweite Bit aus der oberen Hälfte (d 32 bis d 63) der Datenbits stammt

Bis vor kurzem wurde in der Computerindustrie als Hochgeschwindjgkeits-Arbeitsspeicher fast ausschließlich der Magnetkernspeicher verwendet Herstellungsund Prüfverfahren bei einem Kernspeicher sind jetzt so ausgefeilt, daß kaum noch ein Kernspeicher die Produktion verläßt, der nicht hundertprozentig benutzbar ist Der Hauptgrund dafür liegt darin, daß jeder einzelne Magnetkern gesondert geprüft wird, bevor er in den Speicher eingesetzt wird. Daher sind Fehler an einem einzelnen eingebauten Magnetkern ziemlich ungewöhnlich. Die normalerweise auftretenden Fehlerarten betreffen eine ganze Zeile oder Spalte des Speichers und sind gewöhnlich auf beim Betrieb des Speichers auftretende Fehler in der Verdrahtung oder in den Treiberschaltungen zurückzuführen und erfordern eine vollständige Neuherstellung oder einen Ersatz des Speichers.

Die Einführung eines neuen Speichertyps mit hunderten von Datenstellen auf einem einzigen integrierten Halbleitersubstrat brachte jedoch vollkommen verschiedene Problemstellungen mit sich. Bei diesen Speichern ist es praktisch unmöglich, einzelne Transistoren oder Datenstellen während des komplizierten Herstellungsverfahrens schrittweise zu prüfen. Die allgemein benutzten Prüfverfahren werden im letzten Verfahrensschritt angewandt oder sehr häufig auch nach Abschluß der Herstellung. Außerdem ist es nicht möglich, einen fehlerhaften Schaltkreis physikalisch zu entfernen, wenn ein solches Speicherplättchen einmal in Betrieb ist Man muß daher aus Gründen der Herstellungskosten und des Wettbewerbs mit anderen Speicherarten eine bestimmte Anzahl von Datenbitfehlern in einem Plättchen in Kauf nehmen.

Eine Möglichkeit zur Korrektur solcher Fehler besteht in der Verwendung von Fehlerkorrekturcodes wie z. B. dem bekannten Hamming-Code. Bei diesem Verfahren werden einem dem Speicher entnommenen Datenwort zusätzliche Bits hinzugefügt, und durch logisches Kombinieren der Datenbits mit den zusätzlichen oder Prüfbits kann festgestellt werden, ob ein dem Speicher entnommenes Datenwort fehlerhaft ist oder nicht und ob im Fehlerfall der Code den Fehler korrigieren kann.

So ist beispielsweise im USA-Patent 36 4S239 ein Speichersystem beschrieben, bei dem eine Codierung zur Korrektur von Einzelfehlern und zur Erkennung von Doppelfehlern benutzt wird. In der Patentschrift sind die Schaltungen angegeben, die benötigt werden, um die für die Korrektur erforderlichen Syndrombits zu erzeugen.

Die Verwendung von Codes, die es gestatten, Einzelfehler zu korrigieren und Doppelfehler zu erkennen, im folgenden kurz als EFK/DFE-Codes bezeichnet, zur Erhöhung der Zuverlässigkeit des Speichers ist sehr beliebt Diese Erhöhung ist besonders groß, wenn der Speicher so organisiert ist, daß jedes Bit eines Wortes sich auf einem anderen Modul befindet Bei einer solchen Organisation wird der eine große Speicher ersetzt durch eine Anzahl kleiner Unterspeicher, von denen jeder mit einem unabhängigen Satz von Treiber- und Leseschaltungen ausgerüstet ist Jede Speicherzelle für ein gegebenes Codewort (Datenbits und Prüfbits) wird aus einem anderen Basisbetriebsmodul (BBM) ausgewählt Bei einer Organisation von einem Bit pro BBM ist es sehr wahrscheinlich, daß ein Fehler in einer Datenstelle eines Codewortes willkürlich ist und mit den anderen Datenstellen in dem Codewort keinerlei Zusammenhang hat Somit arbeitet ein

konventioneller Hamming-EFK/DFE-Code vollkommen zufriedenstellend.

Nach der neuesten Entwicklung werden beim BBM-Speicher zwei und nicht nur ein Bit pro BBM gespeichert. Das ist besonders vorteilhaft bei großen Speichersystemen, die als Basisbetriebsmoduln HaIbleiterplättchen mit integrierter Schaltung verwenden. Für ein gegebenes Codewort werden bei einem Speicher, bei dem sich 2 Bits auf einem Basisbetriebsmodul befinden, nur die Hälfte der Halbleherplättdien benutzt Außerdem ist die auch auf dem Halbleiterplättchen befindliche Decodierschaltung für einen Speicher mit 2 Bits pro Basisbetriebsmodul weniger komplex.

Diese Verbesserung war jedoch nicht ohne einen entsprechenden Nachteil möglich, weil die Möglichkeit, ι5 nur Einzelfehler zu korrigieren, nicht ausreicht Bei einer Speicherorganisation, bei der sich 2 Bits auf einem Basisbetriebsmodul befinden, ist es sehr wahrscheinlich, daß die defekte Schaltung, die einen Fehler in einem der Bits eines Halbleiterplättchens hervorruft, auch einen Fehler im anderen Bit erzeugt Mit anderen Worten ist es also sehr wahrscheinlich, daß bei Auftreten eines Fehlers er in beiden zusammengehörenden Bits auftritt Außerdem ist es auch wahrscheinlich, daß Einzelfehler willkürlich auftreten, es ist jedoch sehr unwahrscheinlieh, daß willkürliche Doppelfehler auftreten, d. h. Fehler, die im selben Codewort in zwei Bits auftreten, die nicht zusammengehören.

Aus der DE-OS 19 46 365 ist eine Fehlererkennungsund Korrektureinrichtung bekanntgeworden, in der mehrere, zu einem bestimmten Datenblock gehörende Datenbits korrigiert werden können. Dabei wird davon ausgegangen, daß die einzelnen Datenblocks, aus denen sich ein Datenwort zusammensetzt, in zugehörigen Speichermoduln, zusammen mit jeweils einem Prüfbit « gespeichert sind. Für k Datenblocks werden also k Prüfbits erzeugt Zur Erzeugung der Prüfbits werden aus den Datenbits k Untergruppen gebildet, wobei jedes Datenbit in einer Untergruppe nur einmal vorkommt und jedes Datenbit in zwei Untergruppen enthalten ist und wobei keine zwei Untergruppen dasselbe Bitpaar enthalten. Mit Hilfe dieser Codierung kann erkannt werden, ob Fehler vorliegen, die nur auf einen einzigen Datenblock beschränkt sind, und es können die fehlerhaften Datenbits eines einzelnen Blocks korrigiert werden.

Diese Einrichtung hat jedoch den Nachteil, daß die Zahl k eine Primzahl sein muß. Da diese Zahl zugleich die Anzahl Prüfbits und auch die Anzahl der Datenblocks, d. h. die Anzahl von einzelnen Speicher- so moduln, angibt, ist der beschriebene Code praktisch kaum realisierbar, da die Adressierung einer Datenverarbeitungsanlage fast immer auf eine Anzahl von Speichermoduln ausgerichtet ist, welche eine Potenz von 2 ist Beispielsweise könnten nach der bekannten Einrichtung bei der Verwendung von 13 Prüfbits 65 Datenbits vorgesehen werden, doch müßten diese Datenbits auf 13 Speichermoduln verteilt werden, die jeweils fünf Bits des Datenwortes speichern würden. Andererseits könnten bei Verwendung von zwei Datenbits pro Speichermodul insgesamt nur 14 Datenbits vorgesehen werden. Hierfür werden andererseits 7 Prüfbits notwendig. Auch dieser Fall ist also in der Praxis kaum in vorteilhafter Weise realisierbar, da einerseits das Datenwort viel zu kurz und andererseits die Anzahl der Prüfbits unverhältnismäßig hoch wäre.

Der vorUegeftdeirErflniiungTIejit daher dfe Aufgabe zugrunde, in einer Anordnung, der im Oberbegriff des Anspruchs 1 beschriebenen Art unter Verwendung der in den heutigen Datenverarbeitungsanlagen gebräuchlichen Anzahl von Daten- und Prüfbits die Korrektur von Doppelfehlern von zwei zusammengehörigen Datenbits zu ermöglichen.

Diese Aufgabe wird erfindungsgemäß durch die im Kennzeichen des Anspruchs 1 beschriebene Anordnung gelöst

Die Erfindung hat den Vorteil, daß bei verhältnismäßig niedriger Anzahl von Prüfbits nicht nur Einzelfehler erkannt und korrigiert sowie auch Mehrfachfehler erkannt und korrigiert werden können, sondern daß auch fehlerhafte Bitpaare, d. h. zwei fehlerhafte, zusammengehörige Bits korrigiert werden können. Zwischen den beiden Bits eines Paares besteht voi-teilhafterweise ein gewisser Zusammenhang. Beispielsweise können die beiden Bits eines Paares im gleichen Speichermodul gespeichert sein oder von einer gemeinsamen Stromversorgung abhängen.

Mit der Erfindung ist es möglich, unter Beibehaltung der gebräuchlichen Anzahl von 64 Datenbits in einem Datenwort die Anzahl der Prüfbits auf 13 zu beschränken, wobei diese Prüfbits nicht zusammen mit gewissen Datenbitgruppen abgespeichert werden müssen. Vorteilhafterweise werden die 64 Datenbits auf 32 Basisbetriebs-Speichermoduln aufgeteilt, doch sind auch andere Gruppierungen denkbar, wobei allerdings die Erfindung ihre vorteilhafte Wirkung nur voll entfalten kann, wenn eine hohe Wahrscheinlichkeit dafür besteht daß bei fehlerhafter Übertragung eines Bits auch das andere Bit des Bitpaares fehlerhaft ist.

Ein Ausführungsbeispiel der Erfindung ist in der Zeichnung dargestellt und wird anschließend näher beschrieben. Es zeigen

F i g. 1 und 2 ein Blockschaltbild einer Rechenanlage, in welcher die vorliegende Erfindung angewendet wird,

Fig.3 eine Paritätsprüfmatrix für ein (n=77, /=64) Codewort das im Ausführungsbeispiel verwendet wird,

Fig.4 das Schaltbild eines Syndromgenerators für eines der Prüffelder der Paritätsprüfmatrix der F i g. 3,

F i g. 5 in einem Blockschaltbild das Ausführungsbeispiel des in F i g. 1 allgemein gezeigten Syndromdecodierers,

Fig.6 ein Schaltbild der in Fig.5 gezeigten Syndromgruppierungsschaltungen,

F i g. 7 ein Schaltbild der in F i g. 5 gezeigten Decodierschaltungen,

Fig.8 ein Schaltbild der in Fig.5 gezeigten Generatoren für die korrigierten Daten und der in F i g. 1 gezeigten Datenkorrekturschaltungen,

Fig.9 ein Schaltbild der in Fig.5 dargestellten Fehleranzeigelogik und

Fig. 10 und 11 Schaltbilder bestimmter Abschnitte des in F i g. 2 gezeigten Prüfbitgenerators.

Vor der Beschreibung der Figuren wird zunächst die Fehlerkorrektur-Codeanordnung (FKC-Anordnung) der Erfindung allgemein beschrieben. Diese Anordnung korrigiert Einzelfehler, zusammenhängende Doppelfehler und erkennt nichtzusammenhängende Doppelfehler. Die FKC-Anordnung arbeitet mit Daten, die vom Hauptspeicher abgerufen werden und mit Daten, die in den Hauptspeicher gesetzt werden.

Die verwendete FKC-Anordnung arbeitet mit Redundanz. Eine binäre Informationsfolge kann so codiert werden, daß ein Decodierer die ursprüngliche Information aus der Codierfolge mit einem hohen Grad von Zuverlässigkeit wiedergewinnen kann trotz während der Übertragung von und zum Speicher möglicherweise

auftretender Fehler. Diese FKC-Anordnungen benutzen im allgemeinen das Konzept der Paritätsprüfziffer, bei welchem ein Paritätsprüfbit jeder redundanten Informationsgruppe hinzugefügt wird.

Das Prüfbit für jede redundante Gruppe wird systematisch durch Summierung über ausgewählte Datenstellen in der Informationsfolge errechnet, um die Summe der Informations- und Prüfziffern entsprechend einer vorgegebenen Entscheidung gerade (oder ungerade) zu machen. In der Codiersprache erhalten die gewählten Datenstellen einen Elementwert von 1 zugeordnet; die nichtgewählten Stellen erhalten einen Elementwert 0 zugeordnet. Im allgemeinen unterscheiden sich die Datenstellen in einer Redundanzgruppe von den Stellen in jeder anderen Gruppe. 1 >

Auf dem Weg der aus dem Hauptspeicher abgerufenen Daten empfängt die FKC-Anordnung ein aus einem Datenfeld und einem Eingabe-FKC-Feld (Paritätsprüfziffer) bestehendes Codewort. F i g. 1 zeigt diesen Datenweg. Ein Syndromgenerator erzeugt ein Syndrombitfeld aus den codierten Daten und dem FKC, welches genau so groß ist wie das FKC-FeId. Dieses FKC-FeId kann man sich als Syndrom-Fehler-Vektor (SFV) vorstellen, bei dem jede Vektorposition einem erzeugten Syndrombit entspricht. Ein Syndrombit Si ist das Bit, welches aus dem Vergleich eines Prüfbits im Eingabe-FKC-FeId aus dem Hauptspeicher mit einem entsprechenden Prüfbit des FKC-Feldes resultiert, welches in der FKC-Anordnung aus dem Datenfeld erzeugt wurde. Verschiedene auf verschiedenen Code-Wörtern erzeugte SFV-Muster bezeichnen bestimmte Fehlertypen.

Der SFV durchläuft dann verschiedene Decodierbereiche für die Fehlererkennung, Korrektur von Einzelfehlern und zusammenhängenden Doppelfehlern und Erkennung nichtzusammenhängender Doppelfehler. Der Decodierer erzeugt eine Datenkorrekturbitanzeige für jedes Datenbit, welches zu korrigieren ist Eine Fehleranzeigelogik-Einheit im Decodierer erzeugt entweder eine Nachricht »Kein Fehler«, »Korrigierbarer Fehler« oder »Nichtkorrigierbarer Fehler«.

Die Korrekturbitanzeige läuft zusammen mit dem nichtkorrigierten Datenfeld in eine Datenkorrekturschaltung, und das Feld wird korrigiert, wenn ein Korrekturbit erzeugt wurde.

Auf dem Weg zum Hauptspeicher empfängt ein Prüfbitgenerator oder Codierer, der ein Unterabschnitt des FKC-Systems ist das Datenfeld. Nach der Darstellung in Fig.2 werden die Datencodes, das FKC-Prüffeld und die resultierenden Daten und FKC-Prüfbits in den Hauptspeicher zurückgespeichert

Die in F i g. 1 gezeigt? F.echcnanlage verfügt ühpr einen Hochgeschwindigkeits-Hauptspeicher 100, der einen Satz von Basisbetriebsmoduln enthält die als BBM 0, BBM 1 usw. bis BBM 31 bezeichnet sind und Signale erzeugen, welche im Rechner zu benutzende Datenbits darstellen. Der Speicher umfaßt außerdem BBM A... BBM G, die die Prüfbits C1,... C12 und CT speichern, welche im Codiersystem benutzt werden. Im Ausfühningsbeispiel wird berücksichtigt, daß jeder Basisbetriebsmodul, im folgenden kurz als BBM bezeichnet aus einem Halbleiterplättchen besteht welches eine Matrixanordming von Transistor-Flipflops enthält von denen jedes zwei Signale erzeugen kann, die ein O-Bit und ein 1-Bit anzeigen. Solch eine Anordnung ist allgemein bekannt and enthält außerdem Wort- und Bittreiberschaltungen sowie Abfrageverstärker nebst den übrigen Schaltungen, die zu einem solchen

System gehören.

Die Erfindung ist nicht auf die gezeigte Speicherart beschränkt. Der BBM kann eine diskrete Anordnung von Kondensatoren oder Dioden auf Karten enthalten. Außerdem können die Moduln eine Magnetkernanordnung umfassen, wie sie in der US-Patentschrift Nr. 34 36 734 beschrieben ist. Die vorliegende Erfindung ist auch nicht auf einen Speicheraufbau beschränkt in welchem zwei Datenbits aus demselben Modul kommen. Die breiteste Anwendung findet die Erfindung in einem Datensystem, wo ein Datenbit in einer solchen Beziehung zu einem anderen Datenbit in dem Codewort steht, das mit einiger Wahrscheinlichkeit ein Fehler im ersten Datenbit auch einen Fehler im zweiten Datenbit bedeutet

Der Hcchgcschwindigkeitsspeicher !00 in Fig.! wird auf übliche Weise durch den Adressendecodierer 102 in Verbindung mit der übrigen, der Einfachheit halber nicht dargestellten Schaltung adressiert und schreibt entweder Informationsbits an jede Datenstelle in den BBM's oder liest die Information für einen Datenprozessor 120 aus. In F i g. 1 wird der Decodierer zu letzterem Zweck benutzt und die Daten für ein gewähltes Codewort sowie die zugehörigen Prüfbits werden zuerst in das Eingaberegister 103 geladen. Das Eingaberegister erhält die Daten- und Prüfbits in paralleler Form zur Eingabe in das Fehlerkorrektursystem. Die Ausgabe aus dem Register wird in konventioneller Weise durch Taktimpulse bewirkt und die Datenbits und Prüfbits zu diesem Zeitpunkt parallel zum übrigen System übertragen. Die Datenbits 0 bis 63 werden durch das Kabel 104 zum Knotenpunkt 106 übertragen. In bestimmten Abschnitten dieser Beschreibung steht vor den Datenbitzahlen der Klarheit halber der Buchstabe »die So kann z. B. das Datenbit 0 geschrieben werden als d(0), das Datenbit 63 als d(63) usw. Diese Ausdrücke werden abwechselnd benutzt

jetzt wird angenommen, daß Daten- oder Prüfbits Fehler enthalten, die korrigiert und/oder erkannt werden sollen. Bedingt durch die Systemumgebung sind die zusammengehörigen Datenbits 0,32; 1,33;... 31,63 oder die zusammengehörigen Prüfbits CI₁ C2; ...CIl, C12 wahrscheinlich beide fehlerhaft wenn ein Fehler in den Abfrageleitungen, den Bitleitungen oder Treiberschaltungen in den entsprechenden BBM's vorliegt Eine beträchtliche Wahrscheinlichkeit für das Auftreten eines Einzelfehlers in einem der Daten- oder Prüfbits ist ebenfalls gegeben. Die Wahrscheinlichkeit daß Fehler in zwei nichtzusammengehörigen Bits auftreten, z. B. Bit 0 und Bit 34 oder Bit 31 und Bit CIl, ist wesentlich geringer. Somit werden die Einrichtungen der betrachteten Fehlerprüf- und Korrekturanordnung jeden Einzelfehler und jeden zusammengehörigen Doppelfehler korrigieren, der im Codewort auftreten kann. Außerdem erkennt die Anordnung jeden nichtzusammenhängenden Doppelfehler im Codewort

Die Signale von den Stellen 0 bis 63 werden auf dem Kabel 107 zum Syndromgenerator 109 geleitet Signale von den Prüfbitstellen Cl bis CTwerden parallel über das Kabel 105 zum Syndromgenerator geleitet Der Syndromgenerator ist ein Codierer, der das Daten- und Prüfbitfeld verarbeitet und Syndrombits errechnet Im Ausführungsbeispiel ist das Syndrommuster 13 Bits lang, wobei die Bhs mit S1,52... S12 und STnotiert sind.

Die Syndrombits werden über Kabel 110 zum Syndromdecodierer 112 übertragen, welcher anzeigt ob ein Fehler im Codewort vorliegt oder nicht ob der Fehler korrigierbar ist, d. h, ob es ein Einzelfehler oder

ST

ein zusammengehöriger Doppelfehler ist, oder ob der Fehler nicht korrigierbar ist, d. h., ob es ein nichtzusammengehöriger Doppelfehler ist. Wie später noch genauer beschrieben wird, wird all dies abgeleitet von der Feststellung der von dem Syndrombitmuster ^r> gezeigten Symmetrie. Das Syndrommuster liefert auch Anzeigen der verschiedenen Fehlerarten, die im System erkannt werden können. Der Decodierer erzeugt Anzeigen richtiger Bits auf dem Kabel 113, die zur Datenkorrekturschaltung 114 übertragen werden. Die in Datenkorrekturschaltungen enthalten einen Satz von Modulo-2-Addierern, die im wesentlichen die von dem Eingangsregister über das Kabel 108 übertragenen nichtkorrigierten Daten mit den Anzeigen der korrigierten Bits vergleichen. Das Ergebnis am Ausgang der DatenkorrekturschaJtungen ist ein richtiges Datenwort, welches die ersten 64 Bits des Codewortes umfaßt. Die Daten werden dann über das Kabel 116 zum Datenprozessor 120 übertragen.

Wenn der Datenprozessor ein bestimmtes korrigiertes Codewort nicht mehr braucht, sendet er das korrgierte Codewort über das in F i g. 2 gezeigte Kabel 121 zu einem Register 122, welches ähnlich funktioniert wie das Register 103. Das 64 Bit große Datenwort wird über das Kabel 123 zum Knotenpunkt 124 geleitet, wo es sowohl dem BBM 0 bis 31 des Hochgeschwindigkeitsspeichers 100 als auch dem Prüfbitgenerator 128 zugeleitet wird. Der Prüfbitgenerator ist ein die Daten verarbeitender Codierer, welcher die Prüfbits C1 bis CT errechnet, die dann den entsprechenden Positionen in den BBM A bis G zugeleitet werden. Der Eingang zu den Moduln wird durch die Steuerlogik 130 und den in F i g. 1 gezeigten, in F i g. 2 der Klarheit halber weggelassenen Adressendecodierer gesteuert

F i g. 3 zeigt die Anlage einer Paritätsprüfmatrix und den neuartigen Code der Erfindung. Die »//-Matrix«, wie sie allgemein genannt wird, umfaßt η Bits, einen Datenfeldteil des Codewortes und einen Prüf teil. Im vorliegenden Ausführungsbeispiel umfaßt das Datenfeld spy =

64 Bits, d(0) bis </(63) und das Prüffeld 12 Prüfbits, Cl bis Cl2, und ein Gesamtparitätsbit CT. Jedem Bit des Codewortes wird ein Spaltenvektor in H mit der Dimension rx 1 zugeordnet

Die Prüfbits sind den r= 13 Spalten vektoren zugeordnet, die Prüfsyndromspaltenvektoren (PSSV) genannt werden. Diese PSSV Cl bis C12 bilden eine Einheits-Untermatrix (r — 1) χ (r— 1), die in F i g. 3 unter der Oberschrift »Prüfbitsteilen« wiedergegeben ist Die r-te Zeile der Matrix, die Gesamtparitäts-Zeile, enthält nur Einsen. Jede Position in einem PSSV entspricht einer bestimmten Zeile von H. Der einfacheren Notierung halber sind die PSSV-Spaltensteüen C1 bis CT bezeichnet durch ihre entsprechende Zeile i worin 1 </<r=rist

Den Datenfeldbits d(0) bis d(63) des Codewortes werden n—r=l Spaltenvektoren zugeordnet, die Datensyndromspaltenvektoren (DSSV) genannt werden und eine rx / Untennatrix in diesem Tefl von H bilden. Jede Stelle in einem DSSV entspricht ebenfalls einer bestimmten Zeile von H.

Die Syndrombits 51 bis 512 werden nach der folgenden Gleichung erzeugt:

Zeichen 1 in einer gegebenen Zeile / enthält; Ci das Prüfbit für die Zeile ;'; £ die Modulo-2-Summe über der Zeile /'; und ^*die Modulo-2-Summe ist.

Das Syndrombit 51 kann so z. B. errechnet werden durch Modulo-2-Addition über der Zeile 1 der Matrix nach folgendem Muster:

S1 = d(0) Φά{\)Φ d(2) Φ Φ d(7) Φ

·■ Φά(21)Φ

■ Φ </(39) Φ

</(47) Φ rf(48) Φ...

(2)

Bas Syndrombit 57* wird über allen Daten- und Prüfbits erzeugt:

J-o

(3)

Für den Fall, in welchem kein Fehler vorliegt, ist es in der Codierung üblich, das Prüfbit Cl so zu wählen, daß 51 gleich 0 ist, usw. für alle Syndrombits. Somit bezeichnet der Syndromfehlervektor (SFV) der Gleichung 4, wenn er lauter Nullen enthält die fehlerfreie Bedingung für ein Codewort.

51	-0\
52	= 0
53	= 0
54	= 0
55	= 0
56	= 0
57	= 0
58	= 0
59	= 0
510	= 0
511	= 0
512	= 0
ST	= 0

= 0

Die //-Matrix der Fig.3 ist eindeutig, weil sie die folgenden Eigenschaften hat:

1.

Si =

j-o

Jeder Einzelfehler oder zusammenhängende Doppelfehler im Codewort resultiert in einem bestimmten, von 0 verschiedenen SFV, der die Erkennung und Korrektur des Fehlers gestattet

Ein nichtzusammenhängender Doppelfehler resultiert in einem SFV, welcher von O verschiedene Bits an anderen Stellen als der im Absatz 1 erwähnte SFV enthält, läßt sich aber grundsätzlich nicht unterscheiden von einem SFV, welcher aus einem anderen nichtzusammenhängenden Doppelfehler resultiert

(1)

worin </ß), die Datenbitsteile in einer Spalte /ist, die ein Die //-Matrix ist aus den in der nachfolgenden Tabelle I aufgeführten Elementen folgendermaßen aufgebaut:

Tabelle 1

Konstruktion der //-Matrix

Daten-Bitposilionen	Prüfbit- 5	10	, (r-l)X(r-l)	15	1 Xr
	positioner) r	Einheitsmatrix	Matrix
111 111
EFK EFK
Code Code
für 112 Datenbits (wiederholt)
Minimalgewicht-3-Spalten
EFK Code für 1/2 Datenbits -
»verteilt« über Datenbits
Feld für Gesamtparitätsprüfung

Nach der Darstellung in Tabelle 1 umfaßt die //-Matrix:

A) Einen Einzelfehlerkorrektur-Code (EFK-Code), für 1/2 Datenbits im Codewort, der für die andere Hälfte des Codewortes wiederholt wird. Der Ausdruck »Wiederholung« soll hier bedeuten, daß für jede Datenbitsteile im Codewort nur eine andere Datenbitstelle mit demselben DSSV vorhanden ist Diese Bits sind zusammenhängend. Im Ausführungsbeispiel wird nach Darstellung in Tabelle I der EFK-Code gebildet für die ersten 1/2 Datenbits und für die zweiten 1/2 Datenbits wiederholt Diese Form dient nur der graphischen Einfachheit, die zusammenhängenden Bits, dh, die Bits mit demselben DSSV, können natürlich jede Spalte in der Matrix belegen.

B) Einen EFK-Code für die ersten 1/2 Datenbits, dessen Spaltenvektoren das Minimalgewicht 3

haben. Der Code wird dann über das ganze Feld von / Datenbits ausgedehnt. Der Ausdruck »ausdehnen« ist für jedes Matrixelement durch die folgende Gleichung definiert:

//2), = J U)₁

(S)

worin +d(j)j ein Element des Codes mit dem Minimalgewicht 3 für die 1/2 Datenbits (des Originalcodes) ist, d(j)jund d(j+1/2), zusammenhängende Elemente in dem Feld aus / Bits (des erweiterten Codes) abgeleitet von Gleichung (5) sind.

Ein Feld STzur Gesamtparitätsprüfung für die Erkennung nichtzusammengehörender Doppelfehler.

Wiederholter EFK-Code

Die nachfolgende Tabelle II bringt ein Beispiel für einen Einzelfehlerkorrektur-Code nach Art des Hamming-Codes, der sich beim Ausführungsbeispiel der Erfindung bewährte. Dieser Code, als Calvert-Code bekannt hat dieselben Merkmale und fordert im wesentlichen denselben Schaltungsaufwand wie der Hamming-Code. Der Hauptunterschied zwischen dem Hamming-Code und dem Calvert-Code liegt in der Anordnung der Datenbits und Prüfbits. Beim Hamming-Code sind die Prüfbits zwischen den Datenbits angeordnet Mit anderen Worten, entsprechende Bits aufeinanderfolgender Bytes beeinflussen nicht dieselben Prüfbits. Der Calvert-Code nimmt dagegen die Prüfbits aus dem Datenteil des Wortes heraus und ist so angelegt, daß jede aus acht Bits bestehende Gruppe dieselbe generelle Prüfbitkonfiguration aufweist mit geringen Ausnahmen. Es werden sechs Prüfbits benutzt und die gesamten Merkmale zur Fehlererkennung und Korrektur des üblichen EFK-Hamming-Codes werden beibehalten.

Tabelle II Datenbitpositionen

0 12 3 4 5 6 7

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

Prüfbitpositionen Cl Cl C3 C4 C5 C6

Sl 1111111

000000011111111100000000

52 11111111111111110000000000000001

53 00000000000000011111111111111111

54 11110000111100001111000011110001

55 11001100110011001100110011001100

56 10101010101010101010101010101010

Tabelle III Dntenbitpositionen (ä)

0 12 3 4 5 6 7

1	0	0	0	0	0	K)
0	1	0	0	0	0	K)
0	0	1	0	0	0	σ·)
0	0	0	1	0	0	O
0	0	0	0	1	0	OO
0	0	0	0	0	1	(Jl
						O

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 2S 29 30 31

Prüfbitpositionen Cl C2 C3 C4 C5 C6

57 1111111111

111110000000100010111

58 00000001000101111111111111111111

59 11111111000000111111111100010000

510 11110000111101001111000011110001

511 11001101110011001100110111001010

512 10101011 101 1 10101010101010101 100

0
1
0
0
0
0

0 0 1 0 0 0

0 0 0 1 0 0

Jedes Datenbit ist mindestens bei der Berechnung von zwei Prüfbits beteiligt Jeder Einzelbitfehler im Datenteil des Wortes ändert mindestens zwei Prüfbits, die die fehlerhafte Stelle bezeichnen. Für die vorliegende Erfindung können trotz Bevorzugung des Calvert-Codes gegenüber dem Hamming-Code beide oder eine der zahlreichen inzwischen erschienen Varianten benutzt werden.

Aus dem Vergleich der Tabelle II mit der //-Matrix der F i g. 3 ist zu ersehen, daß der EFK-Code der Tabelle II genau der aus den Zeilen S1 bis 56 und den Spalten 0 bis 31 der Fig.3 zusammengesetzten Untermatrix sowie der aus den Zeilen 51 bis 56 und den Spalten 31

SFV =

und somit genau derselbe SFV, der durch das fehlerhafte Bit d(32) erzeugt wird.

Die zweite Eigenschaft ist auf die Tatsache zurückzuführen, daß Fehler in zusammengehörigen Bits sich

SFV =

welches derselbe SFV ist, der für die fehlerfreie Bedingung erzeugt wird.

Bei Kombination mit dem erweiterten Code mit dem Minimalgewicht 3 sind die Eigenschaften des wiederholten Codes sehr nützlich.

Die vorstehende Tabelle III zeigt die Paritätsprüfmatrix für einen EFK-Code mit dem Minimalgewicht 3. Dieser Code ist, soweit bekannt, bisher nicht beschrieben worden und ist daher neu. Sein großer Nutzen liegt nicht in der Einzelfehlerkorrektur allein, da es andere Codes mit weniger oder gleichem Gewicht gibt, die die Einzelfehlerkorrektur in 32 Bits ausführen können. Im vorliegenden Zusammenhang liegt die Bedeutung dieses Codes in seiner Verwendung zusammen mit dem wiederholten EFK-Code, woraus sich ein bedeutender Fortschritt in der Fehlerkorrektur-Codierung ergibt.

Der Ausdruck »Minimalgewicht« ist definiert als die Anzahl der von Null verschiedenen Komponenten in

51	= l\
52	= 1
53	= 0
54	= 1
55	₌ J
*(S6*

bis 63 zusammengestzten Untermatrix entspricht Dieses ist ein wiederholter EFK-Code.

Die wichtigen Eigenschaften dieses wiederholte! EFK-Codes sind: Erstens ist ein Einzelfehler in dei Datenbits erkennbar, aber nicht korrigierbar, um zweitens liefert ein zusammenhängender Doppelfehle unter den Datenbits dasselbe Syndrom wie de fehlerfreie FaIL

Die erste Eigenschaft ist offensichtlich, da der SVF fü die Syndrombits 51 bis 56 derselbe ist, wie für eil gegebenes fehlerhaftes Datenbit und ein zugehöriges Datenbit Der SFV für ein fehlerhaftes Bit rf(O) ist z. B.:

selbst ausnullen in bezug auf den erzeugten SFV, wei der DSSV für die zusammengehörigen Bits derselbe ist Das ist als Beispiel gezeigt für den Fall, in welchen beide Bits d{0) und d{32) fehlerhaft sind:

jeder Spalte einer Paritätsprüfmatrix. So hat ein Codt mit dem Minimalgewicht 3 mindestens drei Einsen ii jeder Matrixspalte. Die Tabelle III zeigt, daß diese Bedingung erfüllt ist Aus den grundlegenden Lehrsät zen der linearen Algebra ist bekannt, daß zahlreich« andere Matrizen mit den Eigenschaften des Codes mi dem Minimalgewicht 3 gefunden werden können. Se kann z. B. der Codevektor einer Spalte gegen dei Codevektor einer anderen vertauscht werden, ohne dal die Eigenschaften des Code verändert werden.

Wie bereits im Zusammenhang mit der Gleichung (5 erklärt wurde, wird der für 1/2 Datenbits ausgelegt' Code mit dem Minimalgewicht 3 erweitert auf / Bits. Ii der //-Matrix der F i g. 3 findet sich der erweiterte Codi

so in der Untermatrix, die die Prüffeldzeile 56 bis 512 um die Datenbitsteilen 0 bis 63 umfaßt. Der Ausdrucl »erweitern« kann in Form einer Matrixadditioi folgendermaßen dargestellt werden:

Sl = l\	Ψ	51 = l^y	=	io\
52 = 1		52= 1		0
53 =0		53 = 0		0
54 = 1		54= 1		0
55 = 1	55 = 1	0
_t56 = l,	1*6=1,	Io j

d (O)₁₂.... </ (3I)₁₂

d (O)₁₂ .

</(32)₇.

</(63)₇

worin + d das Element des Code mit dem Minimalgewicht 3 in Tabelle III und t/das Element im erweiterten Code in der //-Matrix der F i g. 3 bezeichnet. Für jedes

,₂ ....</(63)₁₂

c?-Element sind in Fig.3 zwei d-Elemente vorhandei die die zusammenhängenden Bits sind. Aus der Anwendung der oben gegebenen allgemeii

nen Gleichung (5) lassen sich rf(O)₇ und d(32)j aus 3(O)₇ folgendermaßen errechnen:

rf (O)₇ = rf (O)₇ #rf(32)₇

1 = 1 Φ 0
entsprechend

(9)

rf (O)₈ = rf (O)₈ *
0 = 0 Φ

rf(5)_n = rf(5)„ * i/(37)„
1 = 0 # 1

rf(4)₈ = rf(4)_s # rf (35),
0 = 1 Φ 1

(10)

(H)

(12)

Daraus geht die große Wahlmöglichkeit für die Stellung der Bits in den Zeilen 57 bis 512, basierend auf der Antivalenzfunktion, hervor. Die einzig wichtige Beschränkung liegt in der Stellung der Bits 57 und 58, mit denen Einzelfehler unterschieden werden. Der SFV der Bits 51 bis 56 des wiederholten Code ist bekanntlich für ein gegebenes fehlerhaftes Datenbit und sein zugehöriges Bit derselbe, wodurch die Einzelfehlerkorrektur verhindert wird. Dieser Mangel wird durch Verwendung eines von zwei Syndrombits des erweiterten Codes ausgeglichen, um zwischen einem Fehler in einem Datenbit und seinem zugehörigen Bit zu unterscheiden. Im vorliegenden Ausführungsbeispiel wird mit den Syndrombits 57 und 58 sichergestellt, daß der DSSV eines Datenbits sich in den Stellen 57 und 58

ίο von dem DSSV des zugehörigen Bits unterscheidet Die einfachste Technik ist in F i g. 3 gezeigt Ein 1-Bit wird in die Stellen 57 oder 58 für die Bits 0 bis 31 und ein Bi; 0 in beide Stellen 57 und S 8 für die Bits 32 bis 63 mit Ausnahme von Bit 36 gesetzt Bit 36 hat ein 0-1-Muster in 57 und 58. Die zugehörige Bitstelle 4 hat jedoch ein 1-1-Muster in 57 und 58. Somit ergibt jedes fehlerhafte Datenbit einen eindeutigen DSSV anhand der Syndrombits 5 Ibis 58.
Grundsätzlich besteht die einzige Forderung für die EinzelfehJerkcrrckfor darin, da£ der DSSV eines Sits von dem des zugehörigen Bits verschieden ist Jedes andere der Syndrombits 58 bis 512 kann ebenso verwendet werden.

Die Hauptbedeutung der Erweiterungstechnik liegt in der Tatsache, daß der SFV für einen zugehörigen Doppelfehler in der erweiterten Untermatrix (Zeilen 5 7 bis 512, Spalten 0 bis 63) der //-Matrix derselbe ist wie der SFV eines fehlerhaften Einzelbits in Tabelle III. Daraus folgt z. B.:

30

SFV	rf <0)>
57	= 1
58	= 0
59	= 1
510	= 1
511	= 1
512	= 1

= SFV[rf(0)	n\	Φ rf(32)	0\	]	—	η
=	0		0			0
=	0		1			1
=	0	•p*	1		1
=	0		1		1
=	W		U,
=

Zwischen zusammengehörigen Doppelfehlern im erweiterten Code und Einzelfehlern im ursprünglichen Code mit dem Minimalgewicht 3 besteht somit eine 1 :1-Entsprechung.

Das bedeutet, daß Fehler in zwei zusammengehörigen Bits einen eindeutigen SFV für die Syndrombits 57 bis 512 erzeugen und dadurch einen zusammengehörigen Doppelfehler von einem anderen in den Datenbits unterscheiden.

Mit der Forderung, daß der erweiterte Code ein Minimalgewicht von 3 haben muß, soll eine ausreichende Anzahl von Bits sichergestellt werden, so daß jeder zusammengehörige Doppelfehler ein Syndrommuster erzeugt, welches sich von einem anderen zugehörigen Doppelfehler unterscheidet Im vorliegenden Fall werden 32 mögliche zusammengehörige Doppelfehler in den Datenbits und drei mögliche zusammengehörige Doppelfehler in den Prüfbits (CT, CS; £79, ClO; CIl, C12) eindeutig durch die Syndrommuster von 57 bis 512 bezeichnet.

Ein Code mit einem Minimalgewicht von 2 kann nicht benutzt werden, weil ein nichtzusammengehöriger Fehler in den Prüfbits, z. B. C9, ClI, nicht von einem zusammengehörigen Doppelfehler in den Datenbits zu unterscheiden ist.

Das 57"-Bit wird als Gesamtparitäts-Syndrombit bezeichnet, weil zu seiner Berechnung alle Daten und

anderen Prüfbits herangezogen werden. Wie bereits gesagt wurde, ist der Wert von CT so gewählt worden, daß für den fehlerfreien Fall 5T=0 ist Dieses Bit wird für die Erkennung von Doppelfehlern erzeugt, und seine Eigenschaft geht aus Fig.3 hervor. Für jeden Einzelfehler ist ST=I. Wenn ein Doppelfehler auftritt, heben sich die Fehler gegenseitig auf, und ST=O.

In der vorliegenden FKC-Anordnung dient ST in erster Linie der Erkennung von Fehlern in zwei nichtzusammengehörigen Bits und der Unterscheidung der Syndrommuster eines Einzelfehlers von dem eines nichtzusammengehörigen Doppelfehlers.

Wie bereits gesagt wurde, ist die Bedeutung separater Codes in der vorliegenden FKC-Anordnung begrenzt auf die Funktion, für die diese Codes ursprünglich entwickelt wurden. Als Einzelfehlerkorrektur-Codes sind sowohl der Calvert- als auch der Code mit dem Minimalgewicht 3 nützlich, können aber durch jede Anzahl anderer Codes ersetzt werden, von denen einige in bestimmter Beziehung bequemer sind.

In ähnlicher Weise hat das Gesamtparitätsprüfbit für Doppelfehlererkennung sein Gegenstück im Original-Hamming-Code.

Nur wenn die drei Codes in einer einzigen FKC-Anordnung kombiniert werden, liefern sie das beschriebene wichtige Ergebnis. Die gegenseitige Beziehung der Codes läßt sich aus der nachfolgenden

Tabelle IV entnehmen, die die Syndrommuster (SFV) zeigt, welche durch die verschiedenen möglicherweise auftretenden Fehler erzeugt werden. Die Tabelle IV ist unterteilt in Bedingungen für Fehlerfreiheit, Einzelfehler und Doppelfehler. In dem Fall, in welchem kein

Tabelle IV
Syndrommuster

Fehler auftritt, ist SFV=O. Bei einem Einzelfehler erzeugt jede Datenbitstelle ein eindeutiges Syndrommuster in den Syndrombits 51 bis 58, wenn dieses Bit fehlerhaft ist

Fehlerbedingungen

SFV

51 52 54 55 56 57

59 510 511 512 ST

Kein Fehler
Einzelfehler
Ein Datenbit fehlerhaft

Ein Prüfbit Ci, fehlerhaft
(ausgenommen CT)
Einzelprüfbit CT fehlerhaft

Doppelfehler

Zusammengehörige Datenbits
fehlerhaft

Zusammengehörige Prüfbits
Ci, C(i + 1) fehlerhaft

Fehler in zwei zusammengehörigen Datenbits oder in
einem Daten- und einem
Prüfbit*)

Nichtzusammengehörige Prüfbits Ci, C(/ + m) fehlerhaft
(ausgenommen CT)*)

Prüfbits Ci und CT fehlerhaft*)

0 0

0 0 0

Eindeutige,? Syndrommuster

S; = 1, Alle anderen Syndrombits = 0
Si = 0

0 0 0 • ♦ »unbeachtlich« ■

0 0 0 0 0 Eindeutiges Syndrommuster (Gew. 3)

5/ und S(i + 1) = 1, Alle anderen Syndrombits = 0

Mindestens Ein Syndrombit = I Nicht eindeutiges
Syndrommuster

S/ und S(i + m) = 1, Alle anderen Syndrombits
S/ = 1, Alle anderen Syndrombits = 0

0 0

> 1

*) Für jeden nichtzusammengehörigen Doppelfehler wird ein anderer SFV erzeugt als für irgend einen Einzelfehler oder einen zusammengehörigen Doppelfehler.

Die Syndrombits 59 bis 512 spielen hier keine Rolle, und daher ist in diesem Teil der Tabelle IV der Ausdruck »unbeachtlich« eingesetzt. Dasselbe Syndrom wird bekanntlich erzeugt, wenn ein Einzelfehler in einem der beiden zusammengehörigen Datenbits auftritt Daher müssen die Syndromstellen 57 bis 58 benutzt werden, um anzugeben, welches der beiden zusammengehörigen Bits tatsächlich fehlerhaft ist Das erreicht man leicht dadurch, daß man einfach sicherstellt, daß die Spaltenvektoren in den Stellen 57 und S 8 für jedes Paar zusammengehöriger Bits unterschiedlich sind. Mit einer Ausnahme sind die Spaltenvektoren der Bits 31 bis 63 auf den Syndromstellen S 7 und 58 z. B. 0, wogegen die Vektoren für die Datenbits 0 bis 31 mindestens eine 1 in einer der beiden Vektorpositionen S 7 und 58 enthalten. Daraus ist die erste wichtige gegenseitige Beziehung zwischen dem wiederholten EFK-Code, der die Vektoren 51 bis 56 umfaßt, und dem erweiterten Code zu ersehen, der die Positionen 57 bis 512 umfaßt

Im Zusammenhang mit dem Doppelfehlerabschnitt der Tabelle IV wurde bereits erklärt, daß der SFV der fehlerhaften zusammenhängenden Datenbits für die ersten sechs Syndrompositionen 0 ist Die Syndrombits 5 7 bis 512 zeigen jedoch ein eindeutiges Syndrommuster für jeden zusammengehörigen Doppelfehler, was durch eine 1 :1-Entsprechung zwischen dem Syndrom eines Doppelfehlers im erweiterten Code und dem Syndrom eines Einzelfehlers im ursprünglichen Code mit dem Minimalgewicht 3 sichergestellt ist. Die Bedeutung des wiederholten Codes im Zusammenhang

mit Doppelfehlern läßt sich an der Bedingung des Syndrommusters für zwei fehlerhafte, nicht zusammenhängende Datenbits oder ein fehlerhaftes Daten- und ein Prüfbit ermessen. Die zuletzt genannte Bedingung ergibt mindestens ein Syndrombit in den Positionen S1

so bis 56. Dies steht im Gegensatz zum Nullvektor in diesen Positionen bei fehlerhaften zusammenhängenden Datenbits. Somit ist die Kombination des wiederholten Codes mit dem Code mit dem Minimalgewicht 3 ausschlaggebend für die Korrekturfähigkeit, d.h., das

Erkennen zusammengehöriger Doppelfehler.

Bekanntlich ist jeder zur Korrektur eines 64 Bit großen Datenwortes entwickelte Code sehr komplex, und die Berechnungen, die für ein perfektes Arbeiten des Codes erforderlich sind, sind sehr mühsam. Im

vorliegenden Fall sind diese Berechnungen natürlich noch mühsamer, weil dieser Code drei Fehlerarten erkennen und zwei dieser Arten korrigieren kann, wogegen frühere Codes auf Einzelfehler und Doppelfehlerkorrektur beschränkt waren.

Um das perfekte Arbeiten des Codes in jeder möglichen Situation zu prüfen, wurde ein Rechnerprogramm in der Programmiersprache PL 1 geschrieben und auf einem Rechner programmiert. Der Rechner

behandelte jeden möglichen Einzelfehler, zusammenhängenden Doppelfehler und nichtzusammenhängenden Doppelfehler. Das Ergebnis des Programms zeigt, daß der SFV für jeden nichtzusammenhängenden Doppelfehler vom SFV für jeden korrigierbaren Fehler verschieden ist

Fig.4 zeigt einen Abschnitt des Syndromgenerators 109, der das Daten- und Prüfbitfeld verarbeitet, um Syndrombits S1 bis ST zu erzeugen. Der Abschnitt umfaßt eine baumartige Anordnung von Antivalenzschaltungen 140, 142, 144 und 146, die jede eine Modulo-2-Addition vornehmen. Diese Berechnungstechnik für Syndrombits ist allgemein bekannt und wird daher nicht näher beschrieben.

Zur Erzeugung jedes Syndrombits Si wird ein Prüfbit aus den im Register 103 gespeicherten Daten errechnet und mit Syndromprüfbit bezeichnet und das errechnete Syndromprüfbit mit dem im Register 103 gespeicherten Prüfbit verglichen. Eine Wertdifferenz zwischen diesen beiden Prüfbits ergibt 5/= 1 und zeigt eine Fehlerbedingungan.

Fig.4 zeigt die Berechnung von Syndrombits, in diesem Fall Sl. Wenn angenommen wird, daß das Codewort im Register 103 steht, werden die Antivalenzschaltungen mit jeder Datenstelle verbunden, die zur Berechnung gewählt ist, abhängig von den in Fig.3 gezeigten Stellen in der //-Matrix. Somit werden für das gezeigte Cl-FeId die Antivalenzberechnungen durchgeführt über den Datenbitsteilen 0 bis 7,15 bis 23,32 bis 39,47 bis 55 durch die Schaltungen 140,142 und 144. Das so aus den Daten bestimmte Syndromprüfbit wird in dsr Schaltung 146 mit dem Bit in der Prüfbitstelle CX verglichen und ergibt eine Anzeige für 51. Eine ähnliche Berechnung wird für jedes der Prüfbitfelder Cl bis CT durchgeführt. Das Syndrombit ST ist ein Ergebnis der Antivalenzberechnung über jeder Datenbit- und Prüfbitstelle in der //-Matrix. In einem betriebsfähigen System können außerdem die zu bestimmten Datenbitstellen gehörenden Antivalenzschaltungen zur Berechnung anderer Syndrombits benutzt werden, die über denselben Bitstellen errechnet werden.

Die im Syndromgenerator 109 codierten Syndrombits 51 bis Srwerden nach Darstellung in Fig. 1 über ein Kabel 110 an einen Syndromdecodierer 112 übertragen. Fig.5 zeigt die Komponentenschaltungen des Syndromdecodierers 112. Wie das bei Fehlerkorrektursystemen der Fall ist, zeigt das von dem Syndromgenerator erzeugte Syndrommuster (SFV) durch Vergleich der Datenbits mit den Prüfbits im Generator 109 nn, ob ein Fehler in den Daten- oder Prüfbits vorhanden ist Wenn alle Bits des 13 Bit großen SFV Null sind, liegt kein Fehler in dem vom Speicher erhaltenen Codewort vor. Ein oder mehrere Einerbits, im Syndrommuster bezeichnen die verschiedenen Fehlertypen, die auftreten können und durch das vorliegende Korrektu/system erkannt und/oder korrigiert werden können.

Der Decodierer 112 übernimmt drei Grundfunktionen. Zuerst liefert er die Einzelkennzeichnung eines jeden möglichen Einzel- und zusammenhängenden Doppelfehlers. Zweitens liefert er Korrekturanzeigen an die Datenkorrekturschaltungen und drittens enthält er eine Fehleranzeigelogik, die eine externe Anzeige der Fehlerbedingungen liefert Der Decodierer enthält einen Umsetzer 150, einen Satz von Syndromgruppierschaltungen 156, Decodierschaltungen 158, Generateren 164 für korrigierte Daten und eine Fehleranzeigelogik 166. Das vom Generator 109 empfangene Syndrommuster wird dem Umsetzer 150 zugeleitet, der jedes Syndrombit in seine echte und in seine Komplementärform umsetzt Somit werden die 13 echten Syndrombits 5^52, ..., STumgesetzt in 26 Ausgangssignale S\, Sl, S2,~S~2, ..., ST, ST. Neben dieser Urnsetzungsfunktion enthält der Umsetzer 150 auch Verstärker für jedes der Eingangssignale, um den übrigen Schaltungen ausreichend starke Signale liefern zu können.

Die echten und komplementären Syndrombits werden über das Kabel 151 zum Knotenpunkt 152

übertragen, wo die echten Syndrombits Sl, S 2 ST

über das Kabel 153 und die Verbindung 165 zur Fehleranzeigelogik 166 übertragen werden. Diese wird später im Zusammenhang mit F i g. 9 genauer beschrieben. Die echten und komplementären Snydrombits mit Ausnahme der Bits ST und ST werden zu den Syndromgruppierungsschaltungen 156 übertragen, die aus einem Satz von 48 UND-Gliedern bestehen und in Fig.6 im einzelnen gezeigt sind. Die Gruppierungsschaltungen sammeln Sätze von vier Syndrombits und liefern eine Ausgabeanzeige jeder möglichen logischen Kombination der gruppierten Bits. Die Ausgänge der Gruppierungsschaltungen «nd also 51 -S2-53-S4, Sl · S2 · S3 · S4, Sl · 52 · 53 ■ 54 usw. für diese Gruppe von Syndrombits. Ähnliche Ausgänge sind vorgesehen für die Bitgruppen 55, 56, 57, 58 und 59, 510,511,512.

Die 48 Ausgangssignale werden durch das Kabel 157 zu den Decodierschaltungen 158 übertragen, welche dann einzelne Ausgangssignale K für jedes einen Einzelfehler oder einen zusammengehörigen Doppelfehler oder einen Prüfbitfehler bezeichnende Syndrommuster erzeugen. Im vorliegenden Ausführungsbeispiel sind 115 derartige Ausgänge vorhanden, die 64 mögliche Einzeldatenfehler, 13 mögliche Einzelprüfbitfehler, 32 mögliche zusammenhängende Datenfehler und sechs mögliche zusammenhängende Prüfbitfehler anzeigen.

Die Ausgangssignale der Decodierschaltungen 158 werden über das Kabel 159 dem Knotenpunkt 160 zugeleitet, von wo sie der Fehleranzeigelogik 166 und den Generatoren für korrgierte Daten 164 zugeführt werden. Die Generatoren verarbeiten die Ausgangssignale der Decodierschaltungen 158 und erzeugen Anzeigen bezüglich der zu korrigierenden Datenbits. Diese Anzeigen werden dann den Datenkorrekturschaltungen 114 (F i g. 1) zugeführt zur Erzeugung korrigierter Datenbits, die im Hochgeschwindigkeitsprozessor 120 verwendet werden.

Fig.6 zeigt die Syndromgruppierungsschaltungen 156 im einzelnen, die einen Abschnitt des Syndromdecodierers 112 bilden. Diese Schaltungen bestehen aus einer Reihe von UND-Gliedern 168, von denen jedes ein Ausgangssignal liefert, wenn alle Eingangssignale des UND-Gliedes den Binärwert 1 aufweisen. Diese 48 UND-Glieder liefern jede mögliche_Kombination der UNDjfunktion für die Sätze (Sl, 51, 52, 52, 53, S3, 54, 54), (S5, S3,56, S^, S7, 57, SS, 58)und (59,39, SlO₁ SlQ, 511, STT, 512, 5Ί2> Diese Gruppierungsschaltungen dienen lediglich der einfachen Realisierung des Decodierers. Vom Standpunkt der für die Erfindung unerläßlichen Schaltungen sind sie nicht erforderlich.

Fig.7 zeigt die Decodiererschaltungen 158 des Syndromdecodierers 112. Die gruppierten Syndromanzeigen der Gruppierungsschaltungen 156 sind vom Verbiiidungsblock 170 an einen Satz von UND-Gliedern 172 verteilt Zu den Eingangssignalen für die UND-Glieder gehört auch das vom Umsetzer 150 über die Leitungen 155 empfangene Syndrombit 57! Jedes

UND-Glied 172 liefert ein Ausgangssignal K, welches ein einzelnes Syndrommusterbit zeichnet. Jedes Syndrommuster entspricht einem Syndromfehlervektor (SFV), der einen korrigierbaren Fehler eindeutig beschreibt. Die Ausgänge der UND-Glieder 200 bis 263 sind bezeichnet mit Kd(O), K-d(\), ■ · ■, Kd Ausgangssignal von einem dieser UND-Glieder besagt, daß der SFA eines entsprechenden Datenbits aufgetreten ist un< markiert dadurch das Bit als fehlerhaft. Ein Ausgangs signal vom UND-Glied 200 besagt z. B, daß folgend Funktion aufgetreten ist:

K_d(0) = Sl -52 -SZ -SA -55 -56 -57 -58 -59 -510-511 -512 -57".

(14)

Diese Funktion entspricht natürlich dem Datensyndrom-Spaltenvektor (DSSV), der in Fig.3 für das Datenbit 0 gezeigt ist.

Dieselbe Überlegung gilt für die Anzeiger K_C\, K_C7,

ίο .... Herder UND-Glieder 264 bis 276. Ein Ausgangssi gnal vom UND-Glied 264 zeigt z. B. einen Fehler in C an, weil die Eingabefunktion folgende ist:

K_C] = Sl -52 SZ -54 -55 -56 -57 -58 -59 -510-511 -512 · ST.

(15)

Aus einem Vergleich mit F i g. 3 ist zu ersehen, daß diese Funktion dem DSSV von C1 entspricht

Eine weitere Beschreibung der Fehleranzeigen für die Einzelfehler erscheint überflüssig, da die Eingangsfunktion zu jedem der UND-Glieder 200 bis 276 dem DSSV der Daten- und Prüfbits der F i g. 3 in entsprechender Reihenfolge entspricht

Der SFV für die zusammengehörenden Doppelfehler wird in den UND-Gliedern 277 bis 314 decodiert Die Ableitung des SFV für die Doppelfehler ist nicht ganz so offensichtlich wie für die Einzelfehler, und Tabelle V zeigt den SFV für jeden möglichen zusammenhängenden Doppelfehler für die Datenbits und die Prüfbits, di< zu dem UND-Glied gehören, welches die jeweilig' Funktion erzeugt.

Die in Tabelle V gezeigten Muster sind ausführliche dargestellt als in den vorhergehenden Tabellen fü zusammenhängende Doppelfehler. Es sind jedocl dieselben Muster; der wiederholte EFK-Code stellt ζ. Β sicher, daß der SFV für die Bits 51 bis 56-0 ist fü zusammengehörende Doppelfehler gemäß Tabelle V. Ii ähnlicher Weise gilt ST=O für zusammengehörend Doppelfehler.

Tabelle V	UND-	Eingabe SFV	S2	Funktion	SA	SS	S6	S7	S8	S9	SlO	SIl	S12	sr
Ausgabe-	Glied		0		0	0	0	1	0	1	1	1	1	0
Anzeige		SI	0	S3	0	0	0	1	0	1	1	1	0	0
	277	0	0	0	0	0	0	1	0	1	1	0	1	0
Kd (0,32)	278	0	0	0	0	0	0	1	0	1	1	0	0	0
^Kd (1,33)	279	0	0	0	0	0	0	1	0	1	0	1	1	0
Kd (2,34)	280	0	0	0	0	0	0	1	0	1	0	1	0	0
^Kd (3,35)	281	0	0	0	0	0	0	1	0	1	0	0	1	0
^d (4,36)	282	0	0	0	0	0	0	1	1	1	0	1	1	0
^d (5,37)	283	0	0	0	0	0	0	1	0	0	1	1	1	0
^d (6,38)	284	0	0	0	0	0	0	1	0	0	1	1	0	0
^d (7,39)	285	0	0	0	0	0	0	1	0	0	1	0	1	0
^d (8,40)	286	0	0	0	0	0	0	1	1	0	1	0	1	0
^Kd (9,41)	287	0	0	0	0	0	0	1	0	0	0	1	1	0
-^d (10.42)	288	0	0	0	0	0	0	1	1	0	1	1	0	0
■^d (11,43)	289	0	0	0	0	0	0	1	1	1	0	0	1	0
*<f(12.44)	290	0	0	0	0	0	0	1	1	1	0	0	0	0
Ad(13,45)	291	0	0	0	0	0	0	0	1	1	1	1	1	0
Kd (14,46)	292	0	0	0	0	0	0	0	1	1	1	1	0	0
Kd (15,47)	293	0	0	0	0	0	0	0	1	1	1	0	1	0
^d (16,48)	294	0	0	0	0	0	0	0	1	1	1	0	0	0
^d (17,49)	295	0	0	0	0	0	0	0	1	1	0	1	1	0
^d (1840)	296	0	0	0	0	0	0	0	1	1	0	1	0	0
^(1941)	297	0	0	0	0	0	0	0	1	1	0	0	1	0
Kd (2042)	298	0	0	0	0	0	0	1	1	1	0	1	0	0
^i (2143)	299	0	0	0	0	0	0	0	1	0	1	1	1	0
^d (2244)	300	0	0	0	0	0	0	0	1	0	1	1	0	0
^d Q3 <5)	301	0		0
^dC446)	302	0		0
Λ.ΑΓ1Ζ <"7Λ

	UND-	23	52	22	Funktion	S4	60	850	S7 SS	59	24	SlO	SIl	S12	sr
	Glied		0			0			0	0		1	0	1	0
Fortsetzung			0		S3	0			1	1		1	0	0	0
Ausgabe-	303		0	0	0			0	0		0	1	1	0
Anzeige	304		0	0	0			1	0	0	0	1	0
	305	Eingabe SFV	0	0	0	S5	S6	1	0	0	0	1	0
^</(26,58)	306		0	0	0	0	0	1	0	1	0	0	0
Ktiin.59)	307	Sl	1	0	0	0	0	0 (	0	0	0	0	0
K<1 (28,60)	308	0	Q	0	1	0	0	0 (	0	0	0	0	0
K-d (29,61)	309	0	0	0	0	0	0	0 (	0	0	0	0	0
"w/(30.62)	310	0	0	!	0	0	0	1	0	0	0	0	0
^d (31,63)	311	0	0	0	0	0	0	0 (	1	1	0	0	0
Kc\.C2	312	0	0	0	0	0	0	0 (	0	0	1	1	0
^C5, C4	313	0		0	0	0
^CS, C6	314	1		0	1	1
^C7, Γ8		η			0	0
^C9. ClO	0	0	0
^fIl, C12	0	0	0
	0
	0		)
			)
	)
	I
	)
	)

F i g. 8 zeigt die Generatoren für korrigierte Daten 164 des Syndromdecodierers 112 und die Datenkorrekturschaltungen 114 des EKC-Systems. Die Generatoren für korrigierte Daten erzeugen eine richtige Bitanzeige aufgrund der Fehlersignale K von den Decodierschaltungen 158. Zu diesem Zweck enthalten die Generatoren eine Reihe von ODER-Gliedern 174, wobei jedem dieser Glieder 0 bis 63 eine entsprechende Datenbitstel-Ie 0 bis 63 zugeordnet ist Jedes ODER-Glied erzeugt ein Ausgangssignal, wenn die Decodierschaltungen anzeigen, daß ein Einzelfehler in der entsprechenden Bitstelle oder Fehler in dieser Bitstelle und der zugehörigen Bitstelle aufgetreten sind. So erzeugt z. B. das ODER-Glied 0 eine richtige Bitanzeige, wenn entweder Kd(O) oder Kd(o,22) vorhanden ist Ein Ausgangssignal vom ODER-Glied 0 bedeutet, daß die Datenbitposition 0 fehlerhaft ist und geändert werden muß. Wenn umgekehrt Kd (0.32) vorhanden ist, würden sowohl das ODER-Glied 0 als auch das ODER-Glied 32 Anzeigen für die Korrektur der Bits in den Stellen 0 und 32 liefern.

Zur Erzeugung der korrigierten Datenbits, die im Datenprozessor 120 verwendet werden können, werden die nicht korrigierten Daten vom Eingangsregister des Hauptspeichers 100 mit den Anzeigen für zu korrigierende Bits in der Datenkorrekturschaltung 114 verglichen. Diese Schaltungen sind Antivalenzschaltungen 176, eine für jedes Datenbit, und verändern die nicht korrigierten Daten, wenn das Eingangssignal vom entsprechenden ODER-Glied des Datengenerators 1 ist Dies ist in Tabelle VI gezeigt

Tabelle VI

Eingabe vom	Eingabe	Ausgabe
ODER-Glied	nicht kor	korrigierter
	rigierter	Daten
	Daten

Fehleranzeige

Anzeige
kein Fehler

1
0
1
0

0
1

1
0

Wenn z. B. das Ausgangssignal des ODER-Gliedes 0 eine 1 ist, wird dadurch ein Fehler in der Stelle d (0) bezeichnet und das Ausgangssignal des Antivalenzgliedes 0 ist immer die Inversion des Signals auf der Leitung t/(0) der nicht korrigierten Daten.

Fig.9 zeigt die Fehleranzeigelogik 166, die den möglichen Zustand eines Codewortes anzeigenden Signale erzeugt Das vom Umsetzer 150 (Fig.5) stammende Syndrommuster Sl bis ST ist das Eingangssignal für den ODER-Funktionsblock 180. Der ODER-Block stellt eine baumartige Anordnung von ODER-Schaltungen dar, die ein Eins-Ausgangssignal liefert, wenn ein Syndrombit 1 ist und dadurch eine Fehlerbedingung anzeigt Wenn das Syndrommuster 0 ist ist das Ausgangssignal des ODER-Blocks 180 eine 0. Das 0-Signal wird durch den Inverter 181 invertiert zur Abgabe eines Signals »Kein Fehler«.

Ein Fehlersignal vom Block 180 wird über die Leitung 190 zum UND-Glied 189 übertragea Das andere Eingangssignal für das UND-Glied kommt vom ODER-Glied 184 über den Inverter 185. Dem ODER-Glied 184 wird ein Signal von einem der ODER-Funktionsblocks 182 oder 183 zugeführt Die Eingangssignale zum ODER-Block 182 umfassen die Anzeigen für korrigierbare Doppelfehler Kdtp.32), ■·-, Ken, C12, die von den Decodierschaltungen 158 über das Kabel 159 übertragen werden (Fig.5). In ähnlicher Weise gehören zu den Eingangssignalen des ODER-Blocks 183 die Anzeigen korrigierbarer Einzelfehler Kd(O), ■■-, K(CT). Ein Ausgangssignal des Blocks 183 ist eine Anzeige eines korrigierbaren Einzelfehlers; ein Ausgangssignal vom Block 182 ist eine Anzeige für einen korrigierbaren zusammenhängenden Doppelfehler.

Wenn das Ausgangssignal des ODER-Gliedes 184 eine 0 ist, wird damit angezeigt, daß keine korrigierbaren Fehler vorliegen, und dann ist das Ausgangssignal des Inverters 185 eine 1 und wird über die Leitung 191 an das UND-Glied 189 weitergeleitet Dieses liefert die Anzeige »Nicht korrigierbarer Fehler«, wenn ein Fehlersignal des Blocks 180 mit einem Signal vom Inverter 185 für einen nicht korrigierbaren Fehler zusammentrifft

Die Fig. 10 und 11 zeigen ein Ausführungsbeispiel der in Fig.2 in Blockform gezeigten Abschnitte des Prüfbitgenerators. Der Prüfbitgenerator ist ein Codierer, der dem in F i g. 4 gezeigten Syndromgenerator sehr ähnlich ist Die Prüfbits werden durch Antivalenzver-

den

10

15

knüpfung der Datenbitpositionen für das durch Code festgelegte jeweilige Prüfbitfeld erzeugt.

Fig. 10 zeigt das Feld Cl, welches in der //-Matrix der F i g. 3 erschien. Die Antivalenzglieder 186,187 und 188, die im Block 128 gezeigt sind, haben dieselbe Funktion wie die Antivalenzglieder in Fig.4. Das Prüfbit C1 steht in seinem zugehörigen BBM A.

F i g. 11 zeigt die zur Berechnung des Gesamtparitätsprüfbits CTerforderliche Schaltung. Das Syndrombit ST wird bekanntlich im Syndromgenerator 109 aus allen Daten- und Prüfbits errechnet. Auf den ersten Blick kann man den Eindruck gewinnen, daß CT genauso im Prüfbitgenerator 128 errechnet werden sollte, d. h., durch Berechnung aus allen Daten- und Prüfbitstellen im Register 122. Das ist jedoch unnötig. Es kann gezeigt werden, daß die Berechnung von CT aus allen Daten- und Prüfbits das logische Äquivalent für die Berechnung aus nur bestimmten Datenpositionen darstellt, um so jedem DSSV in der //-Matrix ein ungerades Gewicht zu verleihen. Daher ist CTein Paritätsbit für ein ungerades Spaltengewicht und seine Benutzung verbessert die Codiergeschwindigkeit und reduziert die Schaltungsanforderungen.

Aus einer Betrachtung der //-Matrix der F i g. 3 geht bei Ignorieren der Zeile ST hervor, daß die Vektoren der Spalten 0 und 2 ungerade bzw. gerade sind. Bei der Berechnung von CT wird nun die Datenbitsteile 0 nicht benutzt, aber die Datenbitsteile 2. Die Prüfbitpositionen werden überhaupt nicht benutzt

Für den speziellen, in F i g. 3 gezeigten Code wird CT folgendermaßen berechnet:

CT

dQ.) </(3) Φ d(5) Φ d{l) Φ </(8) Φ d(9) Φ </(13) Φ rf(18) Φ d(\9) Φ d(20) Φ d(2l) Φ rf(24) Φ d(25) Φ d(27) Φ d(29) Φ d(32) Φ

rf{34) Φ rf(38) Φ dQ9) Φ rf (40) Φ d(42) Φ rf(44) φ rf(45) φ rf(47) Φ d(48) Φ d(50) Φ d{52) Φ rf(54) Φ rf(56) Φ d(58) Φ d(59) Φ

(16)

40

ST kann auf diese Weise jedoch nicht zuverlässig berechnet werden, weil ein oder beide vom Speicher 100 dem Syndromgenerator zugeführte Prüfbits fehlerhaft sein können. Somit muß ST aus allen Daten- und Prüf bits errechnet werden.

Die in F i g. 11 gezeigte Schaltung funktioniert ähnlich wie die in Fig. 10 gezeigte. Die aus den Schaltungen so 193,194 und 195 bestehende Schaltung aus Antivalenz-Gliedern im Generator 128 führt eine Modulo-2-Addition mit den in gemäß der Gleichung (12) ausgewählten Stellen des Registers 122 gespeicherten Daten aus. Das Ausgabebit CTwird dann im BBM G des Speichers 100 "55 gespeichert

Zur Erklärung der Arbeitsweise der erfindungsgemäßen FKC-Anordnung wird zuerst angenommen, daß die Datenbits und Prüfbits in den richtigen Stellen im Speicher 100 gespeichert sind Die Prüfbits wurden eo durch den Prüfbitgenerator 128 in Fig.2 nach dem erfindungsgemäßen Code erzeugt und in die entsprechenden BBM gesetzt. Zu diesem Zeitpunkt können bestimmte Daten- oder Prüfbits fehlerhaft in den Speicher eingeschrieben sein, oder beim Auslesen des Codewortes aus dem Speicher können infolge eines Schaltungsdefektes die Bits fehlerhaft werden. Zu Illustrationszwecken wird weiter angenommen, daß die Daten in den Bitstellen 0 und 32 aufgrund irgendeines Fehlers zur Zeit ihrer Eingabe in das Eingaberegister 103 invertiert wurden. Die Daten werden aus dem Register in den Syndromgenerator 109 zusammen mit den Prüfbits übertragen. Die Syndrombits werden erzeugt durch Vergleich der von den BBM-Stellen empfangenen Prüfbits mit den aus den Datenbits abgeleiteten Prüfbits. Da die zusammengehörigen Bits 0 und 32 fehlerhaft sind, ergibt sich folgendes Syndrommuster (SFV):

20

25 SFV =

35

'51	= (T
52	= 0
53	= 0
54	= 0
55	= 0
56	= 0
57	= 1
58	= 0
59	= 1
510	= 1
511	= 1
512	= 1
ST	= 0,

(17)

Dieses Muster ist gemäß den obigen genaueren Ausführungen eindeutig für einen in den Datenbitsteilen 0 und 32 gespeicherten Doppelfehler. Dieses Syndrommuster wird vom Syndromgenerator 109 zum Syndromdecodierer 112 übertragen, der ein, diesen speziellen zusammengehörigen Doppelfehler bezeichnendes Ausgangssignal in dem Kabel 113 erzeugt, welches zu den Datenkorrekturschaltungen 114 führt, sowie ein Signal »Korrgierbarer Fehler« auf den Fehleranzeigeleitungen. In diesem speziellen Fall invertieren die Antivalenz-Glieder 0 und 32 in der Datenkorrekturschalcung 114 die Signalanzeige der nicht korrigierten Daten in den Datenstellen 0 und 32. Am Ausgang der Datenkorrekturschaltungen 114 erscheinen 64 Signale, die die richtigen Daten in jeder Datenspeichersteils im Speicher anzeigen. Diese korrigierten Daten können dann zuverlässig durch den Prozessor 120 benutzt werden.

Nachdem der Prozessor die Daten gemäß Fig.2 benutzt hat, werden sie fiber das Register 122 an den Prüfbitgenerator 128 zurückgeleitet, wo neue Prüfbits errechnet werden. Die Daten und die neu errechneten Prüfbits werden dann in dem Hauptspeicher 100 gespeichert.

Hierzu 8 Blatt Zeichnungen

Claims

Patentansprüche:

1. Schaltungsanordnung zur Erkennung von Einzel- und Mehrfachfehlern und zur Korrektur von Einzel- und bestimmten Mehrfachfehlern in einer aus einem aus mehreren Basisbetriebsmoduln bestehenden Speicher entnommenen Bitfolge mit einem eine Codiermatrix ^//-Matrix) zur Erzeugung von r redundanten Prüfbits zu den zu speichernden 7 Datenbits enthaltenden Prüf bitgenerator, mit einem ι ο Syndromgenerator zur nochmaligen Erzeugung von Prüfbits zu den entnommenen Datenbits mit Hilfe der gleichen //-Matrix und zum Vergleich der gespeicherten mit den nochmalig erzeugten Prüfbits zur Erzeugung von Syndrombits und mit einem Syndromdecodierer zur Steuerung einer Datenbitkorrekturschaltung aufgrund der. erzeugton Syndrombits, dadurch gekennzeichnet, daß die /Datenbits den /Spalten der //-Matrix (F i g. 3) in zwei Hälften zugeführt werden, daß für eine erste Gruppe von Prüfbits (Ci bis C6, obere Hälfte von F i g. 3) die //-Matrix nach einem Einzelfehlerkorrekturcode (EFK-Code) aufgebaut ist, wobei es für jedes Datenbit der ersten Hälfte (z. B. dÖ) ein und nur ein Datenbit (W 32) in der zweiten Hälfte gibt (»Bitpaar«), das den gleichen Spaltenvektor aufweist,

daß für eine zweite Gruppe von Prüfbits (C 7 bis C12, untere Hälfte von Fig.3 mit Ausnahme der Zeile ST) die //-Matrix nach einem Code aufgebaut ist, der aus einem beliebigen, für 1/2 Spalten definierten EFK-Code mit einem Minimalgewicht von Drei (Tabelle III) durch die Erweiterungsbeziehung