Cryptography Reference
In-Depth Information
a) Welche Kodes sind eindeutig dekodierbar?
b) Welcher Kode entsprechend a) hat die kleinste Kodewortlänge?
c) Wie groß ist die Koderedundanz des unter b) ermittelten Kodes?
2. Man beweise folgenden Satz, der zur Ableitung der Gl. (3.7) verwendet wurde:
Wenn eine diskrete Quelle
X
die Entropie
H
(
X
)
hat, dann gilt für ihre
m
-fache
Erweiterung
H
X
[
m
]
)=
.
Hinweis:
Lösungsansatz siehe „Verbundquellen“!
(
mH
(
X
)
Abschn. 3.4.2.1
und
3.4.2.2:
SHANNON-FANO- und HUFFMAN-Verfahren
1. Eine diskrete Quelle mit den Zeichenauftrittswahrscheinlichkeiten
(
p
(
x
i
)) = (0
,
15 0
,
14 0
,
30 0
,
10 0
,
12 0
,
08 0
,
06 0
,
05)
ist optimal zu kodieren
a) nach dem SHANNON-FANO-Verfahren,
b) nach dem HUFFMAN-Verfahren.
Zum Vergleich der Optimalkodes sind die Koderedundanzen zu bestimmen.
2. Ein um den Amplitudenwert Null symmetrisch verteiltes analoges Signal sei im
positiven wie im negativen Bereich jeweils in sieben Intervalle unterteilt. Die Auf-
trittswahrscheinlichkeit der Amplitudenwerte in diesen Intervallen soll mit stei-
genden Absolutwerten nach folgender Beziehung abnehmen:
p
x
i
+1
)=
2
(
p
(
x
i
)
für
i
=1
,
2
,...,
5
,
wobei
p
(
x
7
)=
p
(
x
6
)
.
Bestimmen Sie
a) einen HUFFMAN-Kode für diese Quelle,
b) die mittlere Kodewortlänge,
c) die Differenz der mittleren Kodewortlänge gegenüber der Länge eines gleich-
mäßigen Kodes!
3. Der Wertebereich eines Signals von 0 bis 999
mV
in Stufen von 1
mV
soll in vier
Intervalle mit folgenden Auftrittswahrscheinlichkeiten unterteilt werden können:
0
...
49 :
p
(
x
1
)=0
,
60
50
...
199 :
p
(
x
2
)=0
,
25
200
...
499 :
p
(
x
3
)=0
,
10
.
Innerhalb jedes Intervalls sind gleichwahrscheinliche Signalwerte anzunehmen.
Es ist folgende Quellenkodierung vorgesehen:
-
Optimalkode nach SHANNON-FANO für die Intervalle,
-
gleichmäßige Kodes für die Signalwerte innerhalb der Intervalle.
Zu berechnen sind:
a) Quellenentropie,
b) mittlere Kodewortlänge (für den gesamten Quellenkode),
c) Verringerung der Redundanz durch die vorgesehene Quellenkodierung gegen-
über einem vollständig gleichmäßigen Kode.
500
...
999 :
p
(
x
4
)=0
,
05
