Cryptography Reference
In-Depth Information
von Befehlssätzen verwendet, damit häufig vorkommende Befehle möglichst
kurz sind [VIT 87], oder bei Verfahren der Datenspeicherung zum Zweck der
Datenkompression (meist in „Verkettung“ mit verlustbehafteten Kompressi-
onsverfahren, wie im MP3-Verfahren für die Kompression von Audiodaten, im
JPEG-Verfahren für die Kompression von Bilddaten, oder mit verlustfreien
Kompressionsverfahren wie in Fax-Geräten).
3.4.2.3 Optimalkodierung erweiterter Quellen
Im Zusammenhang mit dem SHANNONschen Kodierungstheorem wurde be-
reits von einer
m
-fachen Erweiterung diskreter Quellen gesprochen. Jetzt wol-
len wir solche Quellen konkret unter dem Aspekt der Optimalkodierung un-
tersuchen.
Definition 3.4.1
Unter einer
erweiterten Quelle
verstehen wir eine aus
der ursprünglichen Informationsquelle (mit
N
Zeichen) gebildete Ersatzquel-
le, in der jeweils
m
Zeichen der ursprünglichen Quelle zu einem Ersatzzei-
chen zusammengefasst sind (Anzahl Ersatzzeichen:
N
m
).
Aus der ursprünglichen Quelle
X
=
{x
1
,x
2
, ..., x
N
}
mit den zugehörigen Auf-
trittswahrscheinlichkeiten
p
(
x
i
)(
i
=1
,
2
, ..., N
)
wird die erweiterte Quelle
X
[
m
]
=
{x
[
m
]
1
,x
[
m
]
2
, ..., x
[
m
]
N
m
}
mit den erweiterten Zeichen (Ersatzzeichen)
x
[
m
]
j
=(
x
j
1
x
j
2
... x
jm
)
x
jk
∈ X
)
)=
m
k
=1
und den Wahrscheinlichkeiten
p
(
x
[
m
]
j
p
(
x
jk
)
für
j
=1
,
2
, ..., N
m
.
Für die Entropie erweiterter Quellen gilt (s. 2. Aufg. zum Abschn. 3.2)
H
(
X
[
m
]
)=
mH
(
X
)
.
(3.8)
Die mittlere Kodewortlänge der
m
-fach erweiterten Quelle wird wie folgt be-
rechnet:
N
m
p
(
x
[
m
]
j
)
l
[
m
j
.
l
[
m
]
m
=
ml
m
=
(3.9)
j
=1
Bezogen auf die ursprüngliche Quelle gilt dann
l
[
m
]
m
m
.
l
m
=
(3.10)