Cryptography Reference
In-Depth Information
Bei unveränderter Quellenentropie entsteht die folgende Koderedundanz:
R
K
=2
,
26
−
1
,
68 = 0
,
58
bit/Zustand .
Die Kodierung vorliegender Informationsquelle zeigt unter Berücksichtigung
der Übergangswahrscheinlichkeiten eine beträchtliche Reduzierung der mittle-
ren Kodewortlänge von
2
,
26
auf
1
,
75
Bit/Zustand
. Die Koderedundanz re-
duziert sich von
0
,
58
auf beachtliche
0
,
07
bit/Zustand
.
Anmerkungen
zur Dekodierung:
Entsprechend
p
(
x
j
|x
i
)
tritt das Kodewort für
x
j
unter der Bedingung auf, dass
unmittelbar davor das Kodewort für
x
i
aufgetreten ist. Deshalb benötigt man
für die Dekodierung den Startzustand, der als erstes Zeichen übertragen wer-
den muss. Desweiteren wird für die eindeutige Dekodierung selbstverständlich
auch die Zuordnung der Teilkodewörter entsprechend der Matrix
(
p
(
x
j
|
x
i
))
be-
nötigt.
Die im Beispiel 3.4.4 gegebene MARKOW-Quelle soll z. B. die Zeichenfolge
x
3
,x
5
,x
2
,x
1
,x
3
,x
4
, ...
ausgeben. Auf der Grundlage der Kodetabellen er-
geben sich folgende Kodewörter:
p
(
x
5
|x
3
)=0
,
30 :
1 0
p
(
x
2
|x
5
)=0
,
20 :
1 1 0
x
2
)=0
,
60 : 0
p
(
x
3
|x
1
)=0
,
50 : 0
p
(
x
4
|x
3
)=0
,
05 : 1 1 1 0
Da die Zeichenfolge mit
x
3
beginnt, muss zuerst
i
=3
(als Kodewort 0 1 1)
übertragen werden, damit der Dekodierer weiß, zu welchem Teilkode das erste
Kodewort gehört. Der empfangene (fehlerfreie) Bitstrom kann dann entspre-
chend den Kodetabellen wie folgt dekodiert werden:
0 1 1 1 0 1 1 0 0 0 1 1 1 0 . . .
xx
p
(
x
1
|
x
3
x
x
x
5
2
1
3
4
Hinweis
:
Aufgaben
s. Abschn. 3.5
3.4.3
Verfahren ohne Kenntnis der Quellenstatistik
(LEMPEL-ZIV-Verfahren)
Dieses Quellenkodierungsverfahren wurde erstmals im Jahr 1977 von A. LEM-
PEL und J. ZIV [LEZ 77] als neue Methode der
verlustfreien
Datenkompression
publiziert.
Der wesentliche Unterschied zur Optimalkodierung auf der Grundlage der
Quellenstatistik kommt vor allem im Prinzip der Redundanzreduktion zum
