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 .
Search WWH ::




Custom Search