DE1238245B - Fehlerkorrigierendes Datenuebertragungssystem - Google Patents

Description

BUNDESREPUBLIK DEUTSCHLAND

DEUTSCHES

PATENTAMT

AUSLEGESCHRIFT

Int. Cl.:

G06f

Deutsche Kl.: 42 m3 -11/08

Nummer: 1 238 245

Aktenzeichen: T 25151 IXc/42m3

Anmeldetag: 28. November 1963

Auslegetag: 6. April 1967

Die Erfindung betrifft ein fehlerkorrigierendes Datenübertragungssystem, das auf der Sendeseite ein Kodierwerk besitzt, in dem für jeweils eine Datengruppe ein rt-stelliger Priifvektor gebildet wird, und das auf der Empfangsseite ein ähnliches Kodierwerk besitzt, in dem aus der übertragenen Binärfolge (Datengruppe — Priifvektor) ein n-stelliger Korrekturvektor gebildet wird, der bei fehlerloser Übertragung NULL ist, und mit dessen Hilfe ein Übertragungsfehler anschließend in einer Korrigiereinrichtung erkannt und gegebenenfalls korrigiert wird.

Solche Systeme sind an sich bekannt. Bezüglich ihrer theoretischen Grundlagen wird auf das Buch von W. VV. Peterson, »Error Correcting Codes«, The Technology Press 1961, verwiesen. Dort sind zahlreiche Kodes mit ihren Eigenschaften diskutiert. Die Klasse von Kodes, mit denen sich die Erfindung befaßt, nennt man Gruppenkodes. Deren Eigenschaften sind in einem Aufsatz des Erfinders in den »Annales Universitatis Saraviensis — Scientia«, Vol. IX, Fase. 1/2, 1960/61, S. 3 bis 12, ausführlich behandelt.

Auf Seite 11 dieser Schrift ist ein Beispiel eines besonders günstigen, »maximal« genannten (4, 7, 5)-Kodes für vier Informationselemente und sieben Prüfbits angegeben. Ein (m, r, d)-Code ist ein Code mit m Informationsstellen und r Prüfstellen, dessen Vektoren paarweise eine Distanz größer oder gleich d haben. Die folgende Tabelle zeigt ein matrixartiges Binärmuster gemäß diesem Kode, dessen elf Spalten elf siebendimensionale Binärvektoren bilden.

Tabelle

Will man ein solches Muster zur Bildung von Prüfzeichen verwenden, dann ordnet man jeder Spalte ein binäres Informationselement der Datengruppe zu und addiert vektoriell modulo 2 die Spaltenvektoren miteinander, deren Informationselemente den Wert EINS aufweisen.

Soll beispielsweise eine Datengruppe 1001 mit einem Prüfvektor versehen werden, dann entsteht dieser durch Addition der ersteren (1111000) und vierten Spalte des (1100110) in obiger Tabelle angegebenen Musters. Das Ergebnis lautet 0011110. Bildet man

1	O	O	1	1	O	O	O	O	O	O
1	O	1	1	O	1	O	O	O	O	O
1	O	1	O	O	O	τ—Ι	O	O	O	O
1	1	O	O	O	O	O	1	O	O	O
O	1	1	1	O	O	O	O	1	O	O
O	1	O	1	O	O	O	O	O	1	O
O	1	1	O	O	O	O	O	O	O	1

Fehlerkorrigierendes Datenübertragungssystem

Anmelder:
Telefunken

Patentverwertungsgesellschaft m. b. H.,
Ulm 'Donau, Elisabethenstr. 3

Als Erfinder benannt:

Dr. Günter Hotz, Saarbrücken

schließlich auf der Empfangsseite aus Datengruppe + Prüf vektor (10010011110) einen Korrekturvektor auf dieselbe Weise wie den Prüfvektor, dann lautet dieser in allen Stellen NULL, wenn die Übertragung fehlerfrei erfolgte. Ein einzelner Fehler läßt einen Vektor entstehen, welcher gerade der Spalte des Musters entspricht, deren zugeordnetes Informationselement fehlerhaft ist. Ein Mehrfachfehler führt auf einen Vektor, der der Vektorsumme mehrerer Spalten entspricht. Die diesen Spalten zugeordneten Informationselemente werden so als fehlerhaft erkannt.

Ausgehend von diesen im wesentlichen theoretischen Erkenntnissen wird durch die Erfindung ein fehlerkorrigierendes Übertragungssystem angegeben, das sich durch geringen Aufwand auszeichnet. Außerdem besitzt es den Vorteil, daß es sich für jeden vom Standpunkt der Fehlererkennung vorteilhaften Gruppenkode eignet.

Die Erfindung ist dadurch gekennzeichnet, daß die Kodierwerke auf der Sende- und der Empfangsseite je ein Schaltwerk enthalten, das synchron' mit der Datenübertragung jeweils für jede Binärstelle einen H-dimensionalen von Null verschiedenen und auch für jede Binärstelle verschiedenen Binärvektor bereitstellt, dessen Komponenten nur bei Vorliegen des Wertes EINS der jeweiligen Binärstelle in ein erstes Register in der Weise übertragen werden, daß dort die Summe modulo 2 sämtlicher für eine Datengruppe übertragener Binärvektoren gebildet wird, daß das auf der Sendeseite befindliche Kodierwerk Ausgabemittel aufweist, über die nach dem Durchlauf einer Datengruppe der Inhalt des ersten Registers als Prüfvektor an den Sendekanal abgegeben wird, und daß auf der Empfangsseite eine Vergleichseinrichtung vorgesehen ist, mit welcher der Inhalt des ersten Registers nach jeder Übertragung einer Binärfolge (Datengruppe und Prüfvektor) mit den von dem Schaltwerk nacheinander bereitgestellten Binärvektoren verglichen wird, wobei die Vergleichseinrichtung bei Identität des Inhaltes des

709 548/163

3 4

ersten Registers und des Schaltwerksinhaltes einen mit jedem weiteren der synchron mit den Uhrimpulsen Impuls abgibt, der den Binärwert der dem jeweils auftretenden Informationselemente wird das Schaltvorliegenden Schaltwerksstand zugeordneten Binär- werk weitergeschaltet. Wenn das letzte Informationsstelle der Binärfolge (Datengruppe und Prüfvektor) element (im vorliegenden Beispiel das vierte) eingeinvertiert. 5 troffen ist, dann enthält das Register 33 des Kodier-

Weiterbildungen der Erfindung sind in den Unter- werks einen «-dimensionalen Prüfvektor, der in der ansprüchen gekennzeichnet. Es sei betont, daß die Zwischenzeit, bis die nächste Gruppe von Informations-Erfindung sich nicht auf den erwähnten Kode be- elementen am Eingang 15 eintrifft, über einen Ausschränkt und daß die Wahl eines bestimmten Kodes gang 16 auf den Übertragungskanal ausgeschoben lediglich ein entsprechendes Bitmuster ähnlich der io wird. Das Register ist zu diesem Zweck schiebefähig Tabelle und damit eine geeignete Ausführung des ausgebildet. Es ist offensichtlich, daß dieses einfache Schaltwerkes 6 zur Folge hat. Dieses Schaltwerk für Kodierwerk einen Prüfvektor gemäß dem in der sich ist jedoch nicht Gegenstand der vorliegenden Einleitung erwähnten Zahlenbeispiel zu bilden im-Erfindung. stände ist.

Ausführungsbeispiele der Erfindung werden nach- 15 Ein besonderer Vorteil der beschriebenen Lösung

folgend an Hand der F i g. 1 bis 4 näher erläutert. besteht darin, daß ein Kodierwerk desselben Aufbaus

F i g. 1 zeigt das Blockschema eines derartigen auch auf der Empfangsseite einzusetzen ist, um den Übertragungssystems mit einem Datensender 1 und Korrekturvektor zu bilden, und daß schließlich nur einem Datenempfänger 2. Auf dem Übertragungs- geringfügige Erweiterungen nötig sind, um mit denkanal 3 werden nicht nur gruppenweise die Daten des 20 selben Einrichtungen die Korrektur der übertragenden Senders 1, sondern auch Prüfvektoren übertragen, Datengruppe durchzuführen. Ein solches Dekodierdie in einem Kodierwerk 4 auf der Sendeseite von der werk ist in F i g. 3 dargestellt. Es enthält ebenfalls ein Datengruppe abgeleitet werden. Auf der Empfangs- Schaltwerk 6, dessen Ausgänge die Spalten des zwischen seite mündet der Übertragungskanal 3 in ein Deko- Sende- und Empfangsseite verabredeten Bitmusters dierwerk 5, in dem auf Grund der Prüfvektoren Über- 25 herstellen. Weiter finden sich auch hier die Exklusivtragungsfehler erkannt und gegebenenfalls korrigiert Oder-Tore 7 bis 10, das Register 33 mit den Elementen werden, ehe die Datengruppe den Empfänger 2 Ra, Rb, Rc ... Rg, sowie die Und-Tore 11 bis 14. erreicht. Der Dekodiervorgang läßt sich im einfachsten Fall

F i g. 2 zeigt ein Kodierwerk, in dem ein «-stelliger in zwei Schritte einteilen, von denen der erste zur Prüfvektor gebildet wird. Das Kodierwerk enthält als 3° Bildung des Korrekturvektors in dem Register 33 wesentliches Element ein Schaltwerk 6 zur Bereit- und der zweite zur Korrektur der Datengruppe mit stellung von Binärvektoren, der η Ausgänge aufweist. Hilfe des Korrekturvektors vorgesehen ist. Der erste Für den obenerwähnten Kode ist η = 7; das Schalt- Schritt dauert gerade so lange wie die Übertragung werk vermag elf verschiedene Zustände einzunehmen, einer Datengruppe einschließlich Prüfzeichen. Erst entsprechend den elf Spalten des Musters aus der 35 wenn das letzte Prüfzeichen über den Eingang 17 Tabelle. Es enthält vorzugsweise sieben bistabile des Dekodierwerks eingetroffen ist, kann mit der Elemente, deren Aus- und Eingänge in bekannter Korrektur begonnen werden. Zur Zwischenspeicherung Weise über logische Und- und Oder-Tore derart der Datengruppe ist ein Verzögerungsglied, beispielsverbunden sind, daß an den Ausgängen eine Zustands- weise in Form eines Schieberegisters 18 vorhanden, folge gemäß den Spalten der Tabelle auftritt. Eine 40 dessen Eingang die übertragene Datengruppe zugenicht gezeichnete Uhrimpulsquelle schaltet den Zähler führt erhält. Nach Abschluß des ersten Schrittes in jeder Zeiteinheit um einen Zustand weiter. (Bildung des Korrekturvektors im Register 33) ist das

Weiter enthält das Kodierwerk ein «-stelliges erste übertragene Informationselement gerade am Register 33 mit den bistabilen Registerelementen Ra, Ausgang des Schieberegisters angekommen.
Rb, Rc ... Rg, sowie η Exklusiv-Oder-Tore 7 bis 10, 45 Zur Steuerung der beiden Schritte ist, vorausgesetzt, deren jeweils erster Eingang mit dem Ausgang eines daß nur Einzelfehler bei der Übertragung auftreten, bistabilen Elements des Registers verbunden ist und lediglich ein Vielfachkontakt 19 nötig, in dessen deren Ausgang je auf den Eingang desselben Register- Ruhestellung die Ausgänge aller Exklusiv-Oderelements einwirkt. Die η Ausgänge des Schaltwerkes 6 Tore 7 bis 10 mit den Eingängen der Registerelemente sind über je ein Und-Tor 11 bis 14 mit den zweiten 50 Ra bis Rg verbunden sind. Gleichzeitig ist der InEingängen der Exklusiv-Oder-Tore 7 bis 10 verbunden. f ormationseingang 17, wie in F i g. 2 der Eingang 15, Alle Und-Tore werden gemeinsam von einem Eingang auf die Und-Tore 11 bis 14 geschaltet, so daß gleich-15 des Kodierwerks gesteuert, dem die Signalfolge artig wie beim Kodiervorgang der Korrekturvektor zugeführt wird, deren Prüfvektor gesucht ist. Die durch vom Informationszustand am Eingang 17 ab-Exklusiv-Oder-Tore wirken also genauso, als wenn 55 hängige Addition des Schaltwerkes 6 auf den Registerdie bistabilen Registerelemente einen Wechseleingang inhalt 33 entsteht.

besäßen, der unmittelbar von den Und-Toren ange- Nach Ablauf des ersten Schrittes, d. h. wenn der

steuert würde. Korrekturvektor gebildet ist, wird lediglich der Viel-

Ein solches Kodierwerk erfüllt die obenerwähnte fachkontakt 19 in seine Arbeitsstellung gebracht, so

Funktion, indem der Zustand des Schaltwerkes 6 60 daß die Ausgänge der Exklusiv-Oder-Tore nicht mehr

jeweils dann mit dem Inhalt des Registers über die mit den Eingängen des Registers, sondern mit den

Exklusiv-Oder-Tore zu einem neuen Registerinhalt Eingängen eines Vergleichsnetzwerks 20 verbunden

verknüpft wird, wenn am Eingang 15 ein Impuls der sind. Dieses Vergleichsnetzwerk besteht im einfachsten

Bedeutung EINS vorliegt. Zu Beginn des Vorgangs Fall aus einem NOR-Tor, dessen Ausgang nur dann

ist das Register gelöscht und das Schaltwerk 6 sieht 65 erregt ist, wenn alle seine Eingänge die logische

in einer definierten Anfangsstellung, die der ersten Bedeutung NULL zeigen. Der Ausgang dieses Ver-

Spalte der Tabelle 1 entspricht. Mit dem Eintreffen gleichsnetzwerks ist also gerade dann erregt, wenn

des ersten Informationselements am Eingang 15 und der Inhalt des Schaltwerkes 6 mit dem des Registers 33

übereinstimmt. Nur dann ist nämlich keines der Weise miteinander verbunden. Der erste Schritt zur Exklusiv-Oder-Tore 7 bis 10 erregt. Ein besonderer Bildung des Korrekturvektors und der zweite Schritt Kontakt des Vielfachkontaktsatzes 19 hat den In- zur Korrektur von Einzelfehlern laufen also wie bisher formationseingang 17 von den Und-Toren 11 bis 14 ab. Im Schieberegister 18 wird auch hier die ganze abgetrennt und letztere mit einer logisch EINS 5 Datengruppe, die vom Eingang 17 kommt, zwischenbedeutenden Spannung verbunden, die an einem gespeichert. Sie wird jedoch nicht bereits während Eingang 21 anliegt. Dadurch ist gewährleistet, daß des zweiten Schrittes auf den Ausgang 22 gegeben, während des zweiten Schrittes die Und-Tore 11 bis 14 sondern das Schieberegister 18 ist über das fehlerdauernd geöffnet sind, so daß der Vergleich ungestört korrigierende Exklusiv-Oder-Tor 23 zu einem Schiebedurchgeführt werden kann. io ring geschaltet, in dem die Datengruppe so lange

Es wurde bereits erwähnt, daß ein Einzelfehler einen umläuft, bis alle korrigierbaren Fehler korrigiert

Korrekturvektor erzeugt, der gerade der Spalte des sind, also das Register 33 gleich NULL ist. Erst dann

Musters nach der Tabelle entspricht, deren zugeordne- wird ein die Ausgabe steuerndes Und-Tor 24 geöffnet,

tes Informationselement fehlerhaft ist. Da das Schiebe- das den Ausgang des Schieberegisters 18 auf den

register 18 mit dem Schaltwerk 6 synchronisiert ist, 15 Ausgang 22 des Dekodierwerks durchverbindet,

wird erreicht, daß das fehlerhafte Informationselement Der Ausgang des Vergleichsnetzwerks 20 steuert

gerade dann am Ausgang des Schieberegisters 18 zur hier nicht nur das den Fehler korrigierende Exklusiv-

Ubertragung auf einen Ausgang 22 des Dekodier- Oder-Tor 23, sondern auch die Parallelübertragung

werks ansteht, wenn der Inhalt des Schaltwerkes 6 des Inhalts eines Hilfsregisters 34 mit den Register-

mit dem Korrekturvektor übereinstimmt. Dadurch 20 elementen Ha, Hb, Hc ... Hg in das Register 33. Zu

bietet sich nach erfolgter Fehlererkennung die Korrek- diesem Zweck sind weitere η Und-Tore 25, 26, 27 und

tür unmittelbar an, da nunmehr nur das Ausgangssignal 28 vorgesehen, die von dem Ausgang des Vergleichs-

des Vergleichsnetzwerks 20 dazu benutzt werden muß, netzwerke gesteuert werden.

um das gerade am Ausgang des Schieberegisters vor- Daß auch hier die Ablaufsteuerung der einzelnen liegende Informationselement bezüglich seiner Binär- 25 Schritte extrem einfach realisiert werden kann, ist bedeutung umzukehren. Dies erfolgt in einem Exklusiv- daran zu sehen, daß anstelle des Vielfachkontaktsatzes Oder-Tor 23 in an sich bekannter Weise. Der Ausgang 19 nunmehr nicht mehr als zwei Vielfachkontaktdieses Tores bildet unmittelbar den Ausgang 22 des sätze 29 und 30 vorhanden sind. Der erste Kontakt-Dekodierwerks und ist mit dem Eingang des Daten- satz 29 verbindet in seiner Ruhelage die Ausgänge empfängers 2 aus F i g. 1 verbunden. 30 der Exklusiv-Oder-Tore 7 bis 10 mit den Eingängen

Die soweit beschriebene Schaltung vermag also der Registerelemente Ra bis Rg, während er in seiner im ersten Schritt einen Korrekturvektor zu bilden, Arbeitslage diese Verbindungen auftrennt. Dieser der natürlich NULL ist, wenn kein Übertragungsfehler Kontaktsatz wird in noch zu beschreibender Weise aufgetreten war, und im zweiten Schritt mit Hilfe während des zweiten und der weiteren Schritte kurzeines Vergleichsnetzwerks das fehlerhafte Informations- 35 zeitig jeweils in seine Arbeitslage gebracht. Der zweite element zu lokalisieren und zu korrigieren. Sind jedoch Kontaktsatz 30 stellt in seiner Arbeitslage die Ver-Doppelfehler oder Mehrfachfehler bei der Über- bindung zwischen dem Vergleichsnetzwerk 20 und den tragung aufgetreten, dann vermag das Dekodierwerk Ausgängen der Exklusiv-Oder-Tore 7 bis 10 her und gemäß F i g. 3 lediglich durch die Abfrage, ob das trennt diese Verbindung in seiner Ruhelage. Dieser Register 33 ungleich NULL ist, zuerkennen, daß solche 40 Kontaktsatz ist während des ganzen ersten Schrittes Fehler aufgetreten sind, nicht jedoch, sie zu korri- in seiner Ruhelage und während aller weiteren Schritte gieren. In diesem Fall läßt sich während des ganzen in seiner Arbeitslage. Er entspricht weitgehend dem zweiten Schrittes keine Identität zwischen dem Schalt- Kontaktsatz 19 aus F i g. 3 und besitzt auch einen werk 6 und dem Korrekturvektor feststellen, obwohl Kontakt, der in der Ruhelage den Eingang 17 des der Inhalt des Registers 33 ungleich NULL ist. Die 45 Kodierwerks mit den Und-Toren 11 bis 14 verbindet, Datengruppe wird dann nach Abschluß des zweiten während er in seiner Arbeitslage über den Eingang 21 Schrittes ausgegeben. Aus der Tatsache, daß keine das erwähnte EINS-Potential auf diese Und-Tore Identität aufgetreten war, läßt sich jedoch eine schaltet. Schließlich unterscheidet sich dieses Dekodiergeeignete Maßnahme ableiten, insbesondere den werk von dem gemäß F i g. 3 noch in einem parallelen Befehl an die Sendestelle zu melden, die vorher 50 Übertragungsweg zwischen dem Schaltwerk 6 und übertragene Datengruppe nochmals zu senden. dem Hilfsregister. Zur Vereinfachung der Darstellung

Es gibt jedoch Kodes, die im Prinzip die Korrektur ist dieser Weg nur durch eine einzige Leitung 31

von Mehrfachfehlern zulassen. Beispielsweise erlaubt dargestellt, die über zwei in Serie geschaltete je einem

der in der Tabelle angeführte Kode die Korrektur der beiden Kontaktsätze 29 und 30 zugeordnete

von Einzel- und Doppelfehlern, wobei die beiden 55 Kontakte den Zähler mit dem Hilfsregister verbindet,

fehlerhaften Informationselemente an beliebigen Stellen Diese Verbindung wird nur wirksam, so lange der

innerhalb der Datengruppe einschließlich des Prüf- Kontaktsatz 29 in seiner Ruhelage, der Kontaktsatz 30

vektors liegen können. Es empfiehlt sich deshalb, das in seiner Arbeitslage steht.

Dekodierwerk den prinzipiellen Fähigkeiten des Die Funktion dieses Dekodierwerks ist folgende:

Kodes anzupassen. Es zeigt sich, daß diese An- 60 Während des ersten Schrittes wird wie erläutert der

passung durch relativ geringfügige Erweiterung des Korrekturvektor im Register 33 gebildet. Dann werden

Einzelfehler korrigierenden Dekodierwerks möglich beide Kontaktsätze aus der gezeichneten Ruhelage in

wird. ihre Arbeitsstellung gebracht, so daß der zweite

F i g. 4 zeigt eine solche Erweiterung für die Schritt ablaufen kann, genau wie dies an Hand von

Korrektur von Doppelfehlern. Das Schaltwerk 6 und 65 F i g. 3 erläutert wurde.

das Register 33 für den Korrekturvektor, die Exklusiv- Hat dieser Schritt bereits zu einer Identität zwischen

Oder-Tore 7 bis 10 und die Und-Tore 11 bis 14 sind dem Inhalt des Registers 33 und dem des Schaltwerkes 6

auch hier vorhanden und in der bereits geschilderten geführt, dann wird das gerade am Ausgang des

Schieberegisters 18 anstehende Informationselement wird dann der Kontaktsatz 29 für nunmehr zwei

in dem Exklusiv-Oder-Tor 23 korrigiert und der Uhrimpulse in seine Ruhelage gebracht, wodurch

Inhalt des Hilfsregisters 34 wird gleichzeitig über die bewirkt wird, daß der Anfangszustand des Schalt*

Und-Tore 25 bis 28 in das erste Register 33 übertragen. Werkes 6 und der diesem unmittelbar folgende Zustand

Das Hilfsregister war jedoch bis dahin noch nicht 5 über die Exklusiv-Oder-Tore 7 bis 10 nacheinander

über die Leitung 31 auf das Schaltwerk 6 durch- in das erste Register addiert werden. Durch die

geschaltet gewesen, so daß nach der Übertragung Eigenschaft der Modulo-2-Addition, die identisch mit

beide Register den Inhalt NULL aufweisen. Das einer entsprechenden Subtraktion ist, wird der zu

Kriterium »Register 33 zeigt den Inhalt NULL«, Beginn des vorhergegangenen Schrittes auf den

das das Ende des Korrekturvorganges anzeigt, wird io ursprünglichen Korrekturvektor addierte Schaltwerk-

dazu benutzt, den Inhalt des Schieberegisters über das Anfangszustand (erster Schaltwerk-Vektor) wieder

Ausgabe-Und-Tor 24 auszugeben. Falls überhaupt subtrahiert und dafür auf den ursprünglichen Korrek*

kein Übertragungsfehler aufgetreten war, dann führte turvektor nunmehr der zweite Schaltwerk-Vektor auf-

bereits nach dem ersten Schritt dieses Kriterium zur addiert. Gleichzeitig wird auch in das Hilfsregister

Ausgabe der Datengruppe. Ohne umfangreiche Steuer- 15 dieser zweite Schaltwerk-Vektor eingetragen. In dem

mittel ist damit eine schnellstmögliche Freigabe des ersten Register steht nunmehr die Summe aus dem

Dekodierwerks möglich. Korrekturvektor und dem zweiten Schaltwerk-Vektor

Wenn bei der Übertragung zwei Fehler aufgetreten zur Verfügung, so daß im nächstfolgenden Schritt

waren, dann führt auch der zweite Schritt nicht zu dieser Vektor mit allen Schaltwerk-Vektoren auf

einer Identität zwischen dem ersten Register und dem 20 Identität geprüft werden kann. Hat auch dieser

Schaltwerk, da ja in dem Register die Summe zweier Schritt zu keiner Identitätsanzeige geführt, dann

Vektoren gespeichert ist, die bei einem maximalen wird mit dem letzten Uhrimpuls dieses Zyklus der

Kode mit keinem der ursprünglichen Vektoren zweite Schaltwerk-Vektor subtrahiert und mit dem

identisch ist. Nach Abschluß des zweiten Schrittes nächstfolgenden Uhrimpuls die Summe aus dem

wird der erste Kontaktsatz 29, der während des zweiten 25 ursprünglichen Korrekturvektor und dem dritten

Schrittes in seiner Arbeitsstellung lag, für eine einzige Schaltwerk-Vektor im ersten Register hergestellt;

Uhrimpulslänge kurzzeitig in die Ruhelage versetzt. gleichzeitig wird dieser dritte Schaltwerk-Vektor in

Dadurch wird der Anfangszustand des Schaltwerkes 6 das Hilfsregister übertragen.

sowohl über die Leitung 31 in das Hilfsregister Dieser Vergleichsvorgang wiederholt sich so lange,

übertragen, als auch über die Exklusiv-Oder-Tore 7 30 bis irgendwann eine Identität festgestellt wird. Gleich-

bis 10 auf dem bisherigen Inhalt des ersten Registers zeitig rotiert die Datengruppe in dem Schieberegister,

stellenweise modulo 2 aufaddiert. Dann wird der Wenn eine Identität festgestellt wird, wird schließlich

Kontaktsatz 29 wieder in seine Arbeitsstellung gebracht der Hilfsregisterinhalt in das erste Register 33 über-

und so folgt ein dem zweiten Schritt ähnlicher dritter tragen, das Hilfsregister 34 wird gelöscht und der

Schritt, in dem wieder das erste Register mit dem 35 letzte Fehler kann auf Grund des Inhalts des ersten

Schaltwerk verglichen wird. Registers korrigiert und lokalisiert werden. Dabei

War bereits das erste Informationselement eines wird der Inhalt des ersten Registers über die Undder beiden fehlerhaften Informationselemente, dann Tore 25 bis 28 zu NULL, so daß das Abschlußführt dieser dritte Schritt zur Identität bei einem kriterium erfüllt ist und die Datengruppe ausgegeben Schaltwerkstand, der dem anderen fehlerhaften In- 40 werden kann.

formationselement entspricht. Gerade dieses Infor- Nach diesen Erläuterungen soll abschließend ein mationselement ist in diesem Augenblick am Ausgang Rechenablauf als Zahlenbeispiel die Funktion des des Schieberegisters verfügbar und wird in dem erfindungsgemäßen Dekodierwerkes vollends klar-Exklusiv-Oder-Tor 23 korrigiert und anschließend stellen. Wir nehmen wieder an, daß das Schaltwerk 6 wieder dem Eingang des Schieberegisters zugeführt. 45 nach dem Kode gemäß der Tabelle arbeitet und daß Gleichzeitig wird der Inhalt des Hilfsregisters in das eine Datengruppe 1001 auf der Senderseite mit dem erste Register übertragen, so daß dieses nunmehr den Prüfvektor 0011110 versehen worden ist. Auf der Anfangszustand des Schaltwerkes enthält. Sorgt man Empfangsseite soll 10010010110 eingetroffen sein, d. h., nun dafür, daß die Kontaktsätze während eines das achte Informationselement wurde fehlerhaft übernachfolgenden vierten Schrittes in ihren Arbeitslagen 50 tragen. Im ersten Schritt wird der Korrekturvektor verharren, dann wird automatisch beim Vergleich mit durch vektorielle Addition der Spalten 1, 4, 7,9 und 10 dem Schaltwerk-Anfangszustand wieder Identität fest- aus der Tabelle gebildet. Daraus ergibt sich der gestellt, so daß das in diesem Zeitpunkt am Ausgang Korrekturvektor 0001000.

des Schieberegisters 18 anliegende erste Informations- Im zweiten Schritt wird dieser Korrekturvektor

element ebenfalls korrigiert wird. Hat man beim 55 mit den einzelnen Spalten verglichen und es wird

Auftreten der ersten Identität das Hilfsregister auf Identität mit der achten Spalte festgestellt, d. h., der

NULL gesetzt, was beispielsweise über eine Leitung 32 Fehler liegt an der achten Stelle. Diese Stelle steht

erfolgen kann, die mit dem Ausgang des Vergleichs- gerade in dem Augenblick, in dem die Identität fest-

netzwerkes verbunden ist, dann wird bei der zweiten gestellt wird, am Ausgang des Schieberegisters 18

Identität dieser NULL-Inhalt über die Und-Tore 25 60 zur Korrektur bereit.

bis 28 in das erste Register übertragen, so daß auf Nunmehr soll angenommen werden, daß nicht nur

Grund des erwähnten Abschlußkriteriums der Inhalt die achte Stelle sondern auch die dritte Stelle fehlerhaft

des Schieberegisters 18 ausgegeben werden kann. übertragen worden ist, d. h., die empfangene Daten-

In den meisten Fällen trifft jedoch die Annahme gruppe lautet 10110010110. Im ersten Schritt wird der

nicht zu, daß bereits das erste Informationselement 65 Korrekturvektor gebildet aus den Spalten 1, 3, 4, 7, 9

fehlerhaft ist. Dann führt also der dritte Schritt noch und 10 der Tabelle. Er lautet demnach 0111101. Der

nicht zur Identität und zum Ansprechen des Vergleichs- Vergleich mit den vorhandenen Spalten der Tabelle

netzwerks. Mit dem letzten Uhrimpuls dieses Schrittes führt diesmal im zweiten Schritt nicht zur Identität.

Deshalb folgt im dritten Schritt der Vergleich aller Spalten der Tabelle mit der vektoriellen Summe aus der ersten Spalte (1111000) und dem Korrekturvektor. Diese Summe lautet 1000101. Da auch dieser Vektor, nicht in den Spalten der Tabelle vorkommt wird in einem weiteren Schritt die obengebildete Summe (1000101) zuerst mit der ersten Spalte (1111000) addiert (wodurch der ursprüngliche Korrekturvektor 0111101 wieder entsteht) und dann mit der zweiten Spalte (0001111) addiert. Dabei wird ein Vektor 0110010 gebildet. Der Vergleichsschritt zeigt, daß auch dieser Vektor nicht zu den Spalten der Tabelle gehört. Derselbe Vorgang wiederholt sich nun mit der Summe aus dem Korrekturvektor und der dritten Spalte, wobei 0001000 entsteht. Der Vergleich mit der Tabelle zeigt, daß dieser Vektor gerade die achte Spalte beschreibt, d. h., es wird Identität mit dem Schaltwerkinhalt festgestellt, während gerade das achte Informationselement am Ausgang des Schieberegisters bereitsteht. Dieses wird korrigiert und der Inhalt der dritten Spalte, der bis dahin im Hilfsregister gespeichert wurde, wird in das erste Register übertragen und der abschließende Vergleichsschritt zeigt Identität mit der dritten Spalte. Nunmehr sind beide Fehler gefunden und korrigiert. Das erste Register ist zu NULL geworden und die fehlerfreie Datengruppe kann an den Ausgang 22 abgegeben werden.

Würde die Datengruppe noch einen dritten Übertragungsfehler enthalten, dann wäre bei dem verwendeten Kode keine eindeutige Korrektur mehr möglich. Es gibt jedoch Kodes mit einer größeren Redundanz, bei denen auch drei und mehr Fehler korrigierbar sind. Um diesen theoretischen Forderungen gerecht zu werden, muß das Dekodierwerk für jeden weiteren korrigierbaren Fehler um ein Hilfsregister erweitert werden. Der Vorgang verläuft ähnlich wie bei den beschriebenen Dekodierwerken: Zuerst wird der Korrekturvektor gebildet, im zweiten Schritt werden Einzelfehler, falls vorhanden, korrigiert, im dritten und weiteren Schritten werden Doppelfehler, falls vorhanden, korrigiert und dann werden nacheinander im ersten Hilfsregister die Summen jeweils zweier Spalten der Tabelle bereitgestellt und auf den Korrekturvektor aufaddiert. Ergibt der Vergleich dieses neuen Vektors mit den Spalten der Tabelle eine Identität, dann wird das Informationselement, das zum Zeitpunkt der Identität am Ausgang des Schieberegisters bereitsteht, korrigiert und die im ersten Hilfsregister bereitgestellte Summe zweier Spalten der Tabelle wird in das erste Register übernommen. Nun wird der verbleibende Doppelfehler in der beschriebenen Weise korrigiert.

Es wurde also ein Datenübertragungssystem mit Kodierwerk und Dekodierwerk angegeben, daß mit verhältnismäßig geringem Aufwand (allerdings auf Kosten der Zeit) die Korrektur von Fehlern für einen beliebigen Gruppenkode vornimmt. Gerade wegen des geringen Aufwands an Steuermitteln und speichernden und logischen Elementen ist eine hohe Funktionssicherheit des Systems gewährleistet. Durch geeignete Wahl des Kodes läßt sich das Schaltwerk so redundant auslegen, daß ein Einzelfehler im Schaltwerk nur einen Einzelfehler in der Nachricht zur Folge hat, der aber automatisch korrigiert wird. Weiter kann man bei manchen Beschädigungen auf Sende- und Empfangsseite auf einen weniger redundanten Kode herunterschalten, für den das Übertragungssystem noch arbeitet.

Claims (5)

Patentansprüche:

1. Fehlerkorrigierendes Datenübertragungssystem, das auf der Sendeseite ein Kodierwerk besitzt, in dem für jeweils eine Datengruppe ein «-stelliger Prüfvektor gebildet wird, und das auf der Empfangsseite ein ähnliches Kodierwerk besitzt, in dem aus der übertragenen Binärfolge (Datengruppe und Prüfvektor) ein «-stelliger Korrekturvektor gebildet wird, der bei fehlerloser Übertragung NULL ist und mit dessen Hilfe ein Übertragungsfehler anschließend in einer Korrigiereinrichtung erkannt und gegebenenfalls korrigiert wird, dadurch gekennzeichnet, daß die Kodierwerke (F i g. 2, 3) auf der Sende- und der Empfangsseite je ein Schaltwerk (6) enthalten, das synchron mit der Datenübertragung jeweils für jede Binärstelle einen «-dimensionalen von NULL verschiedenen und auch für jede Binärstelle verschiedenen Binärvektor bereitstellt, dessen Komponenten nur bei Vorliegen des Wertes EINS der jeweiligen Binärstelle in ein erstes Register (33) in der Weise übertragen werden, daß dort die Summe modulo 2 sämtlicher für eine Datengruppe übertragener Binärvektoren gebildet wird, daß das auf der Sendeseite befindliche Kodierwerk Ausgabemittel (16) aufweist, über die nach dem Durchlauf einer Datengruppe der Inhalt des ersten Registers als Prüfvektor an den Sendekanal (3) abgegeben wird, und daß auf der Empfangsseite eine Vergleichseinrichtung (20) vorgesehen ist, mit welcher der Inhalt des ersten Registers nach jeder Übertragung einer Binärfolge (Datengruppe und Prüfvektor) mit den von dem Schaltwerk (6) nacheinander bereitgestellten Binärvektoren verglichen wird, wobei die Vergleichseinrichtung bei Identität des Inhaltes des ersten Registers und des Schaltwerkinhaltes einen Impuls abgibt, der den Binärwert der dem jeweils vorliegenden Schaltwerksstand zugeordneten Binärstelle der Binärfolge (Datengruppe und Prüfvektor) invertiert.

2. Fehlerkorrigierendes Datenübertragungssystem nach Anspruch 1, auf dessen Empfangsseite in an sich bekannter Weise ein Verzögerungsglied, z. B. ein Schieberegister, vorgesehen ist, das eine übertragene Binärfolge (Datengruppe und Prüfvektor) in Serie aufnimmt und erst abzugeben beginnt, wenn der Korrekturvektor gebildet ist und das Schaltwerk zum Zwecke der Korrektur erneut alle jeder Binärfolge zugeordneten Binärvektoren zu durchlaufen beginnt, dadurch gekennzeichnet, daß die Vergleichseinrichtung auf ein Korrekturtor (23) einwirkt, das am Ausgang dieses Verzögerungsglieds (18) derart angeschlossen ist, daß die Korrektur in der von dem Verzögerungsglied abgegebenen Binärfolge vorgenommen wird.

3. Fehlerkorrigierendes Datenübertragungssystem nach Anspruch 1 und 2 zum Erkennen von zwei fehlerhaften Binärstellen innerhalb einer Binärfolge, wenn die Vergleichseinrichtung keine Identität zwischen dem Korrekturvektor und einem Binärvektor des Schaltwerkes feststellt, dadurch gekennzeichnet, daß auf der Empfangsseite ein weiteres Register (34) vorgesehen ist, dessen Eingänge mit dem Schaltwerk (6) und dessen Ausgänge mit dem ersten Register (33) verbunden sind, daß dort die zu einer Binärfolge (Datenblock und Prüfvektor) gehörenden Binärvektoren des Schaltwerkes über Exklusiv-Oder-Tore (7 bis 10) nach-

. --■;■■:. 709 548/163

einander auf den im ersten Register (33) stehenden Korrekturvektor modulo 2 aufaddiert und gleichzeitig in das weitere Register (34) eingespeichert werden und nach jeder Addition der Inhalt des ersten Registers (33) über die Vergleichseinrichtung (20) mit allen durch das Schaltwerk (6) bereitstellbaren Binärvektoren auf Identität verglichen wird, daß bei Nichtidentität während eines Schaltwerkszyklus der zuvor in das erste Register (33) addierte Binärvektor nochmals in das erste Register (33) addiert und erst dann der nächste Binärvektor in dasselbe addiert wird, daß bei Identität der Inhalt des weiteren Registers (34) in das erste Register (33) übernommen wird und das Schaltwerk (6) so lange weiterläuft, bis die Vergleichseinrichtung (20) eine zweite Identität feststellt, wobei synchron mit den Schaltwerkzyklen die Binärfolge (Datenblock und Prüfvektor) so oft durch das Verzögerungsglied (18) gesandt wird, bis beide Fehler durch je eine Identität festgestellt und korrigiert sind.

4. Fehlerkorrigierendes Datenübertragungssystem nach Anspruch 3, dadurch gekennzeichnet, daß an das erste Register (33) an sich bekannte Mittel zur Feststellung des Inhaltes NULL angeschlossen sind, die die Ausgabe der Datengruppe aus dem Verzögerungsglied (18) veranlassen.

5. Fehlerkorrigierendes Datenübertragungssystem nach einem der Ansprüche 1 bis 4, dadurch gekennzeichnet, daß die Schaltwerke (6) durch ihre Schaltlogik so redundant ausgelegt sind, daß ein Fehler beim Weiterschalten derselben einen nächsten Schaltwerksinhalt verursacht, der sich von dem ungestörten Schaltwerksinhalt nur in einer Binärstelle unterscheidet, während der darauffolgende Schaltwerkszustand (Binärvektor) fehlerfrei ist.

In Betracht gezogene Druckschriften:
Annales Universitatis Saraviensis — Scientia,
Vol. IX, Fase. 1/2, 1960/61, S. 3 bis 12;
Scientific American, Februar 1962, S. 96 bis 108.

Hierzu 1 Blatt Zeichnungen

709 448/163 3.67 © Bundesdruckerei Berlin