Cryptography Reference
In-Depth Information
Ein Kode kann auch als gerichteter Graph in Form eines
Kodebaumes
[de-
coding tree] dargestellt werden (Bild 3.2.1). Dabei wird jedes Kodewort durch
einen von der Baumwurzel ausgehenden Pfad bis hin zu einem Endknoten be-
stimmt.
Kommakode:
0
1
0
1 0
1 1 0
1 1 1
l
=1
0
1
0
1
l
=2
0
1
0
1
0
1
0
1
Endknoten
l
=
l
max
=
3
Bild 3.2.1
Kode-Beispiel mit entsprechendem Kodebaum
Um die Dekodierbarkeitsbedingung gemäß Definition 3.2.1 zu erfüllen, darf es
auf jedem Pfad selbstverständlich nur einen Endknoten geben.
Die Stufen des Kodebaumes bestimmen die verschiedenen Kodewortlängen
l
=1
,
2
, ..., l
max
.
l
max
Knoten,d.h.,eskönnen
2
l
max
Kodewörter
Auf der Stufe
l
max
gibt es
2
gleicher
Länge gebildet werden.
Beim
ungleichmäßigen
Kode wird die Anzahl zulässiger Kodewörter durch je-
den Endknoten reduziert, der auf einer Stufe
l<l
max
liegt. Anders ausge-
drückt: Unter jedem Endknoten, der auf einer Stufe
l<l
max
liegt, befinden
sich
(2
l
max
−l
)
„ungenutzte“ Knoten auf der Stufe
l
max
.
Summiert man diese Knoten für jedes der
N
Kodewörter der Länge
l
i
für
i
=1
,
2
, ..., N
, so erhält man die Bedingung
i
=1
2
N
l
max
−l
i
l
max
.
=2
l
max
und unter Berücksichtigung des Falls, dass ein
Kode nicht alle möglichen Endknoten nutzt, entsteht die von L.G. KRAFT
gefundene Ungleichung
Nach der Division durch
2
N
2
−l
i
≤
1
.
(3.1)
i
=1
Die Aussagefähigkeit dieser Ungleichung wird im folgenden Beispiel untersucht.
