DE2324538A1 - Digitale nachrichtenuebertragungsanordnung - Google Patents

Description

293-20.721P 15. 5. 1973

The Secretary of State for Defence in Her

Britannic Majesty's Government of the United

Kingdom of Great Britain and Northern Ireland

Whitehall, London (Großbritannien)

Digitale Nachrichtenübertragungsanordnung

Die vorliegende Erfindung bezieht sich auf eine digitale Nachrichtenübertragungsanbrdnung mit Fehlerkorrektureinrichtungen.

Es besteht ein steigender Bedarf an digitalen Übertragungseinrichtungen für alle Arten von. Nachrichtenverbindungen und ein Bedürfnis an einem hohen Grad von Zuverlässigkeit der übertragenen Nachrichten. Beschränkungen und Fehler der zur Verfügung stehenden Nachrichtenverbindungen sowie ungünstige Funkwellen-Ausbreitungsbedingungen bei irgendwelchen benutzten Funkverbindungen neigen jedoch dazu,

3098 81/1048

293-(JX3909/06)-¥-Hd-r (8)

die gesendeten Signale zu verzerren, so daß einige der Empfangssignale so stark gestört sind, daß sie im Empfänger falsch erkannt werden.

Um diese Schwierigkeiten zu überwinden, sind verschiedene Verfahren entwickelt worden. Die Signale haben gewöhnlich binäre Form. Eine Methode, die als Blockcodierung bekannt ist, besteht darin, die zu sendenden binären Informationssignale in Blöcke aufzuspalten, wobei jeder Block eine vorbestimmte Zahl k von Informationsstellen oder -ziffern(zeichen) umfaßte Von jedem Block aus k Informationsstellen wird gemäß einem gewählten Code eine größere Zahl von η Stellen abgeleitet, so daß folgende Matrizengleichung erfüllt ists

(1)

mit H = Matrix mit η - k = r Zeilen und η Spalten, die Kontrollmatrix des Codes genannt wird (tatsächlich stellt sie den Schlüssel des Codes dar); und

d = abgeleiteten Symbole oder Stellen,

die rechte Seite der Gleichung ist ein Vektor mit allen Elementen oder Komponenten gleich Null. Die bei der Bildung des Matrixproduktes vorkommenden Additionen werden nach den Regeln der Modulo-2-Arithmetik ausgeführt. Die η abgeleiteten Stellen werden zum geforderten Bestimmungsort übertragen, wo sie einer Kontroll- oder Prüfeinrich-

309801/1043

tung zugeleitet werden. Um die Möglichkeit anzuzeigen, daß eines oder mehrere der empfangenen Stellen bei der Übertragung gestört oder im Empfänger falsch erkannt wurden, werden die empfangenen'Stellen durch Symbole e., , e„, ... e dargestellt. Die Prüfeinrichtung benutzt diese, um mit einer Modulo-2-Addition wenigstens einige Elemente des Matrizenproduktes abzuleiten:

	e	η
H

(2)

. e_n = d_n, und

S des Korrektors sind Null.

Dieses Produkt heißt der Korrektor (Prüfvektor) oder das Syndrom dieses Blockes der empfangenen Stellen. Wenn keines der empfangenen Stellen gestört öder falsch erkannt wurde, ist natürlich e.. = d.. , e₂ = d₂, alle Elemente S , S„, .
Wenn jedoch eines oder mehrere der empfangenen Stellen gestört oder falsch erkannt wurde, enthält der Korrektor wahrscheinlich wenigstens ein Element ungleich Null. Wenn die Kontrollmatrix günstig gewählt wurde, können die gestörten Stellen aus der Kenntnis der Korrektorelemente erkannt und korrigiert werden. Nützliche Codes besitzen eine Fehlerkorrigierbarkeit, die durch eine ganze Zahl t ausgedrückt wird, d. h. wenn irgendeine Kombination von t, oder weniger als t, der Symbole e.,

e gestört

wurde, können die Positionen der gestörten Symbole eindeutig aus den Symbolen des Korrektors bestimmt werden. Eine weitere wichtige Eigenschaft irgendeines gegebenen Codes ist seine Senderate k/n, d. h. das Verhältnis der Zahl von Informationsstellen bezogen auf die Zahl von Stellensignalen, die gerade 0bytragen werden.

309881/1048

Zwei Typen von Blockcodes sind vergleichsweise ein-· fach; Ein-Fehler-korrigierende Hamming-Codes, die nur dann brauchbar sind, wenn eine vergleichsweise geringe Erhöhung der Zuverlässigkeit gefordert wird, und Wiederholungscodes mit nur einer in jedem Block (2t + i)-mal wiederholten Informationsstelle (d. h. η = 2t + 1 und k = 1). Die Wiederholungscodes sind brauchbar, wenn eine große Verbesserung der Zuverlässigkeit gefordert wird und eine niedrige Senderate annehmbar ist. Bei vielen praktischen Anwendungen jedoch wäre es vorteilhaft, einen Code mit mittlerer Senderate und mittlerer Fehlerkorrigierbarkeit zu verwenden. Obwohl einige solcher Codes gefunden wurden, ist ihre Herleitung außerordentlich verworren, und ihre Beschreibung und Definition ist schwierig. Zu diesem Thema sind Bücher verfaßt worden, z. B. "Algebraic Coding Theory" von E. Berlekamp, "Error-Correcting Codes" von W. W. Peterson und "Information Theory and Reliable Communications" von R. Gallager.. Natürlich ist es wünschenswert, einen Code auszuwählen, der die maximale Senderate zuläßt, die für irgendeine gewün„chte Fehlerkorrigierbarkeit t erreichbar ist. Ferner ist von großer praktischer Wichtigkeit, einen Code auszuwählen, der die Durchführung der Codierung, Decodierung und Fehlerkorrektur mit verhältnismäßig einfachen logischen Schaltungen gestattet, um damit sowohl die Fertigungs- als auch die Wartungskosten kleinstmöglich zu machen. Einige der mathematisch interessanten und in theoretischer Hinsicht wirksamen gefundenen Codes wurden nicht angewandt, da es unmöglich scheint, irgendwelche vernünftige wirtschaftliche Schaltungen zu entwerfen, die eine Anwendung der Codes gestatten. Von wissenschaftlicher Seite wurde viel Aufmerksamkeit langen zyklischen Codes (mit großem n)

309881/1048

zugewandt, mit denen eine Folge von iterativen logischen Operationen zur Prüfung jeder empfangenen Stelle und falls notwendig auch zur Korrektur, der Reihe nach angewandt werden kann; obwohl einige solcher Codes für den praktischen Einsatz entwickelt wurden, begrenzt die Notwendigkeit von nacheinander ablaufenden iterativen Operationen die Codier- und Decodiergeschwindigkeit.

Viele bekannte Codes sind von der Art der systematischen Blockcodes, die sich durch die Eigenschaft auszeichnen, daß sie die k Inf orrna tionss teilen enthalten, die unter die gerade übertragenen η Stellen gemischt werden, um irgendeinen gegebenen Block von Signalen darzustellen. Die Kontrollmatrix für einen systematischen Blockcode kann einen Satz von r verschiedenen einfachgewichteten Spalten haben, d. h. Spalten mit je (r-i) Nullen und nur einer einzelnen Eins, wobei sich die Eins in verschiedenen Zeilen und in verschiedenen Spalten des Satzes befindet. Es kann z. B. so eingerichtet werden, daß die ersten k Stellen in jedem übertragenen Block die Informationsstellen sind.

Wenn die Kontrollmatrix für irgendeinen Code gegeben ist, ist es möglich, andere scheinbar verschiedene Codes zu bilden, die alle dieselbe Senderate und dieselbe Fehlerkorrigierbarkeit besitzen. Dies geschieht durch verschiedene Modifikationen, im allgemeinen durch Änderung der Reihenfolge der Spalten, durch Änderung der Reihenfolge der Zeilen, durch Addition aller Elemente einer beliebigen Zeile zu den entsprechenden Elementen einer beliebigen anderen Zeile, oder durch laufende Anwendung einer beliebigen Zahl derartiger Modifikationen. Solche Modifika-

309881/104Ö

Neue Seiten 6, 7 und c

(anstelle der bisher cüitlgen Seiten 5, 7 und C)

tionen können einen Code günstiger oder weniger günstig für die praktische Verwendung machen. Derartige Codes sollen im folgenden äquivalente Codes genannt werden, Ein Code mit speziellen Werten von n, k und t heißt (n, k, t)-Code.

Aufgabe der Erfindung ist es, eine digitale Nachrich tenübertragungsanordnung zu erzeugen, die eine Blockcodie rung zum Zweck der Fehlerkorrektur verwendet, vielseitig ist, eine schnelle Arbeitsweise erlaubt und mit vergleichsweise einfachen logischen Schaltkreisen gebaut werden kann»

Eine digitale Nachrichtenübertragungsanordnung zur

Decodierung von Signalen gemäß einem systematischen (n,

. weist auf

k, t)-Biockcode xxiiaixsCxradHocxije^eaiäßc^ eine Einrichtung, um gleichzeitig Darstellungen der Digitalsignale, die zu jedem empfangenen Block von Signalen gehören, auf getrennten Digitalsignalleitungen zu erzeugen;

einen Satz von Ableitschaltungen mit Modulo-2-Addierern und Eingängen, die an die Digitalsignalleitungen angeschlossen sind, um alle Korrektorelemente von einem Block empfangener Signale gleichzeitig abzuleiten;

einen Satz von Fehlererkennungsschaltungen, die an die Ausgänge der Korrektorelement-Ableitschaltungen angeschlossen sind, um gleichzeitig Anzeigen von irgendwelchen Fehlern abzuleiten, die bei Informationsstellen innerhabl eines Blockes von empfangenen Signalen aufgetreten sind, mit Koinzidenzgattern, die auf vorgegebene Kombinationen

309881/1048

232A538

von Korrektorelementen ansprechen, welche sich aus Fehlern innerhalb der Informationsstellen ergeben; und

:tluroii einen Satz von k Korrekturgattern mit Modulo-2-Addierern, welche an die Erkennungsschaltungen angeschlossen sind und an vorbestimmte der Digitalsignalleitungen, auf denen Informationsstellensignale dargestellt werden sollen, um korrigierte Darstellungen der Informationsstellensignale zu erzeugen.

Es ist ersichtlich, daß bei dieser Anordnung die Korrektor-Ableitschal tungen alle gleichzeitig arbeiten können, wobei die Ausgangssignale, welche die Korrektorelemente darstellen, auf getrennten Ausgangsleitungen auftreten. Die Fehlererkennungsschaltungen können alle gleichzeitig arbeiten, wobei sie auf getrennten Leitungen Ausgangssignale abgeben, um irgendwelche Informationsstellensignale anzuzeigen, die gestört oder falsch erkannt wurden. Die Korrekturgatter können ebenfalls gleichzeitig arbeiten, um die korrekten Informationsstellensignale zu übertragen und die fehlerbehafteten Informationsstellensignale zu korrigieren, indem eine Modulo-2-Addition mit den entsprechenden Ausgangssignalen der 'Fehlererkennungsschaltungen durchgeführt wird. Die Aufeinanderfolge von Korrektorableitung, Fehlererkennung und Modulo-2-Addition kann verhältnismäßig schnell durchgeführt werden.

Die Anordnung kann einen ersten Pufferspeicher mit η parallelen Ausgängen enthalten, der so angeordnet werden kann, daß die empfangenen Signale in entsprechende der Digitalsignalleitungen eingespeist werden, sowie einen Pufferspeicher mit k parallelen Eingängen, die an die Ausgänge der Korrekturgatter angeschlossen sind.

30-9881/104 8

NACHGEREiCHT

dieser Anordnung Eine tttCE;fcÄ3cili2U£fc6 Weiterbildung dÖKJ-EKfiKacaBCffigl wird

erreicht durch eine Codiereinheit zum Codieren von Signalen nach dem systematischen (n, k, t)-Blockcode, bestehend aus einem Pufferspeicher mit k Ausgängen, die an einen Satz von Informationsstellensignal-Leitungen angeschlossen sind, einem Kontrollstellen-Codierer mit Eingängen, die an die Informationsstellensignal-Leitungen angeschlossen sind, und mit r = η - k getrennten Ausgängen, an denen Kontrollstellensignale gebildet werden, sowie einem weiteren Pufferspeicher,, der η parallele Eingänge hat, von denen k Eingänge an die Informationsstellensignalleitungen und r Eingänge an die Ausgänge des Kontrollstellen-Codierers angeschlossen sind.

Die oben angeriebene Aufgabe wird gelöst

Itxaasjxtäxxyjxiaxfäe&Mxetäf;2«±-Ed■::-Oj-:^iforogtgg durch Ein-

di e eine
richtungen,ZLUX Codierung und Decodierung von digitalen Signalen nach einem ausgewählten aus einem Satz von Blockcodes mit verschiedenen Senderaten und unterschiedlicher Fehlerkorrigierbarkeit ermöglichen.

Der Satz von Codes kann so gewählt werden, daß er einen (11, 7, 1)-Ein-Fehler-korrigierenden Code, einen (11, k, 2)-Zwei-Fehler-korrigierenden Code sowie einen (¹¹> ¹i 5)-Fünf-Fehler-korrigierenden Code aufweist.

Weiterhin kann der Satz von Codes auch einen (11, 2, 3)-Drei-Fehler-korrigierenden Code umfassen.

Die Anordnung kann ferner Maßnahmen vorsehen, um Signale direkt ohne irgendeine Codier- oder Fehlerkorrektureinrichtung zu übertragen. Der bevorzugte (11, 7> 1)-Code hat die Kontrollmatrix:

309881/1048

10000010110 01000101011 00101001101 00011110001

Der bevorzugte (11, h, 2)-Code hat die Kontrollmatrix

10000001110 01000001101 001000010 10 00010001001 00001000110 00000100101 00000010011

Es darf angemerkt werden, daß ein sehr ähnlicher Code von Slepian im Bell System Technical Journal, Band (1956), S. 217, aufgestellt wurde und daß Slepians Code wahlweise angewandt werden könnte.

Der bevorzugte (11, 2, 3)-Code hat die Kontrollmatrix

10000000001 01000000001 00100000001 00010000010 00001000010 00000100010 00000010011 00000001011 00000000111

309881/ 1048

- 1Ο_β -

Der (1Τ, 1» 5)-Code ist ein ¥iederholungscode mit der Kontrollmatrix

10000000001 01000000001 00100000001 00010000001 00001000001 00000100001 00000010001 00000001001 00000000101 00000000011

Diese Codes sind vorteilhaft, weil sie die höchsten Senderaten erlauben für Codes mit einer Slocklänge von η = 11 bei Wahl der Fehlerkorrigierbarkeit und sie sich alle mit vergleichsweise einfachen Schaltungen aufbauen lassen. Außerdem ist günstig_s daß alle diese Codes dieselbe Blocklänge η = 11 haben.

Ausführungsbeispiele der Erfindung werden anhand der Zeichnung näher beschrieben. Es zeigenι

Fig. 1 ein schematisches Blockschaltbild einer Codiereinheit zum Codieren von Signalen nach einem systematischen (n, k, t)-Blockcode;

Fig. 2 ein schematisches Blockschaltbild einer Decodiereinheit zum Decodieren von Signalen nach einem systematischen (n, k_s 6)-Blockcode ;

309881/1048

Fig. 3» 4 und 5 Schaltbilder einer Codiereinheit für den (i1, 7, 1)-Code, den (11, k, 2)-Code bzw. den (i1, 2, 3)-Code;

Fig. 6, 7 und 8 Schaltbilder einer Decodiereinheit für den (11, 7, 1)-Code, den (11, k, 2)-Code bzw. den (11, 2, 3)-Code;

Fig. 9 eine kombinierte Anordnung aus Codier- und Codeauswahlschaltungen; und

Fig. 10 ein schematisehes Schaltbild einer Demultiplex- und einer Decodieranordnung, die zusammen mit der Anordnung von Fig. 9 verwenden werden.

Fig. 1 zeigt eine Codiereinheit, die einen Pufferspeicher 1 enthält, der so angeordnet ist, daß er (durch irgendwelche geeignete, hier nicht gezeigte Einrichtungen) binäre Informationsstellensignale für die Übertragung aufnehmen kann. Diese Informationsstellensignale werden in Blöcken mit k Stellen empfangen, und der Pufferspeicher 1 ist so angeordnet, daß die k Stellensignale jedes Blockes in k getrennte Ausgangsleitungen 2 eingespeist werden. Der Pufferspeicher 1 kann z. B. ein Schieberegister mit parallelen Ausgangsleitungen sein. Ein Satz 3 von Kontrollstellen-Codierern, die r Codierschaltungen mit getrennten Ausgangsleitungen 4 enthalten, haben Eingänge, die mit den Ausgangsleitungen 2 des Speichers 1 verbunden sind. Ein weiterer Pufferspeicher 5 hat η parallele Eingänge, von denen k Eingänge getrennt mit den Leitungen 2 und r Eingänge getrennt mit den Leitungen k verbunden sind.

309881 /1048

Eine Synchronisierschaltung 6 steuert die Eingabe von Signalen in den Speicher 1 und die Ausgabe von Signalen aus dem Speicher 5·

Im Betrieb werden Darstellungen von k Informationssignalen gleichzeitig in entsprechende Leitungen der Di— gitalsignalleitungen 2 eingespeist» Die r Kontrollstellen-Codierer sprechen auf diese Signale" gleichzeitig an, wobei jeder ein Kontrollstellen- oder Paritätsprüfungssignal gemaß dem verwendeten Code erzeugt. Die Kontrollstellensignale werden mit den Informationsstellensignalen in den Pufferspeicher 5 eingegeben, um den vollen Block aus' η Signalen für die Übertragung zu bilden. Einzelheiten zu den Kontrollstellen-Codierern für die bevorzugten Codes werden nachstehend gegeben« Die im Speicher 5 gebildeten Signalblöcke werden für die Übertragung durch irgendwelche geeignete, hier nicht gezeigte Einrichtungen abgenommen.

Uni die Arbeitsweise der Kontrollstellen-Codierer etwas genauer zu beschreiben, darf bemerkt werden, daß die oben dargestellte Matrixgleichung (1) tatsächlich eine kurze und passende Form ist, um das System von r Gleichungen darzustellen

=0

η ^"^ «in ι

^hr1 ^dn © ...-...-. - ........... .'. i . . O h_rn Ci₁ = O

wobei das Zeichen (+) die Modulo-2-Addition bedeutet und die Koeffizienten h Elemente der Kontrollmatrix H sind. Da

30 9881/1048

hier ausgewählte Codes und binäre Signale verwendet werden, können diese Koeffizienten h nur 0 oder 1 sein. Jeder Term, für den der Koeffizient h gleich 0 ist, kann weggelassen werden und jeder Term, für den der Koeffizient h gleich 1 ist, ist einfach gleich der Stelle d, die er enthält. Somit gibt jede Gleichung des Gleichungssystems tatsächlich nur eine Bedingung dafür an, daß eine bestimmte Auswahl aus den zu übertragenden Stellen eine Modulo-2-Summe gleich Null haben muß; d. h. die Auswahl muß eine gerade Zahl von Eins-Stellen oder Symbolen enthalten, wobei Null als eine gerade Zahl betrachtet wird., Praktisch bildet jede Gleichung eine Regel zur Erzeugung einer der Kontrollstellen aus einer oder mehreren oder allen Informationsstellen mittels einer Modulo-2-Addition. Somit müssen die Kontrollstellen-Codierer nur Modulo-2-Addierer enthalten, wobei alle gleichzeitig arbeiten können und verschiedene Kombinationen der Informationsstellen summieren. Zweckmäßigerweise wird angenommen, daß die Kontrollmatrix so angeordnet ist, daß die Elemente h , h__p, h ... h alle Eins sind und die anderen Elemente in den ersten r Spalten alle Null. Dann reduzieren sieh die Gleichungen des Systems (3) in der Praxis auf eine Form

d = Modulo-2—Summe eines ersten gegebenen Satzes von Informationsstellen,

d = Modulo-2-Summe eines zweiten gegebenen Satzes ~ von Informationsstellen,

d, = Modulo-2-Summe eines r-ten Satzes von Informationsstellen.

Dies soll im folgenden mit Bezugnahme auf einige der bevorzugten Codes erläutert werden.

309881/1048

Flg. 2 zeigt eine Kontrollanordnung, bestehend aus einem Pufferspeicher 10, der so angeordnet ist, daß er durch irgendwelche geeignete, hier nicht gezeigte Einrichtungen Signalblöcke aufnehmen kann. Der Pufferspeicher 10 hat insgesamt η parallele Ausgänge mit k Ausgängen 11, an denen er die Informationsstellensignale abgibt, und r Ausgänge 12, an denen er die Kontrollstellsignale abgibt. Ein Satz von Schaltungen 13» deren Eingänge an die Ausgänge des Speichers 10 angeschlossen sind, besteht aus r Korrektorelement-Ableitschaltungen mit getrennten Ausgängen,, Weiter gibt es einen Satz. 14 von r Fehlererkennungsschaltungen mit getrennten Ausgängen und Eingängen, die so geschaltet sind, daß sie verschiedene Kombinationen der Ausgänge der Schaltungen 13 aufnehmen können. Ein Satz von Korrekturgattern 15 enthält k Modulo- 2-Addierer, von denen jeder einen Eingang an eine der Leitungen 11 angeschlossen hat und einen Eingang an einen entsprechenden Ausgang der Fehlererkennungsschaltungen. ' Die Ausgänge der Korrekturgatter 15 sind getrennt an k parallele Eingänge eines Pufferspeichers 16 angeschlossen. Eine Synchronisierschaltung 17 steuert die Eingabe von Signalen in den Speicher 10 und die Ausgabe von Signalen aus den Speicher 16.

Im Betrie,b gibt der Speicher 10 die Stellensignale eines empfangenen Blockes gleichzeitig an seinen entsprechenden Ausgängen ab. Die Korrektorelement-Ableitschaltungen arbeiten gleichzeitig und sprechen auf die verschiedenen Kombinationen an den Ausgängen des Speichers 10 an, wobei jede ein Element des Korrektors aus dem Block von empfangenen Signalen gemäß dem verwendeten Code ableitet. Bei Berücksichtigung der Beziehung zwischen den Matrizenglei-

309881/1Ü48

chungen (ι) und (2) überrascht es nicht, daß die Korrektor Ableitschaltungen für denselben Code den Kontrollstellen-Codierern sehr ähnlich sein können. Tatsächlich folgt aus diesen Gleichungen, daß jedes Korrektorelement durch eine Modulo-2-Addition aller Terme in. einer entsprechenden der Gleichungen (h) abgeleitet werden kann. Das heißt:

S = e Q) die Modulo-2-Summe des ersten gegebenen Satzes von Informationsstellen (wie empfangen)

S = e, (+) die Modulo-2-Summe des r-ten gegebenen

Satzes von Informationsstellen (wie empfangen) . . ■

In den nachfolgend gebrachten speziellen Beispielen von Schaltungen für die bevorzugten Codes wird gezeigt, daß jede Korrektorelement-Ableitschaltung wie der entsprechende Kontrollstellen-Codierer einen eigenen Eingang und einen eigenen Modulo-2-Addierer aufweist.

Jede der Fehlererkennungsschaltungen 14 enthält einen Majoritätsschaltkreis, der so geschaltet ist, daß er eine Kombination von Korrektorelementsignalen aufnimmt, derart, daß der Schwellenwert des Majoritätsschaltkreises dann und nur dann überschritten werden soll, wenn eines der zugehörigen Informationsstellensignale gestört oder als falsch erkannt wurde. Bei irgendeiner falschen Informationsstelle gibt die entsprechende Fehlererkennungsschal tung ein Eins-Signal am Ausgang ab; bei jeder richtigen Informationsstelle liefert die zugehörige Fehlererkennungs schaltung ein Null-Signal an den Ausgang. Durch eine Modulo-2-Addition dieser Signale mit den Informationsstellen-

309881/1048

Signalen (in den Korrekturgattern) werden die falschen Signale, komplementiert, während die richtigen Signale unverändert gelassen werden.

Es soll besonders betont werden, daß keine Notwendigkeit besteht, irgendwelche Schaltungen zur Korrektur oder sogar zur Erkennung des Auftretens von irgendwelchen Fehlern innerhalb der Korrekturstellen zu verwenden; diese können ohne Korrektur gelöscht werden, wenn einmal die Korrektorelemente ermittelt sind.

Es darf ferner bemerkt werden, daß die geeignete Anzahl von Ein- und Ausgangsleitungen der verschiedenen Einheiten von k oder r abhängt und dementsprechend gemäß dem verwendeten Code ausgetauscht werden muß. Fig. 1 und 2 zeigen schematisch die grundsätzliche Anordnung der Zwiseisenverbindungen, ohne daß die genaue Zahl von für irgendeinen speziellen Code notwendigen Leitungen angegeben wird.

Zum besseren Verständnis werden nun die genauen Schaltungen für die bevorzugten Codes beschrieben, als ob sie vollkommen unabhängig voneinander erzeugt wurden. In den folgenden Beschreibungen sind die zu codierenden Informationsstellen mit d bis d, _Λ und die Kontrollstellen mit

ο k-1

d, bis d beziffert; in den Decodierschaltungen werden die empfangenen Informationsstellen von e bis e, und die empfangenen Kontrollstellen von &_Λ bis e durchnume-

ic n— 1

riert. Die Korrektorstellen sind von s bis s ., durch-

o- r-1

numeriert.

Fig. 3 zeigt die Codierer für die Kontrollstellen des

3098 81/1048

bevorzugten (11, 7» 1)-Codes, der im folgenden als "Betriebsart sieben" bezeichnet wird. Die Leitungen 2, die vom Speicher 1 abgehen, sind mit den Bezugszeichen der Informationsstellensignale markiert, die in die Leitungen eingespeist werden. Für diesen Code gehen die Gleichungen (3) und (4) über in

10

= d₂ = d_t = ^d( = cL

^d3 θ ^d2

(6)

und Fig. 3 zeigt eine einfache Anordnung von Modulo-2-Addierern zur Ableitung dieser Kontrollstellen.

Die zugehörige Decodierschaltung kann ausgeschaltet sein wie in Fig. 6 gezeigt. Die Gleichungen (5) für den "Betriebsart-sieben"-Code nehmen folgende Formen an:

S = e^ _ ft) eι. (+) e.

= ^e ₉ (±) ^e5 C±) ^e3 <+)

S_n =

S_n =

^e8 Ct)

(7)

, ¥ie aus Fig. 6 deutlich hervorgeht, beinhalten die Korrektor-Ableitschaltungen 13 die Anordnung der in Fig. 3 verwendeten Modulo-2-Addierer.

Die Gleichungen (1), (2) und (3) verbinden die Informationsstellen mit den letzten k Spalten der Kontrollmatrix;

309881 /1048

durch die Matrizenmultiplikation werden die Elemente der letzten Spalte mit der ersten Informationsstelle e multipliziert, die Elemente der vorletzten Spalte mit der'zweiten Informationsstelle e usw. Daraus folgt, daß dann, wenn eine und nur eine der Informationsstellen fehlerhaft ist, die Positionen der Einsen in der entsprechenden Spalte der Kontrollmatrix darüber bestimmen, welches der Korrektorelemente durch den Fehler geändert wird. Als Beispiel sei angenommen, daß die letzte Spalte der Kontrollmatrix für den "Betriebsart-sieben"-Code eine Null in der ersten Zeile und Einsen in den anderen Zeilen aufweist; daraus folgt, daß ein Fehler in e , wenn dieses der einzige Fehler im Block ist, S =0 beläßt, dagegen S , S₂und S~ alle zu Eins macht.

Aus diesen Betrachtungen läßt sich die Fehlererkennungsschaltung von Fig. 6 direkt ableiten. An die Ausgänge -'■ der Schaltung 13 zur Bildung der Korrektorelemente, sind Inverterschaltungen 19 angeschlossen, damit das inverse oder komplementäre Signal jedes Korrektorelementsignals zur Verfügung steht. Jedes der Fehlererkennungsgatter 21 ist ein Koinzidenzgatter mit vier Eingängen, wobei deren Eingänge so geschaltet sind, daß sie eine, Signalkombination, die entsprechend den Elementen in einer zugehörigen Spalte der Kontrollmatrix bestimmt ist, aufnehmen können; somit besitzt das Gatter zur Erkennung von Fehlern in e (es handelt sich um das unterste der. Gatter 21 in Fig. 6) Eingänge zur Aufnahme von S„, S₂, S und dem inversen Signal von S , die den Einsen und Nullen in der letzten Spalte der Kontrollmatrix entsprechen. Das nächsthöhere Gatter in der Zeichnung, das zur Erkennung von Fehlern in e dient, besitzt Eingänge zur Aufnahme von S , S , dem

309881/1048

inversen Signal von S_p und dem inversen Signal von S„, die den Einsen und Nullen in der vorletzten Spalte der Kontrollmatrix entsprechen.

Fig. h zeigt Kontrollstellen-Codierer des bevorzugten (11, h, 2)-Codes, der im folgenden als "Betriebsart-vier" bezeichnet wird. Wie zu sehen ist, können die sieben Kontrollstellen mit Hilfe von sieben Modulo-2-Addierern gewonnen werden. Die entsprechenden Decodierschaltungen sind in Fig. 7 dargestellt. Die Gleichungen für diesen Code lauten

d₍
d_{
d„

I₁₀ = d₃ Q d₂ = d₃ © d₂ ^₃ 0 ^₁

= d

= d.

^d2 © ^d1

^d1 Θ

^So ^=ei0

= e

2 S₃ =

^S6

Zu vermerken ist, daß in diesem Fall die Korrektor-Ableitschaltungen 13 in Fig. 7 nicht so genau mit den Kontrollstellen-Codierern (Fig. h) übereinstimmen. Die Codier schaltungen sind vereinfacht wegen d,- = d (+) d„ und d,- = d (+) d , doch im Decodierer genügt es nicht anzunehmen, daß &f- = e (+) e oder e_ = e (jh) e_ ist. Die Ableitung der Fehlererkennungsschaltungen ist ebenfalls etwas schwie riger.

Bei Betrachtung der Kontrollmatrix kann man sehen,

309881/1048

daß das Korrektorelement S^ durch Fehler in e< , e und/oder e beeinflußt werden kann; das Korrektorelement S- kann durch Fehler in e_, e„ und/oder e beeinflußt werden; das Korrektorelement S kann durch Fehler in e_, e„ und/oder e beeinflußt werden* Durch Modulo-2-Addition der zweiten, dritten und fünften Zeile der Matrix kann gezeigt werden, daß die Summe (S (+) S₀ (+) S.) durch e_Q, e_s, e^ und/oder e beeinflußt werden kann. Diese vier Größen, nämlich S^, S , S„ und (S₁ (+) S₀ (+) Si ), werden ausgewählt, weil sie an verschiedenen Korrektorelekemten beteiligt sind; während ein Fehler in e alle vier Größen beeinflußt, kann kein anderer Fehler mehr als, eine der vier Größen beeinflussen. Wenn also ein Fehler in e der einzige Fehler im Block ist, besitzen alle vier Größen den Wert Eins. Falls es Fehler in e und in irgendeinem anderen empfangenen Symbol gibt, sind drei der vier Größen Eins. Jeder andere Einzelfehler macht nur eine der Größen zu Eins, und jedes andere Fehlerpaar macht gerade zwei der Größen zu Eins, Deshalb werden Signale, die diese vier Größen kennzeichnen, getrennten Eingängen eines Majoritätsschaltkreises oder Schwellenwertgatters 23 zugeleitet, das so konstruiert ist, daß es eine Eins am Ausgang abgibt, wenn drei oder alle ihre Eingänge Eins-Signale aufnehmen.

Durch Prüfen und durch Ausprobieren werden weitere Sätze dieser Art mit vier Größen ausgewählt, um in ähnlicher Weise Fehler in den anderen Informationsstellen e , e. und e„ zu erkennen. Somit lassen sich Fehler in e er-

kennen, weil diese wenigstens drei der Größen S„, S^, S^ und (S (+) S„ (+\ S_) gleich Eins machen; Fehler in e_o werden erkannt, da diese wenigstens drei der Größen Sr,

^Sk (^s Θ ^so) ^und (^si (±) ^sr>) gleich Eins machen; Fehler j ο ^^ <£ ' J

309881/1048

in e werden erkannt, weil diese wenigstens drei der Grö

ßen S

S , (S

_} O

(+) Si ) und (S

S₁,) gleich Eins ma-

chen. Aus diesen Überlegungen lassen sich natürlich direkt die Fehlererkennungsschaltungen in Fig. 7 ableiten.

Fig. 5 zeigt Kontrollstellen-Decodierer für den bevorzugten (11, 2, 3)-Code, der nachstehend als "Betriebsart Zwei" bezeichnet wird. Dieser Code benötigt nur einen Modulo-2-Addierer und einige direkte Verbindungen, um die benötigten Kontrollstellen zu bilden. Fig. 8 zeigt die zugehörigen Decodierschaltungen« Die Gleichungen für diesen Code lauten;

^d10 = ^do

= d = d = d = d.

= d.

= d = ^di Θ = d

^So ^{= e}i0

^si = ^e9

f+J e

= e

^S6· =

^S4 = ^e6

(+J

ο "0 Ό *1 ^!1

C+J e

(+J e

= e

+) ^e- (+je

In den Fehlererkennungsschaltungen von Fig. 8 stellen die mit k/6 markierten Blöcke Majoritätsschaltkreise oder Schwellenwertgatter dar, wobei jedes so ausgeführt ist, daß ein Eins-Ausgangssignal erzeugt wird, wenn einer der vier oder mehrere ihrer Eingänge Eins-Eingangssignale erhalten. Ein Fehler in e wird erkannt, weil er wenig-

309881/1048

stens vier der sechs Größen S , S , S (S- (+) S_R) ,

(S. (+) S₇) und (S„ (+) Sg) zu Eins macht. Ein Fehler

. (+) S₇) und (S„
in e wird erkannt, weil wenigstens vier der sechs Größen S₃, S₄, S₅, (S₂ <+) Sg), (S₁ Q S₇) und (S_q Q S₅) zu Eins gemacht .werden» Diese Erkennungsprozesse können durch keine der möglichen Kombinationen aus jeweils drei Fehlern gestört werden.

Für die (11, 1, 5)-Betriebsart, nachstehend als "Betriebsart Eins" bezeichnet, sind die benötigten Anordnungen sehr einfach. Die Codierung wird in einfacher Weise so durchgeführt, daß jede Informationsstelle elfmal wiederholt wird. Zum Decodieren benötigt man nur einen Majoritätsschaltkreis oder ein Schwellenwertgatter, das ein Eins-Signal abgibt, wenn irgendeines der sechs oder mehrere Signale in irgendeinem Block Eins-Signal sind.

Natürlich sind einige naheliegende Modifikationen möglich, und einige Teile können in mehr als einer der Betriebsarten der Anordnung benutzt werden. Die Pufferspeicher können aus Schieberegistern bestehen, wobei sie mit einer geeigneten Zahl von Stufen, entsprechend der Betriebsart, ausgestattet sind.

Die Anordnung kann in einem MuItiplex-Übertragungssystem angewandt werden, in dem die k Informationsstellen in jedem Block aus getrennten Kanälen genommen werden, so daß eine Einrichtung zur Übertragung von Signalen aus k Kanälen zur Verfügung steht, wobei k sich nach dem verwendeten Code richtet. Der verwendete Code kann entsprechend den vorherrschenden Übertragungsbedingungen und Anforderungen an die Zuverlässigkeit der zu übertragenden Nachrichten

309881/1048

gewählt werden oder entsprechend der Zahl der benötigten Kanäle zu irgendeiner vorgegebenen Zeit. Fig. 9 zeigt eine Codier- und Multiplexanordnung für ein solches System, Die Anordnung besitzt Dateneingabekontakte 30» die mit den Abkürzungen der von ihnen empfangenen Signale bezeichnet sind, entsprechend der schon oben benutzten Schreibweise. Bei der praktischen Anwendung der Anordnung stammen diese Signale aus getrennten (hier nicht gezeichneten) Kanälen. Die Anordnung kann in irgendeiner der fünf Betriebsarten betrieben werden, die nachstehend als "Betriebsart Elf", "Betriebsart Sieben", "Betriebsart Vier", "Betriebsart Zwei" bzw. "Betriebsart Eins" bezeichnet werden, entsprechend der Anzahl von Kanälen, die durch sie in Betrieb genommen werden. Die Codierschaltungen, die Modulo-2-Addierer und Verbindungen enthalten, die innerhalb der Begrenzungslinie 31 liegen, führen Operationen zur Codierung der Kontrollstellen durch, und zwar in "Betriebsart Sieben", "Betriebsart Vier" und "Betriebsart Zwei". Tatsächlich stellen diese Codierschaltungen eine Kombination von Schaltungen dar, die in den Fig. 3t k und 5 dargestellt sind, wobei einige kleinere Änderungen vorgenommen sind, die es gestatten, die notwendigen Operationen mit weniger Addierern durchzuführen, ohne ihre Funktionsweise zu ändern. Die Multiplexoperationen werden über einen Satz von Zeitschlitz-Auswahlkontakten t , t.., t„, ... t gesteuert; der Kontakt t befindet sich in der unteren linken Ecke von Fig. 9, während die anderen auf der rechten Seite dargestellt sind. Im Betrieb werden diese Zeitschlitz(fenster)-Auswahlkontakte mit einer (hier nicht gezeichneten) Taktschaltung verbunden, die mit den Kontakten der Reihe nach eine Verbindung herstellt, so daß diesen nacheinander in aufeinanderfolgenden Zeitschlitzen

309881/1048

- 2k -

Energie zugeführt wird. Für jede der Betriebsarten "Elf", "Sieben", "Vier" und "Zwei" wird ein Satz von Multiplex<gattern benötigt»

Die Gatter 32 übertragen Signale für die "Betriebsart Elf"; sie bestehen aus elf NAND-Gattern, die je einen Eingang an einer der Zeitschlitz-Auswahlkontakte (t bis t ) und einen anderen Eingang an einen entsprechenden der Dateneingabekontakte 30 angeschlossen haben» Alle Ausgänge der elf NAND-Gatter sind mit einem einzigen Inver-« ter verbunden» Ein weiterer ähnlicher Satz 33 aus elf NAND-Gattern und ein Inverter übertragen die Signale für die "Betriebsart Sieben"; in diesem Satz besitzen die sieben Gatter Eingänge, die an die Zeitschlitz-Auswahlkontakte t bis ts angeschlossen sind, während ihre anderen Eingänge direkt mit den ersten sieben der Dateneingabekontakte 30 verbunden sind, doch die anderen vier Gatter sind so geschaltet, daß sie die Kontrollstellensignale aus der Codierschaltung 31 nach "Betriebsart Sieben" aufnehmen. In ähnlicher Weise übertragen ein Satz von elf NAND-Gattern und ein Inverter Signale für die "Betriebsart Vier"; in diesem Satz haben die vier Gatter Eingänge, die an die Zeitsehlitz-Ausvahlkontakte t bis t~ angeschlossen sind, während ihre anderen Eingänge an die ersten vier der Dateneingabekontakte 30 angeschlossen, sind und die anderen sieben Gatter so geschaltet sind, daß sie die Kontrollstellensignale der Codierschaltung 31 nach "Betriebsart Vier" aufnehmen, können. Ein weiterer Satz 35 i^s* angeschlossen, um die Signale für die "Betriebsart Zwei" zu übertragen.

Die Invert erausgänge der Gatt er sät ze 32 _f 33, 3^* und

35 sind mit den entsprechenden NAND-Gattern g , g_, gr und g verbunden. Ein weiteres NAND-Gatter g hat einen Eingang direkt an den ersten der Dateneingabekontakte 30 angeschlossen; dies ist für die "Betriebsart Eins", in der das Signal vom ersten Dateneingabekontakt über elf Zeitschlitze hinweg in jedem Block gesendet wird. Die Gatter g , g_, g, , g_ und g werden durch Signale gesteuert, die an entsprechende Betriebsart-Auswahlkontakte m- , m_, mjL , m„ und m angeschlossen werden, so daß jeweils einer und nur einer auf einmal die Multiplex-Datensignale überträgt» Wenn z» B. die "Betriebsart Vier" verwendet werden soll, werden Signale an die Betriebsarten-Auswahlkontakte angelegt, so daß nur das Gatter g. aufgesteuert wird, um Datensignale zu übertragen. Die Ausgänge der Gatter S₁ .. » g₇» gh» g? und g sind alle über eine Leitung 37 zusammengefaßt und über einen Inverter an einen der Eingänge des Gatters 38 angeschlossen. Der zwölfte Zeitschlitz-Auswahlkontakt t ist so geschaltet, daß er ein Gatter 39 direkt und ein Gatter 38 über einen Inverter kontrolliert. Das Gatter 39 dient zur Aufnahme des Synchronisationssignals und von Systemsteuersignalen aus einem Eingangsanschluß hO. Die Ausgänge der Gatter 38 und 39 sind über einen Inverter mit dem Ausgang 4i der Anordnung verbunden. Somit werden im Betrieb codierte Datensignale einer ausgewählten Betriebsart über die Leitung 37 und das Gatter 38 an den Ausgang 4i übertragen, während den Zeitschlitz-Auswahlkontakten t bis t„_Λ nacheinander

ο 10

Energie zugeführt wird, danach wird ein Synchronisieroder Systemsteuersignal aus dem Eingang 4θ über das Gatter 39 übertragen, solange der Kontakt t erregt wird; anschließend beginnt ein weiterer Zyklus»

309881/1048

Fig. 10 zeigt den Gesamtaufbau einer Demultiplex- und Decodieranordnung, die in Verbindung mit der Anordnung nach Fig. 9 verwendet wird. Sie hat einen Eingang 49, der an einen Demultiplexer 50 angeschlossen ist, der so konstruiert ist, daß er aufeinanderfolgende Bit-Signale zyklisch auf zwölf Ausgangsleitungen verteilt, von denen elf parallel an Gattersätze 53, 54, 55, 56 und 57 angeschlossen sind. Die zwölfte Ausgangsleitung (in Fig. 10 mit 50 S bezeichnet) ist mit einer Synchronisierschaltung 51 und einer Betriebsarten-Steuerschaltung 52 verbunden. Die Synchronisierschaltung 51 steuert den Demultiplexer 50, und die Betriebsarten-Steuerschaltung 52 steuert die Gattersätze 53 bis 57· Die Ausgänge der Gatter 53 sind direkt an die Ausgangsleitungen 58 der Anordnung angeschlossen, während die Ausgänge der anderen Gattersätze 54 bis 57 mit zugehörigen dieser Leitungen 58 über schon beschriebene Decodierer verbunden sind.

Im Betrieb nimmt der Eingang 49 (über irgendwelche hier nicht gezeigten Nachrichtenverbindungen) Signale auf, die in einer Anordnung nach Fig. 9 iⁿ einer entfernten Station codiert wurden. Der Demultiplexer 50 ist so aufgebaut, daß seine Synchronisation anfangs zum Abwandern neigt, bis die Synchronisiersignale (jedes zwölfte Bit-Signal) auf der Leitung 50 S erscheint. Die Synchronisiersignale haben ein Muster mit vergleichsweise langen Folgen aufeinanderfolgender Nullen und Einsen, was bewirkt, daß die Synchronisierschaltung 51 eine Spannung aufbaut, die zur Stabilisierung der Synchronisation des Demultiplexers 50 nach einer üblichen Methode verwendet wird. Über einen längeren Zeitraum wird da,s Muster der Folgen von Nullen und Einsen in den Synchronisiersignalen benutzt, um die

0 9 8 8 1/10 4

verwendete Betriebsart anzuzeigen; die Betriebsart-Steuerschaltung 52 ist so konstruiert, daß die Betriebsart erkannt wird, wodurch der zugehörige Satz der Gattersätze 53 bis 57 aufgesteuert wird, um die codierten Datensignale zu übertragen» In einer weiteren Ausführung könnten die Gatter ^h bis 57 in die Leitungen, die von den Decodierern zu den Ausgangsleitungen 58 führen, geschaltet werden, um die Zahl der benötigten Gatter zu verringern«

309881/1041

Claims (11)

1. NACHQEREICHT

   293-20.721P-KoBk (6)

   P 23 24 538.7 ν.15.5c1973 12. 10. 1973

   Neue Patentansprüche

   Π. .y Digitale Nachrichtenübertragungsanordnung, gekennzeichnet durch Einrichtungen, die eine Codierung und Decodierung von digitalen Signalen nach einem ausgewählten aus einem Satz von Blockcodes mit verschiedenen Senderaten und unterschiedlicher Fehlerkorrigierbarkeit ermöglichen_s ' .
2. 2. Anordnung nach Anspruch I₅ dadurch gekennzeichnet, daß der Satz von vorbestimmten Blockcodes aufweist einen (11, J₃ I)-Ein-Fehler-korregierenden Code, einen (11,-4, 2)-Zwei-Fehlerkorrigierenden Code sowie einen'(11, I₃ 5)-Fünf-Fehler-korri-

   gierenden Code, ·
3. 3. Anordnung nach Anspruch 2._s gekennzeichnet durch Einrichtungen zur Codierung und Decodierung von digitalen Signalen gemäß einem (11, 2_S 3)»Drei-Fehler-korrigierenden Code.
4. 4. Anordnung nach Anspruch I₅ dadurch gekennzeichnet, daß der Satz vorbestimmter Blockcodes aufweist einen Ein-Fehler-korrigierenden Code mit der -Kontrollmatrix ■

   10000010110
   01000101011
   00101001101

   .00011110001

   oder einen im wesentlichen gleichwertigen Code<
5. 5. Anordnung nach Anspruch 1, dadurch gekennzeichnet, daß der Satz vorbestimmter Blockcodes aufweist einen Zwei-Fehler-korrigierenden Code mit der Kontrollmatrix

   10000001110 01000001101 00100001010 00010001001 00001000110 00000100101 L00000010011_

   oder einen im wesentlichen gleichwertigen Code.
6. 6. Anordnung nach Anspruch 1, dadurch gekennzeichnet, daß der Satz vorbestimmter Blockcodes aufweist einen Drei-Fehlerkorrigierenden Code mit der Kontrollmatrix

   10000000001'

   01000000001

   00100000001

   00010000010

   00001000010

   00000100010

   00000010011

   00000001011

   00000000111

   oder einen im wesentlichen gleichwertigen Code.
7. 7. Anordnung nach Anspruch 1, dadurch gekennzeichnet, daß der Satz vorbestimmter Blockcodes aufweist einen Fünf-Fehlerkorrigierenden Code mit der Kontrollmatrix

   309881/1048

   10000000001 01000000001 00100000001 00010000001 00001000001 00000100001 00000010001 00000001001 00000000101 00000000011

   oder einen im wesentlichen gleichwertigen Code.
8. 8. Anordnung nach Anspruch 1, gekennzeichnet durch eine zusätzliche Einrichtung zur direkten Signalübertragung ohne Codierung.
9. 9. Digitale Nachrichtenübertragungsanordnung in der Form einer Multiplex-Nachrichtenübertragungsanordnung, dadurch gekennzeichnet, daß sie arbeiten kann in irgendeiner aus einer Vielzahl vorbestimmter Betriebsarten, die zur Übertragung von digitalen Signalen nach vorbestimmten fehlerkorrigierenden Blockcodes dienen, wobei die vorbestimmten Blockcodes Codes umfassen, die alle eine gemeinsame Blocklänge η haben, Jedoch unterschiedliche Senderaten und unterschiedliche Fehlerkorrigierbarkeit. - .
10. 10. Digitale Nachrichtenübertragungsanordnung in der Form einer Muitiplex-Nachrichtenübertragungsanordnung zur Übertragung digitaler Signale in irgendeiner aus einer vorbestimmten Vielzahl von Betriebsarten, gekennzeichnet durch eine erste Betriebsart, in der sie Signale von elf Kanälen im Zeitmultiplex ohne Redundanz und ohne Fehlerkorrigierbarkeit übertragen kann; durch eine zweite Betriebsart, in der sie Signale von sieben Kanälen gemäß einem (11, 7* l)-fehlerkorrigierenden Blockcode übertragen kann;

    09881/1048

    durch eine dritte Betriebsart, in der sie Signale von vier Kanälen gemäß einem (11, 4, 2)-fehlerkorrigierenden Bloekcode übertragen kann; und durch eine vierte Betriebsart, in der sie Signale von einem einzelnen Kanal gemäß einem (11, 1, 5)-fehlerkorrigierenden Code übertragen kann.
11. 11. Anordnung nach Anspruch 10, gekennzeichnet durch einen Satz von Gattern für jede der Betriebsarten, durch einen Codierer, um Eingangssignal an den ersten Satz von Gattern zu übertragen und entsprechende codierte Signale für die zweite, dritte und vierte Betriebsart abzuleiten und diese codierten Signale in die zugehörigen Sätze de? Gatter einzuspeisen, und durch eine Betriebsart-Steuereinrichtung, um einen und nur einen'der Sätze von Gattern zu irgendeiner Zeit aufzusteuern, um die an sie angelegten Signale zu übertragen.

    3GS881/1048

    ^u ·

    Leerseife