Cryptography Reference
In-Depth Information
nach vollkommen redundanzfreien Kodes verzichten. Methoden zur Schaffung
redundanzarmer
bzw.
annähernd redundanzfreier
Kodes mit vertretbarem Auf-
wand werden unter dem Begriff „Optimalkodierung“ zusammengefasst. Dafür
ist eine Reihe praktikabler Verfahren entwickelt worden.
Die im Folgenden beschriebenen Verfahren wollen wir in zwei Gruppen eintei-
len: Verfahren, welche die Kenntnis der Quellenstatistik voraussetzen (SHAN-
NON-FANO- und HUFFMAN-Verfahren), auch durch den Begriff der Entro-
piekodierung geprägt, und solche, die dies nicht erfordern (LEMPEL-ZIV-
Verfahren).
Zunächst wollen wir uns klarmachen, worin das Wesen der Redundanzreduzie-
rung bei der Optimalkodierung besteht.
Bei der ersten Verfahrensgruppe (Abschn. 3.4.2) nutzen wir die Auftrittswahr-
scheinlichkeiten der Quellenzeichen, um einen ungleichmäßigen Kode gemäß
Gl. (3.5) nach folgendem Prinzip aufzubauen:
Je höher die Auftrittswahrscheinlichkeit eines Quellenzeichens, um so kleiner
die entsprechende Kodewortlänge.
Mit anderen Worten: Die mittlere Kodewortlänge wird minimiert, wenn die
häufig auftretenden Kodewörter möglichst kurz und die selten genutzten Kode-
wörter dafür entsprechend länger sind (vgl. MORSE-Kode!).
Derartig aufge-
baute Kodes werden wir auch auf erweiterte Quellen (Abschn. 3.4.2.3) und
MARKOW-Quellen (Abschn. 3.4.2.4) anwenden.
Das LEMPEL-ZIV-Verfahren (einschließlich seiner Weiterentwicklungen) be-
ruht auf einem anderen Prinzip der Redundanzreduzierung: Mit Hilfe eines dy-
namisch aufgebauten
Wörterbuchs
werden vor allem die Abhängigkeiten bzw.
Bindungen zwischen den Quellenzeichen ausgenutzt, um mehrere Zeichen auf
ein Kodewort abzubilden. Wir werden darauf im Abschn. 3.4.3 näher eingehen.
Nachdem in den vorangegangenen Abschnitten die wesentlichsten Aspekte der
Quellenkodierung theoretisch behandelt wurden, sollen nun die genannten Ver-
fahren (ohne weitere mathematische Beweise) als Konstruktionsvorschriften
dargestellt und beispielhaft angewendet werden.
3.4.2
Verfahren auf der Grundlage der Quellenstatistik
3.4.2.1 SHANNON-FANO-Verfahren (1949)
Die Konstruktionsvorschrift für den SHANNON-FANO-Kode lautet:
1. Ordnen der Auftrittswahrscheinlichkeiten der zu kodierenden Quellenzei-
chen nach fallenden Werten.
2. Teilen des geordneten Wahrscheinlichkeitsfeldes, so dass die Teilsummen der
Wahrscheinlichkeiten in jeder Gruppe möglichst gleich groß sind.
