Cryptography Reference
In-Depth Information
Hervorzuheben ist hierbei der Fall
symmetrischer Übergangswahrschein-
lichkeiten
p
(
x
2
|x
1
)=
p
(
x
1
|x
2
)=
p
,
p
(
x
1
|x
1
)=
p
(
x
2
|x
2
)=1
− p,
mit den stationären Zustandswahrscheinlichkeiten
p
1
=
p
2
=
2
.
Eine Binärquelle mit gleichen Zustandswahrscheinlichkeiten und symmetri-
schen Übergangswahrscheinlichkeiten (was häufig, wenigstens näherungsweise,
zutrifft) befindet sich demzufolge von Anfang an im stationären Zustand.
Eine anschauliche Beschreibung von MARKOW-Quellen ist auch durch
Zu-
standsgraphen
möglich (Bild 2.2.2), in denen die Ereignisse (Zustände) durch
Knoten und die Übergänge (mit den zugehörigen Übergangswahrscheinlichkei-
ten) durch Kanten dargestellt werden (kantenbewerteter gerichteter Graph).
px
( | )
x
2
1
x
x
1
2
px
( | )
x
p
( | )
xx
2
2
1
1
p
( | )
x
x
1
2
Bild 2.2.2
Zustandsgraph einer binären MARKOW-Quelle 1. Ordnung
2.2.2.2 Entropie diskreter MARKOW-Quellen
Wie wir wissen, ist die Entropie ein Maß für die Unbestimmtheit eines Sys-
tems zufälliger Ereignisse. Bei Quellen mit
N
nicht gleichwahrscheinlichen und
voneinander abhängigen Zuständen liegt Unbestimmtheit in der Hinsicht vor,
dass man für einen bestimmten Zeitpunkt nicht genau voraussagen kann,
-
welcher von
N
möglichen Zuständen gerade vorliegt und
-
welcher von
N
möglichen Übergängen als nächster eintreten wird.
Zunächst wollen wir feststellen, dass bei dem angenommenen Fall immer bei-
de Teile der Unbestimmtheit vorliegen, und zwar unabhängig davon, welches
Quellenmodell verwendet wird. Sobald man aber eine Unbestimmtheit durch
eine Wahrscheinlichkeitsverteilung beschreibt und diese bei der Entropiebe-
rechnung berücksichtigt, wird ein Teil der ursprünglichen Unbestimmtheit be-
seitigt, d. h., die wirkliche Entropie wird kleiner.
Bei MARKOW-Quellen (Definition 2.2.3) werden sowohl die Zustands- als
auch die Übergangswahrscheinlichkeiten berücksichtigt. Man kann demzufolge
