DE2357233A1

DE2357233A1 - Adressenumwandlungseinrichtung

Info

Publication number: DE2357233A1
Application number: DE2357233A
Authority: DE
Inventors: Douglas Craig Bossen; Connor Francis Haugh; Mu-Yue Hsiao
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1972-12-18
Filing date: 1973-11-16
Publication date: 1974-06-20
Also published as: CA1002663A; FR2210793B1; JPS5230336B2; DE2357233C2; IT999371B; FR2210793A1; US3812336A; JPS4991131A; GB1400650A

Description

Böblingen, den 14. November 1973 Iw-sn

Anmelderin: International Business Machines

Corporation,, Armonk/ N.Y. 10504

Amtliches Aktenzeichen? Heoanmeldung Aktenzeichen der Anmelderins PO 972 031

Adressenumwandlungseinrichtung

Die Erfindung betrifft eine Adressenurnwandlungseinrichtimg für einen Speicher, in dem für jede Bitposition eines Wortes eine Speichermatrix vorgesehen ist, weiche von einem Ädressende= / codierer angesteuert wird»

Der Zweck einer solchen Adressemuwandlungseinrichtung besteht darin, angebotene Speicheradressen derart umzuwandeln? daß Speicherworte mit unkorrigierbaren Fehlern in solche mit korrigierbaren Fehlern umgewandelt werden,

Fehlerfeststellungs= und Korrigiereinrichtungen sur Codierung von Daten sind allgemein bekannt» Eine solche Einrichtung kann mehr Fehler feststellen;, als sie korrigieren kann» Für ä®n Fall eines 54 Bit Datenwortes z_oB» kann mit 8 Prüfbits erreicht werden, daß ein einseiner Fehler korrigiert uad ein Doppel= fehler festgestellt werden kann« Die Stelle des einzelnen korrigierbaren Bits kann dabei willkürlich in dem 72-Bitwort liegen» Mit. den 8 Prüf bits 'kann somit die fehlerhafte Bitstelle identifiziert, und der korrekte Wert des Bits angegeben werden» Falls zwei Bits fehlerhaft sind;, kann ein solcher Fehler wohl angezeigt aber die Stelle der fehlerhaften Bits jedoch nicht, identifiziert werden» Die beiden Bits können- somit auch nicht im allgemeinen Falle korrigiert werden»

Es sind Einfachfehler-Korrigiercode bekannt geworden, mit denen auch bestimmte Arten von Mehrfachfehlern, wie z.B. Fehler in benachbarten Bitpositionen, korrigiert werden können. In bestimmten Situationen können solche Code von großem Wert sein, . jedoch stellen sie kein allgemein gültiges Lösungsmittel zur Fehlerkorrektur dar.

In der US PS 3 644 902 wird eine Einrichtung beschrieben, die es gestattet, Fehler, welche wohl feststellbar aber nicht korrigierbar sind, in Fehler umzuwandeln, welche sowohl feststellbar als auch korrigierbar sind. Die Einrichtung macht dabei Gebrauch von der bekannten Eigenschaft von Fehlerkorrektureinrichtungen, mehr Fehler feststellen als korrigieren zu können. Der Speicher in dieser Patentschrift besteht aus einer Anzahl Matrizen, wobei jede dieser Matrizen das Bit einer bestimmten Bitposition der binären Speicherworte speichert. Jede dieser Matrizen wird durch einen eigenen Adreßdecodierer angesteuert. In der bekannten Einrichtung wird vorgeschlagen, zur Vermeidung von Vielfachfehlern, die angebotene Speicheradresse permanent so umzuwandeln, daß Datenbits zwischen Speicherworten durch physikalischen Umtausch von Speichermatrizen ausgetauscht werden. Damit sollen Worte mit unkorrigierbaren Fehlern in Worte mit korrigierbaren Fehlern umgeändert werden. Bei dieser Modifizierung der Spexcheradressen wird jedoch die Kapazität des Speichers eingeschränkt. Da ferner diese Modifizierung permanent erfolgt, ermangelt es dieser Maßnahme an der bisweilen erforderlichen Flexibilität.

Der Erfindung liegt die Aufgabe zugrunde, die Verwendung von Speicherteilen mit schadhaften Bitstellen dadurch zu ermöglichen, daß Bits zwischen den Speicherworten ausgetauscht werden und damit die Bitfehler korrigierbar werden.

Diese Aufgabe wird durch die im Kennzeichen des Hauptanspruches beschriebene Einrichtung gelöst.

Die Erfindung schlägt eine Modifizierungsmethode der Speicherpo 972031 409825/1005

adresse vor, welche elektronisch und dynamisch ausgeführt werden kann. Hierbei wird die dem Adressendecodierer angebotene Adresse durch logische Schaltungen als Funktion von in einem Schieberegister gespeicherten Daten modifiziert. Für jede Bitposition ist dabei ein solches Schieberegister vorgesehen. Wenn Mehrfach-Fehler in einem Datenwort festgestellt werden, wird die in jedem Schieberegister gespeicherte Information derart verändert, daß die Datenbits des Datenwortes in solcher Weise geändert werden, daß die festgestellte Mehrfachfehlersituation aufgehoben wird.

Das Schieberegister ist vorzugsweise als lineares Rückkopplungs-Schieberegister ausgeführt und steuert ein Exklusiv-ODER-Glied für jeden der Eingänge des Adressendecodierers der betreffenden Bitposition. Jedes der Exklusiv-ODER-Glieder empfängt als Eingänge ein Bit der Wortadresse und den Ausgang einer der Stufen des linearen Rückkopplungsschieberegisters. Am Ausgang liefert das Exklusiv-ODER-Glied ein Signal, welches den Eingang des Adreßdecodierers bildet.

In den Schieberegistern werden verschiedene Galoisfeld-Zahlen gespeichert. Dabei wird mit der Zahl 0 im Schieberegister der ersten Bitpositon begonnen und in den aufeinanderfolgenden Schieberegistern die aufeinanderfolgenden Zahlen des Galoisfeldes bis zur höchsten benötigten Zahl im Schieberegister der letzten Bitposition fortgefahren. Der Austausch der Bits zwischen den Worten erfolgt dann als orthogonale Lateinquadrate. Der Austausch kommt dadurch zustande, daß jedes Schieberegister mit Ausnahme des Schieberegisters der ersten Bitposition um eine Galoiszahl weitergeschaltet wird, wenn ein Mehrfachfehler von der Fehlererkennungsschaltung festgestellt wird. Auf diese Weise wird erreicht, daß die festgestellten Mehrfachfehler in einem einzigen Wort auf Einfachfehler in zwei oder mehr verschiedene Adressen aufgeteilt werden. Bezüglich der mathematischen Eigenschaften von Galoisfeldern und Lateinquadraten wird auf die nachfolgende Beschreibung des Ausführungsbeispieles der Erfindung verwiesen.

po 972 031 «»«9825/1005

Die Erfindung hat den Vorteil, daß ein Austesten des Speichers zur Feststellung der schadhaften Bitstellen entfallen kann. Der festgestellte Mehrfachfehler wird dabei in einem einzigen Vorgang eliminiert. Die Art und Weise der Korrektur bringt es mit sich, daß es höchst unwahrscheinlich ist, daß durch die Korrektur andere Mehrfachfehler geschaffen werden.

Ein anderer Vorteil der Erfindung besteht darin, daß in einem vorhandenen Speicher nur geringfügige Änderungen notwendig werden, um die automatische Adressenumwandlung durchführen zu können. Es müssen lediglich das Schieberegister und Exklusiv-ODER-Glieder für jede Bitposition hinzugefügt werden. Ein weiterer Vorteil besteht darin, daß durch die Korrektureinrichtung die Bitkapazität des Speichers nicht eingeschränkt wird, aber trotzdem die Verwendung von schadhaften Speieherteilen, wie z.B. Halbleiterchips mit schadhaften Bitstellen, möglich wird. Die erfindungsgemäße Einrichtung ist auch nicht den Randbedingungen der bekannten Einrichtung unterworfen, das Fehler in einem Viertel oder einem Achtel eines Chips auftreten müssen, wobei nur die restlichen drei Viertel oder sieben Achtel des Chips im Speicher verwendet werden können.

Ein Ausführungsbeispiel der Erfindung soll anhand von Figuren beschrieben werden. Es zeigen:

Fig. 1 eine schematische Darstellung, wie Mehrfach-

fehler in einem einzigen Wort in einzelne Fehler in zwei oder mehr Worten umgeändert werden können,

Fig. 2 eine Speichermatrix, welche durch einen Decodierer

adressiert wird,

Fig. 3 eine Speichermatrix mit einer Adressenumwandlungs-

einrichtung zur Umwandlung der angebotenen Adresse in eine Galoisfeldzahl,

PO 972 03! 409825/1005

Fig. 4 eine Tabelle, welche den Zusammenhang zwischen

den Decodierern der Fig. 1 und Fig. 2 zeigt, und

Fig. 5 eine Adressenumwandlungseinrichtung für einen

4x4 Speicher.

Der in Fig. 1 gezeigte Speicher enthält eine Mehrzahl von Datenworten / welche jeweils vier Bits aufweisen. Jedes Datenbit einer bestimmten Bitposition aller Worte ist dabei in einer Speichermatrix gespeichert. Zum Beispiel enthält das Wort 10 vier Datenbits 12a bis 12d, welche in den Matrizen 14, 16, 18 und 20 gespeichert sind. Das Wort.22 weist vier Bits 24a bis 24d auf, und das Wort 26 enthält die Bits 28a bis 28d. Bei dem Speicher handelt es sich also um einen Speicher, welcher in jedem Basismodul ein Bit einer bestimmten Bitposition speichert.

In einer solchen Anordnung kann ein fehlerhaftes Bit relativ leicht ersetzt werden. Zum Beispiel soll angenommen werden, daß das Bit 12b schadhaft ist. Wenn die Matrix 16 als Ganzes ausgewecheselt wird, d.h. nur mit einwandfreien Chips versehen wird, kann der Speicher wieder fehlerfrei arbeiten. Ein solcher Ersatz ist jedoch umständlich. Deshalb ist in modernen Speichern eine Fehlererkennungs- und Korrektureinrichtung vorgesehen, welche automatisch ein Datenwort mit einem fehlerhaften Bit korrigiert. Die bekannten Einrichtungen stellen auch zwei oder mehr fehlerhafte Bits fest, können jedoch die Daten in.dem Wort nicht mehr automatisch korrigieren. Die Fehlererkennungsschaltung würde im obigen Beispiel einen Doppelfehler im Wort 22 feststellen, in dem die Bits 24a und 24d schadhaft sind, könnte jedoch diesen Fehler nicht korrigieren, da die Anzahl der verwendeten Prüfbits es nicht gestattet, die Stelle der schadhaften Bits anzugeben. . Eine Korrektur könnte z.B. auf die Weise erfolgen, die in der eingangs genannten US PS 3 644 902 beschrieben ist. Nach dieser Methode wäre es nicht notwendig eine der Matrizen 14 bis 20 auszuwechseln,· sondern man würde die angebotenen Speicheradressen umwandeln, d.h. die Worte würden nicht dasselbe Bit in jeder

PO 972 031

409825 / 1 0OS

der Matrizen enthalten. So könnte z.B. ein Doppelfehler im Wort 22 dadurch eliminiert werden, daß in das Wort 22 das Bit 28d anstelle des Bits 24d aufgenommen wird und das Wort 26 würde dann das Bit 24d anstelle des Bits 28d enthalten. Auf diese Weise könnte jedes der Worte 10, 22 und 26 nur einen einzigen Fehler enthalten und könnte somit die Fehlererkennungsschaltung des Speichers diesen einzelnen Fehler automatisch korrigieren..In der bekannten Einrichtung erfolgt die Adressenumwandlung durch physikalische Änderung der Verdrahtung des Speichers oder der Logik in der Adressierung des Speichers.

In Fig. 2 ist eine typische Speichermatrix mit den Adressierungseinrichtungen gezeigt. Die Bits 30 sind in einer 4x1 Matrix angeordnet, wobei jedes Bit am Kreuzungspunkt einer der Wortleitungen 32 bis 38 mit der Bitleitung 40 angeordnet ist. Eine der vier Wortleitungen wird dadurch ausgewählt, daß die Adressensignale rl und r2 durch einen Decodierer 48 decodiert werden. Wenn beide Bits rl und r2 den binären Wert 0 haben, wird die Wortleitung wO ausgewählt. Wenn rl = 1 ist und r2 = 0, wird die Wortleitung wl ausgewählt. Wenn rl = 0 und r2 = 1 ist, wird die Wortleitung w2 ausgewählt und, schließlich, wenn beide Bits rl und r2 1 sind, wird die Wortleitung w3 ausgewählt. Bei einer Leseoperation würde dann das Bit 30 auf der bestimmten Wortleitung 32, 34, 36 oder 38 in den Leseverstärker- 49 ausgelesen werden.

Die oben beschriebene bekannte Einrichtung wird im vorliegenden Ausführungsbeispiel der Erfindung durch die in Fig. 3 gezeigte Umwandlungseinrichtung ergänzt. Die Einrichtung 5O weist ein zweistufiges lineares Rückkopplungsschieberegister (LRSR) 52 und zwei Exklusiv-ODER-Glieder 54 und 56 auf, welche eine Exklusiv-ODER-Operation mit den beiden Datenbits el und c2, welche in den Stufen des Schieberegisters gespeichert sind und mit den Adressenbits rl und r2 des Wortauswahldecodiersignales ausführen. Die bestimmte Wortleitung, 0, 1, 2 oder 3 dieser Matrix, welche von dsn Signalen rl und r2 ausgewählt werden soll, hängt von den Daten,

po 972 031 409825/1 0 0 S

die im Schieberegister 52 gespeichert sind, ab. Wenn z.B. in · beiden Stufen des Schieberegisters je eine binäre O gespeichert ist, erfolgt die Decodierung wie oben im Zusammenhang mit der bekannten Einrichtung beschrieben. Das heißt, wenn beide Bits rl und r2 O sind, wird die Nullwortleitung ausgewählt, usw. .Wenn jedoch in einer der beiden Stufen des Schieberegisters nicht eine 0 gespeichert ist, wird eine verschiedene Kombination von Wortleitungen ausgewählt. Es soll z.B. angenommen werden, daß in der ersten Stufe des Schieberegisters 52 eine 1 gespeichert ist, während die zweite Stufe des Schieberegisters eine 0 enthält. Wenn in diesem Falle beide Bits rl und r2 = 0 sind, sind die Eingangssignale zum Decodierer al und a2 gleich 1 und O. Auf diese Art wird dann die Wortleitung 1 des Speichers ausgewählt.

Die linke Tabelle in Fig. 4 zeigt die resultierenden Adressen al, a2, welche sich durch die verschiedenen Kombinationen von rl, r2, el und c2 ergeben, während die rechte Tabelle in Fig. 4 anzeigt, welche Worte durch die verschiedenen Kombinationen von rl, r2, el und c2 ausgewählt werden.

Die Zahlen 00, 10, 01 und 11 stellen dabei eine Galoisfeld-Elementsequenz dar. Es ist bekannt, daß ein lineares Schieberegister, wie z.B. das-Zweibitschieberegister 52, Zahlen in einer Galoisfeld-Elementsequenz produziert, wenn es von Position zu Position weitergeschoben wird. Ein solches lineares Schieberegister kann also als Galoiszähler betrachtet werden. Zur Beschreibung der Wirkungsweise eines solchen Zählers soll nun angenommen werden, daß eine 1 in der ersten Stufe 58 und eine 0 in der zweiten Stufe 60 des Registers gespeichert ist. Wenn nun ein Schiebepuls an die Klemme 62 angelegt wird, werden die Daten in den Stufen verschoben. Durch diese Verschiebung wird der Inhalt der Stufe 60 in die Stufe 58 verschoben, während das Bit in der Stufe 58 im Exklusiv-ODER-Glied 63 mit dem Bit in der Stufe 60 in einer Exklusiv-ODER-Operation verknüpft wird und das Resultat in die Stufe 60 eingeschrieben wird. Nach der Verschiebeoperation ist also eine 0 in der Stufe 58 und eine 1 in

po 972 O₃I 409825/1005

der Stufe 60 gespeichert. Wenn nun nochmals ein Schiebepuls an die Klemme 62 angelegt wird, werden die Daten im Register wiederum verändert, und sind schließlich in beiden Stufen 58 und 6O je eine 1 gespeichert. Wenn nun schließlich noch ein Schiebeimpuls angelegt wird, kehrt das Schieberegister zu der Ausgangssituation zurück und speichert eine 1 in der ersten Stufe 58 und eine 0 in der zweiten Stufe 60. Die Daten im Schieberegister verändern sich also wie im Diagramm 68 in Fig. 5 gezeigt.

Die drei Zahlen in der Sequenz stellen drei der vier Zahlen in der Galoisfeld-Elementsequenz, welche oben beschrieben wurde, dar. Damit kann für einen Speicher mit vier Worten zu je vier Bits eine Mehrfachfehlerkorrektur erzielt werden. Jedes Bit eines der Worte wO bis w3 des Speichers ist einer verschiedenen Matrix gespeichert und jede Matrix wird durch eine Wortadreßleitung über den Galoisumwandlungscodierer 50 und Decodierer 48 adressiert,

In Fig. 5 stellen wO, wl, w2 und w3 die Worte dar, welche durch die Wortdecodierungssequenz rl und r2 angewählt werden, während die Zahlen in den Spalten Tl, T2 und T3 die Worte darstellen, welche tatsächlich in der betreffenden Matrix 14, 16, 18 oder adressiert werden. Im Schieberegister 52 der Matrix 14 werden zwei binäre Nullen gespeichert. In dieser Matrix ist das erste Bit jedes der Worte wO bis w3 gespeichert und die Daten in diesem Schieberegister werden im gezeigten Beispiel nicht verändert. Die Eingangssignale rl und r2 auf den Adreßleitungen passieren also die Exklusiv-ODER-Glieder 54a und 56a unverändert und das erste Bit jedes der Worte ist zugleich dasselbe Bit wie es in den Spalten Tl, T2 und T3 dargestellt ist.

Zu Beginn wird eine binäre 1 in der ersten Stufe 58b und eine binäre 0 in der zweiten Stufe 60b des Schieberegisters der Matrix 16 gespeichert. Diese Matrix enthält das zweite Bit jedes der Speicherworte. Damit werden die Bits der Worte wie in Spalte Tl umarrangiert, so daß wenn die Adressenbits rl und r2 das Wort wO adressieren, das Bit des Wortes wl erhalten wird, usw.

409825/1005

PO 972 031

Eine andere Umwandlung der Bits erfolgt in der Matrix 18, in der eine 0 in der ersten Stufe 58c und eine 1 in der zweiten Stufe 60c gespeichert ist, und in Wort 20, in dem eine 1 in beiden Stufen des Schieberegisters 52d gespeichert ist. Damit sind die Adressenbits al und a2, welche dem Decodierer angeboten werden, verschieden für jede Matrix, wenn die angebotenen Adressenbits rl und r2 identisch für alle Speichermatrizen sind.

Die Daten werden in den Schieberegistern dadurch gespeichert, daß ein Impuls an die Klemme 64 angelegt wird. Zuerst wird eine binäre 1 an die Klemme 64d angelegt, und ein Schiebepuls an die Klemme 62. Sodann wird eine binäre 1 an der Klemme 64c eingeführt und ein zweiter Schiebeimpuls an die Klemme 62 angelegt. Schließlich wird eine binäre 1 an der Klemme 64b eingeführt, und ein dritter Schiebeimpuls an die Klemme 62 angelegt. Nach dem dritten Schiebeimpuls speichern die Schieberegister 52a bis 52d die oben angeführten Daten.

Es soll nun angenommen werden, daß ein Doppelfehler in einem der Speicherworte durch die Fehlererkennungsschaltung 66 festgestellt wird. Daraufhin wird ein Schiebepuls an die Klemme durch die Schaltung 66 angelegt und damit die in jedem der Schieberegister 52 gespeicherten Daten in Übereinstimmung mit der bei 68 gezeigten Sequenz verändert.

Die in der Speicherkarte 16 gespeicherten Schieberegisterdaten werden also von 10 auf 01 verändert, die in Karte 18 gespeicherten Daten von 01 auf 11, und die in Karte 20 gespeicherten Daten von 11 auf 10, während die Bits im Schieberegister 52a in der Karte 14 unverändert bleiben.

Aus der Betrachtung der Spalte T2 in allen Karten ergibt sich, daß eine vollständige Umordnung der Bits im Speicher durchgeführt wird. Zur Illustration, wie damit ein Doppelfehler eliminiert werden kann, soll angenommen werden, daß das Bit 2 auf der Karte 16 und das Bit 0 auf der Karte 20 schadhaft sind. Ein Doppel-

PO972O31 40982S/1005

fehler besteht also im adressierten Wort 3. Wenn nun der Schiebeimpuls an die Schieberegister 56b bis 56d angelegt wird, befinden sich.diese fehlerhaften Bits nicht mehr beide im Wort 3, sondern es würde nunmehr eines im Wort 0 und das andere im Wort 1 zu finden sein, d.h. es liegen nun zwei Einzelfehlersituationen vor, welche durch die gebräuchliche Fehlererkennungs- und Korrekturschaltung korrigiert werden können.

Es soll nun angenommen werden, daß ein zusätzlicher Fehler im Bit 3 der Karte 16 auftritt, wodurch sich ein Doppelfehler im adressierten Wort 1 ergibt, welcher das Bit 3 in Karte 16 und das Bit O in Karte 2O betrifft. Es wird sodann ein zweiter Schiebeimpuls von der Fehlererkennungsschaltung 66 angelegt, wodurch sich eine Bitanordnung in jeder der Karten ergibt, welche in Spalte T3 der Karten gezeigt ist. Eine Prüfung dieser Spalte T3 zeigt, daß nun in jedem der Worte ein Einfachfehler vorliegt, welcher von der Einrichtung korrigiert werden kann.

Es wurde somit gezeigt, daß nach dem obigen Verfahren, in dem binäre Zahlen in einer Galoisfeld-Transformationssequenz benutzt werden und die Zahlen, wie oben beschrieben, in der Sequenz weitergeschaltet werden, nicht korrigierbare Fehler in solche Fehler umgewandelt werden können, die von der Fehlererkennungs- und Korrekturschaltung des Speichers korrigiert werden können. Wenn dabei nach der Feststellung eines ersten Doppelfehlers ein zweiter Doppelfehler auftritt und die oben beschriebene Fehlerumwandlung vorgenommen wird, ist dabei sichergestellt, daß durch die Umwandlung des zweiten Fehlers nicht die erste Doppelfehlersituation wieder geschaffen wird. Dies wird dadurch erzielt, daß die durch die Galois-Transformationssequenz geschaffene Adressensequenz Ausdrücke von orthogonalen Lateinquadraten darstellt.

Die bereits oben beschriebene Fig. 4 stellt nämlich ein Lateinquadrat dar, da eine bestimmte Ziffer in jeder Zeile und in jeder Spalte genau einmal vorkommt. Ob zwei verschiedene Lateinquadrate orthogonal sind, kann dadurch festgestellt werden, daß man sie sich als übereinandergelegt vorstellt. Dabei ergeben sich in jedem

PO972O31 409825/1005 _;

Kreuzungspunkt des entstehenden Quadrats ein Zahlenpaar, welches aus der Zahl des ersten Lateinquadrates und der Zahl des entsprechenden Kreuzungspunktes im anderen Lateinquadrat besteht. Die beiden Läteinquadrate sind dann orthogonal, wenn ein bestimmtes Zahlenpaar in dem entstehenden Lateinquadrat genau einmal vorkommt. ·

Es ist ersichtlich, daß in dem obigen Ausführungsbeispiel bei Durchlaufen der beschriebenen Sequenz ein solches orthogonales Lateinquadrat entsteht. Falls jedoch ein dritter Doppelfehler auftritt und ein dritter Schiebeimpuls an die Klemme 62 angelegt würde, dann würde die ursprüngliche Fehlersituation wieder entstehen. Hierbei ist jedoch zu beachten, daß aus Gründen der Klarheit der Darstellung und der Übersichtlichkeit der gezeigte Speicher nur sehr geringen Umfang hat. In einer tatsächlichen, praktisch verwendeten Ausführung, würde die Anzahl der auf einer Speicherkarte gespeicherten Bits in die Hunderte oder Tausende gehen. Dementsprechend wären dann auch die nötigen Galoisfeld-TransformationsSequenzen aus viel längeren binären Zahlen zusammengesetzt. Die Wahrscheinlichkeit, nur eine Zahlenkombination in der Sequenz wiederholen zu müssen, ist daher sehr klein.

Zum besseren Verständnis der beschriebenen Einrichtung sei daran erinnert, daß ein Galoisfeld aus einem Residuum-Klassenring modulo m besteht, worin m eine Primzahl ist= Für eine genauere. Beschreibung von Galoisfeldern kann auf das Buch von W.W. Peterson "Error Correcting Codes", 1961, MIT Press, Cambridge, Mass., verwiesen werden.

Eine Beschreibung der Eigenschaften von orthgonalen Lateinquadraten ist in dem Buch von H.B. Mann, "Design and Analysis of Experiments", 1949, Dover Publications, N.Y., enthalten.

409825/1005

PO 972 031

Claims

PATENTANSPRÜCHE

(Iy ' Adressenumwandlungseinrichtung für einen aus Speichermatrizen bestehenden Speicher, in dem in jeweils einer bestimmten Matrix alle Bits einer bestimmten Bitposition der zu speichernden Datenworte gespeichert sind und die Matrix von einem Adressendecoder zur Auswahl eines bestimmten Bits angesteuert wird, sowie mit einer Fehlererkennungs- und Korrekturschaltung, dadurch gekennzeichnet, daß die Adressenbits (rl, r2) den Adressendecodern (48) über Exklusiv-ODER-Schaltungen (54, 56) angeboten werden,

da« diese Exklusiv-ODER-Schaltungen an ihrem zweiten Eingang mit den Ausgängen von entsprechenden Stufen (58, 60) von Schieberegistern (52) verbunden sind, welche jeweils beim Auftreten eines von der Fehlererkennungs- und Korrekturschaltung (FEK-Schaltung 66) wohl erkennbaren, aber nicht korrigierbaren Mehrfachfehlers durch einen von der FEK-Schaltung (66) gelieferten Schiebeimpuls um eine Position verschoben werden,

derart, daß die durch die umgewandelte Adresse adressierten Datenworte nur mehr so viele Fehler aufweisen, wie die FEK-Schaltung (66) korrigieren kann.
2. Einrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die Schieberegister als Galoiszähler ausgeführt sind und voneinander verschiedene binäre Zahlen einer Galoisfeld-Transformationssequenz speichern, derart, daß die den Decodern (48) angebotene binäre Adresse (rl, r2) in eine andere binäre Zahl (al, a2) in der Galoisfeld-Transformationsseguenz umgewandelt wird.
3. Einrichtung nach Anspruch 2, dadurch gekennzeichnet, daß die Galoiszähler als lineare Rückkopplungsschieberegister ausgeführt sind.

409825/1005

PO 972 031
4. Einrichtung nach Anspruch 3-, dadurch gekennzeichnet, daß die Schieberegister zwei Stufen (58, 60) aufweisen, welche über eine Exklusiv-ODER-Schaltung (63) verbunden sind, wobei der zweite Eingang dieser Exklusiv-ODER-Schaltung vom Ausgang der zweiten Stufe (60) gesteuert wird und daß der Eingang der ersten Stufe .(58) mit dem Ausgang einer ODER-Schaltung verbunden ist, deren einer Eingang mit dem Ausgang der zweiten Stufe (60) und deren zweiter Eingang mit einer Klemme (64) zum externen Einspeichern von Daten in die Stufen des Schieberegisters verbunden ist.
5. Einrichtung nach Anspruch 3, dadurch gekennzeichnet, daß in alle Stufen des Schieberegisters (52) eine binäre O gespeichert wird und daß der Inhalt des Schieberegisters bei Auftreten eines Vielfachfehlers nicht verändert wird.
6. Einrichtung nach Anspruch 1, dadurch gekennzeichnet, daß die FEK-Schaltung (66) einen Doppelfehler erkennen und einen Einfachfehler korrigieren kann.

PO 972 O₃₁ 409825/1005