DE2047868A1 - Schaltung zur Korrektur von Einzel fehlern in den Wortern eines zyklischen (n, k) Codes - Google Patents

Description

Böblingen, den 29. September 1970 neu-rz

Anmelderin: Internationa Business Machines

Corporation, Armonk, N.Y. 10504

Amtliches Aktenzeichen: Neuanmeldung Aktenzeichen der Anmelderin: Docket PO 969 018

Schaltung zur Korrektur von Einzelfehlern in den Wörtern eines zyklischen (n, k) Codes

Die Erfindung bezieht sich auf eine Schaltung zur Korrektur von Einzelfehlern in den Wörtern eines zyklischen (n, k) Codes (n=Gesamtzahl der Bits eines Wortes, k«Anzahl der Datenbits) unter Verwendung rückgekoppelter Schieberegister.

Derartige Schaltungen sind bekannt. So sind in der USA-Patentschrift 3 162 837 Schaltungen beschrieben, die die Fehlerkorrektur in seriell übertragenen Wörtern eines zyklischen Codes unter Verwendung rückgekoppelter Schieberegister gestatten.

103015/1783

Im USA-Patent 3 452 328 sind Schaltungen zur Korrektur von Fehlern in Informationswörtern angegeben, die in einem (n, k) zyklischen Code (n=Gesamtzahl der Bits eines Wortes, k=Anzahl der Datenbits) verschlüsselt sind und parallel übertragen werden. Zur Fehlererkennung und -korrektur finden n-k-stufige rückgekoppelte Schieberegister Verwendung, denen die Datenbits parallel zugeführt werden. Diese Schaltungen erfordern für die Fehlererkennung n-k Verschiebevorgän*
Schiebevorgänge zur Fehlerkorrektur.

Fehlererkennung n-k Verschiebevorgänge und --*- weitere Ver-

Der Erfindung liegt die Aufgabe zugrunde, eine Schaltung zur Korrektur von Einzelfehlern in den Wörtern eines zyklischen (n, k)Codes (n=Gesamtzahl der Bits eines Wortes, k=Anzahl der Datenbits) anzugeben, die unter Verwendung eines n-k-stufigen rückgekoppelten Schieberegisters für parallele Dateneingabe eine Beschleunigung der Fehlerkorrektur ermöglicht.

Die genannte Aufgabe wird gemäß der Erfindung dadurch gelöst, daß die Einstell-Eingänge der n-k Schieberegisterstufen über n-k Modulo-2-Addierer mit ausgewählten Ausgängen für die regulären

1 0 9 i 7 5/1783

¹I ■:"''! IB ■■: ' ι ■ ■

Ausgangssignale der Schieberegisterstufen und mit ausgewählten der c Leitungen verbunden sind, die die c Bits eines Teilwortes des η Bits umfassenden Codewortes parallel anliefern, und daß ausgewählte der Ausgänge für die regulären und komplementären Ausgangssignale der n-k Schieberegisterstufen an c UND-Glieder führen, deren Ausgänge jeweils mit einer zugeordneten Antivalenzschaltung verbunden sind, deren zweitem Eingang jeweils eines der c Bits eines zu übertragenden Teilwortes zugeleitet werden.

Ein AusfUhrungsbeispiel der Erfindung ist in den Zeichnungen dargestellt und wird im folgenden näher beschrieben. Es zeigen:

Fig. 1 ein Blockschaltbild der Anordnung gemäß der Erfindung für parallele Eingabe und mit paralleler Rückkopplung zur Verschlüsselung, Fehlerprüfung und Fehlerkorrektur ;

Fig. 2 ein Blockschaltbild für die Anwendung der Schaltung gemäß der Erfindung in einem System für Realzeitbetrieb;

Fig. 3 ein allgemeiner Datenflußplan zur Beschreibung der Prüf- und Fehlerkorrekturoperationen des in Fig. 1 gezeigten Gerätes in dem System nach Fig. 2;

Fign. 44-5 zusammen eine Blockdarstellung des erfindungsgemäßen

/17 8

20A7868

parallel rückgekoppelten Schieberegisters für parallele Eingabe mit Einzelheiten der zugehörigen Eingangs-Trans formationsschaltungen und der Ausgangs-Decodierschaltungen für den Sonderfall c=18 und einen verkürzten zyklischen Code mit n=72, k=64; (n=Gesamtzahl der Bits eines Wortes, k=Anzahl der Informationsbits).

Fig. 6 ein Zeitschema für die Codier- und Decodierfunktionen in dem in den Fign. 4 und 5 dargestellten Schieberegister;

Fig. 7 das serielle Äquivalent des in Fig. 4 gezeigten parallel rückgekoppelten Schieberegisters für parallele Eingabe und

Fig. 8 ein genaueres Blockschaltbild eines der Modulo-2-Addierer (Sl) der Fig. 4.

Fig. 1 zeigt die Anordnung gemäß der Erfindung und Fig. 2 ihre besonders wirkungsvolle Anwendung beim Codieren und Decodieren

10' -/1783

von Datensignalen, die durch die E/A-Kanäle eines Datenverarbeitungssystems laufen. Andere Formen der erfindungsgemäßen Schaltung und andere Anwendungen gehen aus der Beschreibung hervor.

In Fig. 2 umfaßt der zentrale Prozessor 1 den Hauptspeicher 2, die Zentraleinheit 3 und eine Anzahl von Kanaleinheiten 4. Jede Kanaleinheit steht mit mehreren peripheren Einheiten 5 über eine Steuereinheit 6 in Verbindung. Die Steuereinheit 6 verfügt über einen Pufferspeicher 6A, um die Daten sowie Paritätsprüfsignale an der Trennstelle zwischen Steuereinheit und Kanaleinheiten zwi- f Seitenspeichern zu können. Ein Schnittstellenkabel 7 führt c^f Signale über die Schnittstelle zwischen Kanal und Steuereinheit. Die mit der Bezugsziffer 8 bezeichnete Anordnung verfügt über parallele Leitungen 7A und 7B zum Pufferspeicher 6A, wodurch Signalgruppen aus c Elementen zwischem dem Gerät und dem Pufferspeicher in den durch die Pfeile angezeigten Richtungen verarbeitet werden können. Die numerische Bedeutung von c¹ und c wird später in der Beschreibung angegeben. Die Anzahl der Verbindungsleitungen im Kabel 8A zwischen der Anordnung und der peripheren Einheit 5 spielt keine Rolle für die Anwendung der in Fig. 2 gezeigten erfindungsgemäßen Anordnung, da angenommen wird, daß die der Anordnung auferlegten Beschränkungen der Ar- λ beitegeschwindigkeit nur auf die Organisation der Schnittstelle zwischen Kanal und Steuereinheit bezogen ist. Sie wird für die Beschreibung mit η angenommen.

Für die in Fig. 2 gezeigte Anwendung wird weiterhin angenommen, daß die über die Schnittstelle 7 kommenden Signale die Form einer Kombination von Rohdaten mit einfachen Paritätsprüfsig-'nalen haben, wogegen die über die Schnittstelle 8a kommenden Signale die Form einer Kombination von unkorrigierten Daten mit zusätzlichen Signalen haben und zyklische Codewörter bilden, (n«Gesaatzahl der Bits eines Wortes, k«Anzahl der Informationsbit·) .

1 0 ^f -»/1783 Hie aus der genaueren Blockdarstellung in Flg. 1 zu ersehen 1st,

enthält die Anordnung 8 der Erfindung ein lineares parallel rückgekoppeltes Schieberegister 12. Die r(=n-k) getakteten Speieherstufen des kurz mit RSR bezeichneten Rückkopplungs-Schieberegisters liefern die Ausgangssignale F -F . Eingangssignale werden parallel den Stufen des RSR von r Modulo-2-Addierern zugeführt, die allgemein mit 15 bezeichnet sind. Die Modulo-2-Addierer 15 empfangen Eingangssignale von den Schaltungen

20 und 21. Die Schaltungen 20 bilden Modulo-2-Summen von verschiedenen Kombinationen der über die Leitungen 7A oder 22 empfangenen Eingangssignale. Die Schaltungen 21 bilden Modulo-2-Summen von verschiedenen Kombinationen der Rückkopplungssignale des Registers RSR. Die Schalter 25 sind vorgesehen, um Eingangssignale wahlweise von den Leitungen 7A und 22 zu noch zu erklärenden Zwecken der Schaltung 20 zuleiten zu können.

Bei der Codieroperation werden die vom Kanal gelieferten Daten in Signalgruppen von k Elementen geliefert und durch n-k Prüfziffern ergänzt und bilden (n, k) zyklische Codewörter. Diese Wörter werden gegebenenfalls den peripheren Einheiten über den Wortpufferspeicher 26 zugeführt. Die Leitungen 7A und die Schalter 25 führen vom Kanal dem Pufferspeicher 6A zugeführte Rohdaten den Modulo-2-Addierern 20 und dem Wortpufferspeicher 26 sowie der Verbindungsschaltung 27 in Gruppen von c Elenenten zu. Jede Gruppe von k Datensignale lementen (k>c>n-k) wird durch n-k Null-Signale ergänzt. Durch die Schaltungen 2O und 15 werden zusammen mit dem Betrieb des RSR und den Rückkopplungsschaltungen

21 die Prüfbits des (n, k) zyklischen Codes erzeugt. Diese Prüfbits werden dann über die Torschaltungen 28 in den Wortpufferspeicher 26 übertragen und als Endziffern an die Rohdatengruppe aus k Elementen anstelle der n-k Nullsignale angefügt» um durch eine periphere Einheit als ein (n, k) zyklisches Codewort weiterverarbeitet zu werden.

Bei der Decodierung wird ein von einer peripheren Einheit empfangenes codiertes Signal zuerst im Wortpufferspeicher 26 gespeichert, dann geprüft und bei Bedarf korrigiert. Anschließend

10;· './1783

werden die Redundanzbits entfernt und das verbleibende Signal wird über den Pufferspeicher 6A dem Kanal zugeleitet. Die Leitungen 22 führen (n, k) codierte Signale vom Wortpufferspeicher 26 über die Verbindungsschaltung 27A und die Torschaltungen 22A zum Addierer 20, und zwar wieder in Gruppen von c Signalelementen. Die Schaltungen 20, 15 und 21 arbeiten dann ähnlich zusammen wie beim Verschieben für das Codieren und erzeugen eine Anzeige des Prüfergebnisses im RSR. Dieses Prüfergebnis sollte beim Empfang eines fehlerfreien Wortes aus lauter Nullen bestehen. Die Schaltungen 29 sind zur Erkennung dieser Bedingung vorgesehen.

Wenn durch die Schaltungen 29 der Empfang eines fehlerfreien Wortes festgestellt wird, wird das Gerät so gesteuert, daß es die Verarbeitung des Rohdatenteiles des Codewortes über den Pufferspeicher 6A zum Kanal in Gruppen aus c' Elementen einleitet. Bei dieser Verarbeitung können einfache Paritätsprüfziffer η an die Rohdaten auf bekannte Weise angehängt werden und c¹ kann mit c identisch sein oder nicht.

Wenn eine andere als die oben erwähnte, aus lauter Nullen bestehende Anzeige des Prüfergebnisses erfolgt und damit ein Fehler im empfangenen Codewort angezeigt wird, wird das Gerät wieder so gesteuert, das es die Verarbeitung der Rohdaten über den Kanal einleitet, dabei jedoch einer möglichen Ausnahme für ™ die Parität des Restwertes, die später beschrieben wird, unterliegt, und zwar in Koordinaten mit einem Vorgang, durch den der Fehler nach Möglichkeit korrigiert werden soll. Dabei werden zur Korrektur die Schalter 25 geöffnet und die Schaltungen 30 so gespeist, daß sie das Auftreten irgendeines von c bestimmten Hustern von Restprüfziffern im RSR erkennen. Wenn die Schaltungen 30 kein entsprechendes Signal der Erkennung eines solchen Musters liefern, wird ein unveränderter Rohdatenanteil einer ersten c-stelligen Silbe des geprüften Codewortes im Wortpufferspeicher 26 dem Pufferspeicher 6A und von dort dem Kanal als c¹-stellige Signalgruppe zugeführt. RSR und Schaltung 21 führen dann einen Verschiebezyklus aus, in welchem der dann im RSR

10 /17 8 3

— Λ _

stehende Prüfrest durch eine Modulo-2-Addition in den Schaltungen 15 und 21 verändert wird.

Die aufeinanderfolgende Erkennungsoperation der Schaltungen 30 und die Verschiebeoperation des RSR werden wiederholt, bis entweder die Schaltungen 30 ein bestimmtes Muster erkennen oder der gesamte Rohdatenteil des geprüften Codewortes dem Kanal zugeführt worden ist. Die Verschiebephase zum Zeitpunkt der Erkennung eines Musters gibt an, daß die Fehlerstelle in der entsprechenden c-stelligen Silbe des geprüften Codewortes vorliegt und das spezielle erkannte Muster bezeichnet die Lage des Fehlers innerhalb dieser Silbe. Somit kann die den Fehler enthaltende Silbe beim Obertragen zum Pufferspeicher 6A korrigiert werden. Wenn der ganze Rohdatenteil eines geprüften Hortes mit einer Fehleranzeige, aber ohne Fehlererkennung und Korrektur dem Kanal zugeleitet worden ist, wird die Anzeige (NKF) dafür, daß die Daten einen nicht korrigierbaren Fehler enthalten, vom Gerät dem Kanal zugeführt, so daß die Daten nicht fälschlicherweise benutzt werden.

Bei den oben beschriebenen Operationen liefern die Verschiebesteuerschaltungen 35 die folgenden Signale

a) zum Steuern der Operationsfolge der Schalter 25 und der Schaltungen 20, 21, 29 und 30 sowie zum Zuführen der Eingangssignale zum RSR,

b) zum Steuern der Operation der Torschaltungen 28, um die Prüfziffern dem Wortpufferspeicher 26 zuzuführen und die Torschaltungen 22A zur Lieferung von Silben vom Wortpufferspeicher 26 an die Schaltungen 20 zu veranlassen,

c) zum Steuern der Wortübertragung in beiden Richtungen zwi schen dem Wortpufferspeicher 26 und den peripheren Einheiten über die E/A-Steuereinheit 8B und das Kabel 8A und

d) um die Verbindungsechaltungen 27 und 27A dazu xu veranlas sen. Silben dem Wortpufferspeicher 26 zuzuleiten bzw. sie aus ihm zu entnehmen.

Die spezifischen Koafcinationsgrupplerungen der Rückkopplungs-

tCH ^F /1783

elngänge für die Rückkopplungs-Summierschaltung 21 und der genaue Aufbau der Eingangs-Summlerschaltung 20 werden später genauer erklärt.

Die Folge der Decodieroperatlonen der in Fig. 1 gezeigten Anordnung in dem in Fig. 2 gezeigten System wird im Zusammenhang mit Fig. 3 beschrieben. Die Codierfolge wird später genauer beschrieben. In der Prüfphase der Decodierung wird der Inhalt des RSR, der ursprünglich aus lauter Nullen besteht, in nicht dargestellten Rückgriff-Selbsthalteschaltungen vor jeder Parallelverschiebung festgehalten. Die den Leitungen 22 vom | Wortpufferspeicher 26 zugeführten c-stelligen Eingangssilben werden durch Modulo-2-Addition mit den gespeicherten Zuständen des RSR (Schritt 54 in Flg. 3) mit Hilfe der Schaltungen 20, 21 und 15 kombiniert und als neue Teilreste im RSR gespeichert.

Diese Bildung neuer Teilreste im RSR wird für jede der n/c Silben im Wortpufferspeicher 26 wiederholt (Schritt 55 in Fig. 3) und so der End-Prüfrest für das ganze Wort gebildet. Dann werden die Erkennungsschaltungen 29 (Fig. 1) betätigt und prüfen das Vorhandensein von lauter Nullen im RSR (Schritt 55 in Fig. 3). Aufgrund der Eingangscodierung stellen lauter Nullen im RSR zu diesem Zeitpunkt der Verschiebung die End- oder Prüfrestbe- M dingung für ein von den peripheren Einheiten fehlerfrei übertragenes Wort dar. Daher steuert die Anwort "ja" bei der Prüfung auf lauter Nullen die Beendigung der Operation des Gerätes (Schritt 58 in Fig. 3). Die im Wortpufferspeicher 26 zu diesem Zeitpunkt gespeicherten Rohdatenteile von Wörtern werden als richtig betrachtet und ohne Veränderung vom Wortpufferspeicher 26 über die Torschaltungen 59A zur unmittelbaren Verarbeitung den Ausgangeleitungen 59, 7B zugeführt.

Die Antivalenzschaltungen 59* zwischen den Leitungen 59 und 7B beeinflussen das Ausgangssignal nicht, da die Decodierschaltungen 30 abgeschaltet sind, wenn kein Fehler vorliegt. Wird die Prüfung auf lauter Nullen mit "nein" beantwortet, läuft das parallele Verschieben in noch zu beschreibender Art

10' './1783

- IO -

welter, wenn die Eingangsschalter 25 geöffnet sind. Zu diesem Zeitpunkt kann es zweckmäßig sein, den nicht aus lauter Nullen bestehenden Prüfrest im RSR in einen nicht dargestellten Rückgriff-Pufferspeicher zu speichern (Schritt 60 in Fig. 3), um dadurch eine Anzahl später evtl. gewünschter Benützungen zu ermöglichen. Unter diesen befindet sich evtl. die Korrektur von Fehlerbündeln durch eine Tabellensuchoperation, die Einleitung von programmierten System-Fehlersuchen und/oder der erneute Versuch zur Korrektur, um das einwandfreie Arbeiten der Verschiebeeinrichtung sicherzustellen (z.B. durch erneute Eingabe der gespeicherten Prüfrest-Signale in das RSR über einen nicht dargestellten Eingabeweg von dem nicht dargestellten Rückgriff-Pufferspeicher zum RSR).

Wenn der verwendete zyklische Code es gestattet, Doppelfehler festzustellen und Einzelfehler zu korrigieren, würden gleichzeitig die Schaltungen 29 betätigt, um den Inhalt des RSR auf gerade Parität zu prüfen (Schritt 62 in Fig. 3). Es wurde beobachtet, daß bei einem derartigen Code die gerade bzw. ungerade Parität des ganzen oder endgültigen von Null verschiedenen Prüfrestes, der im RSR am Ende der Prüf phase des Schiebezyklus (ScLrItt 56 in Flg. 3) steht, im Verhältnis 1:1 zum Vorhandensein einer geraden/ungeraden Anzahl von Fehlern im gespeicherten Codewort steht. Bei Verwendung eines solchen Codes würde also eine positive Antwort auf die Paritätsprüfung 62 direkt anzeigen, daß das Hort eine gerade Anzahl von 2 oder mehr Fehlern enthält und die positive Antwort würde eine nicht korrigierbare Bedingung anzeigen, wenn das Gerät nur für die Korrektur eines Fehlers ausgelegt ist. Diese Anzeige eines nicht korrigierbaren Fehlers würde natürlich dazu benutzt, um die Korrekturfolge zu beenden (Schritt 63 in Flg. 3) und anschließend ein Fehlersuchverfahren oder andere Korrekturmaßnahmen je nach Bedarf und Möglichkeiten einzuleiten.

Eine negative Antwort auf die Paritätsprüfung 62 zeigt die Existenz einer ungeraden Anzahl von Fehlerstellen in dem im

10 . / 1783

- ii -

Wortpufferspeicher 26 befindlichen Hort an und dieser Antwort folgt eine Reihe von aufeinanderfolgenden Prüfungen der Zustände der einzelnen Bitstufen des BSR, die die Lage der Fehler bestimmen sollen (66, 68 ... 70 in Flg. 3) und bedingte Verschiebungen des Inhaltes des BSR, bei denen die Rückkopplungseingänge nur eingeschaltet werden (72 ... 76 in Flg. 3), wenn eine Lage nicht erkannt wird. Die in den Schaltungen 3O (Fig. 1) durchgeführten Syndronprüfungen.sollen die Lagen der Fehler in dem im Wortpufferspeicher 26 befindlichen Hort feststellen. Diese Folge aus Prüfungen und Verschiebungen wird beendet entweder, wenn ein Syndrom (ein einen Fehler lokalisierendes Restmuster { im RSR) durch die Decodiereinrichtung 3O erkannt wird, oder wenn der Inhalt des RSR parallel um Insgesamt — -lmal verscho-

n-k ben wurde. Bei den 2 -1 möglichen Bestwerten des RSR, die bei dieser Operations folge auftreten können, kann stan beobachten, daß c bestimmte Werte auftreten, die das Vorliegen eines Fehlers in bestimmten Bitstellen einer Silbe, die eine aus c Bits bestehende Untergruppe des geprüften Wortes bildet, eindeutig angeben. Hit diesen Restwerten kann daher die Lage eines Fehlers in einem Silbenteil eines Wortes ±m Wortpufferspeicher 26 genau bezeichnet werden. Außerdem wird später gezeigt, daß die jeweilige einen Fehler enthaltende Silbe der parallelen Verschiebephase des RSR entspricht, wenn die Bildprüfung ge- m macht wird.

Demzufolge würde die Antwort "ja" auf die erste Syndromprüfung (Bildcodeprüfung in Schritt 66 der Flg. 3) vom Decodierer 30 dazu benutzt, die Lage des Fehlers in der ersten Silbe des im Wortpufferspeicher 26 befindlichen Wortes anzugeben (d.h. Wortbits 1, 2 ... c). Die Bits in den so angegebenen Stellen können durch Invertieren korrigiert werden, wahrend sie über die entsprechenden Anitvalenzschaltungen 59* der Fig. 1 zum Pufferspeicher 6A (Schritt 68 in Fig. 3) übertragen werden und die Korrekturoperation des Geräte« kann beendet werden (Schritt 58 in Fig. 3), als ob ein fehlerfreies Hort empfangen worden wäre. Die anderen Silben des Wortes können dann dem Kanalpufferspei-

1 0 ^ /1783

2Q47868

eher 6A ohne weitere korrigierende Änderungen zugeführt werden.

Nach einer negativen Antwort auf die erste Bildprüfung wird der Inhalt des RSR ohne Dateneingabe verschoben (Schalter 25 in Fig. 1 ist geöffnet, Schritt 72 in Fig. 3) und die Bildprüfung wird wiederholt (Schritt 68 in Fig. 3). Eine positive Antwort auf diese zweite Bildprüfung lokalisiert den Fehler in der zweiten Silben des im Wortpufferspeicher 26 befindlichen Wortes (Bits c+1, c+2 ... 2c) und das Ausgangssignal des Decodierers 30 bezeichnet die genaue Lage des Fehlers innerhalb dieser Silbe. Somit kann die zweite Silbe bei der übertragung in den Pufferspeicher 6A korrigiert werden (Schritt 80 in Fig. 3).

Diese Folge der Bildcodeprüfungen mit eventuell anschließenden, fortgesetzt wiederholten Verschiebungen des Prüfrestes wird wiederholt, wobei jede Wiederholung durch eine negative Antwort auf die vorhergehende Bildprüfung bedingt ist, bis schließlich entweder der Fehler im Wortpufferspeicher 26 lokalisiert und korrigiert wird oder der Inhalt des RSR insgesamt — -lmal einschließlich der ersten Silbenverschiebung in der Fehlerentdeckungsphase (Schritt 54 in Fig. 3) durch die Steuereinrichtung 35 in Fig. 1 verschoben wurde. Nach der letzten Bildprüfung (Schritt 7O in Fig. 3) wird entweder ein Einzelfehler in der letzten, der - ten Silbe des Wortes erkannt, der genauso wie die erste Silbe korrigiert werden kann (Schritt 82 in Fig. 3) oder es wird ein unkorrigierbarer Fehler angenommen (Schritt 84 in Fig. 3).

Die Reihenfolge der Verschiebungen kann eingeleitet werden, sobald codierte Daten von den peripheren Einheiten zur Verfügung gestellt wurden und ist daher nicht an die Zeitpunkte für Kanalanforderungen gebunden. Die kontinuierlichen Verschiebungen zur Suche der Fehlerkorrektursyndrome während der übertragung der Rohdaten zum Kanal hängen jedoch zeitlich von der Kanal-Anforderungsgeschwindigkeit ab. Somit können Prüfverschiebungen so schnell durchgeführt werden, wie die Schaltungen des erfundenen

10! /1783

Gerätes betätigt werden können (siehe Flg. 6), wodurch die für die Fehlererkennung benötigte Zelt beträchtlich reduziert wird, während die kontinuierlichen Verschiebungen für die Fehlerkorrektur zeitlich optimal mit der Kanal-Übertragungsfunktion abgestimmt werden.

Die obigen Ausführungen lassen sich leichter an einem bestimmten AusfUhrungsbeispiel erklären, das in den Fign. 4 und 5 gezeigt ist und auf dem folgenden Sonderfall beruht: n=72, k=64, c=18. Bei dem Code (72, 64) handelt es sich um einen verkürzten zyklischen Code zur Feststellung von Doppelfehlern und Korrektur von Einzelfehlern.

Aus Fig. 4 ist zu ersehen, daß verschiedene Vielfache der 18 (=c) Silbeneingangsleitungen II, 12 ... 118 mit den 8 (=n-k) Modulo-2-Addiererschaltungen Sl, S2 ... S8 verbunden sind. Die Ausgänge der Addierer sind mit den Einstell-Eingängen entsprechender Registerstufen Fl, F2 ... F8 des RSR verbunden. Mehrere Vielfache der Registerausgangsleitungen, die mit fl, f2 ... f8 bezeichnet sind, stehen ebenfalls als Rückkopplungseingangsleitungen mit den Summierschaltungen Sl - S8 in Verbindung.

Die verschiedenen Kombinationen von Eingangsleitungen, die über die Schalter 25 an die Summlerschaltungen führen, sind schematisch in der Zeichnung durch gestrichelte Linien 90, die Buchstaben I und bestimmte Indexzahlen, (z.B. 1, 9, 15, 16, 17 am Eingang Sl) dargestellt. Kombinationen von Rückkopplungsleitungen sind in ähnlicher Weise schematisch in dieser Zeichnung durch gestrichelte Linien 91, die Buchstabenbezeichnung r und bestimmte Indexzahlen gekennzeichnet.

In den durch die Addierer und das Register gebildeten Rückkopplungsschleifen sind allgemein bekannte, jedoch nicht bezeichnete Selbethaiteechaltungen vorgesehen, durch welche, wie bereits gesagt, daa Einstellen der Registerstufen F₁ - F_Q verzögert wird, wodurch eine echte Signalverzögerung in dem Rückkopplungspfad 91 erreicht wird. Ferner werden den nicht darge-

10' ·,/ 1783

stellten Rückstelleingängen für F, - F_Q und den Selbsthalte-

1 ο

schaltungen verzögerte Signale zugeführt.

Die Abzweigung 92 der Leitung 91 führt zur Fehlererkennungs- und Korrekturschaltung der Fig. 5. Die Summierschaltungen S - S_ß stellen für einen speziellen Fall die Implementierung der Schaltungen 15, 20 und 21 dar (Fig. 1).

Setzt man nun in Fig. 3 für c die Zahl 18 bzw. für ~ die Zahl 4 ein, dann geht aus der Betrachtung der Fign. 3-6 die Decodieroperation des erfindungsgemäßen Gerätes in Einzelheiten hervor. In der aus vier Schritten bestehenden Fehlerprüfoperation werden die ein aus 72 Bits (64 Rohdatenblts und 8 ergänzende Prüfbits) bestehendes Codewort bildenden vier Silbensignalgruppen nacheinander parallel zu den 18 Eingangsleitungen I₁, I₀, I. ... I₀ von entsprechenden Stufen des Wortpufferspeichers 26 in

Fig. 1 übertragen. Es sind insgesamt nur vier Verschiebungen des Inhaltes des RSR anstelle der 9 oder mehr Verschiebungen erforderlich, die bei Verwendung von kleineren Eingangssilben aus 8 oder weniger Bits zur Bildung der RSR-Rest benötigt werden.

Die in Fig. 5 gezeigte Prüfschaltung überprüft jedes Wort auf Richtigkeit dadurch, daß sie nach der vierten Verschiebung, die als Schritt 4 bezeichnet und durch Markierungsbedingungen auf den Leitungen 108 und 109 dargestellt ist, feststellt, ob alle 8 Restbits im RSR Null sind. Ist das der Fall, wird das Ausgangrsignal des ODER-Gliedes 110 in Fig. 5 durch den Inverter 111 Invertiert und dem vorbereiteten UND-Glied 112 zugeführt, um das WA-Ausgangssignal zu erzeugen, welches die fehlerfreie Verarbeitung des im Wortpufferspeicher 26 in Fig. 1 enthaltenen Wortes anzeigt.

Wenn der Prüfrest des vierten Schrittes nicht aus lauter Nullen besteht, sondern eine gerade Parität aufweist, wird das UND-Glied 115 in flg. 5 vorbereitet durch die Kombination der durch daa nicht invertierte Ausgangssignal des ODER-Gliedes 110 dar-

gestellten Fehlerbedingung und einer geraden Paritätsanzeige, die man über die Leitung 116 von der Schaltung 117 erhält, welche die Modulo-2-Summe der Bits des SSR bildet. Somit zeigt das Ausgangssignal des UND-Gliedes 115 das Erkennen eines Doppelfehlers an, da in diesem speziellen Fall die Anzahl der Fehler im empfangenen Wort und die Parität des Restes im RSR nach dem vierten Schritt eine vorbestimmte Beziehung zueinander haben, die später bei der Beschreibung- des erzeugenden Polynoms erklärt wird, auf welchem der spezielle Divisionsprozeß der Restbildung basiert.

Eine ungerade Paritätsanzeige der Suanierschaltung 117 auf der Leitung 119 im vierten Verschiebeschritt bezeichnet das Auftreten einer ungeraden Zahl von Bitfehlern im geprüften Wort und wird durch das teilweise vorbereitete UND-Glied 120 festgestellt. Ein Ausgangssignal des UND-Gliedes 12O auf der Leitung 121 bereitet die Steuerschaltungen für die Einzelfehler-Korrekturfolge (EFK) vor. In dieser Folge wird das Ausgangssignal des RSR durch die 18 UND-Glieder 130-1, 130-2 ... 130-18 während eines Zeitraumes geprüft, der durch den Einsteilzustand des Flipflops 135 bestimmt ist. Das Flipflop 135 wird über die Ausgangsleitung 121 des UND-Gliedes 120 eingestellt und durch später beschriebene Einrichtungen rückgestellt.

Die UND-Glieder 130-1 bis 130-18 sprechen auf 18 eindeutige Folgezustände des RSR an, die als Fehler-Lokalisierungssyndrome bekannt sind. Diese Zustände haben bei den Verschiebeschritten 4 bis 7 eindeutige Entsprechungen xu den Fehlerstellen von Einzelfehlern in dem geprüften Wort. Die im Schritt 4 festgestellten Syndrome weisen auf Fehler in der ersten empfangenen Silbe des geprüften Wortes (d.h. Bispositionen 1, 2, 3 ... 18J. Somit bezeichnet ein Ausgangssignal des UND-Gliedes 13O-1 in Verschiebungeschritt 4 einen Fehler Jjt Wortbit 1, ein Ausgangssignal des UND-Gliedes 130-2 einen Fehler ie Wortbit 2 usw.

Wenn eine Fehlerstelle im Verschiebeschritt 4 nicht festgestellt

10' /1783

wird, kann die erste Silbe des geprüften Wortes vom Wortpufferspeicher 26 des Kanal-Schnittstellen-Pufferspeicher 6A zugeführt werden, während der Inhalt des RSR im Verschiebeschritt 5 verschoben wird, wobei die Eingänge I_i - I₁₈ gesperrt sind (Schalter 25 geöffnet). Die Leitung 140 wird markiert und die Ermittlung des Fehlerortes mittels der UND-Glieder 130 wird wiederholt, um festzustellen, ob und wo ein Fehler innerhalb der zweiten Silbe des geprüften, aus den Bitstellen 19 , 20 ... 36 bestehenden Wortes aufgetreten ist.

Wenn kein Fehler festgestellt wird, kann im Schritt 5 die zweite Silbe vom Wortpufferspeicher 26 auf den Kanal-Pufferspeicher 6A übertragen und der Inhalt des RSR parallel im Verschiebeschritt 6 verschoben werden, wobei die Eingänge I wieder gesperrt sind. Die Leitung 145 wird markiert (Schritt 6) und die Ermittlung des Fehlerortes in den UND-Gliedern 130 wiederholt. Ein Ausgangssignal in diesem Verschiebeschritt bezeichnet die Lage eines Fehlers in der dritten Silbe des geprüften Wortes (Bits 37, 38 ... 54).

Wenn kein Fehlerort festgestellt wird, wird im Verschiebeschritt 6 die nächste Gruppe von 18 Bits dem Kanal-Pufferspeicher 6A zugeführt und der Inhalt des RSR wird wieder im Verschiebeschritt 7 bei gesperrten Eingängen I verschoben. Die Leitung 150 wird Markiert (Schritt 7) und mit dem Rest des RSR werden Snydrouprufungen durch die Schaltungen 130 vorgenommen, die in dieser Verschiebephase die Fehlerorte in der vierten Silbe des geprüften Wortes (Bit 55, 56 ... 72) feststellen.

Wenn in einer der vorhergehenden Syndromprüfungen ein Fehlerort festgestellt wurde durch das ODER-Glied 151 und eines der UND-Glieder 152-1 bis 152-4, wird das durch das Ausgangsslgnal eines der UND-Glieder 130 bezeichnete Bit durch nicht dargestellte Einrichtungen entsprechend den Antivalenzschaltungen 59* invertiert, wahrend die entsprechende Silbe des Wortes

10 ./1783

dem Kanal-Pufferspeicher 6A zugeführt wird. Die Verschiebefolge würde dann durch Rückstellen des Flipflops 135 über das ODER-Glied 153 beendet, während die übrigen Silben des Wortes fehlerfrei zu dem Pufferspeicher 6A übertragen werden. Wenn ein Fehlerort durch den Verschiebeschritt 7 nicht festgestellt wurde, wird die Leitung 155 (Schritt 8) markiert und liefert ein Signal "Ende der Steuerung", welches dem Kanal anzeigt, daß das gerade übertragene Wort einen nicht korrigierbaren Fehler (NKF) enthält.

Die früher erwähnte Beziehung zwischen bestimmten Restwerten des RSR während der Verschiebeschritte 4 bis 7 und bestimmten Stellen von Einzelfehlern in den 72 Bits des geprüften Wortes werden genau in der folgenden Tabelle I gezeigt. Diese Tabelle setzt auch Codewort-Datenbitsteilen eines Codewortes zu bestimmten Eingangsleitungen I₄ - I₁₀ in Beziehung.

(Siehe Tabelle auf nächster Seite).

Nach einer Anzahl von Verschiebungen des Inhaltes des RSR während der Schritte 4 bis 7 sind die gleichzeitig mit der Verarbeitung des Codewortes ausgeführten Decodierfunktionen der Fehlerprüfung und -korrektur abgeschlossen (Siehe Fig. 6). Es sind nur die mit der Übertragung der Informationssignale auf den Kanal und die gleichzeitige Korrektur von Fehlern verbundenen Verschiebungen zeitabhängig von der Signalbehandlungsfunktion und der zeitliche Ablauf der Fehlerprüfung wird nur durch die Möglichkeiten der parallel rückgekoppelten Verschiebeschaltungen und die Verfügbarkeit der zu prüfenden Signale begrenzt.

Der zeitliche Ablauf der Codierung, die gleichzeitig mit der übertragung der Rohdaten vom Kanal-Pufferspeicher 6A zu dem Wortpufferepeicher 26 und der Parallel-Verschiebeschaltung der Fign. 4 und 5 erfolgt, ist vergleichbar mit der übertragung der decodierten Signale vom Wortpufferspeicher 26 zu dem Kanal-Puf-

10' './1783

Tabelle I

Fehler auf Fehlersyndrommuster Leitung

^f3 ^f4 ^f5 ^f6 ^£7 ^f8 Matrix Vektor Identl- Bit, für welches FK bei Erkennung tat in der Liste der eines bestimmten Bildmusters vor-Auton. Zustände genommen wird in

Verschiebeschritt 4 5 6

118 17 16

^ 15

co 13

12 11 10

9 8

6 5 4

3 2 1

11111101 00111011 01110110

1110 1100 00011001 00110010

01 100100 11001000 0 10 1000 1

10100010 10000 10 1 110 0 1011

01010111 10101110 10011101 72nd Vektor 71st Vektor 70th Vektor

1111 0011 0110

1011 0111 1110

Vektor Vektor Vektor

Vektor Vektor Vektor

Vektor Vektor Vektor

Vektor Vektor Vektor

Vektor Vektor Vektor

1	2	3	4	5	6	7	8	9	10	13	16	19	22	25	28	49	52	37	40	43	46	67	70	55	58	61	64
11	14	17	20	23	26	29	32	35	38	41	44	47	50	53	56	59	62	65
12	15	18	21	24	27	30	33	36	39	42	45	48	51	54	57	60	63	66
68
69
71
72

ferspeicher 6A. Hierzu gehört eine Operationsfolge aus 4 Schritten an 64 Rohdatenbits.

In jedem der ersten drei Schritte werden 18 Rohdatenbits durch die Verschiebeeinheit verarbeitet und im vierten Schritt werden die Eingangssignale der Verschiebeschaltung gebildet durch 10 Rohdatenbits und 8 Nullbits, die durch die Steuerschaltungen eingefügt werden. Am Ende der yierten Verschiebung wird der den Prüfrestwert des Codewortes darstellende Inhalt des RSR an die 64 Rohdatenbits im Wortpufferspeicher 26A angehängt und bildet ein Codewort für die Übertragung an die entsprechende periphere Einheit. Torschaltungen 28 (Fig. 1) sind zu diesem Zweck vorgesehen.

Die Codeform der vom Kanal empfangenen und an ihn abgegebenen Daten spielt natürlich für die vorliegende Erfindung keine Rolle. Somit braucht c^f nicht gleich c in Fig. 2 zu sein. Der Einfachheit halber werden Datensignale jedoch zwischen den Kanälen 4 und dem Pufferspeicher 6A in Gruppen zu 16 Bits (2 Bytes) übertragen, zusammen mit zwei einfachen Paritätsprüfbits.

Diese Paritätsprüfbits werden nur für die Prüfung der Übertragung von Rohdatensignalen über die Kanal-Schnittstellenleitungen 7 benutzt und entfallen nach der Prüfung. In ungekehrter Richtung

werden die Paritätsprüfbits erzeugt und an die ausgehenden Λ

Datensignale angehängt, wenn diese vom Pufferspeicher 6A auf den Kanal gegeben werden.

Unter diesen Bedingungen wird also die Codierung der vom Kanal gesendeten Rohdatensignale relativ zu deren Ankunft im Pufferspeicher 6A verzögert, bis eine volle Gruppe von 18 Bits ohne die Paritätsprüfbits im Pufferspeicher 6A angesammelt ist. Man muß daher mit einer Codeverzögerung von einer Silbenübertragungsperiode rechnen.

Unter denselben Bedingungen wird die Fehlerkorrekturdecodiefung zeitlich nicht verzögert, da die ersten drei Codesilben nur Rohdaten enthalten und daher während der Verschiebe-

10: /1783

schritte 4 bis 6 des RSR in den Pufferspeicher 6A übertragen werden können. Zwei Paritätsprüfbits können jeder Gruppe aus 16 Rohdatenbits angehängt werden, die den Pufferspeicher 6Ά über die Leitungen 7 verläßt. Dadurch bleiben nur 6 Rohdatenbits im Pufferspeicher, die mit den 10 Rohdatenbits der vierten Codesilbe im vierten Übertragungsschritt beim Verschiebeschritt 7 zu behandeln sind.

Die Eingänge zu den Summierschaltungen Sl bis S8 in Fig. 4 und zu den UND-Gliedern 130-1 bis 130-8 in Fig. 5 werden durch eine Matrix bestimmt, die anschließend im Zusammenhang mit Fig. 7 noch besprochen wird. Wie ausführlich in der Literatur beschrieben ist, weist jedes zyklische Codesystem ein charakteristisches Generatorpolynom des Grades n-k auf, und zwar

g(x) - l+a_xx + a₂x² + ... + ^.^^_f

worin die Koeffizienten a , a_ ... bei binären Codes die Werte 1 oder O haben. Wenn Codewortpolynoroe durch das Generatorpolynom dividiert werden, bilden sich Restcodes, die eine eindeutige Beziehung zum Auftreten von Fehlern in dem Wort haben. Somit können die Restcodes zur Fehlerkorrektur benutzt werden.

Bei der normalen seriellen Division eines Polynoms, wie sie in Fig. 7 vorgeschlagen wird, wird das zu prüfende Wort über einen Modulo-2-Addierer um jeweils nur eine Stelle in ein mit n-k Stufen ausgerüstetes serielles Schieberegister hineingeschoben. Der Ausgang der letzten Registerstufe ist auf mehrerer zwischen den Registerstufen angeordnete, Modulo-2-Addierer rückgekoppelt, deren Anordnung durch die Koeffizienten des Generatorpolynoms bestimmt wird.

Sowohl die in den Fign. 4 und 5 gezeigte parallele rückgekoppelte Verschiebevorrichtung für parallele Eingabe als auch die in Fig. 7 dargestellte, parallel rückgekoppelte Verschiebevorrichtung für serielle Eingabe basieren auf dem Generatorpolynom

10 /1783

Tabelle I

Zeile 1

	O	O	1	1	1	O	O	O
•	O	O	O	1	1	1	O	O
•	O	O	O	O	1	1	1	O
•	O	O	O	O	O	1	1	1
	1	1	1	O	O	O	1	1
•	1	O	O	1	O	O	O	1
•	1	O	1	O	1	O	O	O
118	O	1	O	1	O	1	O	O
fl	O	O	1	O	1	O	1	O
f2	O	O	O	1	O	1	O	1
■	1	1	1	O	1	O	1	O
•	O	1	1	1	O	1	O	1
•	1	1	O	1	1	O	1	O
•	O	1	1	O	1	1	O	1
•	1	1	O	1	O	1	1	O

Zeilen 1-18 Matrix der Eingangsverbindungen

Zeilen 19-26 Matrix der Rückkopplungsverbin dungen
26. Zeile

(28.-52. Zeilen)

0	1	1	1	1	O	O	1	55. Zeile
1	1	O	1	1	1	O	O
ο	1	1	ο	1	1	1	ο
O	O	1	1	O	1	1	1
1	1	1	1	1	O	1	1
1	O	0	1	1	1	O	1
1	0	1	0	1	1	1	0	Zeilen 55-72
0	1	O	1	O	1	1	1	= Syndrom-Matrix
1	1	O	O	1	O	1	1	zur Fehlerkorrek
1	0	0	O	O	1	O	1	tur
1	O	1	O	0	O	1	0
O	1	O	1	0	O	O	1
1	1	0	O	1	0	O	O
0	1	1	O	0	1	O	O
O	O	1	1	0	O	1	O
0	O	O	1	1	O	O	1
1	1	1	O	1	1	O	O
O	1	1	1	0	1	1	O	72. Zeile
0	0	1	1	1	0	1	1
1	1	1		ι	1	ο	1
1	O	fl· O	1	■1» 1	•Β· 1	1	O
O	1	O	0	1	1	1	1

/1783

2 8
g (χ) = 1+x+x +χ . Der durch dieses Polynom erzeugte Code dient zur Korrektur eines Fehler und zur Erkennung von zwei Fehlern. Wenn der Inhalt der rückgekoppelten Verschiebevorrichtung für serielle Eingabe von dem Anfangszustand lOOOOOOO der Registerstufen Fl - F8 verschoben wird, und wenn der direkte Signaleingang 180 gesperrt ist, ergeben sich nacheinander die in den Zeilen der folgenden Matrix aufgeführten Restwerte:

Eine Betrachtung der Spalten der Tabelle bis zur Zeile 26 der autonom erzeugten Matrix liefert eine Einsicht in die Restwerte, die erzeugt werden, wenn ein einzelnes Bit in die Verschiebevorrichtung nach Fig. 7 hineingeschoben wird und 18 weitere autonome Verschiebungen (d.h. Verschiebungen, bei denen nur die Rückkopplungsverbindungen wirksam sind) erfährt. Dadurch gewinnt man Einblick in die Schaltungen, die erforderlich sind, um eine parallele Polynom-Division eines 72 Bit-Wortes in parallelen Teilwörtern von jeweils 18 Bits gleichzeitig durchzuführen.

So enthält z.B. die erste Spalte in der obigen Tabelle die Werte der Registerstufe Fl in Fig. 7. Diese Spalte weist in der 1., 9., 15., 16., 17., 21., 23. und 25. Zeile eine 1 und in den übrigen Zeilen eine 0 auf. Die ursprünglich der 1. Registerstufe Fl zugeführte 1 wird also bei autonomer Verschiebung in 18 aufeinanderfolgenden Schritten den Zustand dieser Registerstufe nur in den Verschiebeschritten 1, 9, 15, 16 und 17 beeinflussen. Vor Eingabe der 1 in die erste Registerstufe Fl hat der Inhalt des Registers auch einen Einfluß auf die Registerstufe Fl aufgrund der Rückkopplung, wie sich aus den Zeilen 19 und 26 der obigen Matrix entnehmen läßt.

Der Einfluß einer 1 in einer bestimmten Registerstufe, wie z.B. F3 auf die Registerstufe Fl vor der Eingabe der ersten 1 ist derselbe, als wenn das Register von Anfang an in der Stellung steht, die durch die entsprechende der ersten Zellen, in diesem Falle der dritten Zeile (Registerstufe F3) gegeben 1st. Nach 18 autonomen Verschiebungen wird jetzt der Einfluß der dritten

10 -/1783

Zeile wiedergegeben in der 21. Zeile der Matrix. Daraus ist zu ersehen, daß eine erste 1 in der Registerstufe F3 ein rückgekoppeltes EINS-Eingangssignal für die Registerstufe Fl nach 18 autonomen Verschiebungen ergibt. Betrachtet man die Spalten der durch die Zeilen 19 bis 26 in der Matrix gebildeten Teilmatirx, so ersieht man daraus, daß lediglich die Anfangs zustände von F3, F5 und F7 im Register den Zustand von Fl am Ende der 18 autonomen Verschiebungen, dargestellt durch die ersten 18 Matrixzeilen beeinflussen.

Daraus folgt, daß die Wirkung des Registers für serielle Eingabe bezüglich der Stufe Fl für Gruppen von 18 aufeinanderfolgender Eingangsverschiebungen durch eine parallele Eingangsverschiebung simuliert werden kann, indem man die Modulo-2-Surame der Signale auf den Eingangsleitungen II, 19, 115, 116 und 117 zusammen mit den als Rückkopplungssignale dienenden Ausgangssignalen der Stufen F3, F5 und F7 bildet. Aus Fig. 4 ist zu ersehen, daß das durch den Modulo-2-Addierer Sl gebildete Eingangssignal für die Registerstufe Fl genau dieser Modulo-2-Sunnae entspricht. Die Eingangssignale für die anderen Addierer S2 - S8 und das Verfahren, durch welches sie bestimmt werden, sind aus Fig. 4 und der obigen Matrix ersichtlich.

So läßt sich z.B. der Zustand der Registerstufe F2 (Flg. 7} nach 18 aufeinanderfolgenden Verschiebungen simulieren durch eine einzige parallele Eingangs-Verschiebung (siehe hierzu die ersten 26 Zeilen der zweiten Spalte der obigen Matrix), indem man die Modulo-2-Suauen aus den Signalen auf den Eingangsleitungen 12, 19, 110, 115 und 118 und den als Rückkopplungssignale dienenden Ausgangssignalen der Registerstufen F3, F4, F5, F6, F7 und F8 bildet. Somit laß sich aus der vorher erwähnten Matrix bestimmen, welche Leitungen mit den Eingängen der Summierschaltung S2 zu verbinden sind.

In entsprechender Weise lassen sich die Leitungen ermitteln, die mit den Eingängen der anderen Summierschaltungen S3 - S8 zu ver-

1(K -5/1783

- 24 -binden sind.

Im Zusammenhang mit der Korrekturdecodierung der Schaltungen nach Fig. 5 wird wieder auf die vorher angegebene, autonom gewonnene Matrix, und zwar auf deren Teil, der auf die 72. Zeile folgt, verwiesen. Ein gegebenes Generatorpolynora der in Fig. 7 gezeigten Form läßt sich leicht dahingehend überprüfen, daß die angegebene Folge von Vektorzuständen (Matrixzeilen), die Register-Restwerte darstellen, welche durch autonomes, serielles Verschieben einer einzigen EINS mit paralleler Rückkopplung und ohne daß irgendein anderes Eingangssignal zugeführt wird, erhalten werden, in dem Sinne eindeutig sind, daß alle Restwerte sich in einem Rahmen von 127 aufeinanderfolgenden Werten voneinander unterscheiden und sich in einem periodischen Muster von einem Rahmen zum anderen wiederholen.

In diesem Fall ist die Codewortlänge mit n-72 bedeutend kürzer als die Verschiebezykluslänge der 127 Restwerte und dieser Code gehört zu den Codes, die in der Literatur als verkürzte Codes bezeichnet werden. Aus der vorher angegebenen Matrix ist zu ersehen, daß jede Zeile eine ungerade Zahl von Einsen enthält. Wenn also ein Codewort aus 72 Bits fehlerfrei zum seriellen Register der Flg. 7 oder seinem 18 Bits aufnehmenden parallelen Äquivalent nach Fig. 4 übertragen wird, beträgt der endgültige Restwert des Registers OOOOOOOO. Daraus folgt, daß beim Hineinschieben eine« Fehlers in das Register sich ein von 0 verschiedener endgültiger Restwert ergibt, so als ob die anderen Datensignale nicht in das Register geschoben worden wären.

Wenn das Auftreten eines Fehlers in einem willkürlich angenommenen pten Bit eines aus 72 Bits bestehenden und zu prüfenden Wortes angenommen wird, dann durchläuft das fehlerhafte Bit effektiv 72-p Verschiebungen bis zu dem Zeitpunkt, an welchem der endgültige Prüf rest gebildet wird. Wenn also mit dem Registerinhalt nach Erreichen des endgültigen Prüfrestwertes zusätzlich weitere 55+p Verschiebungen vorgenommen werden, ist das

- · ■ 10? Π5/1783

Fehlerbit insgesamt 127mal, nämlich (72-p+55+p)mal verschoben worden und somit hat der Inhalt des seriellen Registers zur Fehlerprüfzeit den Wert, der in der ersten Zeile der Matrix angegeben ist, nämlich 10000000.

Wenn das Register zum ersten Mal wieder den Inhalt 10000000 nach 55+p zusätzlichen Verschiebungen aufweist, kann also die Gesamtzahl der zusätzlichen Verschiebungen abzüglich 55 zur Feststellung der Zahl ρ benutzt werden, die den Ort des Fehlers angibt. Bei dem vorliegenden verkürzten Code würden jedoch die 55 zusätzlichen Verschiebungen eine Zeitvergeudung bedeuten, die durch das vorliegende Verfahren ausgeschaltet werden kann. Die Zeilen 55-72 der vorher angegebenen Matrix entsprechen offensichtlich den Restwerten der ersten Zeile der Matrix nach den autonomen Verschiebungen 54 - 71. Wenn daher ein einzelner Fehler nur in der ersten Silbe eines empfangenen Wortes (p=l, 2 ... 18) enthalten ist und demzufolge 4xl8-p Verschiebungen zu dem Zeitpunkt durchlaufen hat, an welchem der endgültige Prüfrest im RSR erscheint (d.h. beim Verschiebeschritt 4), dann ist der endgültige Prüfrest identisch mit dem Inhalt der Matrixzeile (72-p+l). Somit erscheint ein Fehler in einer der 18 Bitstellen des ersten Wortes direkt im endgültigen Prüfrest bei Schritt 4 und kann decodiert werden, um den Ort des Fehlers anzugeben. Zu diesem Zweck sind 18 parallele Decodierer vorgesehen, die für die Erkennung eines der Codewörter ausgelegt sind, die in den Matrixzeilen 55 - 72 angegeben sind, nämlich die Decodierschaltung aus den UND-Gliedern 130-1 - 130-18 in Fig. 5.

Genauer gesagt, wird das UND-Glied 130-1 in Fig. 5 so vorbereitet, das es auf den Prüfrest 11111101 im RSR entsprechend der 72. Zeile der Matrix anspricht (wobei die Notierungen f bzw. f das wahre bzw. das negierte Auegangssignal des Registers in den Stufen angibt, die durch die Indexzahlen bezeichnet sind). Das erste Bit eines geprüften Wortes durchläuft einschließlich des 4. Verschiebeschrittes effektiv 71 Verschiebungen (nämlich Verschiebungen, während der Teilprüfrest der ersten Silbe ge-

10' '»/1783

bildet wird 18 weitere Verschiebungen erfolgen, während der Teilprüfest der zweiten Silbe gebildet wird usw.). Somit führt eine fälschlicherweise vor dem ersten Verschiebeschritt in der Eingangsstufe hinzugefügte oder weggelassene 1, zu welcher im ersten Verschiebeschritt in den durch die Leitung 118 beeinflußten Registerstufen eine weitere 1 Modulo-2 addiert wird, dazu, daß am 4. Verschiebeschritt im RSR ein endgültiger Prüfrest von 11111101 erscheint, wenn kein anderer Fehler aufgetreten ist. Wenn also der Ausgang des UND-Gliedes 13O-1 während des 4. Verschiebeschrittes markiert wird, wird das erste Bit der ersten Silbe des geprüften Wortes während der Übertragung der ersten Silbe durch Invertieren in den Antivalenzschaltungen wie 59' (Fig. 1) korrigiert. Die Korrektur dieses besagten ersten Bits der Silbe erfolgt durch Markierung des Steuereinganges des entsprechenden Antivalenzgliedes 59' mit dem Ausgangssignal des UND-Gliedes 130-1.

Es ist aus den Fign. 4 und 5 zu ersehen, daß das UND-Glied 130-2 (Fig. 5) in ähnlicher Weise durch seine speziellen Verbindungen mit den Ausgängen f1, f2, f3, f4, f5, f6, f7, f8 so vorbereitet wird, daß es nur auf einen Restwert im RSR von 00111011 reagiert, der der 71. Zeile der Matrix entspricht. L^ hierdurch ebenfalls der Inhalt des äquivalenten seriellen Registers der Fig. 7 nach 70 autonomen Verschiebungen des Wortes 10000000 wiedergegeben wird, läßt sich hieraus entnehmen, daß Bit 2 des geprüften Wortes im Wortpufferspeicher 26 eine Korrektur erfordert, wenn der Prüfrest 00111011 ist (d.h. wenn der Ausgang des UND-Gliedes 130-2 im Verschiebeschritt 4 markiert wird).

Wenn die UND-Glieder 130-3, 130-4 bis 130-17 (nicht dargestellt) sowie das UND-Glied 130-18 in Fig. 5 durch Kombination der Auegangesignale des RSR entsprechend den Zeilen 70-55 der obigen Matrix im Verschiebeschritt 4 vorbereitet sind, bezeichnen sie die Orte einzelner Fehler in entsprechenden Bitstellen 3-18 des geprüften Wortes entsprechend der Tabelle I.

10 ,-V/17 83

Wenn in der zweiten Silbe aus 18 Bits eines eingegebenen Codewortes (p=19, 20 ... 36) ein Fehler auftritt, zeigt sich dessen Einfluß auf den Prüf rest bei Schritt 5 nach dem Äquivalent der 5x18-p seriellen Verschiebungen. Das wiederum bedeutet zwischen 54 und 71 Verschiebungen des Grundfehlermusters lOOOOOOO, abhängig von p. Demzufolge identifiziert die Markierung des Ausganges eines der decodierenden UND-Glieder 130-1 bis 130-18 in Verbindung mit dem UND-Glied 152-2 (Fig. 5) im Verschiebeschritt 5 die Orte einzelner Fehler in den entsprechenden Bitstellen 19 - 36 eines aus 72 Bits bestehenden Wortes, das im Wortpufferspeicher 26 enthalten ist. Einzelheiten sind ebenfalls in Tabelle I angegeben.

aus der obigen Beschreibung und der Notierung in den Fign. 4 und 5 geht hervor, daß das Durchschalten der UND-Glieder 130-1 bis 130-18 in den Verschiebeschritten 6 oder 7 in Verbindung mit dem UND-Glied 152-3 bzw. 152-4 den Ort eines Einzelfehlers in den entsprechenden Bits 36-72 des geprüften Wortes angibt.

1 0!' ·■ '5/1783

Claims (2)

1. PATENTANSPRÜCHE

   (Γ/ Schaltung zur Korrektur von Einzelfehlern in den Wörtern eines zyklischen (n, k) Codes (n=Gesamtzahl der Bits eines Wortes, k-Anzahl der Datenbits) unter Verwendung eines n-k-stufigen rückgekoppelten Schieberegisters für parallele Dateneingabe, dadurch gekennzeichnet, daß die Einsteil-Eingänge der n-k Schieberegisterstufen (Fl bis F8; Fig. 4) über n-k Modulo-2-Addierer (Sl bis S8) mit ausgewählten Ausgängen (f1 bis f8) für die regulären Ausgangssignale der Schieberegisterstufen und mit ausgewählten der c Leitungen verbunden sind, die die c Bits eines Teilwortes des η Bits umfassenden Codewortes parallel anliefern, und daß ausgewählte der Ausgänge (fl, fT bis f8, f8~) für die regulären und komplementären Ausgangssignale der n-k Schieberegisterstufen an c UND-Glieder (130-1 bis 130-18, Fig. 5) führen, deren Ausgänge jeweils mit einer zugeordneten Antivalenzschaltung (59*, Fig. 1) verbunden sind, deren zweitem Eingang jeweils eines der c Bits eines zu übertragenden Teilwortes zugeleitet werden.
2. 2. Schaltung nach Anspruch 1, gekennzeichnet durch eine Paritätsprüfschaltung (117, Fig. 5) mit zwei Ausgängen (116, 119) zur Anzeige einer geraden und einer ungeraden Parität, deren Eingänge mit den Ausgängen für reguläre Signale der n-k Schieberegisterstufen verbunden ist und dessen eine gerade Parität anzeigender Ausgang an ein UND-Glied (115) führt, das in Verbindung mit dem Ausgangssignal eines ebenfalls an die Ausgänge für die regulären Signale des n-k-stufigen Schieberegisters angeschlossenen ODER-Gliedes (110) einen nicht korrigierbaren Doppelfehler anzeigt, während der eine ungerade Parität anzeigende Ausgang (119) der Paritätsprüfschaltung an ein weiteres UND-Glied (120) angeschlossen ist, das auch mit dem vorher erwähnten ODER-Glied verbunden ist und dessen Ausgang (121) an den Einstell-Eingang einer bistabilen Kippstufe (135) führt, die die Verschiebevorgänge zur Fehlerkorrektur steuert. J{t)$liS