-
Verfahren zur Datenübertragung Die Erfindung betrifft ein Verfahren
zur Datenübertragung, in dem sendeseitig für jeweils einen Datenblock nach einem
vereinbarten Kode eine Prüfzeichengruppe gebildet wird, die auf der Empfangsseite
zur Erkennung und gegebenenfalls Korrektur von Ubertragungsfehlern ausgewertet wird.
-
Solche Systeme sind sowohl theoretisch durchleuchtet wie praktisch
angewendet worden. Eine Zusammenfassung vieler bekannter Systeme ist in dem Buch
von W. W. P e t e r s o n, »Error Correcting Codes«, 1961, zu finden. Die Sicherheit
im Erkennen von Fehlern hängt im allgemeinen von der Redundanz ab, d. h. von dem
Verhältnis der Größe der Prüfzeichengruppe zur Größe des Datenblocks. Je größer
die Redundanz gewählt wird, um so besser ist zwar die Fehlersicherheit, um so geringer
wird aber auch die nutzbare Ubertragungskapazität des Kanals. Außerdem steigt der
Aufwand für die Prüfzeichenbildung dabei gewaltig an. Dieser Aufwand hängt weiterhin
davon ab, wie groß die Prüfzeichengruppe absolut ist, d. h., bei gegebener Redundanz,
wie groß ein Datenblock gewählt wird. An sich erscheint es vorteilhaft, Datenblöcke
möglichst groß zu wählen, da man so systematische, in gewissen Abständen immer wiederkehrende
Fehler am besten erkennt. Aus Aufwandgründen muß man aber sowohl die Redundanz als
auch die Größe der Datenblöcke so weit beschränken, daß nur noch bestimmte Fehler,
z. B. Einzelfehler, sicher erkannt werden. Treten in diesem Fall z. B. Doppelfehler
auf, dann lassen sie sich entweder gar nicht entdecken oder aber nur, wenn sie sich
in einer bestimmten Stellung im Datenblock befinden. Solche bevorzugte Stellungen
sind kodeabhängig. Doppelfehler, die anderswo auftreten, bleiben also unentdeckt.
Durch die Erfindung wird eine Verbesserung insoweit erzielt, als ohne wesentliche
Aufwandsvergrößerung systematisch immer in derselben Stellung im Datenblock auftretende
Fehler in vielen Fällen entdeckt werden können, auch wenn es Fehler sind, die an
sich von dem verwendeten Kode nur in bestimmten Stellungen erkannt werden.
-
Die Erfindung besteht darin, daß für aufeinanderfolgende Blöcke unterschiedliche
Kodes verwendet werden.
-
Im folgenden wird die Erfindung zuerst an einem Zahlenbeispiel und
anschließend an Hand eines Ausführungsbeispiels, das in der Figur dargestellt ist,
im einzelnen erläutert.
-
Ein einfacher Kode soll auf Blöcke von je fünf Informationsbits derart
angewandt werden, daß drei Prüfbits als Prüfzeichengruppe entstehen. Der Kode ist
durch eine Matrix gemäß Tabelle 1 gegeben. Entsprechend der geringen Redundanz
sind mehrere Spalten dieser Matrix einander gleich, beispielsweise die erste und
die fünfte. Ordnet man jedem Informationsbit eine Spalte dieser Matrix zu (also
z. B. dem ersten Bit die erste Spalte usw.) und addiert vektoriell die Spalten,
deren zugeordnetes Informationsbit eine Eins zeigt, so erhält man einen dreidimensionalen
Prüfvektor, der als Prüfzeichengruppe dient. Man erkennt aus der Matrix, daß ein
Einzelfehler des ersten Informationsbits zum selben Prüfvektor führt wie ein Einzelfehler
des fünften Informationsbits, so daß ein solcher Fehler nicht eindeutig lokalisiert
werden kann. Weiterhin erkennt man, daß z. B. ein Dreifachfehler in den ersten drei
Informationsbits zu überhaupt keiner Fehlermeldung führt.
-
Da auftretende Fehler nicht immer statistisch verteilt sind, sondern
vielfach ihre Ursache in einer Fehlkalkulation der Anlage besitzen, die beliebig
oft reproduzierbar ist, kann ein systematisch immer an der ersten Stelle auftretender
Fehler mit der vorliegenden Matrix zwar entdeckt, aber nicht lokalisiert werden,
dagegen kann man solche Fehler gemäß der Erfindung manchmal erkennen, wenn man für
aufeinanderfolgende Informationsblöcke verschiedene Kodes benutzt, wobei der zweite
Kode so gewählt ist, daß man gerade in den Stellen Fehler erkennen kann, für die
sich im ersten Kode eine Zweideutigkeit ergibt. Auf diese Weise wird zwar nicht
vermieden, daß ein Fehler in der ersten Stelle manchmal unkorrigierbar bleibt, aber
es wird sichergestellt, daß er nicht immer unentdeckt bleibt.
Die
Tabelle 2 zeigt einen solchen zweiten Kode, bei den sich nun nicht die erste und
die fünfte Spalte, sondern die zweite und die vierte Spalte gleichen.
| Tabelle 1 |
| 1 1 0 0 1 |
| 0 1 10 0 |
| 1 0 1 1 1 |
| Tabelle 2 |
| 1 1 0 1 0 |
| 0 1 1 1 0 |
| 1 0 0 0 1 |
Durch Anwendung dieses Kodes auf den nächstfolgenden Block würde ein Einzelfehler
des ersten Informationsbits also sicher lokalisiert sowie der erwähnte Dreifachfehler
sicher erkannt. Treten solche Fehler mehrfach nur bei Anwendung des zweiten Kodes
auf, dann ist die Wahrscheinlichkeit groß, daß auch in den dazwischenliegenden Blöcken,
in denen dieser Fehler nicht erkennbar ist, ein Fehler vorlag. Eine hier nicht näher
erläuterte Fehleranalysierschaltung könnte dies feststellen und anschließend beispielsweise
den zueilt mit dem ersten Kode behandelten Block nochmals übertragen, diesmal unter
Anwendung des anderen Kodes.
-
Die Realisierung verschiedener Kodes kann durch Umschaltung der den
Kode bestimmenden Matrix (z. B. eines Zählers) oder durch Vergrößerung der Spaltenzahl
der Matrix erfolgen. Ein Kodezähler, der normalerweise hei jedem Block seinen Zählzyklus
einmal durchläuft, -soll gemäß der Erfindung also einen längeren oder kürzeren Zyklus
besitzen, so daß Blockanfang und Zyklusanfang nicht immer zusammenfallen. Bei Verwendung
sogenannter zyklischer Kodes (vgl. z. B: das erwähnte Buch von W. W. P e t e r s
o n) ist ein Wechsel der Kodematrix besonders einfach durch Wechsel der Rückkopplungsstellen
innerhalb des rückgekoppelten Schieberegisters zu erreichen.
-
Im folgenden Ausführungsbeispiel gemäß der Figur ist ein vollständiges
Datenübertragungssystem gezeigt mit einem Datengeber 1, einer Kodiereinrichtung
2 zur Gewinnung da Prüfzeichengruppe, einer Ubertragungsstrrecke mit Modulator 3
und Demodulator 4, einer Dekodiereinrichtung 5 zur Gewinnung von Korrekturzeichen
und einer Korrigiereinrichtung, bestehend aus einem Pufferspeicher 6 und einem Zuordner
7, der aus den Korrekturzeichen den Fehlerort des im Pufferspeicher stehenden Datenblocks
ermittelt und den Fehler korrigiert.
-
Das Kernstück der Kodiereinrichtung 2 ist ein Kodezähler 8, der nacheinander
alle Spalten einer dreizeiligen Matrix an seinen drei Ausgängen liefert. Der Zähler
besitzt einen achtzehntaktigen Zählzyklus gemäß den Spalten der nachfolgenden Tabelle
3.
| . Tabelle 3 |
| 1 1 0 0 1 1 1 0 0 1 1 0 1 0 1 1 0 0 |
| 0 1 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 |
| 1 0 1 1 1 0 1 0 0 1 0 0 0 1 1 0 1 0 |
Weiterhin ist in der Figur ein Stellenzähler 9 angedeutet, der nagt jedem Block
von neuem zu zählen beginnt. Der Datengeber
1 liefert synchron mit den Taktimpulsen
eines Taktgeherators 10 je Block fünf binäre Informationselemente sowohl an den
Modulator 3 als auch an die Kodiereinrichtung 2. Zwischen zwei Blöcken liegen vier
Takte Pause, die zur Übertragung der Prüfzeichen und zur Fehlerkorrektur benötigt
werden, wie sich später zeigen wird.
-
Der Stellenzähler beginnt also nach jeweils neun Takten von neuem
zu zählen; er wird zur Ablaufsteuerung eingesetzt, indem er erst diejenigen Leitungen
durchschaltet, über die die Prüfzeichen gebildet werden (Takte 1 bis 5) und anschließend
(Takte 6 bis 8) die Übergabe der Prüfzeichengruppe an den Modulator veranlaßt. Die
Prüfzeichengruppe wird durch vektorielle Addition modulo 2 aus den jeweiligen Spalten
der Tabelle 3 gebildet, deren zugeordnetes Informationsbit eine Eins zeigt (Addiernetz
11). Zwischenergebnisse und die endgültige Prüfzeichengruppe werden in einem
dreistelligen Register 12 abgesetzt. Der Inhalt dieses Registers wird während der
Takte 6 bis 8 an den Modulator 3 in Serie abgegeben.
-
Wie schon erwähnt, besitzt der Kodezähler einen achtzehntaktigen Zählzyklus,
was bedeutet, daß während der Behandlung eines Blocks die ersten neun Zählzustände,
während der Behandlung des nächsten Blocks aber die zweiten neuen Zustände durchlaufen
werden. Für den Kodiervorgang werden nur die ersten fünf und die Zustände 10 bis
14 ausgewertet, so daß die übrigen Spalten der Tabelle 3 beliebig ausgebildet sein
können.
-
Für den Dekodiervorgang aber benötigt man zweimal acht Spalten, da
hier der ankommende Datenblock acht Bits umfaßt. Der Pufferspeicher 6 nimmt diese
acht Bits kurzzeitig auf, während gleichzeitig in der Dekodiereinrichtung 5 eine
Korrekturzeichengruppe auf dieselbe Weise wie die Prüfzeichengruppe gebildet wird.
Diese Einrichtung enthält also ebenfalls einen Kodezähler 8, einen Blockstellenzähler
9, ein Addiernetz 11 und ein Register 12. Während der Blockübertragung,
die acht Takte dauert, wird die Korrekturzeichengruppe im Register 12 gebildet.
In der neunten Taktzeit wertet schließlich der Fehlerzuordner 7 den Registerinhalt
zur Korrektur des Datenblocks aus. Gleichzeitig wird das Register 12 gelöscht und
damit für den neuen Block vorbereitet. Der Taktgenerator 10 ist durch an sich bekannte
und hier nicht näher zu beschreibende Mittel mit dem Taktgenerator der Kodiereinrichtung
derart synchronisiert, daß bei Vorliegen des gleichen Datenbits jeweils gleiche
Zählerstände auf der Kodier- und auf der Dekodierseite vorherrschen.
-
Durch die Erfindung wird also eine Anpassung nicht vollkommener Kodes
an die praktischen Erfordernisse der Fehlererkennung erzielt, wodurch systematisch
Fehler auch dann erkannt und korrigiert werden können, wenn ihre Art und Stellung
innerhalb des Informationsblocks bei Anwendung nur eines Kodes an sich keine Korrektur
erlauben würde. Selbstverständlich ist die Erfindung nicht auf das erläuterte Zahlenbeispiel
beschränkt, vielmehr muß nochmals betont werden, daß in der Praxis die Redundanz
und die Zahl der Informationsbits in einem Block wesentlich größer ist.
-
Außerdem ist die Erfindung nicht insoweit auf das Ausführungsbeispiel
beschränkt, als die Zyklusseiten der beiden Zähler 8 und 9 im Verhältnis 2: 1 stehen.
Vielmehr ergibt sich der Vorteil der Erfindung auch bei anderen Verhältnissen, insbesondere
auch bei einem Verhältnis von n : (n ± 1).