Cryptography Reference
In-Depth Information
Aufgrund dieses Teilungsprinzips enthält jeder Teilungsschritt und damit
jedes Kodewortelement die größte Entropie bzw. Informationsmenge.
3. Kodieren nach dem Prinzip, dass der ersten Gruppe (zweckmäßigerweise)
das Zeichen 0 (bzw. 1) und der zweiten Gruppe einheitlich das Zeichen 1
(bzw. 0) zugeordnet wird.
4. Wiederholen der Schritte 2. und 3., und zwar solange, bis jede Teilgruppe
nur noch ein Element enthält.
Bei diesem Verfahren ergeben sich die einzelnen Kodewortlängen zwangsläufig,
wobei entsprechend dem Optimierungsprinzip sowohl ein Auf- als auch ein
Abrunden von ld
p
i
ld
p
i
oder
l
i
=
ld
p
i
.
erfolgt, d. h.
l
i
=
Beispiel 3.4.1
Für eine diskrete Quelle mit dem Wahrscheinlichkeitsfeld
(
p
i
)=(0
,
18 0
,
10 0
,
40 0
,
08 0
,
05 0
,
05 0
,
14)
ist ein Optimalkode nach dem SHANNON-FANO-Verfahren zu entwerfen und
bezüglich der Koderedundanz zu bewerten.
Lösung:
Die einzelnen Schritte gemäß dem o. a. Algorithmus sind im folgenden Lö-
sungsschema zusammengefasst:
p
i
Teilung
Kodewörter
Länge
l
i
p
i
l
i
1
2
3
4
0,40
0
00
2
0,80
0,18
0
1
01
2
0,36
0,14
1
0
100
3
0,42
0,10
0
1
101
3
0,30
0,08
1
0
110
3
0,24
0,05
1
0
1110
4
0,20
0,05
1
1111
4
0,20
l
m
=2
,
52
H
m
=
−
0
,
40
ld
0
,
40
−
0
,
18
ld
0
,
18
−
0
,
14
ld
0
,
14
−
0
,
10
ld
0
,
10
−
0
,
08
ld
0
,
08
−
2
·
0
,
05
ld
0
,
05
=2
,
43
bit/QZ .
Die Koderedundanz ist damit
R
K
=
l
m
−
H
m
=2
,
52
Bit/QZ
·
1
bit/Bit
−
2
,
43
bit/QZ
=0
,
09
bit/QZ .
