Cryptography Reference
In-Depth Information
Beispiel 3.4.4
Eine MARKOW-Quelle mit folgender Matrix der Übergangswahrscheinlichkei-
ten ist nach dem SHANNON-FANO-Verfahren optimal zu kodieren:
⎛
⎞
0
,
10
0
,
30
0
,
50
0
,
08
0
,
02
⎝
⎠
0
,
60
0
0
,
10
0
,
20
0
,
10
(
p
(
x
j
|
x
i
)) =
0
,
05
0
,
40
0
,
20
0
,
05
0
,
30
.
0
0
,
10
0
,
80
0
0
,
10
0
,
30
0
,
20
0
,
10
0
,
40
0
Mittlere Kodewortlänge und Koderedundanz sind mit einem SHANNON-
FANO-Kode der stationären Zustandswahrscheinlichkeiten dieser Quelle zu
vergleichen!
Lösung:
a) Bestimmung der Teilkodes und ihrer mittleren Kodewortlängen
Jede Zeile der Matrix
(
p
(
x
j
|x
i
))
gibt für ein Quellenzeichen die Verteilung der
Übergangswahrscheinlichkeiten an, d. h.,
jede Zeile stellt ein Wahrscheinlich-
keitsfeld für einen Teilkode K
i
(
i
=1
,
2
, ...,
5)
dar. Bei den folgenden Anwen-
dungen des SHANNON-FANO-Verfahrens sind die jeweiligen Wahrscheinlich-
keitsfelder nach fallenden Werten geordnet (bei der Dekodierung zu beachten!).
p
(
x
j
|x
1
)
K1
p
(
x
j
|x
1
)
l
1
j
p
(
x
j
|x
2
)
K2
p
(
x
j
|x
2
)
l
2
j
p
(
x
3
|x
1
)=0
,
50 0
0
,
50
p
(
x
1
|x
2
)=0
,
60 0
0
,
60
p
(
x
2
|x
1
)=0
,
30 10
0
,
60
p
(
x
4
|x
2
)=0
,
20 10
0
,
40
p
(
x
1
|x
1
)=0
,
10 110
0
,
30
p
(
x
3
|x
2
)=0
,
10 110
0
,
30
p
(
x
4
|
x
1
)=0
,
08 1110
0
,
32
p
(
x
5
|
x
2
)=0
,
10 111
0
,
30
p
(
x
5
|x
1
)=0
,
02 1111
0
,
08
p
(
x
2
|x
2
)=0
−
−
l
m,
1
=1
,
80
l
m,
2
=1
,
60
p
(
x
j
|x
3
)
K3
p
(
x
j
|x
3
)
l
3
j
p
(
x
j
|x
4
)
K4
p
(
x
j
|x
4
)
l
4
j
p
(
x
2
|x
3
)=0
,
40 0
0
,
40
p
(
x
3
|x
4
)=0
,
80 0
0
,
80
p
(
x
5
|x
3
)=0
,
30 10
0
,
60
p
(
x
2
|x
4
)=0
,
10 10
0
,
20
p
(
x
3
|x
3
)=0
,
20 110
0
,
60
p
(
x
5
|x
4
)=0
,
10 11
0
,
20
p
(
x
4
|x
3
)=0
,
05 1110
0
,
20
p
(
x
1
|x
4
)=0
−
−
p
(
x
1
|x
3
)=0
,
05 1111
0
,
20
p
(
x
4
|x
4
)=0
−
−
l
m,
3
=2
,
00
l
m,
4
=1
,
20
