 |
Redundanzreduktion (Datenkompression) Wie der Hofmathematiker herausgefunden hat, läßt sich die Coderedundanz durch Wahl einer variablen Wortlänge reduzieren. Häufig auftretende Codeworte erhalten eine kurze Wortlänge, seltene Codeworte sind dafür länger --> optimaler Code. Wir haben aber auch gesehen, daß ein optimaler Code nur für eine ganz bestimmte Häufigkeitsverteilung der Codeworte gilt. So hat schon Samuel Morse bei seinem Code die Häufigkeitsverteilung der Buchstaben in der englischen Sprache berücksichtigt. Dieser Sachverhalt wird durch das Codierungstheorem von Shannon ausgedrückt: - es gibt eine Grenze für die mittlere Codewortlänge
- die Coderedundanz kann beliebig klein werden
Verfahren zur Datenreduktion wurden von Shannon, Fano und Huffman entwickelt. Nehmen wir z. B. die Huffman-Codierung. Sie generiert anhand der Häufigkeiten einen optimalen Code: - suche die beiden "seltensten" Zeichen (geringste Haufigkeit).
- bilde einen Teilbaum mit diesen Zeichen (Unterscheidung durch 0 und 1), wobei diesem nun die Summe der beiden Häufigkeiten zugeordnet wird.
- suche nun die beiden seltensten Zeichen/Teilbäume und wiederhole die Gruppierung.
- fahre mit diesem Verfahren solange fort, solange noch mindestens zwei Teilbäume/Zeichen existieren.
Dazu ein Beispiel: In einem Text werden die Buchstaben gezählt.
Es ergeben sich folgende Häufigkeiten:
Beispiel: Telefax
Bei der Bildübertragung im Telefaxdienst der Gruppe 3 wird die
Vorlage zeilenweise abgetastet und jede Bildzeile in 1728 einzelne
Bildpunkte zerlegt (Codierung schwarz = 1, weiß = 0). Die
vertikale Auflösung beträgt 3,85 Zeilen/mm in Normalauflösung und
7,7 Zeilen/mm in Feinauflösung. Bei einer Papierlänge von ca. 29
cm ergibt sich ein Datenvolumen von
1728 * 290 * 3,85 = 1929312 bit
Bei einer Datenübertragungsrate von 9600 bit/s dauert das Senden
einer Seite ca. 200 s = 3 Minuten, 20 Sekunden. Da eine normale
Schreibmaschinenseite überwiegend weiß ist, haben die Daten
sicher hohe Redundanz. Bei einem Schwarzanzeil von 5% ergibt sich
z. B. ein Informationsgehalt von:
H = 0,05 * ld(1/0,05) + 0,95 * ld(1/0,95)
= 0,216 + 0,07 = 0,286
Für die Datenreduktion werden die Bildpunkte einer Zeile zusam-
mengefaßt, denn eine Bildzeile besteht abwechselnd aus weißen und
schwarzen Feldern unterschiedlicher Länge. Nun werden nicht mehr
die einzelnen Bildpunkte codiert übertragen, sondern nur noch ein
Code für die Anzahl, beispielsweise 10w, 30s, 123w, 2s, 67w, ...
Das Ganze nennt sich dann "Lauflängencodierung" (run length
encoding). Für jede Anzahl weißer und schwarzer Bildpunkte wird nun
ein optimales (Binär-)Codewort ermittelt und übertragen.
Da nun jede Vorlage einen anderen Schwarzanteil besitzt, müßte
man für jede Seite eine optimale Codierung ermitteln und diesen
Code an die Gegenstation senden. Dieses Vorgehen ist sicher nicht
praktikabel. Daher untersucht man eine repräsentative Auswahl von
Vorlagen ("Standardseiten") und ermittelt für diese einen
optimalen Code. Dieser Code wird dann für alle Telefax-Übertragungen
verwendet. In der Realität ist das noch komplizierter, da die
Lauflängen nach einen bestimmten Schema codiert werden. Insgesamt
ergibt sich jedoch - je nach Vorlage - eine Datenreduktion auf 5
bis 20 Prozent des ursürünglichen Volumens.
|
|
|
DIENSTE
