Cryptography Reference
In-Depth Information
Abschn. 3.4.2.3
: Optimalkodierung erweiterter Quellen
1. Eine Binärquelle mit den Auftrittswahrscheinlichkeiten
p
(
x
1
)=0
,
9
und
p
(
x
2
)=
0
der unabhängigen Zeichen ist nach dem SHANNON-FANO-Verfahren zu ko-
dieren. Berechnen Sie die Koderedundanz für die Fälle
a)
m
,
1
=1
,
b)
m
=2
,
.
2. Gegeben sei eine diskrete Informationsquelle mit drei unabhängigen Zeichen, die
mit den Wahrscheinlichkeiten
c)
m
=3
(
p
(
x
i
)) = (0
,
6
,
3
,
1)
auftreten.
sind nach dem HUFFMAN-
Verfahren zu kodieren und durch die Koderedundanz zu bewerten!
3. Die Information einer Binärquelle mit den Auftrittswahrscheinlichkeiten
p
Diese Quelle und ihre Erweiterung mit
m
=2
(0) =
0
soll gespeichert werden, wobei der Speicherbedarf durch eine
Optimalkodierung um mindestens
,
8
und
p
(1) = 0
,
2
25 %
gegenüber dem Bedarf bei einer gleich-
mäßigen Kodierung verringert werden soll.
a) Bestimmen Sie einen Optimalkode, der diese Forderung erfüllt!
b) Wie groß ist die tatsächliche Reduzierung durch den Optimalkode?
c) Wäre durch weitere Optimierung auch eine Reduzierung um
30 %
möglich?
(Begründung!)
Abschn.3.4.2.4
: Optimalkodierung von MARKOW-Quellen
1. Eine stationäre MARKOW-Quelle sei durch die Zustandswahrscheinlichkeiten
(
19)
und dem folgenden Zustandsgraphen (ein mit Übergangswahrscheinlichkeiten kan-
tenbewerteter Graph, Bild 3.5.1) gegeben:
p
(
x
i
)) = (0
,
14 0
,
29 0
,
38 0
,
x
2
0,2
0,6
0,4
0,5
0,1
0,3
x
x
0,1
0,3
1
3
0,1
0,2
1
0,2
x
4
Bild 3.5.1
Zustandsgraph
a) Bestimmen Sie einen Optimalkode für diese Quelle.
b) Berechnen Sie die Koderedundanz.
c) Ermitteln Sie die Verkürzung der Kodewortlänge gegenüber einem Optimal-
kode, der nur die Zustandswahrscheinlichkeiten berücksichtigt!
