Cryptography Reference
In-Depth Information
Beispiel 3.2.2
Zur Kodierung einer diskreten Quelle
X
mit
N
=6
unabhängigen Zeichen
soll ein ungleichmäßiger Kode (
l
max
=4
) verwendet werden. Folgende Kode-
Varianten (K1, K2, K3, K4) sind hinsichtlich Dekodierbarkeit in Verbindung
mit der KRAFTschen Ungleichung zu analysieren.
X
K1
K2
K3
K4
x
1
00
00
00
0
x
2
01
01
01
100
x
3
10
10
10
101
x
4
110
110
110
110
x
5
111
1110
1110
1110
x
6
1101
1101
1111
1111
Lösung:
Wir prüfen, ob Präfix-Bedingung (1) und KRAFTsche Ungleichung (2) erfüllt
sind.
K1: (1) nicht erfüllt,
(2) nicht erfüllt, denn
3
·
1
4
+2
·
1
8
+
1
16
=
17
>
1
.
16
K2: (1) nicht erfüllt,
(2) erfüllt, denn
3
·
1
4
+
1
16
=
16
1
8
+2
·
16
=1
.
K3: (1) und (2) erfüllt.
K4: (1) und (2) erfüllt.
Schlussfolgerungen:
Für eindeutig dekodierbare Kodes (K3, K4) ist die KRAFTsche Ungleichung
immer erfüllt.
Wenn die KRAFTsche Ungleichung erfüllt ist, bedeutet das jedoch nur, dass
ein dekodierbarer Kode mit dieser Struktur existiert, aber nicht, dass jede
beliebige Struktur, die diese Bedingung erfüllt, ein dekodierbarer Kode ist.
Ersetzt man in K2 z. B. das Wort (1101) durch (1111), so erhält man den
dekodierbaren Kode K3.
Wir fassen zusammen:
•
Die KRAFTsche Ungleichung ist eine
notwendige
,aber
keine hinreichende
Bedingung für die Dekodierbarkeit.
•
Da die Präfix-Eigenschaft eine
hinreichende Bedingung
ist, reicht es aus,
wenn ein ungleichmäßiger Kode auf die Erfüllung dieser Bedingung geprüft
wird.
