DE1249909B - Verfahren und Schaltungsanordnung zur Fehlerkorrektur von übertragenen Datenwortern nach der Art der Ahnlichkeitsdecodierung mit einem Kodewortervorrat - Google Patents

Description

BUNDESREPUBLIK DEUTSCHLAND

DEUTSCHES ÄlS||^ PATENTAMT

AUSLEGESCHRIFT

Int. Cl.:

H04b

H041
Deutsche Kl.: 21 al - 7/06

Nummer: 1249 909

Aktenzeichen: T 30332 VIII a/21 al

Anmeldetag: 27. Januar 1966

Auslegetag: 14. September 1967

Die Erfindung betrifft ein Verfahren zur Fehlerkorrektur von übertragenen Datenwörtern nach der Art der Ähnlichkeitsdekodierung, bei dem einem durch Übertragungsstörungen veränderten Kodewort jenes Kodewort zugeordnet ist, das sich von diesem am wenigsten unterscheidet.

Um eine übertragene Information auf Fehler untersuchen zu können, muß diese redundant sein. In dem Maße, in dem die Anforderungen an die Erkennbarkeit von Fehlern oder an die Rekonstruktion zerstörter Informationen gestellt werden, wächst auch die der Information mitzugebende Redundanz. Bei der Fehlerkorrektur durch Rekonstruktion wird jedem Kodewort eine gewisse Umgebung von sinnlosen Wörtern zugeordnet,' die bei Empfang auf dieses Kodewort zurückzuführen sind. Sie bilden den Korrekturbereich des Kodewortes. Außerdem können noch sinnlose Wörter übrigbleiben, die keinem Korrekturbereich zugewiesen sind und als Fehler angezeigt werden.

Eine Art der Rekonstruktion gestörter Information besteht darin, für ein empfangenes sinnloses Wort jenes Kodewort anzunehmen, daß sich von dem empfangenen Wort am wenigsten unterscheidet. Diese Art der Dekodierung wird Ähnlichkeitsdekodierung genannt und ist z. B. erwähnt in der USA.-Patentschrift 3 164 804. Bisher mögliche Anordnungen zur Durchführung dieses Ubertragungsverfahrens erfordern einen sehr großen Schaltungsaufwand, denn es ist hierzu erforderlich, das jeweils empfangene Wort mit allen zulässigen Kodewörtern des Kodes zu vergleichen. Weiter muß mit einem Maximaldetektor jenes Kodewort festgestellt werden, das dem empfangenen Wort am ähnlichsten ist. Besteht ein empfangenes Wort aus mBits, so sind 2^m Vergleichsstufert notwendig, um den eigentlichen Vergleich durchzuführen, und des weiteren der bereits erwähnte Maximaldetektor. Eine Realisierungsmöglichkeit der 2^m Vergleichsstufen einschließlich Maximaldetektor besteht in dem Einsatz einer Lernmatrix, wie sie zu Problemen der Schrift- oder Spracherkennung eingesetzt wird. Eine derartige Lernmatrix ist z. B. beschrieben in der Zeitschrift Kybernetik 1, 1961, Heft 1, S. 36 bis 45. Aber auch diesem Vorgehen sind vorläufig vielfach Grenzen gesetzt, wenn es darum geht, Wörter mit einer Vielzahl von Bits, z. B. mehr als zehn, zu vergleichen und zu detektieren.

Auf der anderen Seite sind viele Korrekturverfahren bekannt, bei denen sendeseitig zu jeder Informationseinheit, z. B. jedem Wort, eine Korrekturinformation (Redundanz) errechnet wird, mittels welcher nach einer Informationsstörung ein wahrscheinlich-Verfahren und Schaltungsanordnung
zur Fehlerkorrektur von übertragenen
Datenwörtern nach der Art der
Ähnlichkeitsdekodierung mit einem
Kodewörtervorrat

Anmelder:

Telef unken

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

Als Erfinder benannt:

Dipl.-Ing. Dr. Horst Ohnsorge, Ulm/Donau;

Peter Drescher, Konstanz

ster Fehler festgestellt werden kann. Derartige Verfahren benötigen weniger Schaltungsaufwand, sie liefern aber auch eine wesentlich kleinere Reduktion der Fehlerwahrscheinlichkeit als das Verfahren der Ähnlichkeitsdekodierung. Verfahren und Anordnungen zum Errechnen einer Korrekturinformation sind z.B. beschrieben in dem Buch von W.W. Peterson, »Efror-Correcting-Codes«, 1961.

Es ist nun das Ziel der Erfindung, ein Verfahren zu finden, mit welchem eine Ähnlichkeitsdekodierung ohne hohen Aufwand durchführbar ist.

Die Erfindung betrifft ein Verfahren zur Fehlerkorrektur von übertragenen Datenwörtern nach Art der Ähnlichkeitsdekodierung mit einem Kodewörtervorrat, von dem nur ein Teil der Kodewörter durch Zeichenzuordnung definiert ist und bei dem empfangsseitig einem empfangenen Kodewort dasjenige definierte Kodewort zugeordnet wird, das sich von ihm am wenigsten unterscheidet, dadurch gekennzeichnet, daß zwischen jedem empfangenen Wort und jedem der definierten Kodewörter des Kodes durch Vergleich der jeweilige Hammingabstand festgestellt und dasjenige definierte Kodewort ausgewählt

wird, für das der festgestellte Hammingabstand kleifür ungeradzahli-

ner oder gleich dem Wert ——

für geradzahliges d ist, wobei die

, , d—2

ges d bzw. r—

den Zeichen zugeordneten definierten Kodewörter einen Mindesthammingabstand d zueinander haben, der größer als 2 ist.

709 647/364

Die Erfindung nutzt die Eigenschaften der sogenannten dichtgepackten Kodes aus. Die erlaubten Kodewörter innerhalb eines solchen Kodes haben einen Mindesthammingabstand, der wohl überschritten, nicht aber unterschritten werden darf. Somit ist der Korrekturbereich, also die Umgebung sinnloser Wörter, eines Kodewortes eindeutig durch den Hammingabstand beschreibbar. Auf diese Weise ist die Möglichkeit gegeben, an Hand des Hammingabstandes zwischen einem Kodewort und einem diesem gegenübergestellten Wort festzustellen, ob es sich bei dem letzteren um ein sinnloses Wort aus dem Korrekturbereich des Kodewortes oder um ein anderes Kodewort handelt. Im letzteren Fall sind dann dem Wort andere Kodewörter nacheinander gegenüberzustellen, bis eine eindeutige positive Entscheidung möglich ist. Bei dichtgepackten Kodes wird diese eindeutige Entscheidung in jedem Fall gefällt werden, da zwischen den Korrekturbereichen der einzelnen Kodewörter keine weiteren sinnlosen Wörter liegen können. Dies ist aber der Fall bei gewissen Kodes, die den dichtgepackten Kodes ähnlich sind. Hier könnte eine Gegenüberstellung eines Wortes mit allen Kodewörtern dieses Kodes keine Entscheidung bringen, und eine Datenwiederholung müßte veranlaßt werden. Bei beiden hier genannten Kodearten liegt die Grenze des Korrekturbereiches um jedes Kodewort bei

d- 1

der von den Antivalenzschaltungen 4 abgegebenen Einsen, wird in einem als Komparator mit einer Schwellwertstufe ausgebildeten Detektor 6 festgestellt. Liegt bei einem Vergleich die Zahl der unterschiedlichen Stellen zwischen beiden Wörtern unter der

d— 1

für, Kodewörter ungeradzahligen

Mindesthammingabstandes und für solche geradzahligen Mindesthammingabstandes bei —=—· ^ '^st die

Mindesthammingdistanz des verwendeten Kodes.

Jedes empfangene Kodewort wird nacheinander bei gleichzeitiger Feststellung des jeweiligen Hammingabstandes den Kodewörtern des Kodes gegenübergestellt, so lange, bis ein Kodewort gefunden wird, in dessen Korrekturbereich das gegenübergestellte Wort liegt. Zu diesem Vergleich wird ein Kodewortgenerator herangezogen, der nacheinander alle erlaubten Kodewörter des Kodes generiert.

Ein Ausführungsbeispiel hierzu zeigt die Fig. 1. F i g. 2 zeigt ein mögliches Zustandsdiagramm für den Kodegenerator der Fig. 1.

In Fig. 1 stellt 1 einen Sender dar, der nacheinander Kodewörter über eine Übertragungsleitung 2 an einen Empfänger aussendet, der durch alle restlichen Teile der F i g. 1 charakterisiert ist. Die Leitung 2 hat Störeigenschaften, so daß ein vom Sender 1 ausgesandtes Kodewort den Empfänger auch als sinnloses Wort erreichen kann. Aus der Unsicherheit, ob ein empfangenes Wort ein sinnloses Wort oder ein Kodewort ist, wird beim Empfänger nur von empfangenen Wörtern gesprochen. Ein empfangenes Wort läuft in das Schieberegister 3 ein. Alle Stufen dieses Schieberegisters sind über Antivalenzschaltungen 4 mit Stufen eines rückgekoppelten Schieberegisters 5 verbunden. Dieses Schieberegister 5 dient als Kodewortgenerator; in ihm werden nach dem Empfang eines Wortes alle zugelassenen Kodewörter des Kodes erzeugt. Jeweils nach der Erzeugung eines Kodewortes werden die Antivalenzschaltungen abgefragt. Bei diesem Abfragen gibt jede Antivalenzstufe eine Null ab, wenn der Inhalt ihrer angeschlossenen Stufen übereinstimmt, oder eine Eins, wenn der Inhalt nicht übereinstimmt. Die Zahl der Nichtübereinstimmungen zwischen dem jeweiligen Kodewort im Kodewortgenerator und dem Schieberegister 3, also die Zahl Schwelle, die der Korrekturgrenze

bzw.

des jeweils verwendeten Kodes proportional ist, so wird das im Kodewortgenerator 5 stehende Kodewort über einen Schalter 7 an eine Datensenke 8 abgegeben, denn sobald ein Wort innerhalb eines Korrekturbereiches angetroffen wird, kann es in keinem anderen Korrekturbereich mehr liegen.

Der Empfänger wird gesteuert von einer Empfängersteuerung 9. Diese leitet aus dem Takt der empfangenen Wörter einen Eigentakt zur Einspeicherung der Wörter in das Schieberegister 3, zur Weiterschaltung des Kodewortgenerators 5 und zur Ausspeicherung eines Kodeworts aus dem Kodegenerator 5 in die Senke ab. Dazu sind alle Takt- und Steuerleitungen gestrichelt dargestellt. Auch der Detektor 6 gibt seinen Schwellwertimpuls an die Empfängersteuerung 9 ab, worauf diese für die Zeit der Ausspeicherung des Kodewortes aus dem Kodewortgenerator 5 den Schalter 7 schließt und entsprechende Einspeichertakte an die Datensenke 8 abgibt. Für den Vorgang des Ausspeicherns eines Kodewortes aus dem Kodewortgenerator 5 muß dieser als Schieberegister geschaltet werden. Zu diesem Zweck sind die Rückkopplungsstellen des Registers aufzutrennen, was ebenfalls von der Empfängersteuerung 9 vorgenommen wird, in der F i g. 1 jedoch aus Gründen der Übersichtlichkeit nicht gezeichnet ist.

Aufbau und Wirkungsweise von Kodewortgeneratoren sind ausführlich in dem bereits genannten Buch von W. W. Peterson beschrieben. Als Detektor 6 läßt sich in vorteilhafter Weise ein Rechteckferritkernkomparator verwenden. Dieser weist dann ebenso viele Rücksetzwindungen auf, wie Antivalenzschaltungen vorhanden sind, und eine von der Empfängersteuerung 9 angesteuerte Rücksetzwicklung, mit der zugleich die magnetische Vorspannung zur Schwellwerteinstellung vorgenommen wird. An Stelle der Antivalenzschaltungen 4 können auch Äquivalenzschaltungen verwendet werden. Dies ist dann bei der Ausführung des Detektors zu berücksichtigen.

Ist der zur Informationsdarstellung verwendete Kode jedoch kein dichtgepackter, sondern ein diesem lediglich ähnlicher, d. h., er weist zwischen den Korrekturbereichen einzelner Kodewörter weitere sinnlose Wörter auf, so ist die Empfängersteuerung 9 so einzurichten, daß nach ergebnisloser Gegenüberstellung eines empfangenen Wortes mit allen Kodewörtern ein Signal abgegeben wird, das entweder zur Veranlassung einer Datenwiederholung oder zu weiteren Schalt- bzw. Anmerkungskriterien ausgenutzt wird.

Bisher wurde nichts über die Struktur eines übertragenen Wortes ausgesagt. Ein Wort kann z. B. aus einer Mehrzahl von Zeichen bestehen, deren jedes einen Buchstaben oder eine Ziffer darstellt, oder es kann mit einem Zeichen identisch sein. Für die folgenden Betrachtungen wird die Identität zwischen einem Zeichen und einem Wort angenommen. Da die Vergleichszeit für jedes empfangene Wort entscheidend für die Übertragungsgeschwindigkeit des Gesamtsystems ist, muß darauf geachtet werden, diese möglichst kurz zu halten. Ein erster Weg zum Errei-

chen dieses Zieles besteht darin, die Kodewörter in zwei Gruppen einzuteilen. Die Einteilung kann nun nach'dem Kriterium der mittleren Übertragungshäufigkeit einer Zeichengruppe oder nach der Zeichenart erfolgen. Durchläuft das Schaltwerk nach seinem Start von der Anfangsstellung ausgehend zuerst die wichtigere Gruppe und dann die ihr untergeordnete Gruppe, so wird die mittlere Vergleichszeit unter der Bedingung, daß der Kodewortgenerator unmittelbar nach einem erfolgreichen Vergleich in seinen Anfangszustand zurückgeschaltet wird, kürzer werden.

Sehr wirksam kann nach diesem Verfahren gearbeitet werden, wenn, wie etwa beim Fernschreibalphabet, Buchstaben- und Ziffernumschaltzeichen eingeführt werden, jedoch unter Beibehaltung eigener Kodewörter für Buchstaben und Ziffern. Dafür zeigt die Fig. 2 ein erfindungsgemäßes Ablauf diagramm für den Kodewortgenerator 5. Jeder der kleinen Kreise in diesem Diagramm stellt einen Schaltzustand des Kodewortgenerators 5 dar. Dieser durchläuft von einem Zustand Null ausgehend eine Vielzahl solcher Zustände, bis er wieder den Anfangszustand Null einnimmt. Ausgehend von der Anfangsschaltstellung Null erzeugt der Kodewortgenerator 5 zuerst das Kodewort für die Ziffernumschaltung, danach dasjenige für die Buchstabenumschaltung und in den folgenden Schaltzuständen Buchstabenkodewörter. Zwischen den Buchstabenkodewörtern und der Anfangsstellung Null liegen die Ziffernkodewörter. Der Kodewortgenerator durchläuft jeweils nur die durch ein vorhergehendes Umschaltzeichen angekündigte Wortgruppe. Außerdem kann er aus jedem Schaltzustand, also von jedem Kreis her, nach erfolgreichem Vergleich in den Anfangszustand zurückkehren, was durch Einwirkung der Empfängersteuerung 9 erreicht wird. Weiter möge die Empfängersteuerung 9 in Verbindung mit einer Erkennungsschaltung in der Lage sein, über den Kodewortgenerator 5 empfangene Ziffernumschaltzeichen und Buchstabenumschaltzeichen zu erkennen. In Abhängigkeit davon werden in F i g. 2 zwei Weichen B und Z gesteuert, derart, daß die Weiche B durchlässig und die Weiche Z gesperrt ist, wenn das letzte empfangene und erkannte Umschaltzeichen ein Buchstabenumschaltzeichen war. In diesem Fall durchläuft der Kodewortgenerator von seiner Ausgangslage Null herkommend die Schaltzustände Zi und Bu und danach die Buchstabenkodewörter. Von dem Kodewort, bei dem der Detektor 6 anspricht, kehrt er in die Ausgangsstellung zurück. Natürlich ist es auch möglich, erst nach dem Durchlaufen der gesamten Gruppe dorthin zurückzukehren. War hingegen das jeweils zuletzt empfangene Umschaltzeichen ein Ziffernumschaltzeichen, so ist die Weiche B gesperrt und die Weiche Z geöffnet. Wird nun ein Wort empfangen, so läuft der Kodewortgenerator über die Stellungen Zi und Bu unter Umgehung aller Buchstabenkodewörter unmittelbar zum ersten Ziffernkodewort, von dem aus er die Ziffernkodewörter durchläuft. Rechnet man nun mit 26 Buchstaben und ungefähr 30 Ziffern einschließlich Sonderzeichen im gesamten Koderaum, so hat der Kodewortgenerator im Höchstfall nur die Hälfte seiner insgesamt möglichen Schaltzustände zu durchlaufen, so daß durch diese Maßnahme ein erheblicher Zeitgewinn beim notwendigen Vergleich der empfangenen Wörter mit jeweils allen Kodewörtern des Kodes zu erzielen ist.

Außerdem wird auf diese Weise eine weitere Reduktion der Übertragungsfehlerwahrscheinlichkeit vorgenommen. Denn wird z. B. innerhalb einer Ziffernsendung, der ein Ziffernumschaltzeichen vorausgegangen ist, eine Ziffer während der Übertragung durch starke Störungen in ein Buchstabenkodewort umgewandelt, so kann der empfangsseitig erfolgende Vergleich nicht zum Erfolg führen, da jeweils nur mit allen Ziffernkodewörtern und nicht mit Buchstabenkodewörtern verglichen wird. Entsprechendes gilt bei der Übertragung von Buchstaben, da ja in diesem Fall der Kodewortgenerator nur die Buchstabenkodewörter, nicht aber die Ziffernkodewörter durchläuft.

Das in Verbindung mit der F i g. 2 aufgezeigte Verfahren wird zweckmäßigerweise bei solchen Übertragungsstrecken angewendet werden, auf denen vorzugsweise größere Folgen von Ziffern und Buchstaben und weniger gemischte Information übertragen wird. Im letzteren Fall würde aber der Vorteil der weiteren Reduktion der Übertragungsfehlerwahrscheinlichkeit den dann auftretenden Nachteil der zu häufig zu übertragenden Buchstaben- bzw. Ziffernumschaltzeichen überwiegen.

Eine Zeitersparnis für die Durchführung des Vergleichs kann natürlich auch dadurch erreicht werden, daß man alle Kodewörter in mehrere Teilmengen zerlegt und auf der Empfangsseite für jede Teilmenge einen Dekodierer nach F i g. 1 vorsieht. Ein empfangenes Wort wird dann zeitlich parallel mit den Kodewörtern der Teilmengen verglichen.

Sind alle Kodewörter gleichwahrscheinlich und z. B. zwei Dekodierer vorgesehen, dann wird der Empfänger nach Fig. 1 im Mittel nur halb soviel Vergleiche durchführen müssen, wie insgesamt Kodewörter vorhanden sind. Das Verfahren bringt also gegenüber den bekannten Verfahren grundsätzlich eine Einsparung von wenigstens der halben Normalvergleichszeit.

Claims (9)

Patentansprüche:

1. Verfahren zur Fehlerkorrektur von übertragenen Datenwörtern nach der Art der Ähnlichkeitsdekodierung mit einem Kodewörtervorrat, von dem nur ein Teil der Kodewörter durch Zeichenzuordnung definiert ist und bei dem empfangsseitig einem empfangenen Kodewort dasjenige definierte Kodewort zugeordnet wird, das sich von ihm am wenigsten unterscheidet, dadurch gekennzeichnet, daß zwischen jedem empfangenen Wort und jedem der definierten Kodewörter des Kodes durch Vergleich der jeweilige Hammingabstand festgestellt und dasjenige definierte Kodewort ausgewählt wird, für das der festgestellte Hammingabstand kleiner

oder gleich dem Wert —χ— für ungeradzahli-

ges d bzw.

rf-2

für geradzahliges d ist, wobei

die den Zeichen zugeordneten definierten Kodewörter einen Mindesthammingabstand d zueinander haben, der größer als 2 ist.

2. Verfahren nach Anspruch 1, dadurch gekennzeichnet, daß der Vergleich nach der Auswahl eines definierten Kodewortes beendet wird und daß dann ein Signal abgegeben wird, wenn der Vergleich des jeweils empfangenen Wortes mit allen definierten Kodewörtern keinen Ham-

mingabstand ergeben hat, der kleiner oder gleich

u d-2

bzw. —

ist.

2 """' 2

3. Verfahren nach den Ansprüchen 1 und 2, dadurch gekennzeichnet, daß die definierten Kodewörter in zwei Gruppen eingeteilt werden, derart, daß die Kodewörter der einen Gruppe eine höhere Übertragungshäufigkeit als diejenigen der anderen Gruppe haben, und daß zuerst die Kodewörter der Gruppe mit der höheren mittleren Übertragungshäufigkeit erzeugt werden.

4. Verfahren nach den Ansprüchen 1 bis 3, dadurch gekennzeichnet, daß die definierten Kodewörter in eine Buchstaben- und eine Ziffern-Sonderzeichengruppe eingeteilt werden, daß FoI-gen von Wörtern beider Gruppen durch Gruppenumschaltzeichen vom Sender angekündigt werden und daß bei jedem Vergleich nur die Kodewörter der angekündigten Gruppe ganz oder teilweise durchlaufen werden. ao

5. Verfahren nach Anspruch 4, dadurch gekennzeichnet, daß Gruppenumsehaltzeichen erzeugt und nach Erkennen eines Gruppenumschaltzeichens für die nachfolgenden empfangenen Kodewörter bis zum nächsten Gruppenumschaltzeichen nur die Kodewörter der angekündigten Gruppe erzeugt werden.

6. Verfahren nach den Ansprüchen 1 bis 4, dadurch gekennzeichnet, daß die definierten Kodewörter in Gruppen eingeteilt werden und daß für die Kodewörter jeder Gruppe getrennt der jeweilige Hammingabstand festgestellt wird.

7. Schaltungsanordnung zur Durchführung des Verfahrens nach den Ansprüchen 1 bis 6, gekennzeichnet durch ein Register (3) zur Aufnahme des jeweils empfangenen Kodewortes, durch einen Kodewortgenerator (5), der auf ein äußeres Signal hin alle definierten Kodewörter des Kodes erzeugt, durch eine Vergleichsstufe (4) zum Vergleich des jeweiligen Registerinhalts und Kodewortgeneratorinhalts und durch einen Detektor (6) zum Feststellen der Anzahl der übereinstimmenden bzw. nicht übereinstimmenden Bits.

8. Schaltungsanordnung nach Anspruch 7, dadurch gekennzeichnet, daß die Vergleichsstufe (4) aus einer Mehrzahl von Antivalenzgliedern besteht und der Detektor als Komparator mit einer Schwellwertstufe ausgebildet ist und daß der Detektor dann ein Signal abgibt, wenn seine Eingangsgröße den Schwellwert unterschreitet.

9. Schaltungsanordnung nach Anspruch 7, dadurch gekennzeichnet, daß der Kodewortgenerator (5) als rückgekoppeltes Schieberegister mit mod-2-Additionsstellen ausgebildet ist.

Hierzu 1 Blatt Zeichnungen

709 647/384 9.67 © Bundesdruckerei Berlin