Cryptography Reference
In-Depth Information
erwarten, dass die Entropie kleiner als beim Quellenmodell mit unabhängigen
Zuständen sein wird.
Zuerst wollen wir die Unbestimmtheit, die in den Übergangsmöglichkeiten von
einem beliebigen
x
i
zu allen
x
j
(
j
=1
,
2
, ..., N
) liegt, berechnen. Analog zur
Gleichung für die Entropie unabhängiger Ereignisse (Gl. (2.2)) erhält man
N
1
p
(
x
j
|
H
i
=
p
(
x
j
|x
i
)
ld
.
x
i
)
j
=1
Den anderen Teil der Unbestimmtheit erfasst man durch Mittelwertbildung
über alle
x
i
(
i
=1
,
2
, ..., N
), d. h. durch Wichtung der einzelnen Beträge
H
i
mit den entsprechenden Auftrittswahrscheinlichkeiten
p
(
x
i
)
:
N
H
m
=
p
(
x
i
)
H
i
.
i
=1
Der Mittelwert
H
m
, der die Entropie bzw. den mittleren Informationsgehalt
der MARKOW-Quelle erster Ordnung darstellt, wird für den stationären Fall
p
(
x
i
)=
p
(
x
i
)
als
MARKOW-Entropie
H
M
bezeichnet:
N
N
1
p
(
x
j
|x
i
)
bit
Zustand
.
H
M
=
p
(
x
i
)
p
(
x
j
|
x
i
)
ld
in
(2.12)
i
=1
j
=1
Anmerkung
:
Da wir uns auf MARKOW-Quellen
erster
Ordnung beschränken, könnte die
Maßeinheit auch
bit/Ereignis
oder
bit/Quellenzeichen
heißen.
Beispiel 2.2.5
Berechnung der MARKOW-Entropie einer diskreten Quelle mit
N
=3
vonein-
ander abhängigen Zuständen (mit den im Beispiel 2.2.4 gegebenen Zustands-
und Übergangswahrscheinlichkeiten) entsprechend Gl. (2.12):
0
,
1
ld
1
0
,
2
ld
1
0
,
2
+0
,
8
ld
1
0
,
1
+0
,
9
ld
1
H
M
=0
,
10
+0
,
76
0
,
8
0
,
9
0
,
2
ld
1
0
,
2
+2
·
0
,
4
ld
1
+0
,
14
0
,
4
=0
,
64
bit/Zustand .
Zum Vergleich soll die Entropie dieser Quelle im stationären Zustand bestimmt
werden, wenn die Abhängigkeiten dabei unberücksichtigt bleiben:
