DE2132565A1 - Umsetzer - Google Patents

Description

Aktenzeichen der Anmelderin: Docket YO 969 065

Umsetzer

Die Erfindung betrifft einen Umsetzer zum Umsetzen von Informationswörtern, die in einem die Korrektur eines Einzelfehlers und das Erkennen eines Doppelfehlers ermöglichenden Code vorliegen, in in Bitgruppen (Bytes) unterteilte Informationswörter, bei denen jedes Byte ein Paritätsbit aufweist, und zur in umgekehrter Richtung erfolgenden Umsetzung von zu speichernden Informationswörtern und zur Prüfung der ausgelesenen bzw. einzuschreibenden Wörter.

Während vieler Jahre ist in der Computerindustrie der dreidimensionale Magnetkernspeicher als schneller Arbeitspeicher verwendet worden. Den Magnetkernspeichern und ihren Herstellungsverfahren ist ein hoher Grad von Zuverlässigkeit eigen. Dies bedeutet, daß es äußerst selten vorkam, daß ein Magnetkernspeicher nach der Herstellung nicht hundertprozentig benutzbar war. Dies liegt an einer Reihe von Faktoren. Der wichtigste ist der, daß jede einzelne Bitspeicherstelle oder jeder Kern vor dem Einbau in den Speicher getrennt prüfbar ist.

109883/1616

Daher sind einzelne fehlerhafte Bitstellen in Magnetkernspeichern ungewöhnlich. Die in ihnen normalerweise auftretenden Fehlerarten beziehen sich auf eine vollständige Zeile oder Spalte des Speichers aufgrund von Fehlern in den Treiberschaltungen oder der Verdrahtung.

Seit dem Aufkommen neuerer, äußerst kurze Zugriffszeiten aufweisender Halbleiterspeicher, die gewöhnlich als integrierte Speicher bezeichnet werden, ist es normalerweise nicht möglich, die einzelnen Bitspeicherstellen zu prüfen, da gewöhnlich eine ganze Ebene mit Speicherelementen gleichzeitig hergestellt wird. Aufgrund des Herstellungsproaesses eines derartigen integrierten Halbleiterspeichers kann ein derartiger Speicher normalerweise nicht eher geprüft werden als er vollständig hergestellt ist. Es ist daher nicht möglich, einzelne fehlerhafte Bitspeicherelemente durch fehlerfreie zu ersetzen. Es ist daher ersichtlich, daß es erwünscht ist, in integrierten Halbleiterspeichern einen bestimmten Prozentsatz fehlerhafter Bitspeicherelemente zu tolerieren. Um die Benützung fehlerhafter Bitspeicherelemente zu verhindern, ist nach dem Stand der Technik ein großer Aufwand an Bauteilen und Programmierung für die Speicherzuteilung erforderlich. Zu diesem Verfahren mußte man jedoch im Falle vieler Fehler in einem solchen Halbleiterspeicher, in dem ein größerer Teil unbrauchbar ist, greifen. Eine andere Möglichkeit besteht in der Verwendung fehlerkorrigierender Codes, wie z. B. der Hamming-Codes, wobei einem Datenwort Redundanzbits beigegeben werden, und durch Kombination der Datenbits mit den Redundanzbits kann festgestellt werden, ob ein ausgelesenes Datenwort fehlerfrei ist und ob erkannte Fehler aufgrund der Codeeigenschaften korrigiert werden können. Das Codierverfahren nach Hamming hat in der Nachrichtentechnik vielfache Anwendung gefunden. Auf dem Feld der Datenverarbeitung hat die Fehlererkennung und -korrektur nur begrenzte Anwendung gefunden, weil zusätzliche Bitspeicherstellen erforderlich sind und umfangreiche zusätzliche Verknüpfungs-

Docket YO 969 065 109883/1616

schaltungen, um die Fehlererkennung und -korrektur durchzuführen.

Es sei bemerkt, daß in einem Datenverarbeitungssystem Paritätsprüfungen erforderlich sind, um die Fehlerfreiheit der zu den verschiedenen Teilen der Anlage, wie den Registern und Rechenschaltungen, übertragenen Daten zu prüfen. Wenn ein Paritatsfehler erkannt wird, wird ein Signal erzeugt und eine neue übertragung der Daten gefordert. In der Mehrheit aller Fälle erhält man dadurch die richtige Information. Bei Speichern jedoch, bei denen ein Fehler normalerweise nicht durch Störimpulse, wie in dem eben genannten Fall, verursacht ist, liefert eine Paritätsprüfung zwar eine Fehleranzeige, aber da die meisten Fehler durch fehlerhafte Schaltungsteile verursacht werden, gibt es keine Möglichkeit, mit Hilfe der Paritätsprüfung das fehlerhafte Speicherelement zu lokalisieren. Aus diesem Grunde muß ein fehlerkorrigierender Code, wie beispielsweise ein Hamming-Code benutzt werden, wenn eine Fehlerkorrektur erfolgen soll. Wie bereits erwähnt, erfordert die Mehrheit der in der Datenverarbeitungsindustrie angewandten Fehlerkorrekturverfahren umfangreiche und teure Verknüpfungsschaltungen. Außerdem mußten in den meisten Fehlererkennungs- und -korrekturschaltungen besondere Paritätsgeneratoren zusätzlich zu der Fehlererkennungs- und -korrekturschaltung verwendet werden, um aus einem Speicher stammende Daten, die zu einer anderen Stelle der Datenverarbeitungsanlage übertragen werden sollten, mit einem Paritätsbit zu versehen. Ferner mußte eine Schaltung vorgesehen werden, die die erforderlichen Prüfbits für jedes in den Speicher einzuschreibende Wort erzeugte. Daher ist ersichtlich, daß für die Fehlererkennungs- und -korrekturschaltung sowie die verschiedenen Schaltungen zur Paritätsbiterzeugung und Paritätsprüfung eine große Anzahl logischer Schaltungen erforderlich war, da bisher die genannten Schaltungen alle als besondere Einheiten ausgeführt wurden.

109883/1616

Docket YO 969 065

' Aus den genannten Gründen wurden Pehlererkennungs- und -korrekturschaltungen bisher nur in sehr teuren und hochgradig zuverlässigen Datenverarbeitungsanlagen eingebaut, bei denen der Benutzer den notwendigen hohen Preis zu zahlen gewillt war.

Der Erfindung liegt die Aufgabe zugrunde, den für eine Fehler-, erkennungs- und -korrekturschaltungen erforderlichen Aufwand zu verringern. Die genannte Aufgabe wird durch einen Umsetzer der eingangs genannten Art gelöst, der durch folgende Merkmale gekennzeichnet ist:

a) ein erstes Register zum wahlweisen Speichern entweder von aus einem Speicher gelesenen Daten- und Prüfbits oder von. in den Speicher einzuschreibenden Daten- und Byteparitätsbits,

b) mehrere erste mehrstufige EXKLUSIV ODER-Schaltungen zur Erzeugung von Redundanzbits (Prüfbits bzw. Paritätsbits), deren Eingänge jeweils an ausgewählte Stufen des ersten Registers angeschlossen sind,

c) ein zweites Register zur Speicherung der ursprünglichen Datenbits und der von den ersten mehrstufigen EXKLUSIV ODER-Schaltungen erzeugten Redundanzbits,

d) mehrere zweite mehrstufige EXKLUSIV ODER-Schaltungen zur Prü- - fung der Parität der Datenbytes und der zugehörigen Redundanzbits ,

e) ein drittes Register zur Speicherung der Ausgangssignale der zweiten mehrstufigen EXKLUSIV ODER-Schaltungen, dessen Stufen, bei erfüllter Paritätsbedingung der Datenbytes und ihrer Paritätsbits einen vorgegebenen Binärwert speichern,

f) eine Prüfschaltung zur Prüfung der von den zweiten mehrstufigen EXKLUSIV ODER-Schaltungen gelieferten Ergebnisse und eine Anzeigeschaltung zur Anzeige eines Datenbit- oder eines Prüfbitfehlers, wenn die Fehlerursache im Speicher liegt.

Docket YO 969 065 109883/1616

Ein Ausführungsbeispiel der Erfindung ist in den Zeichnungen dargestellt und wird nachfolgend näher beschrieben. Es zeigen:

Fig. 1 einen Lageplan für die Fign. IA und IB,

Fign. IA und IB ein Blockschaltbild der vorliegenden Fehler-

erkennungs- und Datenumsetzschaltung mit den wichtigsten Funktionsblocks und dem Datenfluß des Systems,

Fig. 2 einen Lageplan der Fign. 2A bis 2J,

Fign. 2A bis 2J ein genaueres Blockschaltbild, das die wesentlichen Merkmale der erfindungsgemäßen Schaltung zeigt,

Fig. 3 ein Operations-Ablaufdiagramm für einen Speicher-Schreibzugriff ,

Fig. 4 den CW-Taktgeber, der im wesentlichen die Systemoperation bei einem Speicher-Schreibzyklus steuert,

Fig. 5 ein Operations-Ablaufdiagramm für einen Speicher-Lesezugriff,

Fig. 6 den CR-Taktgeber, der das System bei einem Speicher-Lesezyklus steuert,

Fig. 7 ein genaueres Blockschaltbild einer der EXKLUSIV

ODER-Schaltungen mit 19 Eingängen, die in Fig. 2D dargestellt sind und von denen jede 19 Eingänge aufweist,

Fig. 8 ein genaueres Blockschaltbild des A-Taktgebers,

der das übertragen der Daten und Syndrombits

ϊο 969 065 109883/1616

durch die Korrekturschaltung steuert, Fig. 9 eine Paritäts-Prüfmatrix,

Fig. 10 die Paritäts-Prüfmatrix der Fig. 9 in ihren

einzelnen Phasen, die dazu dient, die tatsächliche Verbindung der in Fig. IA dargestellten Paritätsmatrix anzugeben,

Fig. 11 ein Blockschaltbild der Syndrom-Erzeugungsschal-

tung, die benötigt wird, wenn die Anzahl der Bytes und der Prüfbits verschieden ist.

Die Ziele der vorliegenden Erfindung werden allgemein durch ein System erreicht, mit dem in einen und aus einem Hamming-Code zur Einzelfehlerkorrektur- und Doppelfehlererkennung, im folgenden kurz als EFK/DFE-Hamming-Code bezeichnet, und Byteparitätscode umgesetzt und Einzelfehler korrigiert und Doppelfehler erkannt werden in den im Hamming-Code vorliegenden Daten. Das System umfaßt Speichereinrichtungen zur vorübergehenden Speicherung von Daten und Sonderbits, die aus einem zugehörigen Speicher gelesen oder in diesen geschrieben werden. Die Codeumsetzschaltung ist an besagten Speicher angeschlossen zur Umsetzung in den EFK/DFE-Hamming-Code und Byteparitätscode und zur Erzeugung eines anderen Satzes von Sonderbits und zum Speichern dieser Bits in besagtem Speicher. Im vorliegenden Ausführungsbeispiel verfügt der Speicher darstellungsgemäß über zwei Sätze von Registern. Mit entsprechenden Taktgebereinrichtungen und Torschaltungen kommt man jedoch mit einem Satz aus. Zusätzliche Einrichtungen zur Paritätserzeugung aus den Originaldatenbits und einem ausgewählten Satz von Sonderbits sind vorgesehen. Die Ergebnisse der genannten Einrichtungen werden einem Speicher zugeführt. Schließlich spricht eine Erkennungsschaltung auf besagte Erzeugungseinrichtung an und zeigt einen Fehler an, wenn eine vorgegebene Paritätsbedingung bei den Datenbits und den ausgewählten Sonderbits nicht erfüllt ist.

109883/1616

Docket YO 969 065

Die Ausgangssignale besagter Erzeugungseinrichtung umfassen eine Gruppe zusätzlicher Bits, die in einem Speicher-Schreibzyklus einfache Paritätsanzeigen sind und im Fall eines Speicher-Lesezyklus Syndrombits für die nachfolgende Fehlererkennung und -Korrektur. Eine zusätzliche Schaltung ist vorgesehen, um zwischen einem Prüfbitfehler, einem einzelnen Datenbitfehler, einem doppelten Datenbitfehler oder einem Paritätsfehler in Abhängigkeit vom jeweils ausgeführten Speicherzyklus zu unterscheiden.

Das wichtige Merkmal der vorliegenden Erfindung ist das Vorsehen der Codeumsetzschaltung, die gemäß einer eindeutigen Paritäts-Prüfmatrix und einem Hamming-Code entworfen ist, welche der Codeumsetzschaltung die Erzeugung von Prüfbits aus Paritätsbits und Datenbits und von Syndrom- und Paritätsbits aus Prüfbits und Datenbits gestatten. Außerdem gestattet der Aufbau des vorliegenden Systems die Erzeugung einer Anzahl dieser Bits im wesentlichen auf parallelem Wege und spart dadurch beträchtliche Zeit und Ausführungsschritte, wodurch die Doppelfunktionsschaltung offensichtlich eine große Menge an Bauteilen einspart.

Die folgende allgemeine Beschreibung der Theorie der Hamming-Codes und dann die Weiterführung dieser Theorie zur Konstruktion einer Doppelfunktions-Codeumsetzschaltung zeigt klar die Grundprinzipien der vorliegenden Erfindung. Anschließend wird der allgemeine technische Aufbau des Ausführungsbeispieles im Zusammenhang mit der Fig. 1 in den Fign. 3 bis 8 erklärt. Die Erklärung der Arbeitsweise des in den Fign. 2A bis 2J gezeigten Ausführungsbeispieles erläutert die genaue Arbeitsweise des vorliegenden Systems beim Lesen und Schreiben des Speichers und beschreibt die Art, in welcher die Korrektur durch eine typische Hamming-Code-Korrekturschaltung ausgeführt wird.

Fig. 1 ist ein allgemeines Blockschaltbild des vorliegenden Systemes, welches dessen Hauptfunktionseinheiten zusammen mit dem allgemeinen Datenfluß zeigt. Die aus den Fign. IA und IB zusammengesetzte Figur zeigt, daß Daten aus dem Speicher über das

109883/1616

Docket YO 969 065

Register MR dem Kabel 116 zugeführt werden und sowohl die acht Datenbytes als auch die acht Prüfbits des EFK/DFE-Hamming-Codes umfaßen. Das Register MR kann auch von der Zentraleinheit, im folgenden kurz als ZE bezeichnet, geladen, enthält in diesem Fall jedoch acht Datenbytes und acht Byte-Paritätsbits. Kabel . 116 wird für einen Lesezugriff und Kabel 118 für einen Schreibzugriff zum Speicher verwendet. Die acht Datenbytes aus je acht Bits zuzüglich der acht Prüfbits oder Paritätsbits sind nur für das Ausführungsbeispiel gewählt. Abhängig von Größe und Anzahl der Datenbytes ist eine entsprechende Anzahl von Prüfbits vorzusehen. Im Falle eines Lesezugriffs werden bestimmte ausgewählte Datenbits und Prüfbits der Implementierung einer Paritäts-Prüfmatrix, nämlich der Verbindungsmatrix zugeführt. Im Falle eines SchreibZugriffes werden dieselben ausgewählten Datenbits und das Paritätsbit auf der Verbindungsmatrix zugeführt. Die Ausgänge der Verbindungsmatrix führen über die EXKLUSIV ODER-Schaltungen zum Kabel 120, welches dann über die Torschaltung 124 an das Register MDR führt. Die Ausgangssignale auf dem Kabel 120 umfassen acht neue Bits und die Datenbits werden über das Kabel 122 zum Register MDR übertragen. Wie bereits oben im Zusammenhang mit dem Lesezugriff gesagt wurde, setzen die Verbindungsmatrix und die EXKLUSIV ODER-Schaltungen Prüfbits in Paritätsbits um, während im, Falle eines Schreibzugriffes dieselbe Verbindungsmatrix und die EXKLUSIV ODER-Schaltungen die Paritätsbits in Prüfbits umsetzen. Bei einem Schreibzyklus wird das Register MDR direkt von der ZE geladen und in diesem Fall besteht das in das Register MDR geladene Wort aus den acht Datenbytes zuzüglich der acht Paritätsbits. Diese Information wird über das Kabel 128 zugeführt. Bei einem Schreibzugriff werden das Register MR und das Register MDR direkt von der ZE über die Kabel bzw. 128 geladen, und zwar weil zuerst einmal die von der ZE kommenden Daten auf richtige Parität überprüft werden müssen und dann die acht Paritätsbits in acht Prüfbits umgewandelt werden müssen, um das Wort im richtigen EFK/DFE-Hamming-Code zu speichern. Wie bereits gesagt erfolgt dies durch Zuführen des In-.haltes des Registers MR über die Verbindungsmatrix zum Register

Docket YO 969 065 10 9 8 8 3/1616

MDR, wo das Wort über das Kabel 130 für den Speicher im Hamming-Code zur Verfügung steht.

In Fig. 1 ist ein mit Fehlererkennungsschaltung bezeichneter Block gezeigt, der an den Ausgang des Registers MDR angeschlossen ist. Dieser Block enthält im wesentlichen eine Doppelfunktions-EXKLUSIV ODER-Schaltung, mit welcher einmal die Paritätsprüfung bei einem Schreibzugriff ausgeführt wird und die zum anderen schließlich die paritätscodierten Daten, die im Register MDR erscheinen, bei einem Lesezugriff in einen Satz von Syndrombits umsetzt, mit denen die Art des evtl. vorhandenen Fehlers signalisiert und eine Einzelfehlerkorrektur vorgenommen wird.

Wie bereits gesagt wurde, muß der Ausgang der Fehlererkennungsschaltung bei der Paritätsprüfung die Byteparität in jedem Byteabschnitt des Registers MDR prüfen. Da mit ungerader Parität gearbeitet wird, kann ein einfaches UND-Glied diese Prüfung durchführen. Bei einem Lesezugriff ist die Erkennung insofern etwas komplizierter, als die Schaltung zwischen einem Prüfbitfehler unterscheiden muß, dann werden die Daten als richtig erkannt, einem Einzel-Datenbitfehler, dann muß ein Korrekturalgorithmus eingeleitet werden und einem Doppelfehler, in welchem Fall der Betrieb des Systems unterbrochen werden muß, und diese Tatsache bekannt gemacht werden muß. Schließlich muß die Schaltung noch feststellen können, daß kein Fehler erkannt wurde und daß die gegenwärtig im Register MDR stehenden Daten an die ZE übertragen werden können.

Der mit Einzelfehler-Erkennungsschaltung bezeichnete Block benutzt die von der Fehlererkennungsschaltung auf im wesentlichen konventioneller Weise, die nachfolgend im Zusammenhang mit Fig. 2 näher beschrieben wird, erzeugten Syndrombits schließlich zur Korrektur.

Aus der obigen allgemeinen Beschreibung der Fig. 1 ist zu ersehen, daß bei Lese- und Schreibzugriffen zum Speicher im we-

Docket YO 969 065 109883/1616

sentlichen dieselbe Schaltung verwendet wird für Codeübersetzung, Paritätsprüfung, Syndrombiterzeugung usw., was im Gegensatz zu bisher gebräuchlichen Anlagen und Verfahren große Ersparnisse bei der Schaltung mit sich bringt.

Im folgenden wird zuerst ein Schreibzugriff im Zusammenhang mit dem Ablaufdiagramm nach Fig. 3 und der als Taktgeber dienenden monostabilen Kippschaltung nach Fig. 4 beschrieben. Die in Fig. 4 gezeigte Schaltung dient nur der Illustration und stellt eine mögliche Anordnung zur Taktgabe für das vorliegende System dar. Statt dessen kann auch jeder geeignete andere Taktgeber verwendet werden. Während eines SchreibZugriffes wird ein Impuls auf die Startleitung gegeben, der die Ablauffolge startet. Gemäß der Darstellung im Ablaufdiagramm in Fig. 3 veranlaßt der Startimpuls die Eingabe in das Register S. über jedem Block in Fig. 3 ist angegeben, welcher Schritt des CW-Taktgebers den jeweiligen Operationsschritt ausführt. In Fig. 4 weist eine Anzahl von Eingängen Bezugszahlen auf, die die Quelle bestimmter Einschaltimpulse bezeichnen. Diese Bezugszahlen sind ebenfalls in den Fign. 2A bis 2J verwendet worden. Zu Beginn eines Schreibzugriffs werden die beiden Register MR und MDR mit Daten und Paritätsbits von der ZE geladen. Die Eingabe ins Register S bewirkt eine Paritätsprüfung der gegenwärtig im Register MDR stehenden Daten durch. Der nächste durch CW-2 veranlaßte Schritt wird auf einen Fehler geprüft. Lautet die Antwort nein, verzweigt das Programm zum Schritt CW-4 und erzeugt Prüfbits. Dadurch werden die im Register MR gespeicherten Daten und Paritätsbits der Verbindungsmatrix und den EXKLUSIV ODER-Schaltungen zugeleitet und automatisch Prüfbits erzeugt und die Originaldatenbits zuzüglich der neu erzeugten Prüfbits in das Register MDR übertragen. Im Schritt CW-5 werden gültige Daten zum Speicher übertragen und das Programm verzweigt dann zum Ende. Wenn nach dem Schritt CW-2 ein Fehler angezeigt wurde, hätte der nächste Schritt den Taktschritt CW-3 eingeleitet und eine Unterbrechung hervorgerufen. Dabei handelt es sich um eine konventionelle Unterbrechung, die zu einer erneuten Übertragung oder einer ande-

id 969 065 103883/1616

ren Fehlersuch- oder Korrekturroutxne im System führt. Da es sich um einen Paritätsfehler handelt, kann er nicht korrigiert werden und die Daten können in der offensichtlich falschen Form nicht im Speicher gespeichert werden. Damit sind die Grundschritte eines Schreibzugriffs beschrieben.

Im Zusammenhang mit den Fign. 5 und 6 wird jetzt ein Lesezugriff beschrieben. Im Ablaufdiagramm der Fig. 5 sind die einzelnen Taktschritte des in Fig. 6 gezeigten CR-Taktgebers, den verschiedenen einzelnen Operationen zugeordnet, die in Fig. 5 aufgezeichnet sind. Auch hier ist der als Ausführungsbeispiel gewählte Taktgeber nach Fig. 6 insofern nicht der allein mögliche, als die Taktfolgen durch andere Schaltungen als die dargestellten monostabilen Kippschaltungen erzeugt werden können. Die Bezugszahlen bezeichnen das Einschalten der verschiedenen monostabilen Kippstufen und sind dieselben wie in den Fign. 2A bis 2J. Die Startleitung oben in Fig. 5 führt zum ersten Block "Eingabe in MDR und Register S". Da es sich um einen Speicherlesezyklus handelt, wird das Register MDR mit Datenbits und von der Verbindungsmatrix erzeugten Paritätsbits geladen. Anschließend wird der Inhalt des Registers MDR den EXKLUSIV ODER-Schaltungen zugeleitet, welche diese Information gemäß obiger Erklärung in Syndrombits umwandeln und sie im S-Register speichern.

Im Schritt CR-2 wird die Frage gestellt "Liegt ein Fehler vor?" und durch Prüfen des Inhaltes des S-Registers beantwortet, wie vorher beschrieben. Bekanntlich können dabei vier Fälle auftreten. Im ersten liegt kein Fehler vor, im zweiten Fall ein Prüfbitfehler, im dritten ein einzelner Datenfehler und im vierten Fall ein Doppelfehler. Liegt kein Fehler vor, verzweigt das System zum Schritt CR-4 und liefert ein Signal "gültige Daten zur ZE senden" und beendet diese Taktroutine. Wenn ein Fehler vorliegt, verzweigt das System zum Taktschritt CR-3 und stellt mit einer Prüfung fest "Handelt es sich um einen Einzelfehler?". Wird diese Frage verneint, liegt ein Doppelfehler vor und das System verzweigt zum Schritt CR-5 und es wird eine Unterbrechung

109883/1616

Docket YO 969 065

erzeugt, womit diese Taktfolge beendet ist. Handelt es sich um einen Einzelfehler, verzweigt das System zum Schritt CR-6 und • stellt mit einer Prüfung fest "Liegt ein Prüfbitfehler vor?". Wenn, das der Fall ist, verzweigt das System zum Schritt CR-7 und veranlaßt eine Korrektur der vorher erzeugten Paritätsbits. Liegt der Fehler nicht im Prüfbit, verzweigt das System zu dem mit "Byte korrigieren" bezeichneten Schritt. Die Leitung 404, welche zur Taktgeberstufe A-I führt, leitet den Korrekturschritt für ein einzelnes Datenbit ein. Nachdem Paritätsbit und Datenbit korrigiert sind, verzweigt das System dann zum Taktschritt CR-4 zurück, in welchem die jetzt gültigen Daten an die ZE oder eine andere Stelle im System übertragen werden und danach ist der Lesezugriff beendet. Der gerade erwähnte Α-Taktgeber ist in Fig. 8 gezeigt und ist ein sehr einfacher dreistufiger Taktgeber. Die Ausgangssignale der drei Stufen sind die einzigen, die benötigt werden, wie aus der nachfolgenden Beschreibung der Fign. 2A bis 2J hervorgeht, da bei einer notwendigen Korrektur das ganze Datenwort zusammen mit den zugehörigen Syndrombits parallel in die Korrekturschaltung gelesen und parallel wieder in das Register MR zurückübertragen und von dort dem Register MDR mit korrigierten Paritätsbits zugeführt wird.

Fig. 7 ist ein genaueres Blockschaltbild eines der in den Fign. 2D und IA gezeigten EXKLUSIV ODER-Schaltungen. Wie im einzelnen im Zusammenhang mit Fig. 2A bis 2J erklärt wurde, verfügt jede dieser EXKLUSIV ODER-Schaltungen über 19 Eingänge und einen Aus-• gang. Die Arbeitsweise einer EXKLUSIV ODER-Schaltung wird als bekannt vorausgesetzt und bewirkt, daß bei einer ungeraden Zahl von "1"Signalen auf den Eingangsleitungen diese Schaltung eine ungerade Parität oder ein "1"Ausgangssignal auf der Ausgangsleitung erzeugt.

Fig. 8 zeigt den Α-Taktgeber, der die im Prinzip in Fig. 2J gezeigte Korrekturschaltung steuert. Dieser Taktgeber ist im wesentlichen genauso aufgebaut wie der CR-Taktgeber und der CW-.Taktgeber, die aus mehreren (3) monostabilen Kippschaltungen be-

109883/1616

Docket YO 969 065

stehen, deren Einschaltung einen bestimmten Taktimpuls erzeugt und deren Rückkehr in den stabilen Zustand entweder zum Ende des Schrittes führt oder die nächste monostabilen Kippschaltung einschaltet/abhängig von der jeweils ablaufenden Routine. Die Arbeitsweise dieses Taktgebers und der Korrekturschaltung wird im einzelnen im Zusammenhang mit den Fign. 2A bis 2J beschrieben.

Die Arbeitsweise des Umsetzers (so genannt, weil er Prüfbits aus Paritätsbits oder umgekehrt Paritätsbits aus Prüfbits erzeugen kann in Abhängigkeit davon, ob aus dem Speicher gelesen oder in ihn geschrieben wird, wobei die Datenbits auch an der Umsetzung teilnehmen) beruht auf der Paritäts-Prüfmatrix. Die Paritäts-Prüfmatrix ist aus der Literatur bekannt.

Zuerst wird ein einfaches Beispiel einer üblichen Verwendung einer Paritäts-Prüfmatrix behandelt, wie es sich bei der Anwendung in einem elementaren Nachrichtensystem findet. Es wird angenommen, daß das Nachrichtensystem aus einem Sender binärer Signale, einem Empfänger für diese Signale und einem mit dem Buchstaben "K" bezeichneten Kanal besteht. Der Kanal ist zwangsläufig wesentlich unzuverlässiger als der Sender oder der Empfänger. Somit unterliegt der Kanal Störungen, die ein gesendetes Bit komplementieren, d. h. eine gesendete 1 wird als 0 empfangen oder eine gesendete O als 1.

Diese Situation ist direkt analog der Situation eines Speichers, in welchem die Speicher-Schreibschaltung das Analogon zum Sender und die Speicher-Leseschaltung das Analogon zum Empfänger ist.

In einer solchen Situation wird der EFK/DFE-Gode wie folgt verwendet. Ein Wort (ein Satz Bits) wird codiert, gesendet, geprüft mit nachfolgender Korrektur oder Erkennung eines Fehlers innerhalb der Möglichkeiten des EFK/DFE-Codes und erscheint in decodierter Form am Ausgang des Empfängers. Der Code wird durch die folgend© Paritäts-Prüfmatrix H charakterisiert:

Docket YO 969 065 109883/1616

01111000

10110100 H =

11010010

11100001

In dieser Matrix entspricht jede Spalte den Datenbits d₁, d_, d_ und d. und den Prüfbits c. , C₂, C₃, C₄. Das Wort "entspricht" ist in diesem Zusammenhang so zu verstehen, daß die Entsprechung darin besteht, daß eine "1" in einer gegebenen Zeile dem Erscheinen des Daten- oder Prüfbits einer Spalte in der Paritätsglei-• chung für diese Zeile erscheint. Dadurch wird gezeigt, daß ein Fehler lokalisiert (und korrigiert) werden kann, wenn wahlweise die Parität verschiedener Untergruppen der Datenbits festgestellt wird und wenn man beobachtet, welche dieser Paritätsbits den entgegengesetzten Wert zu den Werten aufweisen, die sie bei Fehlerfreiheit haben. Das ist deshalb möglich, weil die Muster dieser Paritätsbits für jeden richtigen und falschen Wert eines jeden Datenbits bekannt sind.

Die Frage ist jetzt, wie Paritäts-Prüfmatrix die Paritätsbits bestimmt und eine Fehlerlokalisierung ermöglicht. Die Beantwortung dieser Frage muß einer anderen "Entsprechung" entnommen werden, nämlich der der Paritätsbits oder Syndrome, wie sie auch genannt werden, zu den einzelnen Zeilen der Paritäts-Prüf matrix. Zur Beantwortung dieser Frage sollen jetzt die durch die Paritäts-Prüfmatrix vorgeschriebenen Paritätsgleichungen aufgezeichnet werden.

1. Zeile; Ol Il 1 O 0 0

4· Ψ Ψ 4· Ψ Ψ Ψ Ψ

1. Gleichung: Q.d^ l.dj l.d^© 1·^α ₄® ¹^i* O.c₂© Ο.σ₃® O.c₄ = S₁

oder d_ Φ d_ θ d₄ Θ C₁ = S₁, worin S₁ das

Syndrom für die 1. Zeile ist.

109883/1616

Docket YO 969 065

Das Prüfbit C₁ ist so gewählt, daß S. = 1 für den .fehlerfreien Fall bei ungerader Parität gilt. Die anderen drei Gleichungen sind folgende:

2. Zeile: d. Θ d- Φ d, θ C₂ = S₂

3. Zeile: d. Φ d₂ θ d₄ Φ C₃ = S₃

4. Zeile: d Φ d₂ Φ d, Φ c. = S₄

und S. = S₂ = S- = S. = 1 bezeichnet die fehlerfreie Bedingung für ungerade Parität. Somit läßt sich die Antwort auf die Frage, wo der Fehler sich befindet, jetzt durch die obigen Gleichungen ausdrücken. Aus diesen Gleichungen ist zu ersehen, daß d. nur in den Paritätsgleichungen für die Zeilen 2, 3 und 4 erscheint. Somit ist d. das einzige Bit, welches bei falschem Empfang nach der Decodierung die Syndrome entsprechend folgender Tabelle verändert.

^Sl ^S2 ^S3 ^S4

dj^ richtig empfangen 1111 d., fehlerhaft empfangen 10 0 0

Es ist zu beachten, daß sich S₁ nicht verändert, da es in seiner Bildung von d unabhängig ist, wie aus der obigen Gleichung für die Zeile 1 zu ersehen ist.

Für ein Beispiel wird jetzt angenommen, daß auf der Senderseite die Datenbits d = 1, d₂ = 0, d₃ = 0 und d. = 1 vorliegen. Die aus den Bits dj, d₂, d_, d. bestehende Nachricht hat also folgendes Aussehen: 10 0 1. Es ist somit:

S₁ = 1 = C₁ Φ d₂ Φ d₃ Φ d₄ = C₁ Φ Ο Φ Ο Φ 1

so daß für C₁ zur Erfüllung dieser Gleichung der Wert 0 angenom men wird.

Docket YO 969 065 109883/1616

Sender &
Codierung

S₂ = ι ₊

S₃-I-

S₁₁₁₁ " τ __

1 Φ O Φ 1 => 1 © O Φ 1 =>. 1 Φ O Φ O =>

= O

Aus der Nachricht wird

^dl ^d2 ^d3 ^d4 ^Cl ^C2 ^C3 ^C4 10010110

Wenn jetzt angenommen wird, daß der Kanal einer Fehlerbedingung unterliegt, so daß die Störung ausschließlich d invertiert, führt das zu folgender Daten- und Prüfbitreihe.

^dl ^d2 ^d3 ^d4 ^cl ^C2 ^C3 ^C4

0 0 0

Empfang

Φ ά. Φ

- 1 = 0

& Decodierung S₃ = σ- Φ d. Φ d_ Φ d. = Ό wie oben vorhergesagt

S₄ - C₄ Φ

Φ d₂ Φ d₃ = 0

Dieses eindeutige Syndroinmuster läßt sich nur unter der Bedingung erzielen, daß α_χ fehlerhaft ist. Die Korrektur ist trivial. Sie besteht darin, daß das Bit d., lediglich logisch invertiert wird (weil bekannt ist, daß die richtige Version von d, nur das Gegenteil des jetzigen Wertes sein kann). Die Schaltung zur Korrektur von d ist folgende:

Docket YO 969 065

d, 1 ist das korrigierte Bit 109883/1616

- 17 - ·

Folgende klare Tatsache läßt sich jetzt feststellen: Bei ungerader Parität ist das Syndrommuster, welches d₁ korrigiert (invertiert) , einfach das Komplement (die logische Verneinung) der Spalte in der Paritäts-Prüfmatrix, welche d., entspricht (die erste Spalte). und grundsätzlich ist also das Syndrommuster, welches d-, d₂, d~ oder d. korrigiert das Komplement der Spalte 1, 2, 3 oder 4. Die Korrekturen für die Prüfbits C₁, c«, C₃ oder C₄ finden sich einfach in den Spalten 5, 6, 7 oder 8 der Paritäts-Prüfmatrix, wenn eine solche Korrektur gerechtfertigt ist. Bei gerader Parität erscheint das Syndrom nicht als Komplement (als Komplement), wenn die Matrixeintragung eine 1 (0) ist.

Ein Doppelfehler wird durch ein Syndrommuster gekennzeichnet, welches sich nicht als Spalte in der Paritäts-Prüfmatrix und auch nicht als Muster für "kein Fehler" findet. Somit sind die Muster, welche einen Doppelfehler anzeigen, folgende:

(S₁, S₂, S₃, S₄) - (0,0,0,0), (0,0,1,1), (0,1,0,1),

(0,1,1,0), (1,0,0,1), (1,0,1,0), (1,1,0,0).

Hierbei handelt es sich offensichtlich um Muster, in welchen zwei Syndrome sich gegenüber ihrem erwartetem Wert verändert haben. Es ist jedoch nicht möglich, die Schuldigen anzugeben: Wenn (0,0,1,1) empfangen wurde, sind dann die Schuldigen d. und d₂ oder sind es c. und C₂? Somit kann bei Empfang eines Musters wie des oben gezeigten nur ein Doppelfehler erkannt werden, außer der Abgabe eines Alarmsignals können jedoch keine weiteren Schritte unternommen werden.

Die Paritäts-Prüfmatrix für die Minimalschaltung bringt eine subtilere Beziehung zwischen der Parität eines gewählten Datenbyte und der Parität über einem ausgewählten Teilsatz von Datenbits und genau e:J.nem Prüfbit mit sich, welches eindeutig zu dem gewählten Datenbyte gehört. Die Untersuchung der in Fig. 9 oder 10 gezeigten Paritäts-Prüfmatrix legt eine wichtige Beziehung klar.

Docket ϊο 969 065 109883/1616

Bei der verwendeten Codierung und Decodierung (die durch die Paritäts-Prüfmatrix spezifiziert ist) erscheint ein Satz von Einsen in jeder Zeile, betrachtet als eine Untergruppe aller Einsen in dieser Zeile, in der Weise, daß die Parität über allen Bits eines vollständigen Bytes (in dem Datenwort) in der Bildung der Syndrome eingeschlossen ist, die dieser Zeile entsprechen, wenn die normale Schaltung zur Implementierung der Parität der Zeile zu verwenden war. Eine Vorschrift der für eine grobe Auslegung des vorliegenden Umsetzers zu Beginn benutzten Technologie besagte jedoch, daß ein Bytegrößenregister automatisch die Byteparität für jede in dieses Register geladene Information liefert. •Für den vorliegenden Fall wurde das nicht angenommen, es erklärt jedoch teilweise, warum es möglich ist, die Paritätserzeugung als Teil des Decodierprozesses in diesen einzuschließen und warum dieselbe Schaltung für Lese- und Schreibprozesse verwendet werden kann. Die hier angegebene Rotations-ParitätsrPrüfmatrix wird grundsätzlich abgeleitet durch Angabe von Spalten mit nur einer 1 als Prüfbitspalten und unter Verwendung von acht Spalten mit drei, fünf usw. Einsen, für den Teil der zum ersten Byte gehörenden Paritäts-Prüfmatrix und anschließende vertikale Drehung in aufsteigender Reihenfolge für jedes der sieben aufeinanderfolgenden Bytes. Die später zu gebende Beschreibung der Paritäts-Prüfmatrix zeigt, warum diese Rotationseigenschaft nützlich, aber nicht notwendig ist für den allgemeinen Fall der Bildung der Paritäts-Prüfmatrix. Es muß besonders darauf geachtet werden, daß man eine Zeile aus lauter Einsen für das erste Byte vor den sieben Drehungen erhält und es muß insbesondere sichergestellt werden, daß keine zwei Spalten ein identisches Muster aus Einsen und Nullen haben. Damit sind die Grundlagen für die Bildung der Rotations-Paritäts-Prüfmatrix erklärt. Normale Korrektur kann durch Interpretation dieser Rotationsmatrix als übliche Paritäts-Prüfmatrix erfolgen.

Anschließend wird die Implementierung und Anwendung der Rotationsparitätscodes in einem Speicherumsetzer beschrieben, wie er hier offenbart wird. Zuerst wird der Leseprozeß betrachtet. Die Grund-

109883/1616

Docket YO 969 065

schritte sind folgende:

1. Unter Verwendung der Paritäts-Prufmatrix sowie der Daten und Prüfbits ist ein Paritätsbit für jedes Byte zu bilden.

2. Datenbyte und Paritätsbit sind aus dem Register MR in das Register MDR für jedes Byte des Wortes zu laden.

3. Syndrome sind aufgrund der Prüfung der Byteparität und ihres Paritätsbits (in Schritt 1 gebildet) für jedes Datenbyte zu bilden.

4. Es ist festzustellen, ob eine Fehlerbedingung in den ausgelesenen Daten vorliegt. Wenn die Daten keinen Fehler enthalten, ist das Wort an die ZE weiterzuleiten? sonst ist jeder Einzelfehler zu korrigieren oder der ZE das Vorliegen von Doppelfehlern anzuzeigen.

Jeder der vier obengenannten Grundschritte wird anschließend genauer erklärt. Zuerst wird das Paritätsbit für jedes Byte erzeugt, indem man die Parität eines ausgewählten Satzes von Datenbits zuzüglich genau eines Prüfbits bestimmt. Die erste Zeile der Rotationäprüfmatrix in Fig. 10 enthält acht Einsen in einer Zeile in den den Bits d-, d„ ... dg entsprechenden Spalten. In der Spalte (erste Zeile) unter c. (Spalte 65 in einer Rotations-Paritäts-Prüfmatrix mit acht Bytes und acht Bits pro Byte) steht eine einzige Eins. Eine Gruppe von Einsen entsprechend anderen Datenbits (weder für c noch Datenbits im ersten Byte) ist ebenfalls vorhanden und hiermit als Paritätsuntergruppe der ersten Zeile definiert. Ähnliche Erläuterungen können über den Aufbau einer jeden derartigen Zeile einer Rotations-Paritäts-Prüfmatrix gemacht werden. Es bleibt jedoch noch zu zeigen, wie das Paritätsbit zu erzeugen ist. Daher werden die folgenden Veränderlichen definiert:

Docket YO 969 065 10 98 8 3/1616

y. - die Parität der Paritätsuntergruppe der ersten Zeile x- die Parität des ersten Bytes

ρ - das Paritätsbit zur Aufrechterhaltung der ungeraden Parität für das erste Byte.

Es ist der hier getroffene Unterschied zwischen der Parität eines Byte und dem Paritätsbit für dasselbe Byte zu beachten. Wenn die Parität (die Anzahl von Einsen) für ein Byte gerade ist (eine gerade Zahl von Einsen unter den Bits des Datenbytes), ist das Paritätsbit eine 1, wenn für die Fehlerkorrektur eine ungerade Parität gefordert ist. Die folgenden Gleichungen leiten sich aus obigen Betrachtungen für die Verwendung der ungeraden Parität in einer Rotations-Paritäts-Prüf matrix her.

X₁ Θ Y₁ Φ C₁ =1,
X₁ Θ _Pl « 1

Durch Addition dieser beiden Gleichungen zueinander (Addition Modulo 2) ergibt sich die Summe

X₁ Φ γ Φ c Φ χ. Φ ρ. = 1 Φ 1 = Ό und

X₁ Φ Y₁ Φ C₁ Φ X₁ Φ P₁ = X₁ Φ X₁ Φ (Y₁ Φ C₁) ® P₁

Dann ist, wenn Y₁ Φ C₁ auf beiden Seiten der Gleichung addiert wird:

Φ (Y₁ ® C₁) = 0 Φ

ν
0

P₁ - Y₁

109883/1616

Docket YO 969 065 v«„,,_olo

Die Bedeutung dieser Gleichung liegt darin, daß das Paritätsbit für das erste Datenbyte aus der Parität der Paritätsuntergruppe der ersten Zeile und dem Prüfbit C₁ zu erzeugen ist (und daß dazu nicht die Bits des ersten Datenbytes herangezogen werden müssen) .

Die Ausgangssignale dieser Paritatserzeugungsschaltung werden direkt in die Byteparitätsstellen des Registers MDR geladen. Gleichzeitig damit werden die Datenbits aller Bytes vom Register MR zum Register MDR übertragen und damit der Schritt 2 abgeschlossen.

Wenn die Pariätsbits einmal aus y. Θ c. erzeugt und gespeichert sind, werden die acht Datenbits eines jeden Bytes (mit der Parität χ,) und das zugehörige Paritätsbit als Eingangssignale für eine Paritäts- (oder EXKLUSIV ODER-)Schaltung benutzt. Da Y₁ Θ C₁ = P₁ und X₁ Φ P₁ =1 sind, ist das Ausgangssignal Sl dieser Parität-Schaltung eine 1, wenn kein Fehler im Byte vorliegt. Das Erzeugen eines Satzes von Syndrombits geschieht in folgender Weise: Für das Ausführungsbeispiel ergibt sich ein Syndrom aus jedem Byte und seinem zugehörigen Paritätsbit. Wenn jedoch im ersten Byte ein Fehler liegt, ist X₁ θ ρ. = 0 * S. und eine Fehlerbedingung wird angezeigt. Damit ist Schritt 3 abgeschlossen und es folgt Schritt 4. Solange kein Fehler vorliegt, ist S₁ = S₂ ^s ... Sg a 1 (für ungerade Parität) und ein mit KF bezeichnetes Signal kann gebildet werden als KP * .S. · S₂ · S₃ · ... · Sg. Wenn KF *» 1 ist, enthält das Datenwort keinen Fehler. Somit braucht die normale Ausgabe des gegenwärtig im MDR gespeicherten Wortes zur ZE nicht gestört au werden. Wenn jedoch KF * 0 ist, muß die Übertragung des Wortes ausgesetzt werden, die Fehlerart bestimmt werden - Einzel- oder Doppelfehler - und entsprechende Schritte unternommen werden. Ein Einzelfehler wird aus der Kenntnis erzeugt, daß KF ♦ 1 ist, weil KF * 1 das Vorliegen einer Fehlerbedingung im Datenwort anzeigt. Der Ausdruck Fehlerbedingung sagt jedoch nicht, ob es sich um einen Einzel- oder einen Doppelfehler handelt. Die Klassifi-

109883/1616

Docket YO 969 065

zierung der Fehlerbedingung erfordert die Ausnutzung einer Eigenschaft der Paritäts-Prüf matrix. Wenn ein einzelner Datenfehler vorliegt, ändert sich eine ungerade Zahl von Syndromen. Wenn sich nur ein Syndrom ändert, liegt der Fehler in einem Prüfbit. Bei diesem Umsetzer brauchen Fehler im Prüfbit nicht berüchtigt zu werden, das durch die Verwendung des fehlerhaften Prüfbits erzeugte Paritätsbit muß jedoch auf seinen richtigen Wert hin invertiert werden. Somit liegt die Notwendigkeit für diese Korrektur vor und sie wird bei allen Paritätsbits im Bedarfsfall durchgeführt, indem'man sie mit dem Komplement der Syndrome anti valent verknüpft. Eine besondere Schaltung zeigt den Bedarf ψ · für diese Korrektur an.

Wenn z. B. die acht Paritätsbits p., p₂, ... p_g gegeben sind als P₁ = If P₂ = Of P₃ = 0, p₄ = 1, p₅ = 1, p₆ = 0, p₇ = 1, p_Q = 0 und die Syndrome als S₁ =1, S, = 0, S, = S. = S₁- = S_c = S_ = S_n =1, bedeutet das, daß das zweite Paritätsbit falsch ist, weil S₂ = 0 ist. Zur Korrektur der Paritäten werden diese dann ersetzt durch ρ Φ s", wobei ρ = (P₁, p₂ ... pg) und S" = (S₁, ÜL, ... Sg) ist. Für dieses obige Beispiel gilt dann

ρ Φ S = (1 Φ 0, 0 Φ 1, 0 Φ 0, 1 Φ 0, 1 Φ 0, 0 Φ 0,

1 Φ 0, 0 Φ 0)
' = (X, 1, 0, 1, 1, 0, 1, 0)

und das ist dann die ursprüngliche Paritätsbitgruppe mit Ausnahme des zweiten Bit, welches aus dem oben gegebenen Wert p₂ durch Invertieren gewonnen wurde. Im vorliegenden Ausführungsbeispiel ist aus Fig. 2J zu ersehen, daß die Gruppe S über die Kabel 100, 102, ... 114 dem Register MDR zugeleitet wird.

Für jeden·anderen Daten-Einzelfehler ändert sich eine ungerade Anzahl von Syndromen, die größer als 1 ist (in jeder Spalte der Paritäts-Prüfmatrix steht eine ungerade Anzahl von Einsen). Somit kann ein Einzelfehlersignal gebildet werden, wenn:

YO 969 065 109883/1616

1. das Fehlersignal eine 1 ist (KF =1)

2. die Parität der Syndrome sich ändert.

Für den zweiten Fall ist für acht Syndrome (acht Bytes) die Parität der Syndrome normal, bei Fehlerfreiheit ist sie gerade, d. h., acht Syndrome sind alle identisch 1. Wenn sich jedoch eine ungerade Zahl ändert, ändert sich die Parität auch auf ungerade Parität. Somit gilt für das Einzelfehlersignal EF EF = W (S₁ Θ S₂ θ ... Φ Sq). Wenn EF = 1 ist, liegt ein Einzelfehler in dem aus dem Speicher gelesenen Datenwort vor. Wenn ein Fehlersignal (KF = 1) vorliegt und es sich nicht um ein Einzelfehlersignal (EF = 1) handelt, ist es ein Doppelfehler, DE = KF /λ EF =1 und ein Alarmsignal kann an die ZE gegeben werden.

Wenn die Datenbits im Register MDR (Einzeldatenfehler) korrigiert werden können und müssen, werden die Datenbits der Korrekturschaltung zugeleitet beim Taktimpuls A-I und über das Register MR und die Korrekturmatrix dem Register MDR bei den Taktimpulsen A-2 und den Taktimpulsen A-3 zugeleitet, wie später noch erklärt wird. Das Datenwort kann dann mit allen angefügten Paritätsbits der ZE zugeführt werden. Zu diesem Zeitpunkt ist natürlich die vorher erklärte Korrektur bereits ausgeführt worden.

Der Schreibprozeß für den Speicher besteht im Empfangen einer Gruppe parltätscodierter Datenbytes von der ZE (über eine Sammelleitung) , in der Prüfung der Parität für jedes Byte, dem Umcodieren der Datenbits unter Verwendung der Verbindungsschaltung und dem Speichern des umcodierten Wortes in einem Register zur Eingabe in den Speicher.

Zur Erleichterung der beiden ersten Schritte eines Schreibzyklus und zur Vermeidung komplizierter Kontrollen und überflüssiger Datenbewegungen wird das ankommende Wort in das Register MDR

Docket YO 969 065 109883/1616

und das Register MR geladen. Das Wort wird in beiden Registern mit allen angefügten Paritätsbits gespeichert. Das in das Register MDR gebrachte Wort wird so dort gespeichert, daß die Paritätsbits für jedes Byte mit den vorhandenen EXKLUSIV ODER-Paritätsprüfschaltungen geprüft worden können, die beim Leseprozeß zur Erzeugung der Syndrome aus den vorher erzeugten Paritätsbits und den Datenbits benutzt werden. Beim Schreiben besteht die aus den EXKLUSIV ODER-Schaltungen für jedes Byte kommende Information (oder sie sollte es wenigstens) aus einem Satz von Einsen, die anzeigen, daß die Parität für jedes Byte stimmt oder aus Nullen in den Paritätsstellen, an denen die Byteparität für das zugehörige Byte nicht stimmt. Wenn die Parität nicht stimmt, wird eine erneute übertragung der Information angefordert. Wenn jedoch kein Fehler angezeigt wird, ist das Wort für die Neucodierung und die Rücksetzung in den Speicher bereit.

Das umzucodierende zu speichernde Wort steht im Register MR. (Andernfalls hätte das im Register MDR stehende Wort in das Register MR übertragen werden müssen, da die Paritätsprüfung nicht so wirksam ist.) Wenn die im Register MDR stehende Version des Wortes für die Speicherung bereit ist, können die Prüfbits für die umcodierte Form unter Verwendung der Schaltung erzeugt werden, die zum Implementieren der Paritäts-Prüfmatrix für einen Lesezugriff vorgesehen ist. Die Datenbits und die Paritätsbits gehorchen folgenden Gleichungen

X₁ ® P₁ = 1,

die bereits oben für die erste Zeile der Paritäts-Prüfmatrix bei einem Lesevorgang angegeben wurden. Für die übrigen Zeilen und Datenbytes gelten wieder ähnliche Überlegungen.

Die obigen Gleichungen können so umgeformt werden, daß aus ihnen die Erzeugung von Prüfbits aus Daten- und Paritätsbits hervorgeht. Die umgeformten Gleichungen lauten:

109883/1616

Docket YO 969 065

P₁ Φ Y₁ Φ C₁ « O
Für den Lesefall wurde diese Gleichung umgeordnet zu

C₁ © Y₁ = P₁.

Für den Schreibfall wird die Gleichung umgeordnet zu P₁ ® Y₁ = C₁.

Diese Gleichung zeigt, was mit dem Wort im Register MR geschieht. Das Paritätsbit für jedes Byte und die durch Y₁ in obiger Gleichung für das erste Byte bezeichnete Paritätsuntergruppe werden antivalent miteinander verknüpft und ergeben die durch die Datenbits jedes Bytes vor dem Speichern geforderten Prüfbits. Die Prüfbits werden dann in den Paritätsbitstellen des Registers MDR gespeichert. Wenn die Prüfbits einmal erzeugt sind, kann das Wort (Daten und Prüfbits) aus dem Register MR entfernt werden, in welches es während der Umcodierung beim Schreibprozeß geladen und gespeichert wurde.

Die folgende Beschreibung der grundlegenden Paritätsmatrix 9 und der daraus entwickelten vollen Parltäts-Prüfmatrix der Fig. 10 zeigt insbesondere die Art, in welcher die in den Fign. 1 und 2 gezeigte Verbindungsmatrix gebildet wird. Die theoretische Erörterung der Grundlagen einer solchen Prüfmatrix muß herangezogen werden, wenn man zu der gewünschten Doppelfunktionsschaltung gelangen will. Die Art, in der sie gewonnen wird, wurde soeben beschrieben. Die nachfolgende Beschreibung zeigt nur die besondere Anwendung einer bestimmten Matrix mit den gewünschten Eigenschaften, die für das vorliegende Ausführungsbeispiel geeignet ist.

Zur Bildung der in den Fign. IA und IB als Block und im einzelnen in den, FignJ 2A, 2B, 2C und 2D dargestellten Verbindungsmatrix,

1 ·

wird folgende· Verfahren benutzt. In,Fig. 9 wird zuerst eine Matrix mit acht Spalten und acht Zeilen gebildet, die dann in das in Flg. 10 gezeigte Rechteck 410 kopiert wird.

109883/1616

Docket YO 969 065

Das bedeutet nicht, daß die obere Zeile mit lauter Einsen zum Verständnis der mathematischen Regeln, welche dieser Erfindung zu-, gründe liegen, nicht wichtig ist. Für den Sonderzweck der Konstruktion der obenerwähnten Verbindungsmatrix wird die obere Reihe von Einsen nicht berücksichtigt.

In Fig. 10 gibt das untere rechte Rechteck 426 die Lage der Prüfbits an. Zur Bildung der im Rechteck 412 der Fig. 10 gezeigten Matrix wird die Matrix im Rechteck 410 nach oben gedreht, mit anderen Worten, die erste Zeile wird durch die zweite Zeile ersetzt, die zweite durch die dritte usw. Die oberste oder erste Zeile geht nach unten oder in die achte Zeile. Die im Rechteck 414 dargestellte Matrix ist die Matrix des Rechteckes 412, welche wieder gemäß obiger Beschreibung einmal vertikal nach oben gedreht wurde. Das die Matrix 416 enthaltende Rechteck wird durch Drehen der Matrix 414 um eine Stelle nach oben gebildet und auf diese Weise entstehen auch die Matrizen in den Rechtecken 418, 420, 422 und 424. Somit wird die Matrix des Rechteckes 410 zur Gewinnung des Rechtecks 412 einmal, des Rechtecks 414 zweimal, des Rechtecks 416 dreimal, des Rechtecks 418 viermal, des Rechtecks 420 fünfmal, des Rechtecks 422 sechsmal und des Rechtecks 424 siebenmal gedreht.

Faßt man die neun Rechtecke in der Fig. 10 mit der Bezeichnung 410 bis 426 als eine Matrix aus acht Zeilen und 72 Spalten auf, so entspricht diese Matrix genau der Anordnung in den Fign. 2A, 2B,, 2C und 2D, Die 72 Spalten in Fig. 10 entsprechen den 72 Bits im Register MR. Die acht Zeilen der Fig. 10 entsprechen den acht Leitungen 204 bis 218. Jede Zeile in Fig. 10 enthält 19 Einsen. Jede Eins in einer Zeile der Matrix entspricht dem 1-Ausgangssignal des genauso numerierten Flipflops des Registers MR. So erscheint z. B> die erste 1 in der Zeile 1 in Spalte 9. Aus Fig. 2A ist zu ersehen, daß der 1-Ausgang des Flipflops 9 an das Kabel 204 angeschlossen ist. Die Verbindungen des Kabels 204 mit den übrigen Flipflops sind aus der Matrix zu ersehen und so sind die Flipflops für die Bits 11, 13, 17, 18 usw. alle mit dem

109883/1616

Docket YO 969 065

Kabel 204 verbunden. Die Anschlüsse der anderen Kabel werden genauso durch Bezug auf die Zeilen der Matrix der Fig. 10 ausgewählt.

Es folgt eine allgemeine Erörterung des Aufbaus einer Paritäts-Prüfmatrix, wenn unterschiedliche Bytezahlen (Byte-Paritätsbits) und Prüfbits vorhanden sind. Wenn m Bytes aus b Bits vorhanden sind, ergibt das mb = K Datenbits. Wenn K gegeben ist, errechnet sich die Anzahl der Prüfbits r nach der bekannten Hamming-Beziehung. Alle Paritäts-Prüfmatrizen haben K + r Spalten und r Zeilen. Die letzten r Spalten enthalten eine 1 und (r-1) Nullen, die so angeordnet sind, daß die r Spalten eine 1 in der ersten, zweiten ... rten Zeile haben. Jede Spalte entspricht einem Prüfbit.

Teile die m Bytes gleichmäßig in r Gruppen T.. Wenn m = dr + e 0 £ e < r ist, setze d + 1 Bytes in die ersten e Gruppen T₁, ... T und d Bytes in die letzten (r-e) ^₁, ··· T_r· Die Gruppe soll dem i-ten Prüfbit und der i-ten Zeile entsprechen. Beginne durch Setzen von b(d+l) in die erste Zeile unter T , b(d+l) Einsen in die zweite Zeile unter T_ und fahre so fort für die ersten e Gruppen. Jetzt setze bd Einsen in die (e+l)te Zeile unter die Gruppe T . und fahre fort bis unter jeder Gruppe b(d+l) oder bd Einsen jeweils in einer separaten Zeile stehen. (In Fig. 1, Zeilen 1 bis 8 und in Fig. 4, Zeilen 1 bis 7 mit acht Bits in Zeile 1, vier in den restlichen.)

Es gibt Ci) - r ' verschiedene Wege, um drei Einsen in r Stellen zu setzen und Kombinationen von drei Einsen mit einer Eins in einer besonderen Zeile. Es sind alle Kombinationen dieser drei Bits zu verwenden, da umso weniger Verbindungen und EXKLUSIV ODER-Schaltungen verwendet werden, je weniger Einsen sich in einer Paritäts-Prüfmatrix finden.

Für r = 7 gibt es 35 derartige mögliche Kombinationen und 32 wer-

109883/1616

Docket YO 969 065

— 2ο "*

den für Fig. 4 benötigt. Eine mögliche Auswahl ist in Fig. 4 ge zeigt. Wenn mehr als (^) benötigt werden, gibt es

ί^Γϊ - r(r-l)(r-2)(r-3)(r-4)

r r

Möglichkeiten mit fünf Einsen, (_) mit sieben, (~) mit neun Eins.en usw.

Die Einsen wählt man am besten so, daß ihre Anzahl in jeder Zeile gleich ist, so daß die durch die Schaltung hervorgerufene Verzögerungen ungefähr gleich sind. Eine Möglichkeit besteht z. B. ) darin, die Spalte 1 in Tabelle I zu wählen, dann den Inhalt der Spalte in allen Bytes zu drehen, dann eine zweite Spalte zu wählen, ihren Inhalt wieder zu drehen usw. Dabei ist auf Verschiedenheit zu achten. Die Bytes sind aus dem Rest zu wählen, indem man Spalten bei Bedarf verschiebt.

Beispiel 1: m < r

Das Beispiel mit zwei Bytes und sechs Prüfbits in Tabelle II dient zur Erklärung folgender Feststellungen:

a) In Fällen, in welchen ein Prüfbit unter Verwendung aller Datenbits in einem Byte (im Beispiel c und c.) gebildet wird, sind Paritätsbit und Syndrombit wie

P vorher zu bilden.

b) Die anderen Syndrombits sind wie gewöhnlich zu bilden, z. B. durch EXKLUSIV ODER-Schaltung der entsprechenden Untergruppe von Datenbits für jedes Prüfbit (im Beispiel Sp, S-, Sj-, S_fi) .

c) Fehlersignale sind wie vorher zu bilden und, falls erforderlich, ist die Korrektur unter Verwendung von Syndrom- und Paritätsbits wie vorher durchzuführen.

1098 8 3/1616

Docket YO 969 065

d) Die Anzahl von Bits in einem Byte ist willkürlich. Siehe hierzu das Beispiel in Tabelle III mit Bytes aus vier Bits und sechs Prüfbits.

Beispiel 2: m > r

In diesem Fall entspricht jedes Prüfbit einer Gruppe Datenbits und jede Gruppe von Datenbits enthält eines oder mehrere Bytes. Tabelle IV und Fig. 11 zeigen ein Beispiel für diesen Fall einschließlich der zur Bildung von Syndromen aus Untergruppen von Datenbits entsprechend der Paritäts-Prüfmatrix erforderlichen Schaltung.

a) Ein Paritätsbit für die ganze Gruppe wird unter Verwendung eines Prüfbits und des Umsetzers wie vorher er-

.zeugt.

b) Jede η Bytes (zwei oder mehr) enthaltende Gruppe ist in η Teile aufzuteilen. Erzeuge n-1 Paritätsbits für die ersten n-1 Bytes und benutzs dieses Paritätsbit für die Byteparitätsprüfung. Das n-te Byte benutzt das Original-Paritätsbit.

c) Die erzeugten Paritätsbits sind einer EXKLUSIV ODER-Verknüpfung zu unterwerfen, und es ist die n-te Paritätsprüfung durchzuführen (welche das aus der Umsetzung gewonnene Paritätsbit benutzt), um das dem Prüfbit entsprechende Syndrombit zu erhalten.

d) Alle Fehlersignale sind wie vorher zu erzeugen und Korrekturen sind unter Verwendung der Syndrombits und Gleichungen wie vorher durchzuführen.

e) Jede Anzahl von Bits kann ein Byte bilden, wie es in dem obigen Beispiel mit Bytes aus drei Bit gezeigt wird.

109883/1616

Docket YO 969 065

ρ> oo

pi

Ρ»

in

M Pl

pi

H	r«
+	VO {Μ
7x1	ιη CS
ι

oo

(J pa eq <d

es

OO H

in

H Pl

σι

co

«ο m

Pl

ο ο ο ο ο ο H

O O O OO H O O O O O H O O O O O H O O O O O H O O O O OHOOOOO H O O O O O O

OHOHOOH HOHOOOH OHHOOOH HHOOOOH O O H OO H H OHOOOHH HHOOOHO HOOOOHH

OHOOHOH OHOOHHO HOOOHOH O O O O H H H HOOHOHO O O O H H O H O O O H O H H O O O H H H O

O O H O O O H H O O H O O O H H OHOH OHHO OHOH OHHH

HOOO HOOH HOOH HHOO HOHO HHOH HOHH i-i r4 t-i Π

HOH OHO HHO HOO OHO HOO HOO OOO

H H O

OOH HOO H O O HOO

OOO O C3 -O OOO

IOOfOOOOOH O M

U1HOOOOHO O M

O OJ

pimoo Η-οοο U H

CSlOOOrHOOOO

υ η

Hr-HOOOOO O H

νΟΙΟΟΗ.ΉΗΟΟ H H Ό

uimooHHoo

H H ■Ο

^•"WOHOHOO H H

Ρ1Ρ1ΗΟΟΗΟΟ H H

NOiOOHHHO H H Ό

HHOHOHHO ΟΟΗΟΟΗΗΟ

	en Ό	en	O	O	O	H	H
	ο	OO	H	O	O	O	H
	Γ·»	t-	H	O	H	O	O
	«ο Ό	«	H	O	H	O	H
		in	H	O	H	H	O
	·* Ό		H	H	O	O	O
CQ	Pl Ό Ό	Pl	H	H	O	O	H
CU ■U	H Ό	Ol	H	H	O	H	O
pq CSJ	H	H	H	-	O	O

O O H O O O

t-| CM ro -<r in v

cn co cn co w co

	I	X
	CO	•Η
	OO	I ι
I	β
co
■Ρ	ti
ted	ö
■u	•Η
•Η	,α
co	CU
Ph	^>

109883/1616

TABELLE III
k«16 r=6 n»22 4 Bytes

^dl^d2^d3^d4 ^d5^d6^d7^d8 ^d9^d10^dll^d12 ^d13^d14^d15^d16 ^Cl ^C2 ^C3 ^C4 ^C5 ^C6

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

S, 1111 0000 0110 1010 100000

5₂ 1100 1111 0000 0110 010000

5₃ 1011 1101 0001 0001 001000

5₄ 0110 1010 1111 0000 000100 Sr 0000 0110 1100 1111 000010

S, 00010001 1011 1101 000001 6

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 31 \

111111000001 000 011 110 101 100000 j^

101010 111111 000 000 011 110 010000 '

110111101010 111 000 000 011 001000

011011 110111 101 111 000 000 000100

000111 011011 110 101 111 000 0 0 0 0

000001 000111 011 110 101 111 000001

Im folgenden werden der Datenfluß vom Eingangsregister MR durch die Verbindungsmatrix zum Register MDR,der Datenfluß und die einzelnen Schaltungsteile für die Erzeugung der Syndrombits, die Schaltung zur Unterscheidung der verschiedenen Fehlerbedingungen und schließlich die Schaltung für die Datenbitkorrekturen beschrieben. Bei allgemeiner Bezugnahme werden der Einfachheit halber die Fign. 2A bis 2J als Fig. 2 bezeichnet, bei Bezugnahme auf bestimmte Schaltungen wird die jeweils zutreffende Figur erwähnt.

Das Register MR erscheint oben in Fig. 2 und erstreckt sich über die Fign. 2A, 2B, 2C und 2D. Es wird angenommen, daß Torschaltungen im Speicher und der ZE vorhanden sind, um dieses Register zu laden, auch wenn diese nicht besonders dargestellt sind. In diesem Register werden die Bits mit der Nummer 1 bis 64 für acht Datenbytes aus je acht Bits und die Bits 65 bis 72 für die acht Prüfbits benutzt. Die besonders in Fig. 1 dargestellte Verbindungsmatrix ist im Ausführungsbeispiel der Fig. 2 durch die acht Kabel mit den Nummern 204, 206, 208, 210, 212, 214, 216 und 218 dargestellt. Jedes dieser Kabel ist an 19 Stufen des Registers MR angeschlossen, wie bereits früher erwähnt. Achtzehn dieser 19 Stufen speichern Datenbits, eine ein Prüfbit. Jedes dieser Kabel ist an, die EXKLUSIV ODER-Schaltung angeschlossen. Es sind acht solcher Schaltungen mit der Nummerierung 172 bis 186 vorhanden. Wie bereits gesagt, sind Einzelheiten einer solchen EXKLUSIV ODER-Schaltung mit 19 Eingängen in Fig. 7 gezeigt. Die acht Datenbytes aus je acht Bits im Register MR werden über die acht Torschaltungen 188 bis 202 geleitet. Diese acht Torschaltungen entsprechen der Torschaltung 124 in Fig. IA und werden.alle durch Zuführen der Signale CR-I, CW-I oder A-3 zum ODER-Glied 125 durchgeschaltet, welches seinerseits einen Ausgangsimpuls auf der Leitung 126 erzeugt. Die Ausgangssignale der EXKLUSIV ODER-Schaltungen 172 bis 186 werden ebenfalls den Torschaltungen 188 bis 202 zugeleitet.Im rechten Teil der Fig. 2D ist die Leitung 156 gezeigt, die das Paritätsbit für das Byte 1 weiterleitet. Auf der Leitung 158 erscheint das Paritäts-

109883/1616

Docket YO 969 065

bit für das Byte 8. Auf der Leitung 160 erscheint das Paritätsbit für das Byte 7. Auf der Leitung 162 erscheint das Paritätsbit, für das Byte 6. Auf der Leitung 164 erscheint das Paritätsbit für das Byte 5. Auf der Leitung 166 erscheint das Paritätsbit für das Byte 4. Auf der Leitung 168 erscheint das Paritätsbit für das Byte 3 und auf der Leitung 170 erscheint das Paritätsbit für das Byte 2. Wie bereits gesagt wurde, sind die Verbindungen der Verbindungsmatrix bezüglich der jeweiligen Daten- und Prüfbits direkt aus der Paritäts-Prüfmatrix in Fig. 10 zu bestimmen. Während eines Lesezugriffs wird der CR-Taktgeber gestartet, kurz nachdem das Register MR geladen ist. Der Impuls CR-I wird über ein ODER-Glied 125 auf die Leitung 126 gegeben, um das Register MDR zu laden und auch der Torschaltung 340 zugeführt, um das in Fig. 2J gezeigte S-Register zu laden, welches zum Speichern der Syndrombit benutzt wird. Das Register MDR besteht aus acht Abschnitten von je neun Bits. Jeder Abschnitt enthält acht Datenbits und ein Paritätsbit. Jeder neun Bit große Abschnitt ist an eine der EXKLUSIV ODER-Schaltungen 222 bis 236 angeschlossen. Diese EXKLUSIV ODER-Schaltungen unterscheiden sich von der in Fig. 7 gezeigten dadurch, daß sie anstelle der in Fig. 7 gezeigten 19 Eingänge nur neun Eingänge haben. Die acht Ausgänge der eben erwähnten EXKLUSIV ODER-Schaltungen werden zum Speichern der acht Syndrombits in das in Fig. 2J gezeigte S-Register benutzt.

Nach dem Taktimpuls CR-I liefert der Taktgeber den Taktimpuls CR-2, Dieser Impuls wird zum Prüfen auf das Vorliegen eines Fehlers benutzt. Bei ungerader Parität wird kein Fehler angezeigt, wenn alle S Bits den Binärwert 1 aufweisen. Die in Fig. 21 gezeigte Leitung 238 wird also erregt, wenn kein Fehler vorliegt und die Leitung 240, wenn ein Fehler vorhanden ist. Das UND-Glied 237 wird nämlich dadurch eingeschaltet, daß im S-Register lauter Einsen erscheinen. Der Impuls CR-2 wird der Torschaltung 242 zugeführt, um den Zustand der Leitungen 238 und 240 zu prüfen. Wenn kein Fehler vorliegt, erscheint ein Impuls auf der Leitung 396. Dadurch wird das System beauftragt, im Register MDR erschei-

109883/1616

Docket YO 969 065

nende Daten zur ZE oder zu einer anderen Stelle im System zu übertragen, da kein Fehler vorliegt. Liegt jedoch ein Fehler vor, erscheint ein Ausgangsimpuls auf der Leitung 398. Die ebenfalls in der Fig. 6 gezeigten Leitungen 396 und 398 bewirken dort die Erzeugung der Taktimpulse CR-4 bzw. CR-3. Wenn die Leitung 240 erregt ist, zeigt sie notwendigerweise einen vorliegenden Fehler an und es muß dann geprüft werden, ob es sich um einen Einzelfehler handelt oder nicht. Diese Prüfung erfolgt durch den an die Torschaltung 244 in Fig. 21 angelegten Taktimpuls CR-3. Liegt ein Einzelfehl'er vor, liefert die EXKLUSIV ODER-Schaltung 246 ein 1-Ausgangssignal, da eine ungerade Zahl von Einsen im k - Register S steht, wenn ein Einzelfehler vorliegt. Das UND-Glied 248 liefert ein Ausgangs signal, weil die Leitung 240 erregt ist. Wenn das UND-Glied 248 zu dem Zeitpunkt ein Ausgangs signal hat, an welchem der Taktimpuls CR-3 der Torschaltung 244 zugeleitet wird, erscheint auf der Leitung 400 ein Impuls und zeigt damit einen Einzelfehler an. Wenn das UND-Glied 248 keinen Ausgangsimpuls zu dem Zeitpunkt liefert, zu dem der Impuls CR-3 der Torschaltung 244 zugeführt wird, erscheint auf der Leitung 402 ein Impuls. Die Leitungen 400 und 402 sind auch in der CR-Taktgeberschaltung der Fig. 6 gezeigt. Der Taktimpuls CR-5 führt zu einer Systemunterbrechung, weil ein Doppelfehler vorliegt, welcher nicht korrigiert werden kann. Dementsprechend muß zu _fc diesem Zeitpunkt vom Betriebssystem ein anderer Mechanismus auf- ^ gerufen werden. Wenn angenommen wird, daß die Leitung 400 erregt war, so wird dann der Taktschritt CR-6 eingeleitet, der das Korrekturverfahren beginnt.

Zuerst muß festgestellt werden, ob es sich bei dem Einzelfehler um einen Prüfbitfehler handelt, welcher nur eine Korrektur des betroffenden Prüfbits erfordert, die als eine Paritätsbitkorrektur im Register MDR vorzunehmen ist, oder ob es sich um einen Einzeldatenfehler handelt. Diese Feststellung wird getroffen durch Anlegen des Impulses CR-6 an die in Fig. 2J gezeigte Torschaltung 405. Die in Fig. 2J gezeigte Verknüpfungsschaltung 407 ist mit den Null-Ausgängen des Registers S verbunden. Bekanntlich

10 9 8 8 3/1616
. Docket YO 969 065

zeigt ein einzelner Syndrombitfehler ein falsches' Prüfbit an und 3, 5 oder 7 Syndrombitfehler einen einzelnen Datenbitfehler. Wenn die Schaltung 407 also ein Ausgangssignal erzeugt, bedeutet das, daß ein Prüfbitfehler festgestellt und die Leitung 354 erregt wurde, welche den Taktimpuls CR-7 einleitet. Dieser Taktimpuls wird auf die Leitung 254 in den Fign. 2E, 2P, 2G und 2H gegeben. Dieser Taktimpuls wird jede der Torschaltungen zugeführt, welche wie die Torschaltung 255 unter der Bitspeicherstelle des Registers MDR erscheint. Dieser Impuls verknüpft den Komplementinhalt des Registers S mit dem Inhalt der Paritätsspeicherstelle des Registers MDR antivalent in EXKLUSIV ODER-Schaltungen, wie z. B. der EXKLUSIV ODER-Schaltung 257. Die Ausgänge dieser Schaltungen sind mit den Torschaltungen 255 verbunden und jedes in einer Paritätsbit-Speicherstelle des Registers MDR gespeicherte Paritätsbit wird bei Zuführen eines Taktimpulses CR-7 mittels der oben beschriebenen Schaltung unter der Voraussetzung geändert, daß das zugehörige Syndrombit für diese spezielle Byteparität den Wert 0 besitzt. Als Beispiel wird für die im linken Teil der Fig. 2E erscheinende Bytespeicherstelle 1 des Registers MDR angenommen, daß das Paritätsbit den Wert 1 besitzt. Wenn weiterhin angenommen wird, daß die Syndrombitstelle 1 einen Prüfbitfehler in dieser Stelle angezeigt und dadurch die Leitung 100 erregt hat, so liegt der Fall vor, daß kein Ausgangsimpuls von der EXKLUSIV ODER-Schaltung kommt, wodurch wiederum der Inverter 259 einen Ausgangsimpuls erzeugt, welcher die Torschaltung 255 beim Auftreten des Taktimpulses CR-7 durchläuft und die Bitstelle über das ODER-Glied 261 auf 0 zurückstellt. In all denjenigen Paritätsbitstellen, in denen das entsprechende Syndrombit im Register S den Wert 1 hat, wird das Paritätsbit durch die gerade beschriebene Schaltung bei Anlegen des Taktimpulses CR-7 nicht verändert.

Wenn jetzt angenommen wird, daß ein Einzelfehler festgestellt wurde und die Korrektur vorzunehmen ist, dann wird die Leitung 4O4 durch Anlegen des Taktimpulses CR-6 an die Torschaltung erregt. Die Erregung der Leitung 404 startet einen in Fig. 8

109883/1616

Docket YO 969 065

gezeigten Α-Taktgeber. Wie bereits gesagt, handelt es sich hierbei um einen, einfachen dreistufigen Taktgeber, der die gegenwärtig im Register MDR gespeicherten Datenbits direkt im Taktschritt A-I über das Kabel. 312 in die im unteren Teil der Fig. 2J dargestellte Korrekturschaltung leitet. Der Taktimpuls A-2 veranlaßt dann die Übertragung der im Register 500 gespeicherten, korrigierten Daten in das Register MR. Das ist erforderlich, da eine Anzahl von während des vorhergehenden Zyklus erzeugten Paritätsbits falsch ist. Auf den Taktimpuls A-2 folgt der Taktimpuls A-3, der an die ODER-Schaltung 125 angelegt wird, um den Inhalt des Registers MR über die Verbindungsmatrix den EXKLUSIV " ODER-Schaltungen zuzuführen und neue richtige Paritätsbits zu erzeugen. Auf den Taktimpuls A-3 folgt der Taktimpuls CR-4, welcher signalisiert, daß die gegenwärtig im Register MDR stehenden Daten für die Übertragung an die ZE jetzt bereit sind.

Die Korrekturschaltung umfaßt ein UND-Glied 502 für jedes Datenbit und auch ein EXKLUSIV ODER-Glied 504 zum Empfang des Original-Datenbits aus dem Register MDR und zur EXKLUSIV ODER-Verknüpfung dieses Bits mit dem Ausgangssignal des UND-Gliedes 502. Diese Art der Korrektur ist allgemein bekannt. Die Eingangssignale für die verschiedenen UND-Glieder stellen die im Register S gespeicherten und entweder in regulärer oder in komplementärer ^ Form zugeführten Syndrombits dar. In der dargestellten Korrekturschaltung werden alle Datenbits, d. h. d.. bis cU₄f parallel der Korrekturschaltung zugeführt und über den Α-Taktgeber auch im wesentlichen parallel korrigiert.

Wenn die Korrektur beendet ist, wird das Register 500 mit den korrekten Daten geladen und danach wird beim Taktimpuls A-2 dieser korrigierte Datensatz in das Register MR und beim Taktimpuls A-3 über die Verbindungsmatrix dem Register MDR zugeführt.

Nach Beschreibung eines Lesezugriffs wird jetzt ein Schreibzugriff beschrieben, wobei der Vorgang im Zusammenhang mit den Fign. und 4 bereits beschrieben wurde ebenso wie der das System bei

109883/1616

Docket YO 969 065

einem Schxeibzugriff steuernde CW-Taktgeber. Vor einem Schreibzyklus werden bekanntlich das Register MDR und das Register MR mit den von der ZE gelieferten Daten- und Paritätsbits geladen. Zuerst muß jedoch mit einer Prüfung festgestellt werden, ob die Parität der ins Register MDR übertragenen Daten stimmt. Zu diesem Zweck erscheint der Taktimpuls CW-I auf der Leitung 145, um das Register S über die EXKLUSIV ODER-Schaltungen 222 bis zu laden. Wie bereits beschrieben wurde, wird damit nur eine Paritätsprüfung durchgeführt, und wenn man die Anwendung der ungeraden Parität voraussetzt, ist das Register S jetzt mit lauter Einsen geladen. Nach dem Taktimpuls CW-I erscheint der Taktimpuls CW-2 auf der Leitung 148 in Fig. 21. Dieser Impuls bewirkt das Prüfen des Inhaltes des Registers S auf richtige Parität (nur Einsen) durch überprüfen des Ausgangssignales des UND-Gliedes 237. Wenn die Leitung 238 erregt ist, bedeutet das, daß das Register S richtig lauter Einsen enthält und kein Fehler vorliegt, wodurch der Taktimpuls CW-4 eingeleitet wird. Wenn andererseits ein Paritätsfehler festgestellt wird, wird der Taktimpuls CW-3 erzeugt, der dem Datenverarbeitungssystem anzeigt, daß ein Paritätsfehler festgestellt wurde und die Daten erneut in die Register MR und MDR übertragen werden müssen.

Wenn angenommen wird, daß kein Fehler auftrat, ist die Leitung 149 in der Fig. 21 erregt. Das Signal auf dieser Leitung betätigt dann die Taktstufe CW-4, deren Taktimpuls über die Leitung dem ODER-Glied 125 zugeführt wird und den Inhalt des Registers MR der Verbindungsmatrix zuleitet, um die erforderlichen Prüfbits zu erzeugen und sie an den entsprechenden Püfbitstellen im Register MDR zu speichern. Die Leitung 126 kommt vom ODER-Glied 125 in Fig. 2D. Nach dem Taktimpuls CW-4 erscheint der Taktimpuls CW-5, der ein Schreibsignal "gültige Daten" an den Speicher sendet, wodurch der ganze Inhalt des Registers MDR, das jetzt die richtigen Datenbits und auch die erzeugten Prüfbits enthält, zum Speicher übertragen wird.

109883/ 1 S16

Claims (9)

1. ""* JO —

   P A T E N T A N S P R ϋ C H E

   Umsetzer zum Umsetzen von Informationswörtern, die in einem die Korrektur eines Einzelfehlers und das Erkennen eines Doppelfehlers ermöglichenden Code vorliegen, in in Bitgruppen (Bytes) unterteilte Informationswörter, bei denen jedes Byte ein Paritätsbit aufweist, und zur in umgekehrter Richtung erfolgenden Umsetzung von zu speichernden Informationswörtern und zur Prüfung der ausgelesenen bzw. einzuschreibenden Wörter, gekennzeichnet fc durch folgende Merkmale:

   a) ein erstes Register (MR, Fig. IA) zum wahlweisen Speichern entweder von aus einem Speicher gelesenen Daten- und Prüfbits oder von in den Speicher einzuschreibenden Daten- und Byteparitätsbits,

   b) mehrere erste mehrstufige EXKLUSIV ODER-Schaltungen zur Erzeugung von Redundanzbits (Prüfbits bzw. Paritätsbits) , deren Eingänge jeweils an ausgewählte Stufen des ersten Registers angeschlossen sind,

   c) ein zweites Register (MDR, Fig. IB) zur Speicherung " der ursprünglichen Datenbits und der von den ersten

   mehrstufigen EXKLUSIV ODER-Schaltungen erzeugten Redundanzbits ,

   d) mehrere zweite mehrstufige EXKLUSIV ODER-Schaltungen zur Prüfung der Parität der Datenbytes und der zugehörigen Redundanzbits,

   e) ein drittes Register (S, Fig. 2J) zur Speicherung der Ausgangssignale der zweiten mehrstufigen EXKLUSIV ODER-Schaltungen, dessen Stufen bei erfüllter Paritätsbedingung der Datenbytes und ihrer Paritätsbits einen

   !OSö'M/ 1 β 1 6

   - 39 vorgegebenen Binärwert speichern,

   f) eine Prüfschaltung zur Prüfung der von den zweiten mehrstufigen EXKLUSIV ODER-Schaltungen gelieferten Ergebnisse und eine Anzeigeschaltung zur Anzeige eines Datenbit- oder eines Prüfbitfehlers, wenn die Fehlerursache im Speicher liegt.
2. 2. Umsetzer nach Anspruch 1, dadurch gekennzeichnet, daß die Prüfschaltung eine Schaltung zur Anzeige eines bei einem Schreibzugriff zum Speicher festgestellten Paritätsfehlers und eine Schaltung zur Anzeige eines bei einem Lesezugriff erkannten Datenbit-Einzelfehler, eines Prüfbit-Einzelfehlers oder eines Doppelfehlers enthält.
3. 3. Umsetzer nach den Ansprüchen 1 und 2, dadurch gekennzeichnet, daß die ersten mehrstufigen EXKLUSIV ODER-Schaltungen wahlweise entweder aus den Datenbits gewonnene Paritätsbits und Prüfbits im Falle eines Lesezugriffs oder aus den Datenbits und Byteparitätsbits gewonnene Prüfbits im Falle eines Schreibzugriffs liefern.
4. 4. Umsetzer nach den Ansprüchen 1 bis 3, dadurch gekennzeichnet, daß erste Torschaltungen zur direkten Eingabe der Bytes und ihrer Paritätsbits in das erste und zweite Register bei einem Schreibzugriff und zweite Torschaltungen zur Ausgabe von Daten- und Paritätsbits über die zweiten EXKLUSIV ODER-Schaltungen zur Prüfung der Byteparität der empfangenen Daten vorgesehen sind.
5. 5. Umsetzer nach den Ansprüchen 1 bis 4, dadurch gekennzeichnet, daß weitere Torschaltungen vorgesehen sind, um nach einer erfolgreichen Paritätsprüfung die empfangenen Daten- und Paritätsbits aus dem ersten Register den ersten mehrstufigen EXKLUSIV ODER-Schaltungen zur Erzeugung von

   109883/1616 Docket YO 969 065

   Prüfbits zuzuleiten und diese mit den Datenbits dem Speicher.
6. 6. Umsetzer nach den Ansprüche'n 1 bis 5, dadurch gekennzeichnet, daß den ersten mehrstufigen EXKLUSIV ODER-Schaltungen bei einem Lesezugriff die Daten- und Prüfbits zugeführt werden, daß Mittel vorgesehen sind, um den Wert eines erzeugten Paritätsbits zu ändern, wenn die Prüfschaltung einen Prüfbit-Einzelfehler aufgrund der Ausgangssignale der zweiten mehrstufigen EXKLUSIV ODER-Schaltungen fest-

   fc stellt, wobei das geänderte Paritätsbit von derjenigen der

   zweiten mehrstufigen EXKLUSIV ODER-Schaltungen erzeugt wird, die das Pehlersignal lieferte.
7. 7. Umsetzer nach den Ansprüchen 1 bis 6, dadurch gekennzeichnet, daß eine Prüfeinrichtung zum Feststellen der Anzahl der fehlerhaften unter den von den zweiten mehrstufigen EXKLUSIV ODER-Schaltungen erzeugten Syndrombits vorgesehen ist und daß an die Prüfeinrichtung eine Anzeigeeinrichtung zur Anzeige eines Prüfbit-Einzelfehlers,

   wenn nur ein Syndrombit fehlerhaft ist, zur Anzeige eines Datenbit-Einzelfehlers, wenn eine ungerade Anzahl größer als Eins von Syndrombits fehlerhaft ist und zur w Anzeige eines Doppelfehlers, wenn eine gerade Anzahl von

   Syndrombits fehlerhaft ist.
8. 8. Umsetzer nach den Ansprüchen 1 bis 7, dadurch gekennzeichnet, daß an die Anzeigeeinrichtung Torschaltungen angeschlossen sind, die bei der Anzeige eines Datenbit-Einzelfehlers die Datenbits und Syndrombits der Fehlerkorrekturschaltung zuführen und die korrigiertem Datenbits wieder speichern, ohne daß die gespeicherten Prüfbits geändert werden.

   109883/1616

   Docket YO 969 065
9. 9. Umsetzer nach den Ansprüchen 1 bis 8, dadurch gekennzeichnet, daß eine Einrichtung zur Erzeugung neuer Byteparitätsbits aus den korrigierten Daten vorgesehen ist, die Torschaltungen enthält zum Zuführen der korrigierten Datenbits und der unveränderten Prüfbits zu den ersten mehrstufigen EXKLUSIV ODER-Schaltungen.

   109883/1616

   Docket YO 969 065

   Hi.

   Leerseite