DE1959231A1

DE1959231A1 - Verfahren und Vorrichtung zur Korrektur von bis zu drei Fehlern eines aus 23 Bits bestehenden Codewortes

Info

Publication number: DE1959231A1
Application number: DE19691959231
Authority: DE
Inventors: Frey Jun Alexander Hamilton; Clark Jun Bradford S
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1969-02-28
Filing date: 1969-11-26
Publication date: 1970-09-10
Also published as: GB1280550A; DE1959231C3; CH532815A; DE1959231B2; US3622982A

Description

IBM Deutschland Internationale Büro-Masthinen Gesellschaft mbH

Böblingen, 24. November 1969 ne-rz

Anmelderin: International Business Machines

Corporation, Armonk, N.Y. 10

Amtliches Aktenzeichen: Neuanmeldung Aktenzeichen der Anmelderin: Docket WA 968 010

Verfahren und Vorrichtung zur Korrektur von bis zu drei Fehlern eines aus 23 Bits bestehenden Codewortes

Die Erfindung bezieht sich auf ein Verfahren zur Korrektur von bis zu drei Fehlern eines aus 23 Bits bestehenden Codewortes, das nach einem zyklischen Golay-Code verschlüsselt ist und aus zwölf Daten- und elf Prüfbits besteht. Der Golay-Code ist ein perfekter Code, der bis zuJLtej. Fehler in einem Wort aus 23 Bits zu korrigieren gestattet. Bei einem aus 23 Bits

11
bestehenden Wort sind genau 2 eindeutige Kombinationen von

drei oder weniger Fehlern möglich. Der Golay-Code gibt alle möglichen Fehlermuster eines aus 23 Bits bestehenden Wortes

11
durch 2 eindeutige Fehlermuster wieder.

Es wurde gefunden-, daß der (23, 12) Golay-Code mit einem zyklischen Code wie dem Bose-Chaudhuri-Code zusammengefasst werden kann. In diesem Fall sind zwölf der 23 Bits eines Wortes Datenbits und elf Prüfbits. Ein Datenwort aus zwölf

009837/1888

;"■■■"■ ' ■ . ■.■■■ \ -2- . _: ■ ■;.■■- -'■■■ .·■.: Bits wird so verschlüsselt, daß zusätzlich elf Prüfbits erzeugt werden, so daß die gesamte Wortlänge 23 Bits beträgt. Das Datenwort wird empfangsseitig mittels eines Prüfwortgenerators entschlüsselt. Der Prüfwortgenerator erzeugt ein aus elf Bits bestehendes Prüfwort, das ein Fehlermuster innerhalb des aus 23 Bits bestehenden Codewortes anzeigt« Das Prüfwort kann daher

durch Vergleich mit den 2 eindeutigen Fehlermustern ent-

11 schlüsselt werden, die den 2 verschiedenen Fehlerkombinationen von drei oder weniger Fehlern innerhalb eines aus 23 Bits bestehenden Codewortes entsprechen. Wenn das 23 Bits enthaltende

Codewort mehr als drei Fehler aufweist, dann entspricht keines

11

der 2 eindeutigen Fehlermuster den durch den Prüfwortgenerator erzeugten Fehlermustern. Daher kann keine Korrektur erfolgen. Wenn jedoch drei oder weniger Fehler in dem 23 Bits enthaltenden Wort vorliegen, dann ist der Inhalt des Prüfwort-

11

generators der gleiche wie eines der 2 eindeutigen Fehlermuster des Golay-Codes. Durch Identifizieren des Inhaltes des Prüfwortgenerators kann man daher bestimmen, welche der 23 Bits eines Wortes fehlerhaft sind und diese dann korrigieren.

Das Hauptproblem bestand bisher dari*^ eine einfache Vorrichtung zu finden, um aus einem 23 Bits enthaltenden, nach dem Golay-Code verschlüsselten Wort die Information zu gewinnen, welche der 23 Bits fehlerhaft sind, wenn bis zu drei Fehler vorlagen.

11 Eine Möglichkeit besteht darin, einen Entschlüsseier aus 2 UND-Gliedern aufzubauen, bei dem jedes UND-Glied elf Eingänge besitzt. Es ist klar, daß diese Lösung einen ungeheuren Aufwand an Bauelementen erfordert.

.
Docket WA 968 010 009837/1880

Mit der Kenntnis, daß der Golay-Code mit einem zyklischen Code zusammengefasst werden kann, können die Eigenschaften zyklischer Codes mit großem Vorteil ausgenutzt werden. Ein zyklischer Code ermöglicht es, den Entschlüsseier anstatt mit 1024 UND-Gliedern nur mit 276 UND-Gliedern aufzubauen, deren jedes elf Eingänge aufweist. Dies ist deshalb möglich, weil der Prüfwortgenerator seinen Zyklus 23-mal durchläuft, was es ermöglicht, jedes der 23 Bits einzeln darauf abzufragen, ob es allein oder in Verbindung mit bis zu zwei anderen Bits des 23 Bits enthaltenden Wortes fehlerhaft ist. Nach der Erzeugung des Prüfwortes ist der Inhalt der Ausgangsstufe des Prüfwortgenerators ein Äquivalent für alle die Fehlermuster, die das erste Bit des 23 Bits enthaltenden Wortes betreffen. Wenn das erste Bit des 23 Bits enthaltenden Wortes fehlerhaft ist, dann erscheint ein eindeutiges Fehlermuster als Inhalt des Prüfwortgenerators. Wenn das erste Bit in Verbindung mit irgendeinem zweiten Bit des 23 Bits enthaltenden Wortes fehlerhaft ist, dann könnten 22 eindeutige Fehlermuster den Inhalt des Prüfwortgenerators bilden. Wenn schließlich das erste Bit in Verbindung mit zwei anderen Bits innerhalb des 23 Bits enthaltenden Wortes fehlerhaft ist, dann gibt es 253 andere eindeutige Fehlermuster, die den Inhalt des Prüfwortgenerators bilden können. Es gibt somit insgesamt 276 unterschiedliche Fehlermuster, die dem Vorliegen von drei oder weniger Fehlern innerhalb eines 23 Bits enthaltenden Wortes zugeordnet sind. Wenn irgendeines der eindeutigen Fehlermuster von dem Prüfwortgenerator festgestellt wird, sind dadurch, daß bekannt ist, welches Bit zu

Docket WA 968 010 009837/1868

einem gegebenen Zeitpunkt abgefragt wird, auch die Stellen der Fehler bekannt· Es sei bemerkt, daß nach dem Stand der Technik 276 UND-Glieder mit je elf Eingängen sowie die notwendige Steuerschaltung erforderlich sind. Dieser hohe Aufwand an Bauelementen macht die Verwendung des Golay-Codes für die Korrektur von dreifachen Fehlern unzweckmäßig.

Dieser Nachteil wird durch das Verfahren gemäß der Erfindung vermieden. Dieses Verfahren zur Korrektor von bis zu drei Fehlern eines aus 23 Bits bestehenden Codewortes, das nach einem zyklischen Golay-Code verschlüsselt ist und aus zwölf Daten- und elf Prüfbits besteht, und bei dem das empfangene Codewort gespeichert und von ihm die Prüfbits erneut abgeleitet werden und bestimmt wird, ob jedes einzelne Bit des Wortes allein oder in Verbindung mit bis zu zwei anderen Bits fehlerhaft ist, ist dadurch gekennzeichnet, daß die einzelnen Bits nacheinander mittels je eines Abfragezyklus darauf abgefragt werden, ob sie allein oder in Verbindung mit bis zu zwei weiteren Bits fehlerhaft sind und dadurch, daß ein Abfragezyklus folgende Schritte enthält: Das Komplementieren des ersten der empfangsseitig abgeleiteten Prüfbits unter der Annahme, daß das abzufragende Bit fehlerhaft ist, das Feststellen, ob weniger als drei gültige Fehler durch die empfangsseitig abgeleiteten und modifizierten Prüfbits angezeigt werden, die Korrektur des abgefragten Bits des gespeicherten Codewortes, wenn weniger als drei gültige Fehler durch die empfangsseitig abgeleiteten und modifizierten Prüfbits angezeigt werden und

Docket WA 968 010 QO9837/180S

das erneute Komplementieren des ersten empfangsseitig abgeleiteten Prüfbits, wenn nach seinem ersten Komplementieren das Vorliegen von weniger als drei gültigen Fehlern nicht angezeigt wurde.

Gemäß einem weiteren Merkmal der Erfindung ist das Verfahren dadurch gekennzeichnet, daß nach dem Abfragen des letzten Bits des gespeicherten Codewortes festgestellt wird, ob die Prüfbits aus lauter Nullen bestehen Und daß, wenn das der Fall ist, ein Signal erzeugt wird, das eine erfolgreiche Fehlerkorrektur des Codewortes anzeigt.

Nach einem weiteren Merkmal der Erfindung ist das Verfahren dadurch gekennzeichnet, daß das nacheinander erfolgende Abfragen der einzelnen Bits auf das Vorliegen von Fehlern nur für die zwölf Datenbits vorgenommen wird, und daß nur festgestellt wird, ob die empfangsseitig abgeleiteten elf Prüfbits weniger als vier Fehler enthalten und daß ein Signal für eine erfolgreiche Fehlerkorrektur der zwölf Datenbits erzeugt wird, wenn das der Fall ist.

Das Verfahren der Erfindung beruht auf dem Konzept, daß, wenn das erste Bit fehlerhaft ist und wenn drei oder weniger Fehler innerhalb des 23 Bits enthaltenden Wortes vorliegen, durch Korrigieren des ersten Bits die Anzahl der Fehler auf zwei oder weniger verringert wird. D. h., wenn drei Fehler vorhanden waren, werden die Fehler dadurch jetzt auf zwei verDocke t WA 968 010 009837/1888

- 4b -

ringert, wenn zwei Fehler vorhanden waren werden die Fehler auf einen verringert. Wenn nur ein Fehler vorlag, liegt nach der Korrektur keiner mehr vor. Wenn jedoch die Annahme falsch war, dann wurde, wenn keine Fehler vorhanden waren, die Anzahl der Fehler auf 1 erhöht. Wenn ein Fehler vorhanden war, dann wurde die Anzahl der Fehler auf zwei erhöht und wenn zwei Fehler vorhanden waren, dann wurde die Anzahl auf drei erhöht. Wenn drei Fehler bereits vorlagen, dann wird die Anzahl der Fehler auf vier erhöht. Das Verfahren sucht nach Anzeigen für das Vorliegen von zwei, einem oder keinem Fehler. In den Fällen, in den ursprünglich zwei oder mehr Fehler vorhanden waren, liefert eine falsche Annahme Ergebnisse, die nicht zu identifizieren sind. Es ist somit ersichtlich, daß eine gewisse Zweideutigkeit vorliegt, ob die Annahme falsch war und ursprünglich ein oder zwei Fehler in dem 23 Bits enthaltenden Wort vorlagen. Es wurde jedoch gefunden, daß die Fehleranzeigen, die sich aufgrund einer falschen Annahme ergeben, zu eindeutigen Zeitpunkten während der Abfrage erscheinen und daher festgestellt und unbeachtet gelassen werden.

Das Verfahren beruht kurz gesagt darauf, anzunehmen, daß das abzufragende Bit fehlerhaft ist und dieses Bit zu korrigieren. Anschließend werden die restlichen 22 Bits auf das Vorliegen von zwei oder weniger Fehlern untersucht· Wenn zwei oder weniger Fehler gefunden werden, dann wird das Fehlermuster nicht als ein fälschliches identifiziert, das aufgrund einer falschen Annahme bezüglich des abgefragten Bits entstand.

Docket WA 968 010 00 9 8 37/1888

Das abgefragte Bit war dann in der Tat fehlerhaft und muß im Speicher korrigiert werden. Das Verfahren verlangt das Abfragen jedes der 23 Bits, um festzustellen ob dieses Bit in der Tat fehlerhaft ist. Eine Entscheidung wird nur getroffen, ob das abgefragte Bit fehlerhaft ist, nicht jedoch darüber, wo weitere Fehler in dem 23 Bits enthaltenden Wort vorliegen. Durch die Annahme, daß das abgefragte Bit fehlerhaft ist, und dadurch, daß es nicht interessiert, wo die anderen Fehler vorliegen, sondern nur, ob sie vorliegen, wird die Verringerung der Bauteile bei einer Vorrichtung zur Durchführung des Verfahrens gemäß der Erfindung ermöglicht.

Docket WA 968 010 009837/1868

Im folgenden wird die Erfindung durch die genauere Beschreibung eines bevorzugten Ausführungsbeispieles in Verbindung mit den Zeichnungen näher erläutert. Von den Zeichnungen zeigen:

Fig. 1 ein Blockdiagramm einer Vorrichtung zur Erkennung und

Korrektur von drei oder weniger Fehlern innerhalb eines 23 Bits umfassenden Wortes, das nach dem Golay-Code verschlüsselt ist;

Fig. 2 ein Schaltbild des in Fig. 1 dargestellten Prüfwortgenera· tors;

Fig. 3 das Schaltbild des Entschlüsselet nach Fig. 1;

Fig. 4 das Schaltbild der Sperrschaltung und der Fehlereinwirkungsschaltung der Vorrichtung nach Fig. 1.

Das Verfahren gemäß der Erfindung dient der Gewinnung der für die Fehlerkorrektur erforderlichen Information aus einem (23, 12) Golay-Code. Das Verfahren erfordert die Kombination des Golay-Codes mit dem bekannten Bose-Chaudhuri-Code. Der Golay-Code ergibt 2048 (2 ) verschiedene Fehlermuster zur Anzeige von drei oder weniger Fehlern innerhalb eines Wortes von 23 Bits. Zwölf der 23 Bits sind Datenbits und die restlichen elf Bits sind Redundanzbits. Bei der Verwendung von zyklischen Codes besteht das Verfahren darin, das eintreffende 23 Bits enthaltende Wort durch das Verschlüsselungspolynom zu dividieren, um ein Prüfwort zu erhalten. Durch das Prüfwort lässt jedes der verschiedenen Fehler-Docke t WA 968 010 .009837/1868

muster darstellen, die beim Vorliegen von drei oder weniger Fehlern in dem ursprünglichen, 23 Bits enthaltenden Wort erhalten werden* Das Verfahren gemäß der Erfindung beruht auf dem grundlegenden Konzept, daß man, wenn man nur eine Information darüber gewinnen will, ob ein vorgegebenes Bit fehlerhaft ist anstatt zu versuchen, alle möglichen erkennbaren Fehler gleichzeitig zu bestimmen, eine gewaltige Verringerung der Bauelemente und der Kosten erzielen kann. Das Verfahren erfordert das Prüfen jedes Bits des 23 Bits enthaltenden Wortes, um festzustellen, ob es allein oder in Verbindung mit zwei oder weniger anderen Bits fehlerhaft ist. Wenn diese Kriterien vorliegen, wird das Fehlerbit im Speicher korrigiert.

Das Verfahren macht von den Eigenschaften des Golay-Codes Gebrauch, wenn dieser mit zyklischen Codes zusammengefasst wird. Eine erwünschte Eigenschaft ist die, daß der Prüfwortgenerator ein Schieberegister ist und gleichzeitig elf Bits des 23 Bits enthaltenden Wortes Überprüft. Wenn bei einem nach dem Golay-Code verschlüsselten Codewort zwei oder weniger Fehler innerhalb der elf Bits vorliegen, die zu einem vorgegebenen Zeitpunkt sich in den Prüfwortgenerator befinden, dann enthält der Prüfwortgenerator zwei oder weniger Einsen, alle übrigen Stellen des Prüfwortgenerators enthalten Nullen. Wenn daher der Inhalt des Prüfwortgenerators 23-mal verschoben wird, werden damit 23 sich überlappende Gruppen von elf Bits überprüft und es wird das Vorliegen von zwei oder weniger Fehlern in den elf Bits nach jeder Verschiebung erkennt, indem festgestellt wird» ob zwei oder weniger Einsen nach jeder Verschiebung in dem Prüf wortgenera-Docket WA |6I 010 009837/1868

tor vorhanden sind.

Es gibt jedoch einen Fall, der gesondert behandelt werden muß. Zunächst ist zu beachten, daß zwei Fehler nicht weiter als elf Bits voneinander entfernt sein dürfen. Wenn ein Fehler in der Stelle 1 und ein Fehler in der Stelle 12 des 23 Bits enthaltenden Wortes vorhanden ist, sind die beiden Fehler elf Bits voneinander entfernt und die beiden Fehler befinden sich zu keinem

W Zeitpunkt gleichzeitig in dem Prüfwortgenerator. Da der Code

ein zyklischer ist, ist dann, wenn das Bit 12 sich in der ersten Stufe des Prüfwortgenerators befindet, das fehlerhafte Bit, das anfangs sich in der Bitstelle 1 befand, zwölf Bits von dieser Bitstelle entfernt. Wenn jedoch das Bit 1 des 23 Bits enthaltenden Wortes und das Bit 13 dieses Wortes fehlerhaft sind, dann beträgt der Abstand zwischen den beiden fehlerhaften Bits ursprünglich zwölf Bits. Es folgt daraus, daß, wenn das Bit 13 in die erste Stufe des Prüfwortgenerators hineingeschoben wird,

|} das Bit 1 elf Bits davon entfernt ist. Daher befinden sich diese beiden fehlerhaften Bits zu keinem Zeitpunkt gleichzeitig in dem Prüfwortgenerator· Da der Code zyklisch ist, könnten die speziellen Fälle, in denen zwei Fehler innerhalb des 23 Bits enthaltenden Wortes auftreten, erkannt werden, wenn es möglich ist, einen Abstand von elf Bits zwischen zwei Fehlern zu erkennen.

Es existiert im Golay-Code ein eindeutiges Fehlermuster für zwei Fehler, das zwei Fehlern, die einen Abstand von elf Bits aufweisen, zugeordnet ist. Wenn daher dieses eindeutige

Docket WA 968 dio 009837/1888

Fehlermuster für zwei Fehler und die Bedingung von zwei oder weniger Einsen im Inhalt des Prüfwortgenerators abgefragt werden, können alle möglichen Fehlerkombinationen von zwei oder weniger Fehlern, die sich im Prüfwortgenerator befinden, erkannt werden.

Das Verfahren erfordert daher das systematische Abfragen jedes der 23 Bits des Wortes in der folgenden Weise:

1. Erzeugen des Prüfwortes in dem Prüfwortgenerator.

2. Der Inhalt des Prüfwortgenerators stellt jetzt die Bitstellen 1 bis 11 des 23 Bits enthaltenden Wortes dar. Es wird angenommen, daß ein Fehler das erste Bit des 23 Bits enthaltenden Wortes betrifft und dieser Fehler wird durch Komplementieren des Inhaltes der ersten Stufe des Prüfwortgenerators korrigiert. .

3. Der Inhalt des Prüfwortgenerators wird um eine Stelle verschoben. Der Prüfwortgenerator zeigt nun Fehlermuster an, die mit den Bits 2 bis 12 des ursprünglichen 23 Bits enthaltenden Wortes verbunden sind.

4. Der Inhalt des Prüfwortgenerators wird bezüglich des eindeutigen Fehlermusters, das zwei Fehler in den Bits 2 und 13 des 23 Bits enthaltenden Wortes anzeigt, und bezüglich des Vorhandenseins von zwei oder weniger Einsen abgefragt. Das Vorliegen von zwei oder weniger Einsen zeigt an, daß zwei oder weniger Fehler innerhalb der Bits 2 bis 12 des ursprünglichen 23 Bits enthaltenden Wortes vorliegen.

5. Wenn das eindeutige, zwei Fehler anzeigende Fehlermuster

Docket WA 968 010 009837/1868

vorliegt oder der Inhalt des Prüfwortgenerators zwei oder weniger Einsen enthält, wird das Vorliegen dieser Bedingungen gespeichert.

6. Die Schritte 3, 4 und 5 werden noch 22-mal ausgeführt.

7. Es wird geprüft, ob der Prüfwortgenerator nach irgendeiner Verschiebung das Vorliegen des eindeutigen, zwei Fehler anzeigenden Fehlermusters oder das Vorhandensein von zwei oder weniger Einsen im Inhalt des Prüfwortgenerators gespeichert hat.

8. Wenn das Vorliegen dieser Bedingung gespeichert wurde, dann war das Bit 1 des 23 Bits enthaltenden Wortes in der Tat fehlerhaft und sollte korrigiert werden. Wenn die vorher erwähnten Bedingungen nicht vorlagen, dann war Bit 1 des 23 Bits enthaltenden Wortes richtig und sollte in der ersten Stufe des Prüfwortgenerators erneut komplementiert werden. Es sei bemerkt, daß nach 23 Verschiebungen der Prüfwortgenerator wieder das ursprüngliche Fehlermuster enthält, das er nach dem Schritt 2 enthielt. Die Schritte 2 bis 8 sind Abfragezyklen.

9. Der Inhalt des Prüfwortgenerators wird um eine Stelle verschoben. Dadurch bilden die Bits 2 bis 12 jetzt den Inhalt des Prüfwortgenerators.

10. Der Abfragezyklus wird wiederholt.

11. Die Schritte 9 und 10 werden wiederholt, bis das Bit 1 wieder in der Stufe 1 des Prüfwortgenerators enthalten ist.

12. Der Inhalt des Prüfwortgenerators wird auf das Vorliegen von lauter Nullen geprüft. Wenn der Prüfwortgenerator Ein-

Docket WA 968 010 0 0 9 8 3 7 / 18 6 8

sen enthält, dann liegen mehr als drei Fehler in dem 23 Bits enthaltenden Wort vor.

Es muß jedoch bemerkt werden, daß die Annahme, ein vorgegebenes Bit sei fehlerhaft, nicht zuzutreffen braucht. Wenn diese Annahme nicht zutrifft, dann wurde die Anzahl der Fehler in dem 23 Bits enthaltenden Wort vergrößert. Wenn also ursprünglich keine Fehler vorlagen, dann liegt jetzt ein Fehler vor. Wenn ursprünglich ein Fehler vorhanden war, dann sind es jetzt zwei. Wenn ursprünglich zwei Fehler vorlagen, dann liegen nun drei Fehler vor. Wenn drei Fehler vorhanden waren, dann sind es jetzt vier. Da jedoch der Decoder nur auf das Vorliegen von zwei oder weniger Fehlern abfragt, wird in den Fällen kein Muster entschlüsselt, in denen ursprünglich zwei oder mehr Fehler vorhanden waren. In dem Fall jedoch, in dem ursprünglich kein oder ein Fehler vorlag, verursacht die Erhöhung auf einen oder zwei Fehler ein unrichtiges Ansprechen der Fehlererkennungsschaltung. Es lässt sich jedoch zeigen, daß das Auftreten eines einzelnen oder eines doppelten Fehlers, das durch eine unrichtige Annahme bedingt war, zu eindeutigen Zeitpunkten innerhalb des Abfragezyklus auftritt. Diese Zeitpunkte sind so eindeutig, daß keine richtige Fehleranzeige für einen einzelnen oder einen doppelten Fehler zu den Zeitpunkten in dem Prüfwortgenerator erscheint, an denen Fehler angezeigt werden, die aufgrund einer falschen Annahme hervorgerufen wurden. Es ist daher ersichtlich, daß die einzelnen Zeitpunkte des Abfragezyklus dazu verwendet werden können, den Ausgang der Fehlererkennungsschaltung für die Anzeige bestimmter

Docket HA 968 οίο 009837/1888

Fehler, die in Wahrheit falsche Anzeigen der abgefragten Bedingungen sind, zu sperren. Eine vollständigere Erklärung des Verfahrens erhält man anhand der Beschreibung der Schaltung zur Durchführung des Verfahrens, die folgt.

Die Schaltung zum Erkennen und Korrigieren von drei oder weniger Fehlern in einem 23 Bits enthaltenden und nach dem Golay-Code verschlüsselten Wortes ist in Fig. 1 dargestellt. Zur Vereinfachung der Erklärung ist ein 23-stufiges Speicherschieberegister zur Speicherung des ursprünglichen 23 Bits enthaltenden Wortes verwendet worden. Die Erfindung ist jedoch nicht auf die Verwendung dieses speziellen Speicherlementes beschränkt, vielmehr kann sie in Verbindung mit jeder beliebigen Speichervorrichtung zusammen mit zusätzlichen Schaltungen angewandt werden, um die gegebene Information zu benutzen. Die Schaltung gemäß der Erfindung hat den Zweck, eine Information darüber zu erhalten, wo der Fehler sich befindet, nicht jedoch darüber, wie der Fehler tatsächlich innerhalb des Speichers korrigiert wird.

Fig. 1 zeigt das Blockschaltbild der Schaltung gemäß der Erfindung. Das eintreffende Wort wird dem 23-stufigen Speicherschieberegister 1 zur Speicherung zugeführt. Außerdem wird das 23 Bits enthaltende Wort auch einem 11-stufigen Prüfwort-

·» ■ ■

generator 2 zugeführt, der ein aus elf Bits bestehendes Prüfwort erzeugt. Der Entschlüssler 3, der notwendig ist, um zu bestimmen, ob das eindeutige Muster für einen doppelten Fehler

Docket WA 968 010 0098 37/1868

oder ob zwei oder weniger Einsen sich in dem Prüfwortgenerator befinden, ist mit dem Prüfwortgenerator 2 verbunden. Eine Sperrschaltung 4 ist ebenfalls an den Prüfwortgenerator 2 angeschlossen, ferner an den Entschlüsseier 3 und die Steuerschaltung 6 zur Bestimmung, ob die Anzeige des Entschlüsseiers 3 eine Anzeige wirklicher Fehlerbedingungen oder eine Anzeige trügerischer Fehler ist, die aufgrund einer falschen Annahme entstanden. Die Fehler-Einwirkungsschaltung 5 liefert ein Ausgangssignal, das anzeigt, ob das abgefragte Bit fehlerhaft ist oder nicht, an das Speicherschieberegister 1 und den Prüfwortgenerator 2. Die Steuerschaltung 6 liefert alle erforderlichen Schiebesignale, Komplementiersignale und Abtastimpulse. Die Steuerschaltung 6 enthält ebenso die notwendigen Taktgeber und Zähler, um die Anzahl der Verschiebungen in einem Abfragzyklus und die Anzahl der Abfragezyklen bei der Prüfung eines 23 Bits enthaltenden Wortes zu steuern.

Die in der Steuerschaltung 6 verwendeten Schaltungen gehören zum Stand der Technik, und es liegt im Rahmen des Könnens eines Durchschnittsfachmanns, die erforderlichen Taktgeber und Zähler aufzubauen und für die Verteilung der Taktsignale an die übrige Schaltung zu sorgen, so daß eine speziellere Beschreibung des Aufbaus der Steuerschaltung nicht erforderlich ist.

In Fig. 2 ist der elfstufige Prüfwortgenerator 2 dargestellt. Dieser Generator ist von einer zum Stand der Technik gehörenden Art. Der einzige Unterschied zwischen Prüf wortgeneratoren nach

Docket WA 968 010 00 9837/1868

dem Stand der Technik und den in Fig. 2 dargestellten besteht darin, daß der Inhalt der ersten Stufe T1 des Prüfwortgenerators • 2 komplementiert werden kann. Wenn der Prüfwortgenerator das Prüfwort aus dem eintreffenden, 23 Bits enthaltenden Wort erzeugt, wird das 23 Bits enthaltende Wort dem Eingang des exklusiven ODER-Gliedes zugeführt. Das Erzeugen des Prüfwortes durch das aufeinanderfolgende Eingeben der 23 Bits ist bekannt. Eine genauere Beschreibung der Arbeitsweise des Prüfwortgenerators

ft " ' ' ' ' ■'■■'■■ ' ■■ ■'■'■"

^m ist daher entbehrlich.

Nach dem Erzeugen des Prüfwortes aus dem eingegebenen, 23 Bits enthaltenden Wortes wird dem Eingang des exklusiven ODER-Gliedes 11 während aller Abfragezyklen der Wert 0 zugeführt. Die Ausgänge der elf Stufen Ti bis T11 des Prüfwortgenerators 2 bilden die elf Ausgangsleitungen t bis t .

1 11

Fig. 3 zeigt den Entschlüsseier 3 der in Fig. 1 dargestellten ^ Schaltung. Die Ausgangsleitungen t bis t des Prüfwortgenerators 2 führen an die Eingänge des Entschlüsselers 3.

Das eindeutige Fehlermuster des Golay-Codes, das zwei Fehlern zugeordnet ist, die elf Bits voneinander entfernt sind, wobei das erste Bit sich in der ersten Stelle des Prüfwortgenerators - 2 befindet, ist 00101110001. Die Inverter 51, 52, 53, 54, 55 und 56 sowie das UND-Glied 57 dienen dazu, den Inhalt des Prüfwortgenerators auf dieses eindeutige Fehlermuster für das Vorliegen zweier Fehler zu überprüfen. Wenn ein Ausgangsimpuls

Docket WA 968 010 Q09837 / 1 868

auf der Ausgangsleitung X1 des UND-Gliedes 57 erscheint, dann ist das eindeutige Fehlermuster für das Vorliegen zweier Fehler in dem Inhalt des Prüfwortgenerators 2 durch den Entschlüsseier 3 festgestellt worden.

Die exklusiven ODER-Glieder 31, 32, 33, 34, 35, 36, 37, 38 und 39 bilden eine Erkennungsschaltung, die einen von dem ODER-Glied 35 erzeugten Ausgangsimpuls liefert, wenn auf den Leitungen t

2 bis t eine ungerade Anzahl von Einsen vorhanden ist. Der

11 Ausgangsimpuls des exklusiven ODER-Gliedes 35 wird dem Inverter

49 zugeführt. Dieser liefert einen positiven Ausgangsimpuls, wenn die Anzahl der auf den Leitungen t bis t vorhandenen

2 11 Einsen geradzahlig oder Null ist. Der Entschlüsseier 3 enthält

außerdem eine Schaltung zur Feststellung, ob weniger als zwei

Einsen auf den Eingangsleitungen t bis t vorhanden sind.

2 11 Die für das Feststellen dieser Bedingung erforderliche Schaltung besteht aus dem ODER-Glied 30 in Verbindung mit den UND-Gliedern 41 bis 48 und den exklusiven ODER-Gliedern 31 bis 33 und 34 bis 39. Die logischen Verknüpfungen, die an den Ausgängen der UND-Glieder 40 bis 48 vorliegen, können der Tabelle I entnommen werden.

Docket WA 968 οίο 009837/1888

	1959231	Tabelle I	Logische Verknüpfung
	(t . t ) 11 10
UND-Glied	(t +t ).(t +t ) 11 10 9 8
40	Ct .t ) 9 8
41	(t +t +t +t ).(t +t +t +t +t +t 11 10 9 8 2 3 4 5 6
42	(t .t ) 7 6
43	(t +t ).(t +t ) 7 6 5 4
44	(t .t ) 5 4
45	(t +t +t +t ).(t +t ) 7 6 5 4 3 2
46	(t .t ) 3 2
47
48

Das Ausgangssignal des ODER-Gliedes 30 stellt die ODER-Verknüpfung der Ausgangssignale der UND-Glieder 40 bis 48 dar. Durch Entwicklung der logischen Ausdrücke der Tabelle I lässt sich zeigen, daß jede mögliche Kombination von zwei Einsen, die auf den Leitungen t bis t vorliegen, ein Ausgangssignal des ODER-Gliedes

2 11 30 erzeugt. Das ODER-Glied 35 liefert immer aann ein positives

Ausgangssignal, wenn mehr als zwei Einsen auf den Leitungen

t bis t vorhanden sind· Das Ausgangssignal des ODER-Gliedes

2 11 30 wird dem Inverter 50 zugeführt. Der Inverter 50 liefert dann

ein positives Ausgangssignal, wenn weniger als zwti Einsen auf Docket WA 968 01Q 009837/1868

den Eingangsleitungen t bis t vorhanden sind. Das UND-Glied

2 11

58 liefert ein Ausgangssignal, wenn auf der Eingangsleitung t

eine Eins vorhanden ist und der Inverter ein positives Ausgangssignal liefert. Genauer gesagt erzeugt das UND-Glied 58 ein positives Ausgangssignal auf der Leitung X2, wenn die erste Stufe des Prüfwortgenerators eine Eins enthält und die restlichen zehn Stufen T2 bis T11 des Prüfwortgenerators lauter Nullen enthalten oder irgendeine dieser Stufen eine weitere Eins enthält.

Ein Eingang des UND-Gliedes 59 ist mit dem Ausgang des Inverters 51 verbunden, dessen Eingang seinerseits an die Leitung t ange-

1. schlossen ist. Der zweite Eingang des UND-Gliedes 59 ist mit dem Ausgang des Inverters 49 verbunden, während der dritte Eingang des UND-Gliedes 59 an den Ausgang des Inverters 50 angeschlossen ist. Auf der Ausgangsleitung X3 des UND-Gliedes 58 erscheint ein Ausgangssignal, wenn auf der Leitung t eine Null vorhanden ist,

1 wenn die Zahl der Einsen auf den Eingangsleitungen t bis t

2 11

nicht ungerade ist und wenn die Zahl der Einsen auf den Eingangsleitungen t bis t kleiner als zwei ist. Daher kann ein Aus-

2 11
gangssignal auf der Ausgangsleitung X3 des UND-Gliedes 59 nur

erscheinen, wenn auf allen Eingangsleitungen t bis t Nullen

1 11 vorhanden sind.

Der Entschlüsseier prüft auf die Bedingungen, die bei der Beschreibung des Verfahrens nach der Erfindung angegeben wurden; d.h. er prüft auf das Vorhandensein des eindeutigen Fehlermusters, das zwei Fehler anzeigt. Diese Anzeige liefert das Aus-

Docket WA 968 010 Ö 0 9837/1868

ZO

Λ* -

gangssignal auf der Leitung X1. Weiter prüft der Entschlüsseier auf das Vorhandensein von zwei Einsen oder einer Eins im Prüfwortgenerator, was ein Signal auf der Leitung X2 anzeigt. Schließlich prüft er darauf, daß keine Einsen in dem Prüfwortgenerator vorhanden, was ein Signal auf der Leitung X3 anzeigt. Es sei bemerkt, daß, da das Verfahren verlangt, daß zwei oder weniger Einsen in dem Prüfwortgenerator vorhanden sind, beträchtliche Einsparungen an Bauelementen bei dem Aufbau der gezeigten Schaltung ermöglicht werden. Dabei wird von der Tatsache Gebrauch gemacht, daß, wenn zwei Fehler in den elf Bits vorliegen, die während eines bestimmten Zyklus in dem Prüfwortgenerator abgetastet werden, dieser eine oder zwei Einsen enthält, während alle seine übrigen Stufen Nullen enthalten. Dieses Muster bleibt bestehen und wird durch den Prüfwortgenerator geschoben, bis ein Fehler durch eine Eins in der ersten Stufe T1 des Prüfwortgenerators angezeigt wird. Wenn zwei Fehler vorhanden waren, dann bildet der eine den Inhalt der Stufe T1, während der andere Fehler den Inhalt einer der restlichen zehn Stufen des, Prüfwortgenerators bildet. Es ist nur erforderlich, zu bestimmen, ob eine Eins auf den Leitungen t bis t des P.rüf-

2 11 wortgenerators vorhanden ist und ob eine Eins auf der Leitung

t vorlag. Alle Fehlermuster, die bei einem nach dem Golay-Code

1 ■ . ■ ■ ■ ...

verschlüsselten Wort beim Vorliegen von 0, 1 oder 2 Fehlern auftreten, können durch den Entschlüsseier 3 erkannt werden.

Fig. 4 zeigt die Sperrschaltung 4 und die Fehler-Einwirkungsschal- «ungen der Schaltung nach Fig. 1. Wenn die zugrundeliegende

Annahme, daß das überprüfte Bit fehlerhaft ist, falsch ist, Docket WA 968 010 009837/1888

wird ein fehlerfreies Bit in ein fehlerhaftes Bit umgewandelt, was sich in dem Fehlermuster eines im Golay-Code verschlüsselten Wortes wiederspiegelt. Dies ist besonders problematisch, wenn ursprünglich kein Fehler oder ein Fehler in dem 23 Bits enthaltenden Wort vorlag. Es wurde gefunden, daß diese falschen Anzeigen zu eindeutig bestimmten Zeitpunkten auftreten, so daß sie nicht mit echten Fehleranzeigen verwechselt werden können. Daher ist es jetzt erforderlich, die möglichen Fälle, echte und falsche Fehleranzeigen von dem Entschlüsseier zu erhalten, zu diskutieren.

Der erste zu untersuchende Fall ist der, bei dem keine Fehler in dem 23 Bits enthaltenden Wort vorliegen. Daher besteht das Prüfwort in dem Prüfwortgenerator aus lauter Nullen. Durch das Komplementieren des ersten Bits in dem Prüfwortgenerator bei dem Versuch, einen angenommenen Fehler zu korrigieren, wurde in der Tat ein Fehler erzeugt. Das Fehlermuster in dem Prüfwortgenerator lautet 10000000000, das von dem Entschlüsseier 3 als ein gültiges Fehlermuster erkannt wird. Nach 23 Verschiebungen des Inhalts des Prüfwortgenerators 2 während des Abfragezyklus erscheint das gleiche Muster erneut und wird erneut durch den Entschlüsseier 3 interpretiert. Daher werden unechte Fehler zu den Zeitpunkten

S und S festgestellt. 0 23

Der zweite zu untersuchende Fall ist der, bei dem ein Fehler in de» 23 Bits enthaltenden Wort vorliegt und dieser Fehler das etste Bit des Wortes betrifft. Der Inhalt des Prüfwortgenerators ift dann 10000000000. Nach dem Komplementieren des Inhalts der

Docket WA 968 010 009837/1868

Stufe 1 aufgrund der Annahme, daß das Bit in der Tat fehlerhaft war, besteht der Inhalt des Schieberegisters aus lauter Nullen. Dieser Zustand des Prüfwortgenerators 2 wird durch den Entschlüsseier 3 erkannt und es erscheint ein Ausgangssignal auf der Aüsgangsleitung X3 des Entschlüsselers 3. Dieses Ausgangssignal ist eine echte Anzeige. Es sei bemerkt, daß keine Möglichkeit besteht, eine falsche Anzeige auf der Ausgangsleitung X3 des Entschlüsselers 3 zu erhalten.

Der dritte zu untersuchende Fall ist der, bei dem ein Fehler vorhanden ist und der Fehler sich unter den Bits 2 bis 11 des 23 Bits enthaltenden Wortes befindet. Das Fehlermuster in dem Prüfwortgenerator besteht aus lauter Nullen mit Ausnahme einer Eins, die in der Stufe des Prüfwortgenerators 2 vorhanden ist, die der Bitstelle des 23 Bits enthaltenden Wortes entspricht, die fehlerhaft war* Durch das Komplementieren des Inhaltes der ersten Stufe des Prüfwortgenerators 2 wird ein zweiter Fehler erzeugt, der unmittelbar von dem Entschlüsseier 3 zum Zeitpunkt

S erkannt wird. Nach 23 Verschiebungen wird das gleiche Fehler-0 muster erneut von dem Entschlüsseier . zum Zeitpunkt S ent-

23

schlüsselt und ein Ausgangssignal erscheint auf der Ausgangsleitung X2. Somit können unrichtige Anzeigen von doppelten

Fehlern vor dem Verschieben, d.h. zum Zeitpunkt S und nach der

23. Verschiebung zum Zeitpuntk S erhalten werden.

Der vierte zu untersuchende Fall ist der, bei dem das Bit 12 Docket WA 968 010 Q₀₉₈₃₇Z₁₈₆₈

- Vd -

des 23 Bits enthaltenden Wortes fehlerhaft ist. Wenn der Inhalt der ersten Stufe des Prüfwortgenerators 2 komplementiert wird, ist das Fehlermuster in dem Prüfwortgenerator 2 das eindeutige Fehlermuster für zwei Fehler, die elf Bits voneinander entfernt sind. Auch in diesem Fall erkennt der Entschlüsseier 3 unmittelbar das Fehlermuster in dem Prüfwortgenerator 2. Und wieder erscheint nach der 23. Verschiebung das gleiche Fehlermuster in dem Prüfwortgenerator 2 und wird durch den Entschlüsseier 3 erneut entschlüsselt und ein Ausgangssignal erscheint auf der Ausgangsleitung X1. Es sei bemerkt, daß das Vorliegen von Fehlern anzeigende Ausgangssignal, das beim Vorliegen des eindeutigen, zwei Fehler anzeigenden Fehlermusters erzeugt wird, zu den

Zeitpunkten S und S erscheint. 0 23

Der fünfte zu untersuchende Fall ist derjenige, bei dem das Bit 13 des 23 Bits enthaltenden Wortes fehlerhaft ist. Nach dem Komplementieren des Inhalts des Prüfwortgenerators 2 wird das Fehlermuster, das in dem Prüfwortgenerator vorhanden ist, durch den Entschlüsseier 3 nicht erkannt. Nach zwölf Verschiebungen jedoch befindet sich zum Zeitpunkt S das 13. Bit des 23 Bits

12 enthaltenden Wortes in der ersten Stufe des Prüfwortgenerators 2 und das fehlerhaft gewordene erste Bit des 23 Bits enthaltenden Wortes wird als nächstes Bit dem Prüfwortgenerator 2 zugeführt. Es ist daher ersichtlich, daß die beiden Fehler 11 Bits voneinander entfernt sind. Das Fehlermuster in dem Prüfwortgenerator 2 zeigt dies an und das eindeutige Fehlermuster für zwei Fehler ist vorhanden. Es sei bemerkt, daß das eindeutige Fehler-

Docket WA 968 010 „0-9837/1*88

muster für zwei Fehler, das zum Zeitpunkt S festgestellt wird,

.12 trügerisch ist.

Der sechste zu untersuchende Fall ist derjenige, bei dem ein Fehler unter den Bits 14 bis 23 des 23 Bits enthaltenden Wortes vorliegt. Es erscheint ein Ausgangssignal auf der Leitung X2 des Entschlüsselers 3. Die speziellen Zeitpunkte für die besonderen Fehlermuster in dem Prüfwortgenerator, die einem Fehler in den η. Stellen 14 bis 23 des 23 Bits enthaltenden Wortes zugeordnet sind, sind in der Tabelle II angegeben. Bei den Fehlermustern handelt es sich um unechte Fehlermuster·

	Tabelle II	Prüfwortjienerator
Bit in Stelle	Zeitpunkt	10000000001
14	S13	10000000010
15	S14	10000000100
16	S15	10000001000
17	S16	10000010000
18	S17	10000100000
19	S18	10001000000
20	S19	10010000000
21	S20	10100000000
22	S21	11000000000
23	S22

Der siebte zu untersuchende Fall ist derjenige, bei dem dfts 23 Bits enthaltende Wort zwei Fehler aufweist, deren einer das erste Bit und deren anderer eines der restlichen 22 Bits betrifft.

^{DoeketWA968010} .009837/1868

Wenn daher der Inhalt der ersten Stufe des Prüfwortgenerators komplementiert wird, wird ein Fehler korrigiert und die Anzahl der Fehler in dem Prüfwortgenerator wird von zwei auf eins vermindert. Das Fehlermuster 10000000000 erscheint während der Zeitpunkte S bis S , um anzuzeigen, daß ein Fehler vorliegt.

1 22
Dabei handelt es sich um echte Fehleranzeigen. Es sei bemerkt,

daß zu den Zeitpunkten S oder S das vorher genannte-Fehler--

0 23
muster, das das Vorhandensein eines echten Fehlers anzeigt,

nicht erscheint.

Der achte zu untersuchende Fall ist derjenige, bei dem zwei Fehler in den Bitstellen 2 bis 23 des 23 Bits enthaltenden Wortes vorliegen und bei dem durch Komplementieren des Inhaltes des Prüfwortgenerators 2 ein zusätzlicher Fehler erzeugt wird. In diesem Fall wird von dem Entschlüssler 3 Vein Fehlermuster erkannt und daher können keine irrtümlichen Fehleranzeigen abgegeben werden.

Der neunte zu untersuchende Fall ist derjenige, bei dem drei Fehler innerhalb der Schieberegisterstellen 2 bis 23 vorliegen und ein vierter Fehler durch Komplementieren des Inhaltes der ersten Stufe des Prüfwortgenerators 2 erzeugt wird. Auch in diesem Fall wird das Fehlermuster, das erhalten wird, von dem Entschlüsseier 3 nicht entschlüsselt*. Daher wird auch in diesem Fall keine trügerische Fehleranzeige von dem Entschlüsseier 3 abgegeben.

Docket WA 968 010 0 0 9 8 3 7/1868

Der zehnte und letzte zu untersuchende Fall ist derjenige, bei dem das 23 Bits enthaltende Wort drei Fehler aufweist,von denen einer das erste Bit betrifft. Durch Komplementieren des Inhaltes der erstenStufe des Prüfwortgenerators wird der Fehler beseitigt und die Anzahl der Fehler, die durch das Prüfwort wiedergegeben wird, wird von drei auf zwei verringert. Es lässt sich zeigen, daß alle Kombinationen von zwei Einsen aus den restlichen 22 Bits von dem Entschlüsseier 3 während der 23 Ver-Schiebungen erkannt werden. Es sei jedoch bemerkt, daß die Fehlermuster, die in den Fällen 3, 4, 5 und 6 für das Vorliegen von doppelten Fehlern existieren, nicht auch durch echte Fehler hervorgerufen werden können. Die Fehlermuster zur Korrektur echter doppelter Fehler und die zur Korrektur trügerischer doppelter Fehler sind einander ausschließende Teilmengen der Gesamtmenge der Fehlermuster zur Korrektur doppelter Fehler und können daher getrennt werden.

In Fig. 4 ist die erforderliche Sperrschaltung dargestellt. Die drei Ausgangsleitungen des Entschlüsselers 3 führen zu drei UND-Selbsthalteschaltungen der Sperrschaltung 4. Eine UND-Selbsthalteschaltung ist eine Schaltung, die beim Eintreten zweier Ereignisse ausgelöst wird und diesen Zustand auch nach dem Verschwinden der Eingangssignale beibehält. Solche UND-Selbsthalteschaltungen sind bekannt und werden daher hier nicht näher beschrieben.

Das Ausgangssignal auf der Leitung X3 des Entschlüsselet 3 wird

Docket.WA'968 010 '

009837/1868

der Selbsthalteschaltung 62 zugeführt. Es sei bemerkt, daß gemäß der vorausgehenden Erörterung der zehn möglichen Fälle diese Ausgangsleitung nie gesperrt werden muß.

Die Ausgangsleitung X2 des Entschlüsslers 3 liefert eine Fehleranzeige nur, wenn der Fehler in der ersten Stelle des Prüfwortgenerators vorlag oder wenn außerdem ein weiterer Fehler im Inhalt der restlichen zehn Stufen des Prüfwortgenerators 2 vorhanden ist. Wie im Zusammenhang mit dem ersten und dritten Fall gezeigt wurde, sind diejenigen Ausgangssignale, die auf der

Leitung X2 während der Zeitpunkte S bis S erscheinen, trüge-

0 23 risch. Daher sollte ihre Weiterleitung unterbunden werden. Somit wird das Auslösen der UND-Selbsthalteschaltung 61 verhindert, wenn eine Anzeige von dem Entschlüsseier 3 zu den Zeitpunkten

S und S eintrifft. 0 23

Wie in Verbindung mit dem Fall 6 gezeigt wurde, können die zwei Fehlermuster, die zu bestimmten Zeitpunkten vorhanden sind, falsche Ergebnisse liefern. Die UND-Selbsthalteschaltungen 63-72 fragen das Vorhandensein dieser Bedingungen ab. Da nur eine dieser Bedinungen während eines Abfragezyklus vorliegt, sind die Ausgangsleitungen der UND-Selbsthalteschaltungen 63 bis 72 alle mit dem ODER-Glied 73 verbunden. Die Wirkung des Auslösens der UND-Selbsthalteschaltung 61 durch ein Signal auf der Leitung X2, das nicht zu den Zeitpunkten S und S auftritt, wird aufge-

0 23 hoben, wenn irgendeine der Selbsthalteschaltungen 63 bis 72

ausgelöst wurde. Daher kann das UND-Glied Docket WA 968 010 009837/1868

75 nur ein positives Ausgangssignal liefern, wenn ein Ausgangssignal auf der Leitung X2 des Entschlüsselers 3 vorhanden ist und die vorher beschriebenen Fälle 1,3 und 7 nicht gegeben sind* Die Ausgangsleitung X1 des Entschlüsselers 3 ist mit der ÜND-Selbsthalteschaltung 60 verbunden. Die UND-Selbsthalteschaltung 60 wird ausgelöst, wenn auf der Ausgangsleitung X1 ein Ausgangssignal zu anderen Zeitpunkten als S , S und S vor-

0 12 23

banden ist. Die Zeitpunkte S , S und S sind mit Rücksicht ' 0 12 23

auf die vorher erörterten Fälle 4 und 5 ausgenommen.

Die Ausgänge der UND-Selbsthalteschaltungen 60 und 61 sowie der Selbsthalteschaltung 62 sind mit dem ODER-Glied 80 verbunden. Der Ausgang des ODER-Gliedes 80 ist der Ausgang der Sperrschaltung. Der einzige Zeitpunkt, an dem das ODER-Glied 80 ein Ausgangssignal liefert, ist der, zu dem eine gültige Bedingung vorliegt, d.h. wenn das eindeutige, das Vorliegen zweier Fehler anzeigende Fehlermuster festgestellt wurde oder zwei oder weniger Einsen in dem Inhalt des Prüfwortgenerators vorhanden waren.

Die Fehler-Einwirkungsschaltung besteht aus dem Inverter 81 und den Torschaltungen 82 und 83. Nach der 23. Verschiebung, nach der der Prüfwortgenerator wieder seinen ursprünglichen Zustand annimmt, wird ein Abtastimpuls E1-E23 erzeugt. E1 dient der Abtastung des ersten Bits, E2 der des zweiten Bits usw. Der Abtastimpuls wird durch die Steuerschaltung 6 erzeugt und tastet die Torschaltungesi 82 und 83 ab. Wenn kein Fehler in der überprüften Bitstelle vorlag, schaltet die Torschaltung 82 den

Docket WA 968 010 009837/1868

Abtastimpuls durch und dieser komplementiert erneut den Inhalt der ersten Stufe des Prüf wortgenerators 2. Wenn ©in Fehler vorlag, durchläuft der Abtastimpuls die Torschaltung 83 und komplementiert das fehlerhafte Bit. In dem gegebenen Beispiel komplesssntiert das Ausgangssignal der Torschaltung 83 den Inhalt der ersten Stufe des Speicherschieberegisters 1. Der Inhalt des Speicher» Schieberegisters wird dann verschoben, wobei das nlefest© abzu» fragende Bit in die erste Stufe gelangt und das Abfrsgera d@s nächsten Bits erfolgt in der gleichen Weise, in der das erste Bit geprüft wurde.

Die vorausgehende Erörterung beschrieb zehn mögliche Kombinationen der ersten elf Bits eines 23 Bits enthaltesiden Wortes, das dem Prüfwortgenerator zugeführt wurde. Ba der verwendete Code ein zyklischer Code ist, ist die Frage, welches das erste Bit des 23 Bits enthaltenden Worts ist, eine Frage willkürlicher Bezugnahme. Durch einmaliges Verschieben des Inhalts des Schieberegisters wird das Bit 2 des 23 Bits enthalttnden Wortes nun das Bit 1 und alle die gleichen Regeln und Erörterungen, die für das ursprüngliche Bit 1 des 23 Bits enthaltendem Wortes galten, gelten auch jetzt.

Es sei bemerkt, daft es, da zwölf der Bits des 23 Bits enthalten den Wortes Datenbits sind, in den meisten Fällen nur erwünscht ist, die Datenbits zu korrigieren. Daher kann die Korrektur nach den Abfragen des zwölften Bits beendet werden« Wenn in de» 25 Bits enthaltenden Wort drei oder weniger Fehle? vorlagen,

Docket WA 968 010 009837/1868

SO

3? -

ist zn diesem Zeitpunkt jeder Fehler, der in den ersten zi-Mlit Bits vorhanden war, korrigiert· Um festzustellen, ob erfolgreich korrigiert wurde, braucht man nur den Inhalt des Prü£w©rtg©iierators noch einmal zu verschieben, so daß die .<§!£ Bits₀ die den" Inhalt des Prüfwortgenerators bilden, die @lf ■ Prüfteits sind (Bits 12«25)₉ Unter diesen Bedingungen wird ©is©- Amdahl ron Binsen, die in dem Prüfwortgenerator 2 vorhanden IBt₉ gezähltο' Wsaa jedoch die Anzahl der Einsen in dem Prüfwort-

™ gexusifst®!? größer als drei ist, dann muß angenommen werden, dal äi® gwölf Batenbits noch fehlerhaft sind.

. ZissSH3H©sfc£a§send ist festzuhalten, daß ein allgemeiner Überblick üb©r ©lae ¥ollständige Operation der Schaltung hier gegeben wird. Nacli dem Speichern des 23 Bits enthaltenden Wortes in dem Speicherschieberegister 1 und dem Erzeugen des Prüfwortes in dem Prüfwortgenerator 2 beginnt das Gewinnen der erforderlichen Korrekturinformation durch das Prüfwort. Der Inhalt des Prüfwort- ^ g®a©rstors 2 entspricht den Bits 1-11 des 23 Bits enthaltenden Wortesa D©r Inhalt der dem Bit 1 zugeordneten Stufe des Prüfwortg@merators wird aufgrund der Annahme, daß der Inhalt fehlerhaft

. Das erzeugte Prüfwort wird dann 23-mal ver- i₉ worauf der Inhalt des Prüfwortgenerators 2 wieder seinen ursprünglichen Wert annimmt. Der Entschlüsseier 3 überwacht den Xs&haliä dos Prüfwort generators und liefert ein Aus gangs signal, wenn

Fehlermuster für zwei Fehler, die genau elf Bits entfernt sind, auftritt oder wenn der Inhalt des

gangssignal der Entschlüsselungsschaltung wird der Sperrschaltung zugeführt, in der es mittels Selbsthalteschaltungen gespeichert wird. Nach der 23. Verschiebung erscheint am Ausgang der Sperrschaltung 4 ein Ausgangssignal, wenn der Entschlüssler 3 eine der vorher genannten Bedingungen feststellt und wenn diese Bedingungen keine trügerischen waren. Die Steuerschaltung erzeugt dann einen ersten Abtastimpuls, der die Fehlereinwirkungsschaltung 5 abtastet, die, wenn kein Fehler festgestellt wurde, den Inhalt der ersten Stufe des Prüfwortgenerators 2 erneut komplementiert. Wenn ein Fehler festgestellt wurde, wird das erste Bit des 23 Bits enthaltenden Wortes durch die Fehler-Einwirkungsschaltung komplementiert. Der Inhalt des Prüfwortgenerators wird dann um eine Stelle verschoben und das Prüfwort besteht aus den Bits 2-11. Der Inhalt der ersten Stufe des Prüfwortgenerators wird dann komplementiert. Der Inhalt des Prüfwortgenerators wird erneut 23-mal verschoben, wobei der Entschlüsseier den Inhalt überwacht, um festzustellen, ob eine der Bedingungen vorliegt. Die Sperrschaltung verhindert wieder falsche Anzeigen. Die Fehler-Einwirkungs schaltung liefert einen Impuls, der entweder den Fehler in der zweiten Stelle des Datenwortes korrigiert oder den Inhalt der ersten Stelle des Prüfwortgenerators 2 erneut komplementiert.

Der Inhalt des Prüfwortgenerators wird dann um eine Stelle verschoben, so daß die Bits 3-14 den Inhalt des Prüfwortgenerators bilden, und es wird der Inhalt der ersten komplementiert. Der Zyklus wird für das dritte Bit und für alle die restlichen Bits fortgesetzt, bis das 23. Bit in gleicher Weise abgefragt wurde. Docket WA 968 010 009837/1868

Zu di@sem Zeitpssakt sollte der Inhalt des Prüfwortgenerators aus laater MiEll@a b©ifefe©ii_e Das würde anzeigen^ daß₉ falls drei oder wenig©? Fehler ¥®ylagesi_p diese drei oder weniger Fehler korrigiert wurden ο ?feaa j©d©cla der Inhalt des Prüfwortgenerators noch Einsen enthält, dann befinden sich unter den 23 Bits noch Fehler.

Docket WA 968 010 0 0 9 8 3 7/1868

Claims

PATENTANSPRÜCHE

1. Verfahren zur Korrektur von bis zu drei Fehlern eines aus 23 Bits bestehenden Codewortes, das nach eimern zyklischen Golay-Code verschlüsselt ist Und aus 12 Daten und 11 Prüfbits besteht, bei welchem Verfahren das eijipfaagoa© Codewoi' gespeichert und von ihm die Prüfbits erneut abgeleitet werden und bestimmt wird, ob jedes einzeln© Bit des Wortes allein oder in Verbindung mit bis zu zwei anderen Bits fehlerhaft ist, dadurch gekennzeichnet, daß die einzelnen Bits nacheinander mittels je eines Abfragezyklns darauf abgefragt werden, ob sie alIeine oder in Verbindung mit bis zu zwei weiteren Bits fehlerhaft simd und daß ein Abfragezyklus folgende Schritte enthält: Das Komplementieren des ersten der empfangsseitig abgeleiteten Prüfbits unter der Annahme, daß das abzufragende Bit fehlerhaft ist, das Feststellen, ob weniger als drei gültige Fehler durch die empfangsseitig abgeleitetes und modifizierten Prüfbits angezeigt werden, di@ Ε@ΤΊ?Θΐτ&η? des abgefragten Bits des gespeicherten Codewort ei; _? wsain weniger als drei gültige Fehler durch die empfangsseitig abgeleiteten und modifizierten Prüfbits angezeigt werden und das erneute Komplementieren des ersten empfangsseitig abgeleiteten Prüfbits, wenn nach seinen ersten Komplementieren das Vorliegen von weniger als drei gültigen Fahlem nicht angezeigt wurde.

Socket «λ .961 010 00 9837/1868

-JA-

'2o Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß nach d@ai Abfragen des letzten Bits des gespeicherten Codewortes festgestellt wird, ob die Prüfbits aus lauter Nullen be- und daß, wenn das der Fall ist, ein Signal erzeugt

las eiae erfolgreiche Fehlerkorrektur des Codewortes ■

rfahren Eseh Ansprach 1, dadurch gekennzeichnet, daß das Eseh@iaaii.der erfolgende Abfragen dsr einzelnen Bits auf das Vorliegen von Fehlern nut für die 12 Datenbits vorg©»

wir dp und daß nur festgestellt wird, ob die empfangsabgeleiteten 11 Prüfbits weniger als 4 Fehler entumd daß ein Signal für eine erfolgreiche Fehlerkorrektur der 12 Datenbits erzeugt wird, wenn das der Fall ist. ■ ■ . . · ■

Vorrichtung zur Durchführung des Verfahrens nach den Ansprüchen 1 bis 3, dadurch gekennzeichnet, daß die Ausgangs-

stufe (T-1j Fig. 2) eines elfstufigen Schieberegister-Früfwortgenerators (2| Fig. 1) zum empfangsseitigen Abl©it@a der Prüfbits einen zusätzlichen Eingang aufweist, Signal zum Komplementieren des Inhaltes dieser

Stufe über ein ODER-Glied (1Oj Fig. 2) zugeführt wird, ,,

(Si Fig. 1) verbunden ist, deren zweiter Ausgang fig. 4) an ά®π Kompleaenteingang ier Ausgangsstufe'

fS@ öle " 0Q9837/1868

eines 23-stufigen Speicherschieberegisters (23j Fig_e 1) angeschlossen ist, weiter dadurch gekennzeichnet, daß die Ausgänge der elf Stufen des Schieberegister-Prüfwortgenera« tors (11) mit einem Entschlüsseier (3, Fig. 1; Figo 3) verbunden sind, dessen Ausgänge an eine Fehleranzeige-Sperrschaltung (4; Fig. 1) angeschlossen sind, mit der auch die Ausgänge der Stufen 2 bis 11 des Prüfwortgenerators verbunden sind und deren Ausgang an die Fehlereinwirkungsschaltung angeschlossen ist.

Docket WA 968 010 009837/186 8