Cryptography Reference
In-Depth Information
lenzeichen vorausgesetzt. Von den MARKOW-Quellen (Abschn. 2.2.2) wissen
wir, dass die Quellenentropie geringer ist, wenn die vorhandene statistische Ab-
hängigkeit der Quellenzeichen berücksichtigt wird. Folglich müssen wir auch
die Aussagen über die Koderedundanz (Gl. (3.4)) und die Schranken der mitt-
leren Kodewortlänge (Gl. (3.6)) entsprechend präzisieren.
Im Abschn. 3.3 wurde bewiesen, dass die mittlere Kodewortlänge nicht kleiner
als die Quellenentropie sein kann. Diese Feststellung ist so allgemeingültig, dass
sie selbstverständlich auch auf die Kodierung von MARKOW-Quellen zutrifft,
bei denen die MARKOW-Entropie die kleinstmögliche mittlere Kodewortlänge
bestimmt. Wie dicht man sich diesem Grenzwert durch einen Optimalkode nä-
hert, hängt vom speziellen Kodierungsverfahren ab. Wir wollen uns überlegen,
wie ein solches Verfahren für MARKOW-Quellen gestaltet sein kann, wenn wir
von den bekannten Optimalkodierungsverfahren ausgehen.
Im Abschn. 2.2.2.1 wurde gezeigt, dass die Abhängigkeit der Quellenzeichen
durch ihre Übergangswahrscheinlichkeiten
p
(
x
j
|
x
i
)
berücksichtigt werden kann,
wobei es für jedes Quellenzeichen i. Allg. eine andere Verteilung der
p
(
x
j
|
x
i
)
für
i, j
=1
,
2
, ..., N
gibt.
Ein Quellenzeichen kann also nicht mehr durch ein einziges Kodewort, wie
bei statistischer Unabhängigkeit, abgebildet werden. Vielmehr muss jedem
Quellenzeichen ein spezieller Kode zugeordnet werden, der alle Übergangs-
möglichkeiten zu den anderen Quellenzeichen durch entsprechende Kodewörter
darstellt. Jeder dieser „Übergangskodes“ wird nach einem Verfahren der Opti-
malkodierung gebildet. Der
Optimalkode der MARKOW-Quelle besteht dem-
nach aus
N
verschiedenen optimalen Teilkodes
, wenn das Alphabet der Quelle
N
abhängige Zeichen enthält.
Immer wenn bei der Nachrichtenerzeugung ein anderes Quellenzeichen auf-
tritt, muss auch der Übergangskode gewechselt werden. Man spricht deshalb
bei MARKOW-Quellen auch von einer
zustandsabhängigen Kodierung
.
Entsprechend der Definition 3.1.3 können wir die
Koderedundanz
R
K
als Dif-
ferenz zwischen der mittleren Kodewortlänge
l
M
des gesamten Quellenkodes
und der Entropie
H
M
der MARKOW-Quelle bestimmen:
N
N
N
R
K
=
l
M
− H
M
;
l
M
=
p
(
x
i
)
p
(
x
j
|x
i
)
l
ij
=
p
(
x
i
)
l
m,i
,
(3.11)
i
=1
j
=1
i
=1
wobei
l
ij
die Kodewortlänge für den Übergang von
x
i
nach
x
j
bzw. für das
bedingte Auftreten des Zeichens
x
j
ist. Die mittlere Länge aller Kodewörter
l
M
ist demnach der Mittelwert der mittleren Längen
l
m,i
für
i
=1
,
2
, ..., N
der
Einzelkodes.
