Cryptography Reference
In-Depth Information
Gemäß dem SHANNONschen Kodierungstheorem (vgl. Abschn. 3.3) wird die
Koderedundanz für solche erweiterten Quellen um so kleiner, je größer
m
ge-
wählt wird.
Mit dem folgenden Beispiel soll diese Aussage gestützt werden, indem ein Ver-
fahren der Optimalkodierung auf eine gegebene diskrete Quelle und zwei ihrer
Erweiterungen angewendet wird.
Beispiel 3.4.3
Gegeben sei eine diskrete Binärquelle mit unabhängigen Zeichen und den Auf-
trittswahrscheinlichkeiten
p
(
x
1
)=0
,
2
und
p
(
x
2
)=0
,
8
.
Zu bestimmen ist die Koderedundanz bei einer Optimalkodierung nach dem
SHANNON-FANO-Verfahren
a) für die gegebene Binärquelle,
b) für die erweiterte Quelle mit
m
=2
,
c) für die erweiterte Quelle mit
m
=3
.
Lösung:
Die Berechnung der Koderedundanz entsprechend Gl. (3.4) erfordert die Be-
stimmung der mittleren Kodewortlänge
l
m
und der Quellenentropie
H
m
.
zu a)
l
m
=1
Bit/QZ ,
H
m
=
−
0
,
2
ld
0
,
2
−
0
,
8
ld
0
,
8=0
,
722
bit/QZ ,
R
K
=1
Bit/QZ
·
1
bit/Bit
−
0
,
722
bit/QZ
=0
,
278
bit/QZ .
zu b)
Bei
m
=2
erhalten wir die erweiterte Quelle
X
[2]
=
{
(
x
1
x
1
)
,
(
x
1
x
2
)
,
(
x
2
x
1
)
,
(
x
2
x
2
)
}
mit den zugehörigen Auftrittswahrscheinlichkeiten
p
(
x
[2
1
)=0
,
2
·
0
,
2=0
,
04
p
(
x
[2
2
)=0
,
2
·
0
,
8=0
,
16
p
(
x
[2
3
)=0
,
8
·
0
,
2=0
,
16
p
(
x
[2
4
)=0
,
8
·
0
,
8=0
,
64
.
Die Anwendung des SHANNON-
FANO-Verfahrens entsprechend Ab-
schn. 3.4.2.1 auf dieses Wahrschein-
lichkeitsfeld wird im nebenstehenden
Lösungsschema dargestellt.
Mit
l
m
=
1
,
56
2
=0
,
780
Bit/QZ
und
H
m
=0
,
722
bit/QZ
erhält man eine
Koderedundanz
p
(
x
[2
j
)
Optimalkode
p
(
x
[2
j
)
l
[2]
j
0
,
64
0
0
,
64
0
,
16
10
0
,
32
0
,
16
110
0
,
48
0
,
04
111
0
,
12
l
[2
m
=
j
p
(
x
[2
j
)
l
[2]
=1
,
56
j
R
K
=0
,
780
Bit/QZ ·
1
bit/Bit −
0
,
722
bit/QZ
=0
,
058
bit/QZ .