DE2619159C2 - Fehlererkennungs- und Korrektureinrichtung - Google Patents

Description

Technical Disclosure Bulletin, Vol.14, No. 2, Juli 1971, Seiten 670 bis 672, bekannt Die bekannte Einrichtung kann zwar Einzelbitfehler und in begrenztem Maße auch Mehrbitfehler erkennen, sie gestauet jedoch nicht die Erkennung eines Totalausfalls des Speicherelements, der üblicherweise zur Folge hat, daß alle ausgelesenen Bits entweder den Wert 0 oder den Wert 1 haben.

Der Erfindung liegt die Aufgabe zugrunde, eine Einrichtung der eingangs beschriebenen Art so abzubilden, daß sie auch einen Totalausfall des Speicherelements erkennen kann. Diese Aufgabe wird durch die im kennzeichnenden Teil des Patentanspruchs 1 angegebenen Merkmale gelöst.

Durch die erfindungsgemäßen Maßnahmen wird bewirkt, daß beim Auslesen aus einem funktionsfähigen Speicher unabhängig von der eingespeicherten Information nie der Fall auftreten kann, daß sämtliche ausgelesenen Bits (einschließlich der Paritätsprüfbits) den Wert 1 (oder 0) haben. De. geschilderte Fehlerzustand, bei dem sämtliche ausgelesenen Bits einschließlich der Paritätsprüfbits den Wert 1 (oder 0) haben, kann zum Ergebnis haben, daß die ganze Speichereinheit ersetzt werden muß. Derartige Fehler treten, wie gefunden wurde, besonders bei Halbleiterspeichern auf.

Von Vorteil bei der Erfindung ist. daß sie sich auf relativ einfache Weise und mit geringen Kosten realisieren läßt, so daß sie, obwohl sie in Systemen mit jeder beliebigen Speicherkapazität nützlich ist, speziell für die Benutzung in Datenverarbeitungssystemen mit einer relativ kleinen Speicherkapazität von Vorteil ist. wie in Minicomputer-Systemen, denn sin benötigt für ihre Verwirklichung nicht speziell entwickelte und relativ teure Logikelemente, wie unten noch erläutert wird. Derartige Minicomputer-Systeme haben häufig Speicherkapazitäten von nur 32K Wörtern oder weniger. Manchmal werden bei Minicomputern auch größere Speicherkapazitäten bis zu 128K Wörtern oder mehr verwendet

Die Ausführungsform nach Anspruch 2 ist besonders dann günstig, wenn die einzelnen Paritätsprüfbits nacheinander berechnet werden, weil dann die Umschaltung zwischen gerader und ungerader Paritätsprüfung keine Zählvorgänge erfordert.

Die Erfindung benutzt eine Hamming-Code-Technik. Das hauptsächliche Problem bei der Verwendung von üblichen Hamming-Codes zur Erzeugung einer direkten Adreßinformaiion zwecks Fehlerkorrektur liegt in der Tatsache, daß zu viele Hamming-Code-Glieder benötigt werden, um eine passende Adreßidentifikation zu erhalten. Beispielsweise müssen bei der Benutzung einer normalen Hamming-Code-Technik mit einem 16-Bit-Datenwort bis zu 11 oder 12 Glieder, die tatsächlich 11 oder 12 Bits des Datenwortes repräsentieren, durch ein einzelnes logisches Element (d. h. ein Exclusiv-ODER-Glied) verarbeitet werden. Beim gegenwärtigen Stand der Technik sind aber Logikelemente mit mehr als höchstens 9 Eingängen nicht verfügbar, und um konventionelle Hamming-Code-Techniken zu verwirklichen, müssen speziell entwickelte Logikelemente für diesen Zweck hergestellt werden; diese Entwicklung erhöht in unerwünschter Weise die Herstellungskosten des Fehlererkennungs- und Korrektursystems. Ein derartiger Kostenanstieg ist besonders bei Minicomputer-Systemen von Nachteil, wo derartige Kosten ein für den Wettbewerb wichtiger Umstand sind. Daher wurde die Verwendung von konventionellen Hamming-Codes zur Erzeugung direkter Adreßinformation üblicherwei-

se vermieden, ausgenommen in Systemen mit relativ großer Kapazität Wie an Hand des Ausführungsbeispiels beschrieben ist benutzt die Erfindung eine modifizierte Hamming-Code-Technik, die die Fähigkeit hat jeden Ort eines Einzelbitfehlers leicht zu identifizieren und einen solchen Fehler sofort zu korrigieren durch die Benutzung von standardisierten und leicht erhältlichen, gegenwärtig verfügbaren Logikelementen mit nicht mehr als 9 Eingängen (Anspruch 4).

Ein Vorteil der in Anspruch 4 beschriebenen Ausführungsform ist noch darin zu sehen, daß sie es gestattet, eine parallele Signalverarbeitung vorzunehmen und dadurch eine große Geschwindigkeit bei der Fehlererkennung und Korrektur zu erreichen.

In der nachstehenden Beschreibung wird die Erfindung an Hand der Figuren beispielhaft erläutert.

F i g. 1 zeigt eine Darstellung der Art, in der die Paritätsprüfbits entsprechend der Erfindung gebildet werden;

Fig. 2 zeigt eine Darstellung der Art, in der die Fehlerbits entsprechend der Erfindung gebildet werden;

F i g. 3 zeigt ein Blockdiagramm der Fehlererkennungs- und Korrektureinrichtung der Erfindung.

F i g. 4 zeigt eine detailliertere Zeichnung des Speicherpufferregisters des Systems nach F i g. 3;

Fig. 5 zeigt eine detailliertere Zeichnung des Code-Generators des Systems nach F i g. 3;

Fig. 6 zeigt eine detailliertere Zeichnung der Zeitsteuerung des Systems nach F i g. 3;

Fig. 7 zeigt eine detailliertere Zeichnung eines Teils des Korrekturdecoders des Systems nach F i g. 3;

F i g. 8 zeigt eine detailliertere Zeichnung eines Teils des Korrekturdecoders des Systems nach F i g. 3;

Fig. 9 zeigt eine detailliertere Zeichnung der Fehlerspeicherung des Systems nach F i g. 3 und

Fig. 10 zeigt eine detailliertere Zeichnung der Logik für die Steuerung der Operationsart des erfindungsgemäßen Systems und die Logik zum Unterbrechen des Datenverarbeitungsgerätes dafür (Interrupt-Logik).

Vor der Diskussion der speziellen Fehlererkennungsund Korrekturlogik einer bestimmten Ausführungsform der Erfindung im Detail ist es hilfreich, das Konzept in allgemeineren Begriffen zu verstehen. Das Fehlerkorrektursystem gestattet zusätzlich zu der Erkennung und Korrektur von Einzelbitfehlern in Worten, die aus dem Speicher gelesen wurden, auch die Erkennung von gewissen Zuständen, bei denen ein im wesentlichen vollständiger Ausfall einer Speichereinheit auftritt. Weiterhin sieht das System die Möglichkeit vor, Fehler aufzuzeichnen, indem es eine geeignete Adresse aufrechterhält, und es sieht Bitregister hierfür vor und weiterhin sorgt es, falls gewünscht, für die Unterbrechung der Operation eines Rechenwerks, wenn Fehler auftreten. Das System ist so ausgelegt, daß es seine Fehlererkennung während der normalen Speicherzyklen ohne irgendeine Zeitverzögerung durchführt. Während jener Zyklen, innerhalb von deren Einzelbitfehler, die eine Korrektur erfordern, festgestellt worden sind, wird die Verarbeitung oder der Arbeitsablauf im Datenverarbeitungsgerät während des Wiedereinschreibteils des Speicherzeitzyklus verzögert, während der Fehler korrigiert wird. Jede der Speichereinheiten eines ganzen Datenverarbeitungssystems ist so ausgebildet, daß sie ihre eigene Fehlererkennungslogik enthält, während jedes Rechenwerk, das mit diesen Speichereinheiten zusammenarbeitet, so ausgebildet ist, daß es die Fehlerkorrekturlogik enthält, wie im einzelnen unten diskutiert wird.

Gemäß der Theorie der Arbeitsweise des Fehlerkorrektur- und Erkennungssystems der Erfindung, das in einem System verwendet wird, das 16-Bit-Datenworte benutzt, wie oben erwähnt, fügt das System zu jedem 16-Bit-Wort ein 5-Bit-Paritätsprüffeld hinzu, während jedes Wort in den Speicher eingeschrieben wird. Wie in Fig.1 gezeigt wird, hat ein Musterwort mit 16 Bits, die als Bits 0 bis 15 bezeichnet sind, zusätzlich fünf Paritätsprüfbits, die darin als Prüfbits CO, CI, C2, C3 und C 4 bezeichnet sind. Die Prüfbits werden in jedem Fall erzeugt durch Berechnung entweder einer ungeraden oder einer geraden Parität quer über das Datenwort, wobei jedes Prüfbit solch eine ungerade oder gerade Parität einer einmaligen Kombination von acht Datenbits des 16-Bit-Datenwortes prüft. Solche Paritätsprüfungen stellen eine einzigartige Modifikation der üblichen Paritätsprüfungen dar, die in einem einfachen Hamming-Code-Prozeß, der bei Fehlererkennungssystemen zur Zeit verwendet wird, durchgeführt werden.

Wie im Diagramm der F i g. 1 gezeigt ist, prüft beispielsweise das erste Prüfbit CO die ungerade Parität der Datenbits 2,5 und 10 bis 15; das Prüfbit Cl prüft die gerade Parität der Datenbits 4 bis 10 und 15; das Prütbit C2 prüft die ungerade Parität der Datenbits 1 bis 3,7 bis 9,14 und 15; das Prüfbit C3 prüft die gerade Parität der Datenbits 0, 2, 3, 5, 6, 9, 12 und 13, und das Prüfbit C4 prüft die ungerade Parität der Datenbits 0,1,3,4,6,8,11, 13. In Fig. 1 bedeuten die mit durchgezogener Linie dargestellten Paritätsprüfungen, die den Prüfbits CO, C2 und C4 zugeordnet sind, »ungerade« Paritätsprüfungen, während die gestrichelten Linien, die den Prüfbits Cl und C3 zugeordnet sind, »gerade« Paritätsprüfungen darstellen. So enthält das im Beispiel gezeigte 21-Bit-Wort, das auf diese Weise erzeugt worden ist, die Muster-Datenbits 0 bis 15 des ursprünglichen 16-Bit-Datenwortes und die Muster-Prüfbits CO bis C4, die von diesen in spezifischer Weise abgeleitet wurden. Das erweiterte 21-Bit-Wort wird dann in den Speicher während eines »Schreib«-Teils des Speicherzyklus geschrieben.

Wenn das erweiterte 21-Bit-Wort, das auf diese Weise geschrieben wurde, anschließend gelesen wird, wird eine einzigartige Paritätsprüfung davon wiederum berechnet, diesesmal für die gesamten 21 Bits, einschließlich der fünf zusätzlichen Paritätsprüfbits CO bis C 4. Die Paritätsprüfungen, die auf diese Weise gemacht werden, sind tatsächlich vergleichbar mit den Paritätsprüfungen, die vorher gemacht wurden, nur umfaßt in diesem Fall jede der Paritätsprüfungen das entsprechende Prüfbit, wie in F i g. 2 gezeigt ist, so daß die Paritätsprüfungen mit Bezug auf 9-Bit-Kombinationen des 21-Bit-Wortes gemacht werden. Die wiederum berechneten Paritäten liefern ein neues 5-Bit-Fehlercodewort, das Fehlerbits £0 bis EA aufweist. So wird das Fehlercodebit EO erzeugt durch eine Paritätsprüfung derselben Bits, die für die Paritätsprüfung, die das Prüfbit CO erzeugte, einbezogen waren, und zusätzlich enthält sie das CO-Bit selbst Dasselbe gilt für jedes der folgenden Fehlercodebits Ei bis EA. Wie vorher werden die Fehlercodebits £"0, E2 und EA erzeugt durch eine »ungerade« Paritätsprüfung, wie sie durch die ausgezogenen Linien angedeutet ist, während die Fehlercodebits El und E3 durch eine »gerade« Paritätsprüfung, wie durch die gestrichelten Linien angezeigt, erzeugt werden.

Für das spezielle in den F i g. 1 und 2 gezeigte Beispiel wurde angenommen, daß ein Fehler im Bit 14 aufgetreten ist, das im ursprünglichen 16-Bit-Wort, wie es eingeschrieben wurde, eine »1« ist, während es indem gelesenen Wort eine »0« ist. Solch ein Einzelbitfehler hat die Erzeugung eines einzigartigen oder eindeutig definierten Fehlercodewortes zur Folge, das in dem zur Diskussion stehenden Fall durch die 5-Bit-Fehlercodebits £"0 bis EA als 10100 dargestellt wird. Die Erzeugung eines 5-Bit-Fehlercodewortes erlaubt die Identifizierung von 32 unterschiedlichen Fehlerzuständen einschließlich eines, in welchem keine Fehler auftraten, 21, bei denen alle Einzelbitfehler des gespeicherten 21-Bit-Wortes nach ihrem Ort identifiziert werden, zwei, bei denen das 21-Bit-Wort, wie es an der betreffenden Speicherstelle gelesen wird, nur Einsen oder nur Nullen enthält (was einen im wesentlichen vollständigen Ausfall der Speichereinheit darstellt), und acht, bei denen die Anwesenheit von Mehrfachbitfehlern angezeigt wird, obwohl ihr Ort nicht speziell identifiziert wird. Eine beispielhafte Tabelle der 32 5-Bit-Fehlercodewörter und der Bedeutung von jeder ihrer einmaligen Codekombinationen ist in Tabelle 1 gezeigt.

	Tabelle 1	Bedeutung
	Fehlercodewort	Kein Fehler
	00000	Fehler war im Prüftbit 4
10	00001	Fehler war im Prüfbit 3
	00010	Fehler war im Datenbit 0
	00011	Fehler war im Prüftbit 2
	00100	Fehler war im Datenbit 1
J)	00101	Fehler war in mehreren Bits
	00110	Fehler war im Datenbit 3
	00111	Fehler war im Prüfbit 1
	01000	Fehler war im Datenbit 4
40	01001	Alle 21 Bits des Speichers sind 1
	01010	Fehler war im Datenbit 6
	01011	Fehler war im Datenbit 7
	01100	Fehler war im Datenbit 8
4Ϊ	01101	Fehler war im Datenbit 9
	OHIO	Fehler war in mehreren Bits
	01111	Fehler war im Prüfbit 0
	10000	Fehler war im Datenbit 11
50	10001	Fehler war im Datenbit 12
	10010	rcilici wdi im l^dicuuii υ
	10011	Fehler war im Datenbit 14
	10100	Alle 21 Bits des Speichers sind 0
55	10101	Fehler war im Datenbit 2
	10110	Fehler war in mehreren Bits
	10111	Fehler war im Datenbit 10
	11000	Fehler war in mehreren Bits
60	11001	Fehler war im Datenbit 5
	11010	Fehler war in mehreren Bits
	11011	. Fehler war im Datenbit 15
	11100	Fehler war in mehreren Bits
65	11101	Fehler war in mehreren Bits
	11110	Fehler war in mehreren Bits
	Hill

Das Fehlerwort, das auf diese Weise bei der Speichereinheil erzeugt worden ist, wird dann der Rechenwerkfehlerkorrekturlogik zugeführt, die eine Decodierlogik zum Decodieren des Fehlercodewortes zur Identifizierung des Ortes des Einzelbitfehlers aufweist. Diese Logik sorgt dann in geeigneter Weise für die Korrektur des fehlerhaften Bits dadurch, daß sie in geeigneter Weise an die identifizierte Stelle ein komplementäres Bit liefert. Zur selben Zeit wird die physische Adresse des falschen Speicherwortes beim Rechenwerk gespeichert. Die Fehlerkorrekturlogik sorgt auch für eine geeignete Unterbrechung der Tätigkeit des Rechenwerks, bis dieser Korrekturprozeß abgeschlossen ist. Das korrigierte Wort wird daraufhin in den speziellen Speichermodul an die korrekte Adresse zurückübertragen und dort wieder eingeschrieben.

Mit Bezug auf die Verwirklichung der Fehlererkennung- und Korrekturlogik bei einer typischen Speichereinheit und bei einem Rechenwerk zeigt F i g. 3 geeignete Abschnitte des Fehlererkennungs- und Korrektursystems, die beide in einer typischen Speichereinheit 10, die beispielsweise eine Speicherebene 13 von 8K Kernspeichervorrichtungen aufweist, und in einem Abschnitt 11 eines Rechenwerks angeordnet sind, wobei die Speichereinheit und das Rechenwerk in geeigneter Weise über eine Speicherübertragungsleitung 12 (SÜL) verbunden sind. Bei dem beschriebenen Ausführungsbeispiel bringt die Rechenwerkfehlerlogik, die im einzelnen später beschrieben wird, die Möglichkeit der Fehlerkorrektur für jede von mehreren Speichereinheiten ohne Geschwindigkeits- oder Leistungsvenrinderung während der nichtkorrigierenden Zyklen.

Die Kernebene 13 der Speichereinheit 10 weist beispielsweise 8K Wörter mit je 21 Bits auf.

Geeignete Leseverstärker 14 liefern Lesebits 0 bis 20 von den Kernspeichervorrichtungen, wobei die letzteren Vorrichtungen durch geeignete X-Y-Tre\ber 15 angesteuert werden, wie dies bei bekannten Datenverarbeitungsspeichereinheiten üblich ist. Jedes aus den Speichervorrichtungen ausgelesene Wort wird in geeigneter Weise in ein 21-Bit-Speicherpufferregister 16 gebracht, zu dem auch ein 16-Bit-Datenwort von der Speicherübertragungsleitung 12 geliefert werden kann, wie gezeigt Das Speicherpufferregister 16 speichert entweder ein Wort von der Speicherübertragungsleitung 12 zum Einschreiben in eine Adreßstelle in der Kernebene 13 oder ein Wort, das von einer Adreßstelle in der Kernebene 13 ausgelesen wurde, zur Eingabe in die Speicherübertragungsleitung 12 über die Speicherübertragungsleitungstreiber 17.

Ein Codegenerator 18, dem ebenfalls die Datenbits 0 bis 15 zugeführt werden, weist eine Logik zur Berechnung der Paritätsprüfung dieser Bits auf, wie oben diskutiert wurde, um die fünf Paritätsprüfwortbits 16 bis 20 (entsprechend den Prüfbits CO bis CA) zu erzeugen. Wenn die Codegeneratorlogik ihre Paritätsprüfung der Bits 0 bis 15 während einer ursprüngBchen Schreiboperation macht, werden die Prüfbits 16 bis 20 zum Speicherpufferregister 16 und hierauf zu der Kernebene 13 zusammen mit den Speicherdatenbits 0 bis 15 über die Inhibitlogik 19 übertragen. Während einer Leseoperation macht der Codegenerator seine Paritätsprüfung von allen Bits 0 bis 20, die aus der Kernebene gelesen werden, einschließlich der Speicherdatenbits 0 bis 15 und der Prüf bits 16 bis 20. Eine derartige Paritätsprüfungsoperation erzeugt die Fehlercodebits EO bis £4 zur Lieferung an einen Korrekturdecoder 20 der Fehlerlogik des Rechenwerks.

Die Speichereinheit weist auch ein Speicheradreßregister 21 zur Speicherung von Adressen, wie sie von > einer Adreßübertragungsleitung 22 (AÜL) erhalten werden, auf. Der Korrekturdecoder 20 beim Rechenwerk decodiert die Fehlercodebits £0 bis £4 und macht eine geeignete Korrektur an der identifizierten Bitstelle, wenn ein Einzelbitfehler aufgetreten ist, wie oben

in diskutiert, und anschließend liefert er ein korrigiertes Datenwort, bezeichnet als COR (0—15), um es an die Datenverarbeitungselemente im Rechenwerk über ein Exclusiv-ODER-Glied 23 zu liefern. Wenn keine Korrektur erforderlich ist, wird das Datenwort, wie es aus der Kernebene ausgelesen wird, zu den Datenverarbeiiungselemenlen des Rechenwerks direkt vor· der Speicherübertragungsleitung über das Glied 23 geleitet, wie gezeigt. Die Adresse des Ortes des falschen Datenwortes wird in geeigneter Weise in einem

2(i Speicherfehleradreßregister 24 gespeichert, während das Fehlercodewort £0 bis £4 aus dem Speicher ebenfalls in geeigneter Weise in einem Speicherfehlercoderegister 25 gespeichert wird, wie gezeigt, wobei diese Adreß- und Fehlercodeinformation ebenfalls zu

2Ί den geeigneten Datenverarbeitungselementen des Rechenwerks geleitet wird, wie unten näher beschrieben wird. Die Speichereinheit weist auch eine geeignete Fehlerkorrektursteuerlogik 27, die im Detail weiter unten beschrieben wird, zur Steuerung der Operation

jo der Elemente der Speichereinheit auf, die an der Fehlerkorrekturoperation teilnehmen. Das Fehlerkorrekturladesignal (ECCLOAD), das Paritätsaktiviersignal (PAR ΕΝΑΒ)\χηά das Schreibinhibitsignal (WINH) werden für diesen Zweck durch das Rechenwerk

r, geliefert, wie im einzelnen unten beschrieben wird.

Die F i g. 4 bis 7 zeigen genauer die Logik, die in einer typischen Speichereinheit verwendet wird. So sind in F i g. 4 das Speicherpufferregister 16 und der erweiterte Pufferregisterabschnitt davon für die Speicherbits 16 bis 20 gezeigt, das sechs 8-Bit-Register 30 bis 35 aufweist. Jedem der Register 30 bis 33 werden vier A/£M-Bit-Eingangssignaie des 16-Bit-Wortes MEMO—15 von der Speicherübertragungsleitung 12 und vier entsprechende Speicherortlesesignale (SO-SiS) zugeführt, zusammen mit einem Taktpulssignal, das bezeichnet wird als das SpeicherpufferladesignalYMÄLO/iD^ zum rechtzeitigen Aufladen der Register. Die Register haben die Eigenschaft, beim Beginn eines jeden Speicherzyklus mit einem geeigneten Speicherzyklussignal (MEMCY- CLE) und ebenfalls mit einem geeigneten Signal zum Löschen des Registers vor einem Lesezyklus (MB PRE- SET) zurückgesetzt zu werden. Die Ausgangssignale der Register 30 bis 33 werden als Speicherpuffersignale MBO-MBiS bezeichnet, und jedes wird zu einem

getrennten Speicherübertragungsleitungstreiber

(ODER-Glied) 36, wie gezeigt, geleitet Jedes der UND-Glieder 36 wird durch ein DATAENABLE-Signal aktiviert, das Daten auf die Übertragungsleitung bringt, ausgenommen, wenn das Signal ECCLD die Treiber von der Übertragungsleitung abschaltet und hierdurch zeigt, daß ein Fehlerkorrekturzyklus im Rechenwerk ausgeführt werden muß.

Ebenfalls mit mehr Einzelheiten ist in Fig.4 das erweiterte Speicherpufferregister gezeigt, das ein Paar von 8-Bh-Registern 34 und 35 aufweist, die mit dem Speicher durch Leseleitungen 516—520 und fünf Leitungen vom Paritätsschaltkreis 50 (in F i g. 5 gezeigt) verbunden sind, wobei die Signale auf den letztgenann-

ten fünf Leitern die fünf Paritätsprüfbits CO bis C4 darstellen, wie mehr im einzelnen unten mit Bezug auf F i g. 5 diskutiert wird. Das Signal MB PRESET wird benutzt, um aus den Registern 34 und 35 die Lesebits 516 — 520 vor einem Lesezyklus zu löschen. Das Signal WINH wird für eine Software-Prüfung des Signals benutzt und bewirkt, wenn es benutzt wird, daß alle Ausgangs-Bits MB 16 — MB 20 »1« sind, wenn das Signal WINHniedrig ist. Die Register 34 und 35 werden in einer Art ähnlich der oben mit Bezug auf die Register 30 bis 33 diskutierten ebenfalls durch das Signal MB LOAD getaktet, wenn das letztere Signal niedrig ist. Aber das Signal MB LOAD wird in Verbindung mit den Registern 34 und 35 durch einen Verzögerungsschaltkreis 38 für eine Zeit verzögert, die ausreicht, um dem Paritätsschaltkreis 50 zu gestatten, die fünf Paritätsprüfbits aus den Signalen MBO-MB 15 zu erzeugen. Die Ausgangssignale der Register 34 und 35 werden als Bits Mßl6-Mß20 bezeichnet.

F i g. 5 zeigt die Paritätsschaltkreise 50, die in der Speichereinheit angeordnet sind, wie dies auch die in F i g. 4 gezeigte Speicherpufferregisterschaltung ist. Der Paritätsschaltungskreis 50 schließt fünf Exclusiv-ODER-Glied-Register 51 bis 55 ein, von denen jedes aus einem separaten Halbleiterplättchen mit neun Eingangsleitungsanschlüssen und zwei Ausgangsleitungsanschlüssen besteht. Diese Halbleiterplättchen können beispielsweise von dem Typ sein, der als Modell-Nr. 74S280 verkauft wird, und sind leicht als Elemente nach dem gegenwärtigen Stand der Technik für die Benutzung beim Erfindungsgegenstand erhältlich.

Wie noch klar werden wird, wirken diese Verknüpfungseinheiten nicht nur als Generatoren für Prüfbits mit ungerader/gerader Parität, sondern auch als Prüfsignalgeneratoren. Die Ausgangsleitungen, die die Bits CO-C5 von jedem der Exclusiv-ODER-Glied-Register 51 bis 55 darstellen, sind zurück zu den Registern 34 und 35 (siehe Fig.4) verbunden und liefern die erzeugten Paritätsbits, wodurch in einer Schreiboperation diese Paritätsbits aus den Registern 34 und 35 durch Taktsignale herausgeholt werden zu einer Zeit, die durch das zeitverzögerte MBL~O~ÄB-S\gn&\ bestimmt ist, um die Speicherpufferregistersignale MB 16 - MB 20 zu erzeugen.

Diese Paritätsbits, die in dem erweiterten Speicherpuffer 16, wie in F i g. 1 gezeigt, gespeichert werden, werden wieder während eines Lesezyklus unmittelbar vor einer Datenübertragung geprüft. Wenn die Oberprüfung der Paritätsbits abgeschlossen ist mit dem Ergebnis, daß sie richtig sind (d. h., es existieren keine Fehler), werden die Daten vom Speicherpufferregister 16 dann durch die aktivierten Speichertreiber 36 in die Speichervoi richtungen der Speichereinheit geleitet. Die Verwendung von fünf üblichen und leicht verfügbaren Exclusiv-ODER-Glied-Registern des Typs mit neun Eingängen, wie in Fig.3 gezeigt, vermeidet das Erfordernis von speziell entwickelten und teuren Elementen, die mehr als neun Eingänge haben, was normalerweise bei der üblichen Verwirklichung einer Hamming-Code-Fehlerkorrektur erforderlich ist Dieser Vorteil ist die Folge der Benutzung eines modifizierten Codes vom Hamming-Typ, bei dem die Paritätsprüf bits aus ausgewählten 8-Bit-Kombinationen des ursprünglichen 16-Bit-Datenwortes erzeugt werden und bei. dem die Fehlercodewortbits erzeugt werden durch Paritätsprüfungen von ausgewählten 9-Bit-Kombinationen des erweiterten Wortes mit 21 Bit, wie es gespeichert wird, wie oben beschrieben wurde. Der modifizierte Code vom Hamming-Typ wird entsprechend durch die Exclusiv-ODER-Glieder mit den geeigneten Kombinationen der Eingangssignale, wie in F i g. 5 illustriert, verwirklicht.

Die fünf Exclusiv-ODER-Glied-Register 51 bis 55 sind ebenfalls mit den Ausgängen MB i6 —MB 20 über NAND-Glieder 56 bis 60 verbunden, wobei zu jedem der NAND-Glieder weiterhin das Signal MBLOAD geführt wird, wodurch die Signale MB\6 — MB20

κι durchgeschaltet werden, wenn das Signal MBLOAD hoch ist. Wenn das Signal MB LOAD niedrig ist, haben die Paritätsbits MB 16-MB 20 keinen Einfluß auf die Erzeugung der neuen Paritätsbits EO-E4. Wie dargestellt ist, ist jedes der Exclusiv-ODER-Glieder 51

ι j bis 55 mit einem entsprechenden NAND-Glied 61 bis 65 verbunden, welche Glieder gemeinsam aktiviert werden durch ein invertiertes UND-Glied 66, das als Eingangssignale das Signal MB LOAD und ein Signal INVALID- DATA hat. Die Ausgangssignale der NAND-Glieder 61 bis 65 liefern die Paritätsfehlercodebits EO-E4, wie oben diskutiert wurde.

Die Eingangssignale der NAND-Glieder 61 bis 65 werden auch zu einem NOR-Glied 67 während der Leseoperation geleitet. Wenn der Speicher einen Fehler

: > feststellt, muß die Operation des Rechenwerks gestoppt werden, bis eine Korrektur durchgeführt worden ist, und die Korrektur muß am Speicher sofort erfolgen. Wenn ein Fehler festgestellt wird, wird eines der Eingangssignale des ODER-Gliedes 67 niedrig und das Eingangssi-

i(i gnal des Elements 68 ist niedrig, um anzuzeigen, daß ein Lesevorgang im Gange ist. Das Ausgangssignal eines UND-Gliedes 69A ist hoch und wenn das Signal PAR ENAB vom Rechenwerk ebenfalls hoch ist (das anzeigt, daß eine Paritätsprüfung gemacht werden

i> sollte, um die Anwesenheit von Fehlern zu untersuchen), wird ein Signal Λί51 am Ausgang eines Gliedes 69 ß erzeugt, welches Signal zum Rechenwerk geleitet wird, um dessen Operation zu stoppen, während der Leseteil des Speicherzyklus im Gange ist, aber bevor das

Mi Rechenwerk den Lesezyklus vollendet. Wenn die Korrektur durchgeführt worden ist und die korrigierten Daten in den Speicher wieder eingeschrieben worden sind (d. h., das Signal MBLOAD liegt am Glied 66 vor), wird das Signal M51 abgeschaltet, um dem Rechenwerk zu gestatten, seine Leseoperation fortzuführen und dann das korrigierte Wort wie gewünscht zu lesen.

Die F i g. 6 bis 8 zeigen die Fehlerkorrekturlogik, die

im Rechenwerk angeordnet ist, wie F i g. 3 zeigt. So wird in F i g. 6 einem Zeitgebergenerator 70 ein Eingangssi-

gnal über ein ODER-Glied 71 zugeführt, und diesem letzteren Glied werden als Eingangssignale jedes der Fehlerbits EO-E4 zugeführt Wenn kein Fehler aufgetaucht ist, ist das Ausgangssignai des ODER-Gliedes 71 niedrig, so daß der Fehlerkorrekturzeitgebergenerator, der normalerweise fortlaufend durch den Zeitgeber des Systems getaktet ist keine Fehlerkorrek turzeitsignale Ti und T2 erzeugt Wenn jedoch ein Fehler vorgekommen ist, so daß irgendeines der Fehlerbits E0-E4 niedrig ist, nimmt das Ausgangssi gnal des ODER-Gliedes 71 einen hohen Wert an, um die Anwesenheit eines solchen Fehlers anzuzeigen, und der Zeitgebergenerator 70 wird derart aktiviert, daß er das Ausgangssignal Π auf einen hohen Wert setzt Dies zeigt den Beginn eines Fehlerkorrekturzyklus an, wie unten diskutiert wird, wobei Ti auch über ein UND-Glied 72 zurückgekoppelt wird, um das Zeitsignal T2 zu setzen, wobei das Ende des letzteren Signals das Ende des Fehlerkorrekturzyklus anzeigt Wenn 77 am

ODER-Glied 73 in F i g. 7 einen niedrigen Wert annimmt, wobei das Ausgangssignai dieses ODER-Gliedes die Korrekturregister 74 bis 77 taktet (Register 77 ist in Fig. 8 gezeigt), nimmt das Ausgangssignal des ODER-Gliedes 73 einen hohen Wert an, und diese Register werden getaktet, so daß der augenblickliche Zustand der Speicherübertragungsleitung, einschließlich der Datenbits MEMO-¹MEMXS und die Fehlerbits £0 —£4 in diese Register eingerastet werden.

Zur gleichen Zeit wird Π zu einem UND-Glied 78 geführt, um das Fehlerkorrekturladesignal ECCLOAD *.u erzeugen, das zurück zur Speichereinheit geleitet wird um anzuzeigen, daß der Fehlerkorrekturzyklus begonnen hat.

Die Speichereinheit liefert anschließend ein geeignetes Signal zum Stoppen der Operation des Rechenwerks (d. h., soweit es sich nicht um die Operation der Fehlerkorrekturschaltung handelt) während des Fehlerkorrekturzyklus. Dieses Signal ist hier beispielsweise als das MSI-Signal in der Speichereinheit bezeichnet, wie oben mit Bezug auf die Fig. 5 gezeigt und diskutiert wurde.

Wenn das Signal T1 einen hohen Wert annimmt, wird die Fehlerkorrekturschaltungsanordnung im Rechenwerk entsprechend aktiviert, um den Fehler zu korrigieren, der in dem in Frage stehenden Datenwort aufgetaucht ist, welches Datenwort in die Fehlerkorrekturregister 74 bis 76 eingespeichert worden ist, wie in Fig.8 gezeigt ist und unten näher diskutiert wird. Das Signal ECC LOAD schaltet die Speichertreiber in der Speichereinheit von der Speicherübertragungsleitung, wie in F i g. 4 gezeigt ist, zu der Zeit ab, zu der das Wort MEMO-MfMTB, das den Fehler enthält, und die Fehlerbits EO-E4 in die Fehlerkorrekturregister eingerastet werden. Ein UND-Glied 79 (siehe Fig. 7) setzt die Fehlerkorrekturschaltungsanordnung in Verbindung mit der Speicherübertragungsleitung, wenn das Zeitsignal 7"1 beim Beginn des Fehlerkorrekturzyklus einen hohen Wert annimmt, wenn einmal der Speicher von der Speicherübertragungsleitung abgeschaltet worden ist. Eine derartige Verbindung findet über die Treiber 80 mit offenem Kollektor der Korrekturschaltungsanordnung statt.

Wenn einmal die Speicherbits in die Fehlerkorrekturregister eingerastet sind, arbeiten die Decoderlogikeinheiten 81 bis 85, wie in F i g. 8 gezeigt, um die modifizierten Hamming-Code-Bits, die durch die Bits £0 —£4 dargestellt werden, zu decodieren, wie oben mit Bezug auf Tabelle 1 diskutiert wurde, und um dadurch in geeigneter Weise zu identifizieren, welches der 16 Bits des Datenwortes, das in die Register 74 bis 76 eingerastet wurde, korrigiert werden muß. Eine

uürcn die

Erzeugung der Korrekturbits CORO-COR 15 durch die Logikeinheiten 83, 84 und 85. Die letzteren Korrekturbits werden zu NOR-Gliedern 87 (F i g. 7) an dem Ausgang der Korrekturregister 74 bis 76 geliefert. Entsprechend dem Decodierprozeß nimmt das richtige Bit der Korrekturbits CORO-COR15 einen niedrigen Wert an, und der Ausgang seines entsprechenden Exclusiv-ODER-GIiedes 87 liefert ein Bit das das Komplement des entsprechenden Bits ist welches in das Korrektursystem beim Korrekturregister eingerastet worden war (d.h., eine »1« für eine »0« oder umgekehrt). Die korrgierten Daten werden dann über die Treiber 80 auf die Speicherübertragungsleitung 12 gegeben. Die Speichereinheit wird dann in geeigneter Weise aktiviert, um die von der Speicherübertragungsleitung empfangenen, korrigierten Daten wieder einzuschreiben. Die Operation der Speichereinheit, dies sollte wiederholt werden, war wegen der Anwesenheit eines ι Fehlerkorrekturladesignals ECC LOAD angehalten worden, nachdem die Speichereinheit den »Lese«-Teil des Speicherzyklus vollendet hatte und vor dessen »Wiedereinschreib«-Teil. Bei der Reaktivierung der Speichereinheit, die der Korrektur des Fehlers folgt, ίο werden die korrigierten Daten anschließend wieder in den Speicherkern während des »Wiedereinschreib«- Teils des Speicherzyklus eingeschrieben.

Das Ausgangssignal des ODER-Gliedes 71 am Zeitgebergeneralor 70 wird niedrig, und der Zeitgeberi) generator 70 wird demgemäß zurückgesetzt. Zu dieser Zeit werden die korrigierten Daten zu der geeigneten Logik, wie erforderlich, im Rechetiwetk übertragen und auch zum Speicher, worauf der Speicher die korrigierten Daten in dem Kern an der richtigen Stelle wieder o einschreibt. Wenn ein Fehler entdeckt worden ist und der Wunsch besteht, eine permanente Aufzeichnung des Ortes des Woites, in dem der Fehler aufgetreten ist, an geeigneten Eingabe-/Ausgabe-(/O-)Geräten außerhalb des Systems über geeignete /O- Daten verbindungen 2Ί verfügbar zu machen, kann die Adresse in Registern 90, wie in Fig.9 gezeigt, über ein geeignetes Taktsignal gespeichert werden. Nach geeigneter Aktivierung von /OTreibern 91 kann die Adreßinformation zu einer geeigneten /O-Übertragungsleitung zur externen Bej(i nutzung, wenn gewünscht, geliefert werden.

Ein Paar von Flip-Flop-Registereinheiten 95 und 96, wie in Fig. 10 gezeigt, erlaubt die Operation des Fehlerkorrektursystems in je einer von vier Betriebsarten. Bei der Betriebsart 0 ist keines der Flip-Flops ü gesetzt, und die Fehlerkorrektur ist in einem nicht betriebsbereiten Zustand gehalten, in dem keine Korrektur und keine Unterbrechung des Rechenwerks stattfinden können. In der Betriebsart 1 ist das Flip-Flop 95 nicht gesetzt, während das Flip-Flop % gesetzt ist. In 4(i dieser Betriebsart ist das Korrektursystem nicht betriebsbereit gehalten, aber es wird ein Untersuchungsbetrieb für einen Prüfvorgang des Fehlersystems ausgeführt. So wird bei einem Schreibteil des Speicherzyklus das System einen vorhersehbaren Satz von Prüfbits zur Simulation eines Fehlers lediglich für diagnostische Zwecke liefern.

In der Betriebsart 2 ist das Flip-Flop 95 gesetzt, während das Flip-Flop 96 nicht gesetzt ist. Dies bedeutet im Ergebnis eine Art der Inbetriebnahme, ;■} wobei das Fehlerkorrektursystem in einem betriebsfähigen Zustand ist, aber keine Unterbrechung des Rechenwerks erfolgen kann, wenn die Fehlerprüfung durchgeführt wird.

Bei der Betriebsart 3 sind beide Flip-Flops gesetzt, und das Fehlerkorrektursystem ist betriebsfähig, und die Unterbrechungslogik 97 ist aktiviert, um es zu gestatten, daß die Tätigkeit des Rechenwerks für Fehlerprüfzwekke unterbrochen wird, obwohl seine Tätigkeit nicht vollständig angehalten wird, wie in dem Fall, wenn das Signal MSl für solch einen Zweck während eines vorliegenden Fehlerkorrekturprozesses vorhanden ist Die in den einzelnen Figuren gezeigten Schaltungen sind teilweise in der obigen Beschreibung nicht im einzelnen erläutert In diesen Fällen müssen die Schaltungseinzelheiten den Zeichnungen entnommen werden. Die in den Zeichnungen und in der Beschrei bung vorkommenden Signalbezeichnungen sind der aus dem Amerikanischen stammenden Rechner-

Fachsprache entnommen. Dies gilt auch für einige in der Beschreibung nicht erscheinende Bezeichnungen von Schaltkreisen.

In der Darstellung der F i g. 6 ist das ODER-Glied 71 durch mehrere zusammengezeichnete ODER-Glieder dargestellt, von denen in der Zeichnung lediglich ein Ausgang mit einem Eingang des Zeitgebergenerators 70 verbunden ist Diese vereinfachte zeichnerische Darstellung ist in der Weise zu verstehen, daß die einzelnen Ausgänge der ODER-Glieder aile mit dem Eingang des Zeitgebergenerators 70 verbunden sind. Diese vereinfachte Darstellung wurde deswegen gewählt, weil die Glieder üblicherweise auf einem einzigen Halbleiter-

plättchen angeordnet sind und die geschild Verbindungen der Ausgänge mit den Eingängen nachfolgenden Schaltung intern vorgenommen sine In F i g. 7 werden die Bits eines Wortes, das korri werden soll, zu den Gliedern 87 gemeinsam entsprechenden Korrekturbits von den Logikeinh 83 bis 85 geleitet, so daß das Komplement des fals Bits geliefert werden kann. Die zusammengezeich Glieder 80 und 87 in F i g. 7 und die zusammenge; neten Glieder in F i g. 8 wirken als getrennte Gliedi sind deswegen zusammengezeichnet, weil sie au< einem gemeinsamen Halbleiterplättchen untergeb werden können.

Hierzu 9 Blatt Zeichnungen

Claims (3)

1 2 η . ♦ ·· u«, 4. Einrichtung nach einem der Ansprüche 1 bis 3, Patentansprüche: 6 . , „ ,. γ ,. dadurch gekennzeichnet, daß die Fehlercodierein-

1. Fehlererkennungs- und Korrektureinrichtung richtung fünf Exklusiv-ODER-Glied-Register (51 bis für Datenverarbeitungsgeräte mit mindestens einem 55) aufweist, von denen jedes neun Eingänge Rechenwerk, mindestens einer Speichereinheit und > aufweist, und auf die fünf 8-Bit-K.ombinationen, die einer Fehlercodiereinrichtung bei jeder Speicherein- während des Schreibteils des SpeicherzyWus ausgeheit zur Durchführung von Paritätsprüfungen wählt wurden, und auf die fünf 9-Bit-Kombiiiationen, während des Schreibteils eines Speicheroperations- die während des Leseteils des Speicherzyklus zyklus bei einer vorbestimmten Anzahl von ver- ausgewählt wurden, anspricht, um die fünf Paritätsschiedenen ausgewählten Bit-Kombinationen glei- io prüfbits bzw. die fünf Fehlerbits zu liefern.

eher Bit-Anzahl in jedem Datenwort, wobei die 5. Einrichtung nach einem der vorhergehenden Paritätsprüfungen eine Anzahl von je einer ausge- Ansprüche, bei dem die Bits der 16-Bit-Datenwörter wählten Kombination zugeordneten Paritätsprüf- als Bits 0 bis 15 bezeichnet sind, dadurch Bits liefern; und mit einer Einrichtung zur Bildung gekennzeichnet, daß die Fehlercodiereinrichtung eines erweiterten Datenwortes, das die Daten-Bits 15 Mittel zur Durchführung von Paritätsprüfungen bei des Datenwortes und die Paritätsprüf-Bits umfaßt, den folgenden fünf ausgewählten Kombinationen und zum Speichern des erweiterten Datenwortes in von acht Bits des 16-Bit-Datenwortes aufweist:
der Speichereinheit; wobei die'Fehlercodiereinrich- (1) Bits 2,5,10, U, 12,13, Hund 15;
tung derart ausgebildet ist, daß sie während des (2) Bits 4,5, 6, 7, 8, 9,10 und 15;
Leseteils eines Speicheroperationszyklus Paritäts- -'<> (3) Bits 1,2, 3, 7, 8, 9,14 und 15;
prüfungen bei der gleichen vorbestimmten Anzahl (4) Bits 0,2, 3, 5, 6, 9,12 und 13; und
ausgewählter Bit-Kombinationen des Datenwortes (5) Bits 0,1, 3, 4, 6, 8,11 und 13.
durchführt und eine Anzahl von Fehler-Bits erzeugt, 6. Einrichtung nach Anspruch 5, dadurch gekennwobei jede derartige ausgewählte Kombination die zeichnet, daß die Paritätsprüfungen bei den ausgegleiche Kombination von Daten-Bits, wie sie :~> wählten Kombinationen (1), (3) und (5) ungerade während des Schreibteils ausgewählt wurde, sowie Paritätsprüfungen sind und die Paritätsprüfungen das zugehörige Paritätsprüf-Bit aufweist; wobei bei den ausgewählten Kombinationen (2) und (4) ferner das Rechenwerk eine Decodiereinrichtung gerade Paritätsprüfungen sind,
aufweist, die auf die Fehler-Bits anspricht und das 7. Einrichtung nach einem der vorhergehenden Vorhandensein und den Ort eines Ein-Bit-Fehlers im s<i Ansprüche, dadurch gekennzeichnet, daß die Deco-Datenwort feststellt, und eine auf die Decodierein- diereinrichtung auf die fünf Fehlerbits anspricht zur richtung ansprechende Korrekturvorrichtung zum Bestimmung von 32 Zuständen in bezug auf das Korrigieren des Ein-Bit Fehlers im Datenwort erweiterte Datenwort mit 21 Bit, wobei diese vorgesehen ist, dadurch gekennzeichnet, Zustände einschließen: (a) einen Zustand, bei dem daß die Fehlercodiereinrichtung (16, 18) derart i"> kein Fehler vorliegt; (b) 21 Zustände, bei denen ein ausgebildet ist, daß die während des Schreibteils und Einzel-Bit-Fehler vorliegt; (c) zwei Zustände, bei des Leseteils ausgeführten Paritätsprüfungen für denen das erweiterte Datenwort mit 21 Bit nur eine erste Gruupe der ausgewählten Bit-Kombina- Einsen und nur Nullen enthält; und (d) acht Zustände, tionen bzw. dieser Bit-Kombinationen zuzüglich des bei denen Mehrfach-Bit-Fehler vorliegen,
zugehörigen Paritätsprüf-Bits eine ungerade Pari- ■;» b. Einrichtung nach einem der vorhergehenden tätsprüfung ist, und für eine zweite Gruppe eine Ansprüche, dadurch gekennzeichnet, daß die Decogerade Paritätsprüfung. diereinrichtung auf die fünf Fehlerbits anspricht zur

2. Einrichtung nach Anspruch 1, dadurch gekenn- Erzeugung eines Korrekturwortes mit 16 Bit, wobei, zeichnet, daß von den Paritätsprüf-Bits eines wenn ein Einzel-Bit-Fehler in einem Datenwort Prüfbitwortes das erste mit ungerader, das zweite ^J> aufgetreten war, ein Bit in einem ersten ausgewählmit gerader, das dritte mit ungerader usf. Paritäts- ten Zustand und alle anderen Bits in einem zweiten prüfung berechnet wird, oder umgekehrt. ausgewählten Zustand sind, und wobei das eine Bit

3. Einrichtung nach Anspruch 1 oder 2, bei der das sich an einem Ort befindet, der dem Ort des Datenverarbeitungssystem Datenworte mit 16 Bit genannten Einzel-Bit-Fehlers entspricht; und daß die verwendet, dadurch gekennzeichnet, daß die Fehler- "><> Korrekturvorrichtung auf das 16-Bit-Korrekturwort codiereinrichtung während des Schreibteils eines anspricht, um das Bit an der Stelle, die der Stelle Speicherzyklus fünf Paritätsprüfungen bei fünf eines Einzel-Bit-Fehlers entspricht, zu korrigieren,
ausgewählten 8-Bit-Kombinationen der 16 Bits eines 9. Einrichtung nach einem der vorhergehenden Datenwortes ausführt, um fünf Paritätsprüfbits (CQ Ansprüche, dadurch gekennzeichnet, daß die Korbis CA) zu erzeugen; daß die Einrichtung (16) zur r> rektureinrichtung die Korrektur durch Komplemen-Bildung eines erweiterten Datenwortes ein erweiter- tärbildung des falschen Bits durchführt und weitertes Datenwort mit 21 Bit bildet, das die 16 Bits des hin Mittel zum Wiedereinschreiben des korrigierten Datenwortes und die fünf Paritätsprüfbits aufweist; 16-Bit-Datenwortes in die Speichereinheit aufweist,
daß die Fehlercodiereinrichtung weiterhin während

des Leseteils eines Speicherzyklus fünf Paritätsprü- *>o
fungen bei fünf ausgewählten 9-Bit-Kombinationen
des erweiterten Datenwortes mit 21 Bit durchführt,
wobei jede 9-Bit-Kombination acht Bits aufweist, die
der 8-Bit-Kombination entsprechen, die während

des Schreibteils des Speicherzyklus ausgewählt <" Die Erfindung betrifft eine Fehlererkennungs- und

wurde und die weiterhin das dieser zugeordnete Korrektureinrichtung nach dem Oberbegriff des An-

Paritätsprüfbit aufweist, wodurch fünf Fehlerbits Spruchs 1. Ein derartiges System zur Fehlererkennung

(EO bis EA) geliefert werden. und Fehlerkorrektur ist jedenfalls im Prinzip durch IBM