DE2450468C2 - Fehlerkorrekturanordnung für einen Speicher - Google Patents

Description

Die Erfindung betrifft eine Fehlerkorrekturanord- Speicher 18 Spalten. Stellt man beispielsweise fest, daß

nung nach dem Oberbegriff im Patentanspruch 1. das zweite Bit eines Wortes fehlerhaft ist so wird der

Mit zunehmender Verwendung von elektronischen Ausgang der zweiten Spalte des Speichers gesperrt. Speichern werden Fehler, die sich aufgrund falscher so Gleichzeitig wird die 18te Spalte, also die Reservespalte Speicherbits ergeben, immer bedenklicher. Es sind in Betrieb genommen und die Informationen, die

bereits verschiedene Anordnungen entwickelt worden, ursprünglich in der zweiten Spalte gespeichert waren,

um das Bitfehlerproblem bei Speichern zu überwinden. werden zur 18ten Spalte übertragen. Von da an arbeitet

In der Hauptsache beruhen diese Anordnungen auf der Speicher normal mit Ausnahme des Umstandes, daß Fehlerkorrektur-Codierungen, bei denen die einzelnen 55 in jeweils aus der 18ten Spalte gelesene Bit nun in die Ausgangswörter eines Speichers geprüft werden, um zweite Bitposition jedes gelesenen Speicherwortes

festzustellen, ob ein Fehler vorhanden ist. Zeigt sich ein eingefügt wird.

Fehler, so wird das fehlerhafte Wort unter Verwendung Bei Anwendung dieser Lösung kann die festgestellte

des Fehlerkorrekturcode richtig gestellt. fehlerhafte Spalte dann aus dem Speicher herausge-

Der grundsätzliche Nachteil eines solchen Lösungs- 60 nommen und repariert oder durch eine neue Spalte Versuches beruht darauf, daß die äußeren Symptome des ersetzt werden, und zwar ohne Unterbrechung des Speicherfehlers behandelt werden, ohne die innere Speicherbetriebs. Die damit erzielten wirtschaftlichen Quelle des Problems zu korrigieren. Nimmt man Einsparungen sind bedeutend. Das ergibt sich aus dem

beispielsweise eine dauernde Fehlfunktion eines Umstand, daß ein typischer Speicher mit 64 000 Wör-

Speicherbits an, so wird jedesmal dann, wenn das Wort 65 tem ohne dieses Verfahren eine mittlere Fehlerzwi-

(byte), das das falsche Bit enthält, aus dem Speicher schenzeit (MTBF) von etwa 6 Jahren besetzt. Nimmt

gelesen wird, der Fehlerkorrekturcode zur Beseitigung man eine Auswechselzeit von einem Tag für jede

der Schwierigkeit benötigt. Mit einem solchen Verfah- Speicherspalte an, die sich als fehlerhaft herausgestellt

hat, so wird die mittlere Fehlerzwischenzeit MTBF unter Anwendung der erfindungsgemäßen Lösung bis über denjenigen Wert verlängert, für den der erste Ausfall anderer Bauteile der Anlage zu erwarten ist, beispielsweise eine Zentraleinheit mit einer Fehlerzwischenzeit von 30 Jahren. Demgemäß läßt sich erfindungsgemäß eine Speicherverdopplung vermeiden und die Zuverlässigkeit erhöhen.

Außerdem können Speicherausgangsfehler automatisch korrigiert werden und die wesentliche Erhöhung der mittleren Fehlczwischenzeit MTBF wird ohne eine strukturelle Änderung des Speichers und ohne Verwendung von Fehlerkorrektur-Codierungen erreicht

Nachfolgend wird die Erfindung anhand der Zeichnung näher beschrieben. Es zeigt

F i g. 1 das Blockschaltbild eines Ausfuhrungsbeispiels unter Verwendung eines Schreib-Lesespeichers; F i g. 2 die Verwendung mehrerer Reservespalten. Vor einer genauen Beschreibung der Gesamtanlage soll zweckmäßig die Funktion einiger der dargestellten Einzelelemente erläutert werden. Die Decodierer, beispielsweise 12, 13, nehmen Datenbits auf den vier Eingangsadern 19 auf. Diese Datenbits stellen im binären Format jede Zahl 0 bis 15 dar. Wenn die Eingangsader für EN 1 eines Decodieren auf niedrigem Potential (L) liegt, so entspricht das Ausgangssignal auf der dem decodierten Wert zugeordneten Ausgangsleitung genau dem Signal auf der Eingangsleitung EN2. Nimmt man beispielsweise an, daß die Eingangsbits 0110 (dezimal 6) auf den Eingangsleitungen 19 zum Decodierer 12 laufen, so wird, wenn die Eingangsleitung EN 2 auf niedrigem Potential liegt die Ausgangsleitung 6 ebenfalls auf niedrigem Potential liegen. Wenn dagegen die Eingangsleitung EN 2 auf hohem Potential (H) liegi, würde die Ausgangsleitung 6 ebenfalls H führen. Das Ausgangssignal wird beim Durchlaufen eines Puffergatters (nicht gezeigt) invertiert

Der Multiplexer MPX14 arbeitet umgekehrt wie die Decodierer. Er überträgt das Signal auf einer der Eingangsadern 0 bis 15 der Eingangsleitung 101 zur einzigen Ausgangsleitung in Abhängigkeit vom decodierten Dezimaläquivalent des binärcodierten Eingangssignals auf den Adern 19. Bei dem Beispiel, bei dem die Eingangsadern 19 die Bits 0110 führe«, würde also das Signal H oder L auf der Ader 6 der Leitung 101 invertiert zur Ausgangsleitung übertragen. Beim Lesen findet eine erneute Invertierung des Bit' statt

Die Paritätsprüfschaltung 11 arbeit« in bekannter Weise derart daß die Adern 0 bis 16 auf Parität geprüft werden. Tritt ein Paritätsfehler auf, so wird ein Ausgangssignal abgegeben Zur Durchführung dieser Funktion sind zahlreiche Schaltungsanordnungen bekannt. Einig- dieser Schaltungen beruhen auf dem Prinzip einer Einzelfehlerfeststellung gemäß US-Patent Re. 23 601 (23. 12.1952).

Die Fehlersteuerschaltung 17 arbeitet aufgrund eines Signals der Paritätsprüf schaltung 11. Sie nimmt das Ausgangswort aus 16 Bits auf und bestimmt welches Bit fehlerhaft ist Verschiedene Verfahren lassen sich zu diesem Zweck verwenden. Dazu gehört ein Einschreiben von nur 1-Werten in den Speicher und Prüfen des Ausgangssignäls, gefolgt von einem Einschreiben von nur 0-Werten, wonach wiederum das Ausgangssignal geprüft wird. Bei Feststellung des fehlerhaften Bits wird ein binäres AusgaOgssignal gebildet, dessen Wert der Bitposition des Fehlerdatenbits entspricht Geht man davon aus, daß das Datenbit in der Position 2 eines Speicherausgangswortes Has fehlerhafte Bit enthalt, dann würde das Ausgangssignal der Fehlersteuerschaltung 17 den Wert 0010 haben. Wenn diese Information zur Verfügung steht, so geht die Ader LOAD auf den Wert L, wodurch das 4-Bit-Register 16 mit den Bits OClO geladen wird, also der Binärdarstellung für die Bit-Position des als fehlerhaft festgestellten Datenbits. Gleichzeitig stellt das Signal auf der Ader LOAD das Flipflop 15 ein.

In einem typischen Fall erhält der Schreib-Lesespeiin eher 10 Informationen von einer Eingangsquelle über die Adern 0 bis 16 des Kabels 101. Diese Informationen werden in den Spalten 0 bis 16 des Schreib-Lesespeichers 10 in Abhängigkeit von der Speichersteuerung 18 in bekannter Weise gespeichert jedes ankommende Wort mit 17 Bit wird aufgenommen. Die Speichersteuerschaltung 18 zur Durchführung dieser Funktionen ist nicht im einzelnen dargestellt Solche Schaltungen sind jedoch bekannt

Spalte 17 des Speichers bleibt zunächst leer und Spalte 16 enthält die Paritätsprüfbits für jedes Wort Beim Lesen eines Wortes aus dem Speicher wird die Information aus den Spalten 0 bis 15 de- Schreib-Lesespeichers 10 zu einem Eingang der W A N D-Glieder IMO bis IM 15 übertragen. Zu diesem Zeitpunkt liegen die Ausgänge 0 bis 15 des Decodieren 13 auf H, wodurch am Ausgang der Glieder IMO bis IM 15 tbr invertierte Wert der vom Speicher 10 kommenden Bits steht Wenn also auf der Ausgangsader 1 bei einem gegebenen Wort aus dem Speicher 10 der Wert H steht, so geht der Asugang des Gliedes 1M1 auf L

Dieses niedrige Potential wird an einen invertierenden Eingang des NAND-Gliedes ICl angelegt. Der Wert H am 1-Ausgang des Decodieren, 12 liegt an anderen invertierenden Eingang des Gliedes ICl. so daß dessen Ausgangssignal H ist. Das ist genau das aus dem Schreib-Lesespeicher 10 gewonnene Datenbit nämlich eine binäre I.

Auf ähnliche Weise wäre, wenn die Bit-Position 2 eines aus dem Speicher 10 gewonnenen Wortes den Wert L führt der Ausgang des Gliedes 1M2 au< H. wodurch der Ausgang des Gliedes 1C2 L ist Wiederum entspricht das Datenbit an der Ausgangsposition 2 des Speichers genau dem aus Spalte 2 des Speichers gewonnenen Datenbit.

Nimmt man an, daß die Paritätspriif schalung 11 feststellt daß das gelesene Wort am Ausgang der Glieder ICO bis IC 15 richtig ist dann wird dieses Wort auf die übliche Weise benutzt Wenn jedoch die Paritätsprüfschaltung 11 feststellt daß eines der Bits so fehlerhaft ist so wird ein Signal erzeugt das die weitere Verarbeitung sperrt und die Fehlersteuerschaltung 17 in Tätigkeit setzt. Diese stellt dann entsprechend der obigen Erläuterung fest welches oder welche der Bits fehlerhaft sind.

E.« se ingenommen, daß das Datenbit der Bit-Position 2 als fehlerhaftes Bit festgestellt worden ist Demgemäß liefert die Fehlersteuerschaltuf^f 17 an ihrem Ausgang den Binärwert 0010 (Dezimal 2). Dieser Wert wird zum *~Bit-Register 16 übertragen. Bei ω Betätigung der Ader LOAD durch die Fehlersteuerschaltung 17 wird dtr Binärcode 0010 in das Register aufgenommen. Außerdem wird zu diesem Zeitpunkt das Flipflop 15 eingestellt, wodurch der Eingang EN 1 der Decodierer 13 und 12 auf L geht Am Ausgang des 4-Bit-Registers 16 stehen jetzt die Bits 0010, die zum Eingang des Decodierers 13 geführt werden. Da der Eingang EN 2 des Decodierers 13 auf L liegt, geht sein Ausgang 2 ebenfalls auf L, wodurch der Ausgang des

NAND-Gliedes IMl den Wert H annimmt. Auf diese Weise werden Daten aus der Spalte 2 des Schreib-Lesespeichers 10 gesperrt.

Gleichzeitig steht der Multiplexer 14 unter dem Einfluß der vom 4-Bit-Register 16 gelieferten Binärda- s ten, wodurch die Ader 2 des Kabels 101 zum Ausgang des Multiplexers geführt wird, der mit Spalte 17 des Speichers 10 verbunden ist.

Unter Steuerung des Ausgangssignals des Flipflops 15 über die Leitung 102 werden dann Daten von einer to äußeren Quelle über das Kabel 101 zum erneuten Einschreiben in den Speicher 10 übertragen. Jetzt wird jedoch die über die Ader 2 des Kabels 101 ankommende Information über den Multiplexer 14 zur Spalte 17 des Schreib-Lesespeichers 10 geführt. Am Ende der Einschreibphase enthält Spalte 17 dann Datenbits, die die Inversion der Datenbits darstellen, die in Spalte 2 hätten eingeschrieben werden sollen. Dann wird der normale Betrieb des Speichers wieder aufgenommen. Immer wenn ein Wort aus dem Speicher geiesen wird, zo gehen die Datenbits aus Spalte 17 zum Eingang EN 2 des Decodierers 12. Die invertierten Bits werden dann über den Decodierer 12 zu dessen Ausgang 2 übertragen, und zwar unter Steuerung des vom 4-Bit-Register 16 gelieferten Binärcode 0010. Die Bits werden dann in den Gliedern ICO bis IC 15 erneut invertiert.

Es sei beispielsweise angenommen, daß eine binäre 1 (H) in der Bit-Position von Spalte 17 steht. Dieser Wert H würde dann über die Ader 2 des Decodierers 12 zu einem Eingang des NAND-Gliedes 1C2 geführt. Da beide Eingänge des NAND-Gliedes 1C2 auf H liegen, ist dessen Ausgangssignal L Man erkennt also, daß das Datenbit aus der Spalte 17 an die Stelle des Datenbits eingefügt wird, das vorher aus der gesperrten Spalte 2 zur Verfugung stand. Diese Arbeitsweise bleibt bestehen, solange das Flipflop IS eingestellt ist. und die gesamte fehlerhafte Spähe 2 des Schreib-Lesespeichers 10 kann ersetzt werden, wenn der Speicher gelesen wird. Nachdem das Flipflop 15 zurückgestellt ist, kommt «o das Ausgangssignal des Speichers wiederum nur von den ersten 16 Spalten, wie oben beschrieben.

Man beachte, daß. wenn das Flipflop 15 und das 4-Bit-Register 16 unter Verwendung von einrastenden Bauteilen hergestellt werden, beispielsweise magnetisch « verrastenden Relais, der Speicher nach einem Stromausfall weiter auf die gleiche Weise arbeiten würde. Die Umschaltung auf eine Reservespalte oder -spalten kann demgemäß auf semipermanente Weise erfolgen.

F i g. 2 zeigt ein Ausführungsbeispiel bei dem mehr als eine Reservespalte benutzt wird. Bei Feststellung eines Paritätsfehlers durch die Paritätsprüfschaltung 31 liefert die Fehlersteuerschaltung 37 in binärcodierter Form ein Ausgangssignal für die Dezimalposition des fehlerhaften Bits auf die oben beschriebene Weise. Dieses codierte Ausgangssignal wird zusammen mit dem Einschreibsignal zur Verteilerschaltung 38 und dann zu einem freien der 4-Bit-Register geführt, beispielsweise den Registern 306 und 326. Jedes dieser Register ist einer der Reserve-Speicherspalten 17, 18, 19 zugeordnet

Es sei beispielsweise angenommen, daß das erste Bit eines Wortes als fehlerhaft festgestellt worden ist Dann liefert die Fehlersteuerschaltung 37 die Bits 0001 zur Verteilerschaltung 38, die diese Bits zum 4-Bit-Register 306 führt und gleichzeitig das Piipftop 305 einstellt

Der Decodierer 303 liefert unter dem Einfluß des eingestellten Flipflops 305 und des Binärwertes 0001 aus dem 4-Bit-Register 306 niedriges Potential L über die Ader 1 zum Eingang des Gliedes 3Af1. Dadurch wird dessen Ausgang dauernd auf H gehalten, das Glied 3M1 also im Effekt abgeschaltet. Damit ist der Ausgang der Spalte 1 des Speichers gesperrt. Gleichzeitig legt der Decodierer 302 den invertierten Wert des Datenbits in Spalte 17 des Schreib-Lesespeichers 30 an einen Eingang des Gliedes 3Cl, so daß jede aus Spalte 17 gelieferte Information über den Decodierer 302 und das Glied 3Cl zur ersten Bitposition jedes aus dem Speicher gelesenen Ausgangswortes geht. Es kann dann erneut in den Speicher vom Kabel 101 aus auf die oben beschriebene Weise eingeschrieben werden, wobei der Multiplexer 304 die Datenbits der Speicherspalte 1 zur Speicherspalte 17 führt.

Es sei jetzt angenommen, daß ein zweiter Fehler durch die Paritätsprüfschaltung 31 festgestellt wird. Die Fehlersteuerschaltung 37 liefert dann erneut das binärcodierte Äquivalent der als fehlerhaft festgestellten Bit-Position lusarutricü mit einem Firi3chrcib;ig"a! zur Verteilerschaltung 38. In diesem Fall werden die ermittelten Bits in das 4-Bit-Register 326 eingegeben und das Flipflop 325 wird eingestellt Nimmt man an, daß ein Fehler in der Bit-Position vorliegt, so lautet das Binärsignal am Ausgang der Fehlersteuerschaltung 37 IUl. Das 4-Bit-Register 326 enthält dann die Bits till, und das Flipflop 325 wäre eingestellt. Der Decodierer 323 liefert aufgrund der zugeführten Bits 1111 und des Wericj L. auf der Ader EN 2 Erdpotential über die Ader 15. so daß das NAND-Glied 3Ai 15 abgeschaltet wird. Gleichzeitig verbindet der Decodierer 323 ebenfalls unter dem Einfhiß der Bits Ί11Ι die Spalte 19 des Schreib-Lesespeichers 30 übertiie Ader 15 des Decodierers 322 mit einem Eingang des NAND-Gliedes 3C15. Folglich wird immer dann, wenn ein Wort aus dem Speicher 30 gelesen wird, das Datenbit in Position 15 des Wortes das in Spalte 19 des Speichers befindliche DatcnbiJ und nicht das Dstenbi» in Spalte 1S sein.

Bei Feststellung des Fehlers werden entsprechend der obigen Erläuterung dem Schreib-Lesespeicher 30 zum erneuten Einschreiben über das Kabel 101 Eingangsinformationen zugeführt Der Multiplexer 324. der ebenfalls in Abhängigkeit von den Bits 1111 aus dem 4-Bit-Register 326 und dem eingestellten Flipflop 325 arbeitet, entfernt vom Kabel 101 die Spalte zugeordneten Bits und überträgt sie zur Spalte 19 des Speichers, wodurch die Informationen aus Spalte 15 zur Spalte 19 gegeben werden.

Obwohl bei dem dargestellten Ausführungsbeispiel bei Feststellung eines Ausgangsfehlers die gesamte fehlerhafte Spalte gesperrt und die darin enthaltene Information an eine Reservespalte übertragen wird, könnte die Anlage auch so ausgelegt werden, daß die Sperrung nur auf einer Wort für Wortbasis auftritt Bei einer solchen Anordnung findet eine Substitution nur statt wenn ein Fehler festgestellt wird. Wegen der prinzipiellen Einfachheit des erfindungsgemäßen Speicnerwiederherstellungsverfahrens dürfte ein Fachmann die Erfindung mit Vorteil in Anwendungsbereichen benutzen können, die strukturell wenig oder keine Ähnlichkeit mit dem oben beschriebenen Ausführungsbeispiel zeigen und zwar ohne vom Grundgedanken der Erfindung abzugehen.

Man beachte, daß statt eines erneuten Einschreibens in den Speicher aus einer äußeren Quelle bei Auftreten eines Fehlers, die Datenbits der fehlerhaften Spalte direkt zur gewählten Reservespalte übertragen werden könnten. Zu diesem Zweck könnte zuerst festgestellt

werden, welche Bit-Position fehlerhaft ist. Dann würde der Speicher zyklisch Zeile für Zeile gelesen und die Bits aus der fehlerhaften Position in die entsprechende Zeile der gewählten Reservespalte übertragen werden. Bei Auftreten eines Paritätsfehlers wird angenommen, daB der Fehler sich in der fehlerhaften Spalte befindet, und das entsprechende Bit wird invertiert, bevor es in der Reservespalte abgespeichert wird. Demgemäß läßt sich

das richtige Bit aus dem fehlerhaften Wort und dem Paritätsbit rekonstruieren.

Die Erfindung kann auch Anwendung finden bei einer Anordnung, bei der die Wörter in den Spalten gespeichert sind und das Ausgangssignal aus den Zeilen gewonnen wird. Die zugeordneten Schaltungen sind dann entsprechend umzuordnen.

Hierzu 2 Blatt Zeichnungen

Claims (3)

Patentansprüche: ren kann man zwar das gewünschte Ergebnis erzielen, jedoch nur auf Kosten zusätzlichen Zeitbedarfs.

1. Fehlerkorrekturanordnung zur Verwendung in Zur Oberwindung dieses Problems sind mehrere einem Speicher mit einer Vielzahl von Spalten und Anordnungen bekannt, bei denen das Ausgangswort Zeilen, bei dem jedes in einer Zeile abgelegte 5 eines Speichers geprüft wird, um festzustellen, ob es Ausgangswort aus je einem Datenbit jeder Spalte fehlerhaft ist Zeigen sich Fehler, so wird das Wort zusammengesetzt ist, wiederum unter Verwendung von Fehlerkorrekturver-

fahren korrigiert und an einen neuen Speicherplatz im

mit einer Prüfschaltung (11), die jedes Ausgangswort Speiche· übertragen. Dieser neue Speicherplatz wird

prüft und ein Fehlersignal erzeugt, wenn ein io dann jedesmal benutzt, wenn der Speicher aa. Platz des

Ausgangswort einen Fehler enthält und ursprünglichen Wortes gelesen werden solL Ein solches

mit einer Fehlersteuerschaitung (17), die in Abhän- Verfahren arbeitet zufriedenstellend, benötigt aber

gigkeit von dem Fehlersignal ein die fehlerhafte komplizierte Schaltungen im Umsetzerabschnitt des

Bitposition anzeigendes Fehlersteuersignal erzeugt, Speichers und außerdem ist eine zusätzliche Operation

Ii erforderlich, bevor eine Information aus dem Speicher

dadurch gekennzeichnet, daß gewonnen werden kann. Die zusätzliche Operation ist

wiederum zeitaufwendig.

erste Schaltungen (12, 13, 15, 16) vorgesehen sind. Die Erfindung hat sich die Aufgabe gestellt eine

die auf das Fehlersteuersignal hin ein Markiersignal einfache Fehlerkorrekturanordnung zu schaffen, die

erzeugen, das die der fehlerhaften Bitposition 20 einen zusätzlichen Zeitaufwand beim Betrieb des

entsprechende Spalte markiert, ferner Speichers vermeidet Die Lösung der Aufgabe ist im

Torschaliungen (IAfO bis IAf 15), die aufgrund des Patentanspruch! angegeben. Weiterbildungen der

Markiersignals die markierte Spalte sperren, Erfindung sind Gegenstand der Unteransprüche,

und zweite Schaltungen (14), die auf das Markierst- Eine Fehlersteuerschaltung, die in Abhängigkeit von

gnal hin in einer zusätzlichen Spalte des Speichers 25 einem Fehlersignal ein eine fehlerhafte Bitposition

(10) der markierten Spake entsprechende Datenbits anzeigendes Binärsignal erzeugt ist bekannt (DE-OS

erzeugen, und daß die ersten Schaltungen (12) so 22 60 850).

ausgelegt sind, daß sie in jedem Ausgangswort an Elektronische Speicher enthalten im allgemeinen eine

der Bitposition der markierten Spalte das Datenbit Matrix-Anordnung von Bits, die in Spalten und Zeilen

aus der zusätzlichen Spalte an die Stelle des 30 organisiert sind. Bei Auswahl einer gegebenen Zeile

Datenbits aus der markierten Spalte setzt erhält man ein Wort (Byte) aus dem Speicher, das aus

2. Fehle'-korrekturanordnung nach Anspruch 1, Datenbits zusammengesetzt ist und zwar jeweils einem dadurch gekennzeichnet daß die zweiten Schaltun- Bit aus jeder Spalte. Beim Ausführungsbeispiel der gen (14) so ausgelegt sind, aaß sie die Datenbits aus Erfindung ist der Speicher so ausgelegt daß er der markierten Spalte zur zusätzlichen Spalte 35 wenigstens eine Reservespalte zusätzlich zu der Anzahl übertragen. von Spalten aufweist, die für die Datenbits und die

3. Fehlerkorrekturanordnung nach Anspruch!, Paritätsprüfung erforderlich sind

dadurch gekennzeichnet daß die zweiten Schaltun- Wenn ein Wort aus dem Speicher gelesen wird,

gen (14) so ausgelegt sind, daß sie von einer äußeren benutzt man ein Paritätsprüfverfahren, um festzustellen.

Quelle in die zusätzliche Spalte diejenigen Bits 40 ob das Ausgangswort richtig ist Zeigt sich ein

eingeben, die in die markierte Spalte eingegeben Paritätsfehler, so wird festgestellt welches Bit und

worden sind. folglich welche Spalte fehlerhaft ¹M, und aufgrund dieser

Feststellung werden die Ausgangssignale der fehlerhaf-

ten Spalte gesperrt

45 Geht man von einem Wort mit 16 Bits, einem Paritätsbit und einem Reservebit aus. so hätte der