-
Verschlüsseler Die Erfindung bezicht sich auf die Verbesserung der
Informationsrate und/oder der Zuverlässigkeit von digitlen Übertragungs- und Aufzeichnungssystemen.
-
Es sind digitale Verschlüsselungsverfahren zur Übertragung oder Speicherung
binärer Daten ersennen worden. Ein solches Verfahren, das als NRZI (non-return-to-zero,
IBM Version) bekannt ist, wird häufig in magnetischen Aufzeichnungssystemen verwendet,
in denen als Datenspeicher Magnetbänder, Magnettrommeln und Magnetplatten verwendet
werden. Bei einer Verschlüsselung nach dem NRZI-Verfahren wird eine 1 in einer Datenfolge
durch einen Wechsel von einer bestimmten Polarität der Magnetisierung zu der entgegengesetzten
Polarität auf der magnetischen Oberfläche dargestellt, während eine 0 in der Datenfolge
lediglich durch das Fahlen eines
Polaritätswechsels dargestellt
wird. Wenn die nach don NRZI-Verfahren aufgezeichneten Polarisationen gelosen werden,
hat eine Knderung der Polarität einen Spannungsimpuls zur Folge, der von dem Losekopf
festgestollt wird und anzeigt, daß eine 1 gelescn wurde, während das Fchlen jedes
Impulses anzeigt, daß Nullen gelesen werden. Wegen des im wesentlichen bandbegrenzten
Frequenzganges des Lesesystems müssen diese Impulse durch eine bestimmte Mindestdistanz
getrennt sein, da sonst Störungen der einzelnen Symbole in ausgedehntem Muße auftreten.
Die Aufzeichnungsdichte ist in diesem Falle hauptsächlich begrenzt durch die gegenseitigen
Stbrungcn der Syrnbole und nicht durch Unbestimmtheit beim Feststellen der Obergangsstellen.
-
Un die Informationsdichte solcher Aufzeichnungssysteme zu erhöhen
kann die minimal zulässige Trennung der Obergänge in verschiedene kleinere gleiche
Spalte unterteilt werden, von denen jede einer Ziffor der verschlüsselten Datcnsoquenz
entspricht. Die minimal zulässige Trennung der Obergänge kann dadurch beibehalten
werden, daß erzwungen wird, daß die Einsen in der verschlüsseiten Datenfolge zu
mindest durch eine bestimmte Anzahl von Nullen getrennt sind, wobei diese Anzahl
hier durch don Buchstaben "d" dargestellt wird.
-
Das einfache NRZI-Verfahren hat den Mangel, daß dann, wenn die Datenfolge
eine lange Reihe von Kullen enthält, beim Lesen während einen langen Zeitporiode
kein Signal festgestellt wird.
-
Dies kann zw einem möglichen Verlust der Synchronisation und
anderer
Schwierigkeiten beim Erkennen führen. Um das zu vermeiden, kann ein maximaler Abstand
zwischen benachbarten übergängen orzwungen werden. Denachbarte Einsen sollten durch
nicht mehr als eine bestimmte Anzahl von Nullen getrennt sein, wobei diese Anzahl
hier mit dem Buchstaben "k" bezeichnet ist.
-
Um eine hohe Informationsdichte mit zuverlässiger Synchronisation
zu orreichen, kann dio Länge irgendeiner Reihe aufeinanderfolgender Nullen in der
Datenfolge so eingeengt werden, da sie :wi schon den Grenzen d und k liegt. dann
solch eine dk-begrenzte Datenfolge nach dem NRZI-Verfahren aufgezeichnet wird, wird
sowohl die minimale als auch die maximale Trennung zwischen benachbarten Obergängen
in erwünschter Weise erhalten.
-
Die Erfindung betrifft ein sehr zweckmäßiges Verfahren zum Verschlässeln
von Eingangszahlen in dk-begrenzte binäre Datenfolgen von n Ziffern und zum Entschlüsseln
solcher Datenfolgen, um die ursprünglichen Eingangszahlen wieder zu gewinnen. Es
wurde gefunden, daß jede dk-begrenzte binäre Datenfolge von n Ziffern (wobei d,
k und n konstante Werte haben) leicht umgesetzt werden kann in eine Reihe aus einer
vorgegebenen Reihe aufeinanderfolgender nicht negativer cantor Zahlen (0 oder größer)
durch nwonden bestimmter $Gewichte auf die bedeutsamen Ziffern (d.h. die Einsen)
in der genannten Datenfolge und durch Addieren dieser gewichteten Werte, um eine
gewichtete Summe zu erhalten, die irgendwo innerhalb der Reihe ganzer Zahlen liegt,
wobei die gewichtete Summe für die besondere dk-begrenzte Datenfolge eindeutig
ist.
Es sei A die gewichtete Summe, xi the Wert einer in binärer Reihe mit i numeriorten
Binärziffer x und wi das Gewicht, das dieser Ziffer zugeordnet ist, dann gilt:
Darin bezeichnet der Ausdruck "R (i-1)" die Anzahl der verschiedenen, dk-begrenzten
Datenfolgen aus (i-1) Ziffern und stollt das Gewicht dar, das xi zugeordnet ist.
Das Symbol "N", auf das die Darstellung einer Zahl in Klammern folgt, zeigt die
gesamte Anzahl der verschiodenen dk-begrenzten Datenfolgen an, die die Anzahl der
Ziffern aufweisen, die in dem folgenden Paar der klammern angegeben Ist. In fodcra
Prall, in der die Anzahl der Ziffern kleiner als O ist, wird angenommen, daß N obenfalls
O ist. In dem Fall, in dem sich die Anzahl der Ziffern genau auf 0 reduziert, wird
N(O) als 1 de£iniort.
-
Ein allgemeiner Ausdruck aus dem man den Wert von N(j) ableiten kann,
in dem j irgendeine nicht negative ganze Zahl darstellt, ist der folgende:
Durch Entwickeln der rekursiven Funktionon auf beiden Seiten dieser Gleichung erhält
man die folgende Bezichung: (3) N(n)+N(n-k-1)+N(n-2k-2)+...=N(n-1)+N(n-d-2)+N(n-2d-3)+...+1.
Es
wird angenommen, daß die Werte von d und k konstant sind.
-
Beginnend mit dem Wert n = 0, der jedesmal um 1 erhöht wird, kann
man leicht bei vorgegebenen Werten von d und k einen Sat2 von Werten für N(0), N(1),
N(2), usw. ableiten, wobei zu berücksichtigen ist, daß in den Klanncrn stehende
Ausdrücke, die sich als negativ erweisen, unberücksichtigt bleiben.
-
Der gewichtete Summenwert A, der vorher erwähnt wurde, liegt irgendwo
innerhalb eines Bereiches von N(n) aufeinanderfolgenden ganzen Zahlen, der einen
minimalen Wort MIN und einen maximalen Wort MAX besitzt, die wie folgt definiert
sind:
Wie im Falle der anderen vorher beschriebenen rekursiven Funktionen können auch
hierbei die Werte von i, durch die die Klammerausdrücke negativ werden, unberücksichtigt
bleiben.
-
Es sei nun für A ein mit An bezeichneter Aufangswert angenommen und
es sollen die entsprechenden dk-bogrenzten Datenfolgen von n Binärziffern xn, xn-1,
... x3, x2, x1 definiert worden, die, wenn sie in der oben angegobenen Weise gewichtet
werden, die Summe An ergeben. Der erste Schritt in dieser Analyse ist der, die höchste
Ordnung t der dk-begrenzten Datenfolge zu finden, in dur xt für einen vorgegebenen
Wert All den Wert 1 annehmon kann.
-
Dies kann durch Vergleichen von An mit einer oder mchroren einer Reihe
von fallenden Schwellwerten bestimmt werden, die wie folgt definiert sind: Für die
höchste Ordnung n, ist der Schwellwert Für die nächste ordnung n-1, ist der schwellwert
Für irgendeine ordnung t, ist der Schwellwert Für die niedrigste Ordnung 1, ist
der Schwellwert
Beginnend mit dem Schwellwert für die n. Ordnung wird der Vergleich so oft rchgeführt
alses notwendig ist, bis die höchste Ordnung t gefunden wurde, in der An den Schwellwert
für diese Ordnung überschroitet oder zumindest orreicht. Die Ziffer xt in dieser
Ordnung wird gleich 1 gesotzt und der Wert von N(t-1) wird dann von An subtrahiert,
um den neuen Wert At zu orgoben, der nun nachoinander mit dem Schwellwort für die
Ordnung (t-10 verglichen wird und (falls notwendig) mit den Schwellerten für die
niodrigeren Ordnungen der Datenfolge, bis die höchste Ordnung gefunden wurde, in
der At den Schwollwert für diese Ordnung erreicht oder überschreitet, worauf das
oben beschriebone
Verfahren wiederholt wird, bis die niedrigste
Ordnung schließlich erreicht wird, zu welchem Zeitpunkt A entweder den 6:crt 1 oder
0 besltst, der nun verglichen wird mit den Schwellwert 1 für die niedrigste Ordnung,
um zu bestimmen, ob x1 den Wert 1 oder 0 haben sollte. In jeder Ordnung i, in der
der laufende Wert von A (oder A1.) geringer ist als der Schwoliwert für diese Ordnung,
wird xi gleich O gesotzt, und es wird keine Verringerung des laufenden Wertes für
A vorgenommen, der dann mit den Schellwerten der niedrigeren Ordnungen (wenn solche
vorhanden sind) verglichen wird, um die nachstniodrigere Ordnung aufzufinden, in
der x gleich 1 gesetzt werden kann usw. bis zum Ende der Datenfolge.
-
Als Ergebnis dieses Verfahrens hat man eine dk-begrenzte Datenfolge
xn, xn-1, ... x3, x2, x1 erhalten, in der die rekursiv gewichtete Funktion
gleich ist An, dem Anfangswert von A. Es ist möglich, eine Reihe solcher dk-begrenzton
Datenfolgen zu erhalten, doren anzahl gleich .tCn) ist, wobei jcdo solche lolge
einen eindeutigen Wort von An hat, dar in einem ontsprechenden Bereich von N(n)
ganzen Zahlen liegt, die sich zwischen den oben angegebenen Minimal- und Maximalwerten
MIN und MAX erstrecken. Da der Bereich der ganzen Zahlen zwischen dem minimalwert
MIN und dem Maximalwert MAX als Eingangsdaten dann nicht zweckdichlich ist, wenn
der minimalwert MIN größer als 0 ist, wird ein neuer Bereich aufeinanderfolgender
ganzer Zahlon B von O bis N(n)-1 definirt. Eine einfache Bezichung
besteht
zwischen diesen beiden Zahlenmengen. J).h. A oder An 1 MAX-B, abhängig davont ob
man an einer Verschlüsselung durch direkte Übersetzung interessiert ist oder an
einer Verschlüsseiung der entgegengesetzten Art. B wird dann die Lingangse zahl
für das Verschlüsselungsverfahren oder die Ausgangszahl fflr das Entschlösselungsverfahren,
je nach dein.
-
Die Erfindung ermöglicht es, daa jede ganze Lingangszahl 13, die einen
Wert in dem Bereich von 0 bis N(n)-1 besitzt, leicht in eine dk-begrenzte Datenfolge
von n Binärziffern verschlässelt wird, um die Anforderungen jedes Aufzeichnungs-
oder Übertragungskanales hinsichtlich der Begrenzungen der Lunge einer Reihe aufeinanderfolgender
gleicher Binärziffern der verschlässolten Datenfolgen zu erfüllen, die ihm zugeführt
werden. Umgekehrt kann eine solche dk-begrenzte Datenfolge zur Wiedergewinnung der
ursprünglichen Eingangszahl B leicht entschlüsselt werden. Datenblocks, die bezüglich
der Länge einer Reihe aufeinanderfolgendergleicher Binärziffern beschränkt sind,
könnon miteinander kombiniert werden, um Nachrichten oder Datenströme jeder gewünschton
Länge zu übertragen.
-
Der erfindungsgemäße Vorschlüsselor für das Umsetzen einer ausgewahlten
ganzen Zahl aus einer Reihe aufeinanderfolgender ganzor Zahlen in eine sogenannte
dk-begrenzte Folge von n Binärziffern, in der die Anzahl der aufeinanderfolgenden
Nullen zwischen zwei Einsen wenigstens d und höchstens k beträgt und wobei die Anzahl
der verschiedenen dk-begrenzten Folgen der Länge n mit N(n) bezeichnet wird, wobei
N allgemein die Anzahl der verschiedenen dkbegrenzten
Folgen angibt,
die eine Länge besitzen wie sie durch die auf N folgende Zahl angegeben wird, vorausgesetzt,
daß N(j)=O für jeden Wert j 0 und N(O) : 1 ist gekennzeichnet durch a) ein erstes
Addierwerk, in dem aus der umzusetzenden ganzen Zahl B durch Verknüpfung mit einem
festen Wert eine Zahl A mit dem Anfangswert An gebildet wird, die entweder gleich
ist einer ausgewählten ganzen Zahl aus einer vorgegebenen Reihe ganzer Zahlen oder
mit ihr in einer mathematischen Beziehung steht, b) eine Schwellwert-Vergleichsschaltung
für jede der N Binärstellen zum Vergleich des jeweiligen Anfangswertes An der Zahl
A mit einem dieser Binärstelle zugeordneten Schwellwert, wobei für die den Schwellwert
der höchsten Stelle die Beziehung
für den der niedrigsten Stelle die Beziegilt und die Schwellwert-Vergleichsschaltungen
die höchste Stelle ermitteln, in der der Anfangswert An den Schwellwert für diese
Stelle erreicht oder überschreitet, c) eine logische Einheit, die die Binärziffer
xtl in derjenigen höchsten Stelle erzeugt, in der der jeweilige Wert von A den Schwellwert
für diese Stelle erreicht oder überschreitet, d) eine Modifizierschaltung für jede
Stelle t mit Ausnahme der niedrigsten, in der die erzeugte Ziffer xt-l ist, um für
die nächstniedrigere Stelle (t-t) einen neuen Wert tAt 1) von A zu erzeugen, der
von dem Wert At der vorhergehenden Stelle um den Betrag N(t-1) vermindert ist, wobei
die Schwellwert-Vergleichsschaltungen den jeweils verminderten Wert von A in jeder
Stelle mit den Schwellwerten für die betreffende Stelle und die niedrigeren Stellen
verglelchen, um die höchste Stelle zu beu stimmen, in der A den Schwellwert für
diese Stelle erreicht
oder überschreitet, so daß die logische Einheit
eine Binärziffer z=1 für diese Stelle erzeugt, und die Modifizierschaltung don Wert
von A weiter verringern kann, bis alle Stellen durchlaufen sind und die logische
einheit die Binärziffer x.O für jede Stelle erzeugt, für die keine Binärziffer x=1
erzeugt wurde, so daß die Binärziffern xn, ...x3, x2, x1 der dk-begrenzten binären
Datenfolge aus n Ziffern eindeutig dein Anfangs wert An der Zahl A entsprechen.
-
Die Erfindung wird im folgenden in Vorbindung mit den Zeichnungen
näher erläutert, von denen zeigt bzw. zeigen Fign. 1A bis 1C in der in Fig. 1 angegebenen
Zusammensetzung ein allgemeines Blockschaltbild einos Verschlüsselers
gemäß
der Erfindung; Fign. 2A bis 2C in der in Fig. 2 angegebenen Zusammensetzung ein
Blockschaltbild eines Verschlässelers der allgemein in den Fign. lA bis tC angegebenen
Art, der für den Fall entworfen ist, daß n=8, d=1 und k=3; Fig. 3 eine Tabelle all
der dk-begrenzten verschlässelten Datenfolgen, in die eine vorgegebene Menge von
Eingangszahlen B in dem speziellen Fall verschlüsselt werden kann, bei dem n=8,
d=1 und k=3; Fi. 4 ln allgemeines Blockschaltbild einer Entschlüsselungsanordnung
gemäß der Erfindung, welche zusammen mit einem Verschlüsseler nach der in den Fign.
lA bis 1C gezeigten Art . zusammenarbeitet; Fig. 5 ein Bl9ockschaltbild eines Entschlüsselers
nach Art der Fig. 4, der speziell für den Fall entworfen werde, daß n=8, d=1 und
k.3.
-
Das allgemeine Ausführungsbeispiel für das Verschlüsselungsprinsip,
das in den Fign. ln bis 1C dargestellt ist, dient dazu.
-
eine Menge von N(n) aufeinanderfolgenden Eingangszahlen B in eine
entsprechende menge von N(n0 dk-begrenzten binär verschlüsselten Polgen von N Ziffern
umzusetzen, wobei jede dioser Folgen eindeutig einer gegebenen Eingangszahl B entspricht.
Dor Wert von N(n) kann aus den vorgegebenen Werten für n, d und k angegeben werden.
Als ein spezielles Beispiel, das im folgenden genauer beschrieben wird in Verbindung
mit den Fign. 2A bis 2C sei angenommen, daß n=8, d=1 und k=3. Durch Einsetzen der
gegebenen Werte von d und k in die Gleichung 3 erhält man die folgende Formel: N(n)
+ N(n-4) + N(n-8) + ...=N(n-1) + + N(n-5) 3 .. at Für die vorliegenden Zwecke wird
n als eine Variable angesehen.
-
Indem, beginnend mit n=0 und endend mit n=8 für n aufeinanderfolgende
wachsenden Zahlenwerte eingesetzt und diejenigen Fälle unberücksichtigt bleiben,
in denen die n zugeordnete Zahl negativ wird, erhält man die folgende Menge von
Gewichtswerten für den Fall, in dem d=1 und k=3: N(0) = 1 N(1) = 2 N(2) = 3 N(3)
= 4 N(4) = 7 N(5) = 10
N(6) = 15 N(7) = 22 N(8) = 32 Die Werte
von N(n) für verschiedone Werte von n sind bedoutsam und auf sie wird in der nachfolgenden
Beschreibung eines Ausführungsbeispieles für ein Verschlüsselungs-Entschlüsselungssystem
(Fig. 2A bis 2C und 5) Bezug genommen, für das die speziellen Werte von n=8, d=1
und k=3 gewält wurden. Jeder der oben aufgeführten "N"-Werte gibt die Anzahl der
Wahlmöglichkeiten wieder, die einem beim Aufzeichnen einer Menge von N(n) Eingangszahlen
in eine entsprechende Menge von eindeutigen dkbegrenzten verschlüsselten Datenfolgen
zur verfügung stehen in den Fnll, in dem dwl und ks3 ist. In einigen Fällen geben
diese "N"-Werte auch die "Gewichte" an, die den verschiedenen Binärstellen für das
Festsetzen der Schwellwerte beim Verschlüssoln und für das richtige Gewichten der
vorschlüsselten Ziffern beim Entschlüsseln (,das allgemein in der Fig. 4 und genauer
in der Pig. s dargestellt ist) beigegeben worden. All dies wird in einzelnen in
folgenden genauer erklärt.
-
Die Wien. 1A bis 1C zeigen das Vrschlüsselungsprinzip für den allgemeinen
Fall, in den n, d und k unbekannt sind. Man wuhlt eine ringnngszahl B aus, die zu
verschlüsseln ist, aus einer Reihe von aufeinanderfolgenden Zahlen in der: Bereich
von 0 bis N(n)-1. Diese Eingangszahl B wird einem Addierwerk 11 zusammen
mit
einer modifizierenden Zahl zugeleitet, in dem die Eingangszahl B in eine entsprechende
Zahl A umgesetzt wird die eine ähnliche Stalle in einer Serie von Werten einnimmt,
die von dem Minimalwert MIN bis zum Maximalwert MAX erreichen, wie sie durch die
Cloicisungen 4 und S definiert sind. Für einen mit direktor Obersetzung arbeitenden
Verschlüsselor (wie or für das Ausführungsbeispiel angenommen wird,) wird dem zweiten
Eingang des Addierwerkes 11 der Wert fliN zugeführt, der , wenn er zu B addiert
wird, den Anfangswert An der gewichteten Summo A erzeugt.
-
Für einen Vorschlüsselor der umgekchrten Art wird dein zweiten Eingang
des Addierwerks 11 der Wert MAX zugeführt und am Ausgang des Addierwerkes 11 erscheint
der Wert MAX-B. Die Wahl hängt davon ab, ob man wünscht, daß der niedrigst Wert
von D der dk-begrenzten Datenfolge niodrigsten oder höchsten Wertes entspricht.
Im vorliogenden Fall wird angenommen, daß die dk-begrenzte Datenfolge niedrigsten
Wertes der Eingangszahl ß niedrigsten Wertes entspricht. Davor ist in vorliegenden
all An gleich B+, MIN, wie das in Fig. 1 dargestellt ist.
-
Anschließend wird ein Test durchgeführt, um festzustellen, ob von
ausreichender Größe ist, ua das Vorhandensein einer 1 in der n. oder hUchston ordnung
der entsprechenden dk-begrenzten Datonfo1go zu erfordern. Mit anderen Worten wird
ein Test gomacht, um zu bestimmen, ob die Ziffer xn in der n. Ordnung der entsprechenden
dk-begrenzten Datenfolge eine 1 oder eine 0 sei sollte. Dazu wird der Wert An einer
Schwellwert-Vergleichssaltung
13 für di. ne Ordnung zugeführt,
die von den Wort t den in der Fig. 1 für die Schwellwert-Vergleichsschaltung 13
angegebenen Schwellwert subtrahiert. Die Diffonenz Tn zwischen An und dem genannten
Schwellwert wird einer logischen Einhoit 14 zugeführt, die bostinot, ob Tn kloiner
als 0 ist. Wenn S kleiner als 0 ist, liefort die logische Einheit 14 ein "Ja"-Ausgangssignal,
das anzeigt, daß die Ziffer xn der n. Ordnung der dkbogrenzten Datenfolge 0 ist.
Wenn die logische Einheit 14 ein "Nein"-Ausgängssignal liefert, zeigt das a@, daß
die Ziffer x1 gleich 1 ist. Abhängig davon, ob An durch den angegebenen Schwellwert
für die n. Ordnung übertroffen oder nicht übertroffen wird* wird die Ziffer xn in
der n. Ordnung der entsprechenden dk-begrenzten Datenfolge zu 0 oder zu 1 gemacht.
-
Wenn xn=1 wird oin geeignotos, von der logischen Einheit 14 erzeugtes
Signal als Eingangssignal oinem Multiplizierwerk 16 zugeführt, das in einer Modifizierschaltung
17 für die n. Ordnung enthalten ist. Das Multiplizierwerk 16 multipliziert xn mit
dem Gewichtsfaktor N(n-1) und führt das Ergebnis als negatives eingangssignal einem
Addierwerk 19 in der Modifizierschaltung 17 zu. Der lanfende Wert An der gewichteten
Summe A wird @b@nfalls als positives Eingangssignal dom Addierwerk 19 zugeführt,
das daraufhin von dem Wert An den gewichtes Wert XnN(n-1) subtrahiert, um einen
neuen laufenden Wert An-1 von A zu erhalten. Wenn die Ziffer xn Null war, dann ist
natürlich An-1 identisch
mit An, sonst ist An-1 um den Betrag des
Gewichtes N(n-1) das der Modifizierschaltung für die n. Ordnung zugeordnet ist,
kleiner als An.
-
Die einheiten 11, 13, 14, 16 und 19 sind von üblichem Aufbau, und
so entworfen, um die dargestellten spoziellen Funktionen auszuführen. Die Modifizierschaltung
17 ist lediglich eine tot bination eines Multiplizierwerkes 16 und eines addierwerkes
19.
-
Eine ähnliche Menge arithmotischor und logischer Einheiten ist für
jede der n Ordnungen (mit Ausnahme der niedrigsten Ordnung) der dk-begrenzten Datenfolge
vorgesehen, in die die ursprüngliche Eingangszahl B verschlüsselt wird. Die für
die niedrigsto Ordnung der Datenfolge ist lediglich einfache 1- oder O-Prüfung erforderlich
wie noch erläutert wird.
-
An diesem Punkt des Verschlüsselungsverfahrens wird der Anfangswert
An auf einen neuen laufenden Wort An-1 verringert, (der gleich An sein kann oder
nicht, wie vorher angogebon wurde, je nach dem, ob xn den Wert 0 oder 1 @at). Der
laufende Wert An-1 wird num einem ähnlichen Schwellwert-Vergleich unterworfen, wie
das bei 20 in Fig. 1A angegeben Ist. Der Ausgangswert TS-1 wird durch eine logische
Einheit 21 geprüft, um festzustellen, ob er kleiner als 0 ist oder nicht. Abhängig
von dieser rsafung wird der Wert der Ziffer xn-1 in der dk-begrenzten Folge zu 0
oder zu 1. Wenn der Wort 1 ist, dann veranlaßt die Modifizierschaltung 23 für diese
Ordnung (Fig. 1B) daß der Wert An-1 UM
das Gewicht N(n-20 reduziert
wird, um einen neuen Wert An-2 zu ergeben. Wenn xn-1 den Wert 0 annimmt, dann ist
Wert An-2 gleich An-1.
-
In ähnlicher Weise wird der laufende Wert A getestet und, falls das
notwendig ist in jeder der iibrigen Ordnwtgon modifiziert bis hinunter zur zweiten
Ordnung der dk-begrenzten Datenfolge.
-
In jeder dieser Ordnungen, z.B. in der Ordnung t, wird der Faingangswert
At in einer Schwellwert-Vergleichseinheit 26 (Fig.
-
1B) mit einem Schwellwert # N [(t-1)-i (k+1)] verglichen und i=0 die
Differenz Tt wird durch eine logische Einheit 28 geprüft, um zu bestimmen, ob die
Ziffer Xt in der t. Ordnung der dkbegrenzten Datenfolge 1 oder 0 ist. Abhängig von
dieser letzteren Prüfung wird der Wert At durch die Modifizierschaltung 30 modifiziert,
um einen neuen laufenden Wert At-1 ZU erzeugen.
-
Wenn die zweite Ordnung der dk-begrenzten Datenfolge beim Verschlüsseln
erreicht ist, wird der laufende Wert A2 mit dem passenden Schwellwert in der Schwellwert-Vergleichsschaltung
32 (Fig. lC) verglichen, und die zugehörige logische reinheit 34 bostirint den geeigneten
1- oder O-Wert für die Ziffer x2 der zweiten Ordnung der dk-begrenzten Datenfolge.
Eine Modifizier-Schaltung 36 verringert dann den laufenden Wort von Al auf A1, Schließlich
wird in der niedrigsten ordnung der Datenfolge ein einfacher Vergleich durch die
Schwellwert-Vergleichsschaltung 38 durchgeführt, um festzustellen, ob A1 von dem
Wert 1 übertreffen
wird oder nicht, der der Schwellwert für die
erste Ordnung ist. Wenn A1 kleiner nls 1 ist, wird die Ziffer x1 der ersten Ordnung
zu ü. Im andern Fall erhält sie durch die logische Einheit 40 den w4rt 1.
-
Das endgültige Ausgangssignal der in den Fign. 1A bis 1C dargestellten
Verschlüsselungseinrichtung ist eine dk-begrenzte Datenfolge, die aus .% Ziffern
x1 bis Xn besteht. Je großer der Wert von n ist, umso größer ist der maximale Wert
der Eingangszahl B, die in die gewünschte dk-begrenzte Datenfolge verschlüsselt
werden kann. Mit wachsendem Wert von n, wird jedoch der Aufbau der Verschlüsselungseinrichtung
ebenfalls komplexer, so daß man einen Kompromiß schließen muß zwischen dem Wunsch
nach langen Datenblöcken und der Notwondigkeit, übermäßige komplexheit beim Entwurf
der Verschlüsselungseinrichtung zu vermeiden.
-
Zum Verschlüsseln einer Eingangszahl, deren Wert die gewählte obere
Grenze von N(n) überschreitet, zur man dieso Zahl in eine Reihe von arithmetischen
Komponenten auflösen, von denen jede in eine dk-begrenzte Datenfolge der Länge n
verschlflsselt werden kann. Die erhaltenen Folgen werden dann hintereinander übertragen,
um die endgültige verschlüsselte Datenfolge zu orhalten, die die ursprüngliche Eingangszahl
darstellt. rs ist offensichtlich, daß man nicht willkürlich eine Reihe von dk-begrenzten
Datenfolgen in beliebiger Reihenfolge hintereinander verschlüsseln kann, ollno dns
die Möglichkeit bcstoht, daß die dk-Bedinungen
zumindest in einigen
Fällen an den Grenzen der hintereinander übertragenen Datenfolgen verletzt werden.
Wenn die Blocklänge n genügend groß ist, kann eine kurze Folga von Pufferziffern
zwischen aufeinanderfolgenden Datenblocks eingefügt werden, um die dk-Grenzwertbedingungen
zu crfnllen, ohne daß die Wirksam keit dos Systems wesentlich herabgesetzt wird.
-
Es läßt sich zeigen, dau, wenn k gleich oder größer als 2d ist, was
in der Praxis der Normalfall ist, die Anzahl der erforderlichen Ziffern für die
Pufferfolge d+2 beträgt. In dieses Fall kann eine Vorausschaueinrichtung erforderlich
werden, um zu bestimmen, wie die Anordnung dieser d+2 Pufforziffern erfolgen muß,
um die dk-Grenzwertbedingungen zwischen irgendeinem Paar aufeinanderfolgender dk-begrenzter
binärer Datenfolgen zu erfüllen. Bin alternatives Schema, bei dem eine Vorausschaueinrichtung
nicht erforderlich ist, beruht darauf, nur die dk-begrenzten Datenfolgen zu verwenden,
die mit der Ziffer 1 beginnend wodurch zwar der Wirkungsgrad der Verschlüsselungseinrichtung
verringert wird, aber ebenso die Anzahl der erforderlichen Pufforziffern auf d+1
vermindert wird. Für die speziellen Fällen, in denen d=0 (k-begrenzte Datenfolge)
und k=unendlich (d-begrenzte Datenfolge ist das Pufferproblem sehr einfach. In dein
Fall der k-begrenzton Datenfolgen erfüllt das einfügen einer Ziffer 1 zwischen den
Blöcken die k-Grenzwertbedingung. Für d-begrenzte Datenfolgen wird die d-Grenzwertbedingung
durch Einfägen von d Nullen zwischen den Blicken erfüllt.
-
Das Entschlüsselungsverfahren ist vorhältnismäßig einfach. In Fig.
4 ist die allgemeine Art eines Entschlüsselers dargestellt.
-
Die Binärziffer x in jeder Ordnung der dk-begrenzten Datenfolge wird
mit einem geeigneten Gewichtsfaktor multipliziert, und die Produkte worden addiert,
um die gewichtete Summo An zu erhalten, die dann in die ursprüngliche Eingangszahl
B durch (in diesem Fall) Subtraktion des minimalen Wertes MIN von An umgesetzt wird.
-
Für jede Ordnung t der dk-begrenzten Datenfolge wird die Ziffer xt
in der betreffenden Ordnung mit dem Gewicht N(t-1) für diese Ordnung in einem Multiplizierwerk
50 multipliziert, und das Produkt ofnon Addierwerk 52 zusammen ttltt den Produkten
der in den anderon Ordnungen durchgefährten Multiplikationen zugeführt.
-
Dies ergibt die gewichtete Summe An, von der der minimale Wert MIN
subtrahiert wird, ua B zu ergeben, die ursprüngliche Eingangszahl, die durch die
dk-bogrenzte Datenfolge dargestellt wurde.
-
Für einen Verschlüsseler vom Umkehrtyp würde An von dem Maximalwert
MAX subtrahiert werden, um B zu erhalten.
-
Es wird nun ein Ausführungsbeispiel eines Verschlüsselungs-Entschlüsselungssystem
erläutert, das für den speziellen Fall entworfen wurde, in dem n=8, d=1 und k=3.
Die Tabelle in Fig. 3 zeigt, wie eine Reihe von Eingangsziffern B, die aufeinanderfolwende
Werte von 0 bis 31 bositzon, in eine entsprechende Menge von 32 dk-begrenzten Datenfolgen
verschlüsselt werden kann.
-
Es wird angenommen, daß das Verschlüsseln durch Obersetzen erfolgt.
Der minimale Wert MIN, der sich aus der Gleichung 4 ergibt,
beträgt
MIN = N(4) + N(0) = 8 Der Wert der Eingangszahl B wird in jedem Falle um 8 erhöht,
um den Wert A8 der gewichteten Summe zu erhalten, der zu verschlüsseln ist. Die
Zifforn der entsprechenden dk-begrenzten Dal tenfolge sind in den Spalten x1 bis
x8 in Fig. 3 angegeben.
-
Die Fign. 2A bis 2C zeigen dem Verschlüsseler von Übersetzungstyp
für den Fall, in dem n=8, d=1 und k=3. Die Schwellwerte.
-
welche für die verschiedonen Schwellwert-Vergleichsschaltungen benutzt
werden, und die Multiplikationsfaktoren für die verschiedenen Multiplizierwerke
können leicht anhand der Formeln bestimmt werden, die in den Fign. 1A bis 1C, welche
das allgomeine Entschlüsselungsschema darstellen, angegeben sind, in der achten
Binärstelle wird beispielsweise A8 verglichen mit einem Schwellwort von 27 und wenn
As diesen Wert erreicht oder überschreitet.
-
dann wird A@ um 22 reduziert, um don Wert A7 zu orgebon. In diesen
Fall wird der I:ort der Ziffer x8 der achten Stelle in der dk-begrenzten Datenfolge
als 1 gespeichert. Wenn A8 kleiner als der Schwellwert von 27 ist, dann wird x8
zu 0 gesetzt und in diesem Falle ist A7=A8. Das gerade beschriebene Verfahren wird
für jede der restlichen Stellen wiederholt, wobei die go@igneton Schwellwerte und
Werte für die Modifizierschaltungen vorwendot werdon wie das in den Fign. 24 bis
2C dargestellt ist,
um die Werte der restlichen Ziffern x1 bis
x7 der dk-begrenzten Datenfolge zu bestimmon, die durch dieses Verschlüsselungssystem
erzeugt wird.
-
Wenn die dk-begrenzte verschlüsselte Datenfolge, die durch das in
den Fign. 2A bis 2C dargestellte Vorschlüsselungsverfahren erzeugt wird, entschlüdsselt
werden soll, wird sie dem in Fig. 5 dargestellten Entschlüsseler zugeführt. Die
Ziffern x1 bis x8 werden mit den passenden Gewichtsfaktoren (, deren Werte aus den
Formeln ab:olcitet werden können, die für das in der Pig. 4 dargestellte allgemeine
Entschlässelungssystem angegeben sind,) multipliziert. und die erhaltenen gewichteten
Produkte werden addiert, um eine gewichtete Summe (A8) zu erhalten, die dann um
8 (den minimalen Wert MIN) vermindertwird, um die ursprüngliche Eingangszahl B zu
erhalten.
-
Das offenbarte Verschlüsselungssystem ist gut geeignet für die Verwendung
in Obertragungs- oder Speichersystemen, die z.B.
-
magnetische oder lichtempfindliche Medien verwenden, um eine maximale
Vordichtung der Daten zu erhalten, ohne daß sich die Symbole gegenseitig stören,
wobei es ermöglicht wird, daß die Synchronisation aufgrund einer von don Daten abhängigen
Taktgabe aufrechterhalten wird. Diese Ziele worden durch das beschriebene Codenufzeichnungsprinzip
erreicht, das es ermöglicht, daß normale Eingangszahlen durch entsprechende Datenfolgen
mit begrenzter Länge einer Reihe aufeinanderfolgender gleicher Binarziffern
dargestellt
werden, in denen die geeigneten Grenzbedingungen für "d" und "k" beachtet werden,
um eine gegenseitige Störung dor symbole zu vorhindern und die von den Daten abhängige
Synchronisation aufrecht zu erhalten.
-
Das Feststellen einer "1" in einer dk-begrenzten Datenfolge der beschriebenen
Art bodoutot, dna die nächsten d Ziffern dieser Datenfolge Nullen sein müssen. Diese
Tatsache kann dazu beuutzt werden, um die Schwellwert-Vergleichs- und/oder Gewichtsfunktionen,
die don d Stufen zugeordnet sind, (welche in jeden Fall unter diesen Bedingungen
unwirksam sind (durch umgehen dieser Stufen zu liiainioren. Dies stellte ein. naheliegende
Ausdehnung der Lehre der Erfindung dar.
-
Es ist klar, daß die numerischen Bezeichnungen "1" und "0", wie sie
in der Beschreibung verwendet wurden, nur ein. relative Bedeutung bestizen. Die
Erfindung findet Anwendung auf ein solches Verschlüsselungssystem, in dem die Information
übermittelt wird durch Feststellen derjenigen Stellen in der Datenfolge, an denen
Obergänge zwischen zwei entgegengesetzten Pegeln erfolgen.
-
Ob diesen Pegelworten oder den Obergängen zwischen ihnen die ziffernmäßige
Bedeutung von "1" oder "0" gegeben wird, ist unwesentlich.
-
Die dk-begrenzten Datenfolgen, welche als Ausgangssignale der beschriebenen
Verschlüsselungseinrichtung erscheinen, oder die
als Eingangssignale
der offenbarten Entschlüsselungseinrichtung zugeführt werden, sind zur Verwendung
in einem Codiersystem bestimmt, für das Oborgiingo zwlschon zwei Pegel charakteristisch
sind, wie z.B. beim NRZI-Verfahren, bei dem dem Übergang eines Signales zwischen
vorgegebenen Pogeln eine ziffernmäßige Bedeutung zukommt, bei dem aber den Signalpegoln
solbst keine absoluten Werte zugeordnet sind. Es sind Fälle donkbar, in denen es
erwänscht ist, von einem Verschlüsselungssystem für Datenfolgen mit begrenzter Länge
einer Reihe aufeinanderfolgender gleicher Binärziffern der eben erwähnten Art auf
ein solches überzugehon, wie es beispielsweise das nach dem NRZ-Vorfahren arbeitonde
ist, in dem den Signalpegeln die Werto "1" und "0" zugeordnot sind oder umgekehrt.
Wenn xn, xn-1, ... x1 eine verschlüsselte Ddtenfolge darstellt, bei der die Grenzen
für die minimale und maximale Länge einer Reihe aufeinanderfolgender gleicher Binärziffern
d und k sind und bei der die eine der beiden Binärziffern durch einen Obergang zwischen
zwei Pegel dargestellt wird, und wenn yn, yn-1, ... y1 eine entsprochende verschlüsselte
Datenfolge darstollt, bei der eine Binärziffor nicht durch einen übergang zwischen
zwei Pegeln dargestellt wird, dann läßt sich zeigen, daß: xi = yi (+) yi-1 oder
yi = yi-1 (+) xx Dabei ist "(+)" das Symbol für eine Module-2-Addition und der
Grenzwert
y0 ist ein binärer Bezugszustand. Die Grenzen für die minimale und die maximalen
Längen einer Reihe aufeinanderfolgender gleicher Binärziffern der y-Datenfolge sind
unter diesen Bedingungen d+1 und k+1.
-
Die hier offenbarten Prinzipien erhöhen in starkem Maße die vielseitige
Verwendbarkeit solcher Datenaufzeichnungs- oder übertragungssystemo, in denen aufgrund
großer Datenverdichtung und der Anwendung einer von den Daten abhängigen Taktgabe
es vorteilhaft ist, Datenfolgen mit begrenzter Länge einer Reihe aufeinanderfolgender
gleicher Binärziffern zu verwenden. Solche Datenfolgen können leicht mittels der
offenbarten Einrichtungen vor-und entschlüsselt werden und ermöglichen dadurch wirksame
Erleichterungen für das Verarbeiten von Daten für solche Systeme.