Cryptography Reference
In-Depth Information
Ein Kode ist eindeutig dekodierbar, wenn man die binäre Empfangsfolge ein-
deutig in Blöcke (Wörter) bestimmter Länge zerlegen und diese den Quellen-
zeichen eindeutig zuordnen kann. Darüber hinaus wird in der Regel gefordert,
dass die Dekodierung unverzögert erfolgen soll: Jedes Wort soll unmittelbar
nach dem Empfang der letzten Binärstelle eindeutig dekodiert werden können.
Die erste Aufgabe bei der Dekodierung ist demnach die Trennung der fortlau-
fenden Empfangsfolge, d. h. das Erkennen der Wortenden. Beim gleichmäßigen
Kode ist dies problemlos, weil alle Wörter gleich lang sind.
Beim ungleichmäßigen Kode ist eine zusätzliche Bedingung für die Erkennung
der Wortenden erforderlich. Diese Bedingung wird von allen ungleichmäßigen
Kodes erfüllt, die die sogenannte Präfix-Eigenschaft besitzen.
Definition 3.2.1 Ein ungleichmäßiger Kode, bei dem kein Kodewort den
Anfang (Präfix) eines anderen Kodewortes darstellt, wird als Kode mit
Präfix-Eigenschaft [instantaneous code] bezeichnet.
X
K1
K2
K3
Beispiel 3.2.1
Das Alphabet einer diskreten Quelle
X enthalte sechs unabhängige Zeichen,
die in nebenstehenden drei Varianten
(K1, K2, K3) kodiert sind.
Betrachten wir diese Kodes hinsichtlich
ihrer Dekodierbarkeit!
x 1
0
0
0
x 2
10
100
10
x 3
110
101
110
x 4
101
110
1110
x 5
1100
1110
11110
x 6
1111
1111
11111
K1: Kode ohne Präfix-Eigenschaft, nicht dekodierbar (d. h., K1 ist kein Kode
entsprechend Definition 3.2.1).
K2: Kode mit Präfix-Eigenschaft, eindeutig und unverzögert dekodierbar.
K3: „Kommakode“, eindeutig und unverzögert dekodierbar.
Zur Entscheidung, welcher der brauchbaren Kodes K2 und K3 geeigneter ist,
sind weitere Kriterien erforderlich.
Die sogenannten Kommakodes bilden eine spezielle Klasse der „Präfix-Kodes“
(s. Beispiel 3.2.1): Jedes Kodewort besteht hier nur aus Einsen und wird mit
einer Null (als „Komma“) abgeschlossen (mit Ausnahme der Kodewörter maxi-
maler Länge, deren letzte Stelle sowohl 0 als auch 1 sein kann). Das „Komma“
wirkt hier wie ein Trennzeichen und erleichtert damit die Dekodierbarkeit des
ungleichmäßigen Kodes. 1
1 Nullen und Einsen können natürlich auch invertiert sein.
Search WWH ::




Custom Search