-
Verfahren zur Erhöhung der übertragungssicherheit von binär codierten
Informationen Die Erfindung bezieht sieh auf ein Verfahren zur Erhöhung dem übertragungs11sicherheit
von binär codierten Informationen. Um mit einem binären Code Informationen übertragen
zu können, ist es erforderlich, jede Information aus einer Reihe von Informationselementen
s1, s2 . . . s", zusammenzusetzen, von denen jedes Informationselement entweder
einen Wert 0 oder einen Wert L hat. Mit zunehmender Anzahl der zu übertragenden
Informationen nimmt auch die Zahl der benötigten Informationselemente zu. Man kann
die zur übertragung einer Information benötigten Informationselemente als Elemente
einer Matrix auffassen, die die jeweils zu übertragende Information bestimmt. Diese
Matrix wird im folgenden »einzeilige Informationsmatrix« genannt und mit S bezeichnet.
Eine Matrix S= (s1, s2 ... sm), deren Elemente beliebig gewählt
werden dürfen, reicht aus; um eine von 2m Informationen unterscheidbar von den übrigen
Informationen darzustellen. Da bei einer Übertragung der Information von einem Sender
zum Empfänger durch Störgrößen die Gefahr besteht, daß einzelne Elemente der Matrix
ihren Wert ändern oder daß plötzlich neue Matrixelemente auftreten, muß sichergestellt
werden, daß derartige Störungen in ihrer Auswirkung rechtzeitig erkannt werden.
-
Zu diesem Zweck ist es bekannt, in dem Sender aus den m Informationselementen
s1, s. ... s", mit den Werten 0 oder L k Prüfelemente r1, r2
... rk
ebenfalls mit den Werten 0 oder L zu bilden, sie gemeinsam mit
den Informationselementen zu übertragen und im Empfänger mit dort in gleicher Weise
aus den von ihm aufgenommenen Informationselementen Prüfelemente zu bilden und diese
mit den übertragenen Prüfelementen zu vergleichen. Tritt bei dieser Prüfung eine
Abweichung auf, so kann damit gerechnet werden, daß ein Übertragungsfehler vorliegt.
Dementsprechend kann ein Störungssignal ausgelöst werden. In ähnlicher Weise, wie
die Informationselemente si als. Elemente einer einzeiligen Informationsmatrix S
aufgefaßt werden können, lassen sich die Prüfelemente r; als Elemente einer Matrix
R auffassen, die als »einzeilige Redundanzmatrix« bezeichnet sei. Bei dieser Darstellungsart
lassen sich die tatsächlich übertragenen Informationselemente si und Prüfelemente
r; zusammenfassen zu einer einzeiligen Codematrix W. Die Zusammensetzung jeder Codematrix
aus einer Informationsmatrix und einer passenden Redundanzmatrix ermöglicht Code,
bei denen sich jede Codematrix von jeder anderen Codematrix in mindestens einer
vorgegebenen Anzahl von Elementen unterscheidet. Diese Zahl sei Codedistanz genannt
und mit dem Buchstaben d bezeichnet. Von der Codedistanz hängt es dann ab, in welchem
Maße sich Veränderungen, welche eine gesendete Codematrix im Verlauf ihrer Übertragung
durch Störungen erfahren hat, am Empfangsort erkennen und gegebenenfalls korrigieren
lassen. Je größer die Codedistanz d ist, um so mehr Fehler lassen siech erkennen
und korrigieren. Um eine vorgegebene Codedistanz d sicherstellen zu können, muß
die Redundanzmatrix aus der Informationsmatrix in geeigneter Weise ermittelt werden.
Dies kann beispielsweise in der Weise erfolgen, daß die einzeilige Informationsmatrix
S mit einer m-zeiligen Prüfmatrix, die nach bestimmten Gesetzen aufgebaut isst,
modulo 2 multipliziert wird. Das Ergebnis dieser Multiplikation ist dann eine einzeilige
Redundanzmatrix R mit den Komponenten r1, r2 ... rk. Multiplikation modulo
2 bedeutet dabei, daß für jede Stelle des Ergebnisses der Rest angegeben wird, der
sich bei der Division durch 2 ergibt. Zum Aufstellung einer geeigneten Prüfmatrix
P ist folgendes zu sagen: Addiert man z beliebige verschiedene Zeilen der Prüfmatrix
P modulo 2, so stellt das Ergebnis eine einzeilige Bedingungsmatrix VZ dar, von
der eine gewisse Anzahl von Komponenten den Wert L haben wird. Bezeichnet man diese
Anzahl mit gZ, so ergibt die Multiplikation der Informationsmatrix S mit der Prüfmatrix
P modulo 2 eine Redundanzmatrix R, die eine Codedistanz; d sicherstellt, wenn die
Bedingung erfüllt ist gz>d-z(z=1,2...d-1).
-
Dieser Bedingung müssen alle Kombinationen von jeweils z Zeilen der
Prüfmatrix P genügen. Entsprechend dieser Regel kann man bei der übertragung einer
aus zwölf Informationselementen aufgebauten Informationsmatrix eine Codedistanz
4 sicherstellen, wenn mit der Informationsmatrix S
eine Redundanzmatrix
R übertragen wird, deren Elemente durch Multiplikation der einzeiligen Informationsmatrix
S mit den Elementen der zwölfzeiligen Prüfmatrix
erhalten werden. Für die angegebene Prüfmatrix P gilt, wie man sich durch Kontrolle
leicht überzeugen kann: gl>4-1 g,>4-2 g3>4-3 Die angegebene Prüfmatrix P ist aber
keineswegs die einzige, die es gestattet, Informationsmatrizes mit zwölf Informationselementen
so zu einer Codematrix zu ergänzen, daß bei der Übertragung eine Codedistanz 4 garantiert
wird. Es gibt noch eine große Anzahl weiterer Prüfmatrizes mit zwölf Zeilen und
sechs Spalten, die ebenfalls den Bedingungen für die Codedistanz 4 genügen. So ist
leicht einzusehen, daß bereits jede Permutation von Zeilen und/oder Spalten der
als Beispiel angeführten Prüfmatrix P zu solchen gleichwertigen Prüfmatrizes führt.
Darüber hinaus erfüllen aber eine große Anzahl weiterer Prüfmatrizes ebenfalls die
oben gestellten Bedingungen.
-
Die Erfindung geht daher von der Frage aus, ob nicht unter der Menge
der bestimmten Distanzbedingungen genügenden Matrizes solche sind, welche einen
Algorithmus für die Berechnung der Redundanzmatrizes erlauben, der für die Durchführung
der Berechnung mit einfachen technischen Mitteln geeignet ist, und hat die Aufgabe,
solche technischen Mittel anzugeben. Es l'äßt sich zeigen, daß ein solcher Algorithmus
besteht. Seine Anwendung führt zu einem Verfahren zur Erhöhung der übertragungssicherheit
von binär codierten Informationen, das nach der Erfindung dadurch gekennzeichnet
ist, daß jeweil i Informationselemente s", ,lr = 1, 2 ... m
einer ; Multiplikationseinrichtung zugeführt werden, in der sie mit quadratisch
in einer i-zeiligen Prüfmatrix angeordneten Elementen 3n4, p=1, 2 . . . i,
anQ=aQ"=L, 3n"=0, deren andere Elemente alle den Wert 0 haben, und in der die dabei
etwa auftretenden quadratischen Matrizes (a") zeilenweise aneinander anschließen
und spaltenweise gegeneinander verschoben sind, modulo 2 multipliziert werden und
die sich bei den Multiplikationen mit in den gleichen Spalten der in der m-zeiligen
Prüfmatrix angeordneten Elementen an" ergebenden Werte, in Addiervorrichtungen modulo
2 addiert, als Prüfelemente dienen. Dabei können nach der Erfindung die Multiplikationseinrichtungen
in der Weise vereinfacht werden, daß sie die Anzahl der Informationselemente s,,
zählen und bei gerader Anzahl als Ergebnis der Multiplikation die Folge der Informationselementes"
und bei ungerader Anzahl die antivalente Folge s-" den Addiervorrichtungen zuführen.
-
Bevor die entsprechenden Schaltungen an einem Ausführungsbeispiel
näher erläutert werden, sei zunächst auf den Aufbau der dazu notwendigen Prüfmatrizes
eingegangen. Anstatt zur Berechnung der Redundanzmatrix die weiter oben erwähnte
Prüfmatrix P zu verwenden, kann man eine Redundanzmatrix, die die Codedistanz 4
sicherstellt, auch durch Multiplikation der Informationsmatrix S mit der Prüfmatrix
gewinnen. Diese Prüfmatrix P4 enthält dreimal die vierzeilige quadratische Untermatrix
Enthalten beispielsweise die Informationsmatrizes S vierzehn Informationselemente,
so kann man eine Codedistanz 4 sicherstellen, wenn man die Informationsmatrix S
mix der Prüfmatrix
multipliziert. Diese Prüfmatrix PS enthält zweimal die Untermatrix
und einmal die Untermatrix
Die Untermatrizes Ml haben nun alle die für die Erfindung wesentliche Eigenschaft,
daß ihre Multiplikation modulo 2 mit einer einzeiligen Matrix Cl mit i Elementen
der Werte 0 oder L dann, wenn die Matrix Cl -eine gerade Anzahl Elemente
vom Wert L enthält, zur Matrix Cl selbst führt, und dann, wenn die Matrix Cl eine
ungerade Anzahl Elemente vom Wert L enthält, zu einer Matrix Cl führt, die
aus der Matrix Cl dadurch hervorgeht, daß die Werte 0 und L ausgetauscht werden.
Hierfür seien nachstehend zwei Beispiele angegeben:
Wie man aus der zuletzt angegebenen Beziehung ersieht, werden in diesem Fall einfach
die Werte der Elemente cl der Matrix Cl durch die Werte der entsprechenden antivalenten
Elemente cl der antivalenten Matrix Cl ersetzt. Ausgehend von dieser Erkenntnis,
ermöglicht die Erfindung eine keine Rechenzeit erfordernde Ermittlung der zu einer
vorgegebenen Informationsmatrix gehörenden Redundanzmatrix, die eine gewünschte
Codedistanz sicherstellt, mit geringeren technischen Mitteln, als säe eine elektrische
Multiplikation an sich erfordert.
-
Die Erfindung sei nun näher an dem Beispiel der Aufgabe erläutert,
eine dreistellige Dezimalzahl mit der Codedistanz 4 binär zu übertragen. Dabei wird
angenommen, daß der Zahlenwert jeder Dezimalstelle in eine entsprechende binär codierte
Darstellung umgewandelt wird. Da zu Darstellung der Zahlenwerte einer Dezimalstelle
vier Binärstellen benötigt werden, die entweder den Wert 0 oder den Wert L haben,
werden dafür insgesamt zwölf binäre Informationselemente benötigt. Somit ist also
eine Informationsmatrix zu übertragen S= (S1, S2 ... S12, wie sie
am Ausgang 1 der in F i g. 1 dargestellten Schaltung des Ausführungsbeispiels auftritt.
Bei diesein dargestellten Ausführungsbeispiel werden die zu übertragenden Dezimalzahlen
für jede Dezimalstelle über das Schalterfeld 2 den Codherem 3 bäs 5 zur Umwandlung
in entsprechende binäre Werte zugeführt.
-
Nach dem Vorhergesagten muß nun, um eine Codedistanz 4 sicherzustellen,
außer der Informatiansmatrix S noch eine Redundanzmatrix R übertragen werden, die
durch Multiplikation der Informationsmatrix S mit einer geeigneten Prüfmatrix P
gewonnen wird. Für die Redundanzmatrix gilt also R=S-P oder in Komponentendarstellung
Spaltet man diese Multiplikation modulo 2 in die folgenden Teilmultiplikationen
auf:
so erhält man die Elemente der Redundanzmatrix R aus der Beziehung
Nach dem weiter oben Gesagten ist nun die Teilmatrix A, je nachdem ob die Informationselemente
Si, s2, s3, S4 eine gerade oder eine ungerade Anzahl vom Wert L enthalten, gleich
den Informationselementen s1, S2, s3, s4 oder gleich den antivalenten Informationselementen
s1, s2, 3,3, s4. Nach der gleichen Regel ergeben sich die Teilmatrizes B und C aus
den Informationselementen s5, se, s7, s8 und s., Si., s11, s12 bzw. den ihnen entsprechenden
antivalenten Informationselementen. Dementsprechend enthalten bei dem Ausführungsbeispiel
der F i g. 1 die Codiere.r 3 bis 5 je ein Zählglied, das prüft, ob eine gerade oder
eine
ungerade Anzahl der in ihnen gebildeten Informationselemente den Wert L hat. In
Abhängigkeit von dem Ergebnis dieser Zählung werden die Relais 6 bis 8 erregt. Diese
Relais betätigen Umschaltkontakte, die vom Normalausgang auf den antivalenten Ausgang
bzw. umgekehrt von an den Codierem 3 bis 5 angeschlossenen Speicherelementen umschalten.
Somit fü -ren also die von den Umschaltkontakten abgehenden Leitungen Signale, die
den Elementen der Teihnatrizes A, B und C entsprechen. In der Addierstufe
21 werden nun die Elemente der Teilmatrizes A, B und C addiert, die gemäß
der oben angegebenen Beziehung für die Elemente r, der Redundanzmatrix zu addieren
sind, um zu diesen Elementen zu gelangen. An den Ausgängen 22 dieser Addierstufe
treten dann die Elemente der Redundanzmatrix auf, die mit den Elementen der Informationsmatrix
zu übertragen sind, damit bei der Übertragung die gewünschte Codedistanz 4 sichergestellt
ist.
-
Bei dem in F i g. 1 dargestellten Beispiel ist angenommen, daß die
Informationselemente, die im Codierer 3 gebildet werden, die Werte haben 0,
L, L, L. Die Anzahl der Informationselemente mit dem Wert L ist dabei ungerade,
d. h., das Relais 6 schaltet die Umschalter so, daß die antivalenten Ausgänge der
Speicher 9 bis 12 an die Eingänge der Addierstufe 21 geführt werden. Für die Informationselemente,
die in dem Codierer 4 gebildet werden, sei angenommen, daß sie die Werte haben
L, 0, 0, L.
Die Anzahl der Informationselemente mit dem Wert L ist
gerade, dementsprechend schaltet das Relais 7 über die Umschalter die Normalausgänge
der Speicher 13 bis 16 an die Eingänge der Addierstufe 21. Für die in dem Codie.rer
5 gebildeten Informationselemente ist die Wertfolge 0, L, 0, 0 angenommen. Da die
Anzahl der Informationselemente mit dem Wert L wiederum ungerade ist, werden über
das Relais 8 die Umschalter an die antivalenten Ausgänge der Speicher 17 bis 20
gelegt, so daß den Eingängen der Addierstufe21 wiederum die antivalenten Werte zugeführt
werden. Somit sind also die notwendigen Multipliziervorgänge auf einfache Zähl-und
Addiervorgänge zurückgeführt worden, die sich in einfacher Weise technisch ausführen
lassen. Ein Ausführungsbeispiel eines entsprechenden Empfängers ist in F i g. 2
im Blockschaltbild dargestellt. Dabei ist bezüglich der Verbindung von Sender und
Empfänger unterstellt, daß die an den Ausgangsklemmen 1 und 22 des Blockschaltbildes
der F i g. 1 gleichzeitig parallel zueinander auftretenden Elemente der Informationsmatrix
und der Redundanzmatrix in einem ParalleIserienumsetzer in nacheinander abgehende
Informationen umgesetzt werden und in einem dem Empfänger gemäß Blockschaltbild
nach F i g. 2 vorgeschalteten Sehenparallelumsetzer wieder in gleichzeitig parallel
zueinander vorliegende Elemente der Informationsmatrix und der Redundanzmatrix umgeordnet
werden, die über die Klemmen 23 und 24 in die Schaltung der F i g. 2 eingehen. So
gelangen die Elemente der Informationsmatrix über die Klemmen 23 auf die Speicherglieder
25 bis 36 und die Elemente der Redundanzmatrix über die Klemmen 24 auf die Und-Glieder
37 bis 42. Die Normalausgänge der Speicherglieder 25 bis 36 sind direkt an die Dezimalcodierer
43, 44 und 45 geführt, in denen die binär übertragenen Informationen wieder in die
Ursprungsinformationen umgewandelt werden. .Zeder der drei Dezimalcodierer entspricht
dabei einer Dezimalstelle. D-mentsprechend hat er zehn Ausgänge, von denen jeder
einer bestimmten Dezimalzahl zugeordnet ist. Den Dezimalcodierern sind Und-Glieder
nachgeschaltet, an die je ein Ausgang jedes Dezimalcodie.rers in der Weise geführt
wird, daß alle auftretenden Kombinationen von ihnen erfaßt werden können. An dem
Und-Glied, das der jeweils übertragenen Information entspricht, tritt dann ein entsprechendes
Ausgangssignal auf, das zur Anzeige oder zur Auslösung von Stellbefehlen dienen
kann. Die Und-Glieder sind in der F i g. 2 mit 46 bezeichnet. Um die Richtigkeit
der Übertragung zwischen Sender und Empfänger feststellen zu können, enthalten die
Dezimalcodiere.r 43 bis 45 je ein Zählwerk, das feststellt, ob die Anzahl der an
ihrem Eingang anliegenden Informationen mit dem Wert L gerade oder ungerade ist.
In Abhängigkeit von den! Ergebnis dieser Zählung sprechen die Relais 47, 48 und
49 an und bewirken dadurch ein Umschalten der auf die Normalausgänge und die antivalenten
Ausgänge der Speicherglieder 25 bis 36 wirkenden Umschalter. Der Aufbau entspricht
hier vollkommen demjenigen, der weiter oben bei der BSchreibung des Senders dargelegt
wurde. Liegt an den Eingängen eine gerade Anzahl von Informationen mit dem Wert
L an, so werden die Normalausgänge der Speicher mit den Addierwerken der Addierstufe
50 verbunden. Ist die Anzahl der Informationen nüt dem Wert L dagegen ungerade,
so werden die antivalenten Ausgänge der Speicherglieder auf die entsprechenden Addierwerke
der Addierstufe 50 geschaltet. Als Ergebnis dieser Additionen treten, wie weiter
oben eingehend dargelegt wurde, an den Ausgängen der Addierstufe 50 die Elemente
der Redundanzmatrix auf, die den empfangenen Informationselementen zugeordnet werden
können, um die gewünschte Codedistanz bei der Übertragung sicherzustellen. Sind
keine übertragunsfehler aufgetreten, so müssen also die in dem Empfänger neu gebildeten
Elemente der Redundanzmatrix mit den im Sender gebildeten Elementen der Redundanzmatrix,
die mit den Elementen der Informationsmatrix übertragen wurden, übereinstimmen.
Aus diesem Grunde sind die Ausgänge der Addierwerke der Stufe 50 an die Eingänge
der Und-Glieder 37 bis 42 geführt, auf die auch die Elemente der übertragenen Redundanzmatrix
einwirken. Da im vorliegenden Fall nur interessiert, ob Abweichungen auftreten,
sind die antivalenten Ausgänge der Und-Glieder 37 bis 42 an einen Signalgeber
51 geführt, in dem dann und nur dann ein Störungsmeldungssignal auftritt, wenn die
übertragene Redundanzmatrix und die im Empfänger neugebildete Redundanzmatrix voneinander
abweichen. Indem man in dem Störungsmelder 51 erkennbar macht, welche Elemente der
übertragenen und der neugebildeten Redundanzmatrix voneinander abweichen, kann man
auch zu Aussagen darüber gelangen, an welchen Stellen Übertragungsfehler vorliegen.
In ähnlicher Weise lassen sich auch weitere Schaltungen nach der Lehre der Erfindung
aufbauen.