Information Theory/General Description

1. Information Theory
2. Quellencodierung – Datenkomprimierung
3. General Description

• Previous page
• Next page

• Previous page
• Next page

# ÜBERBLICK ZUM ZWEITEN HAUPTKAPITEL #

Anwendung findet die Shannonsche Informationstheorie zum Beispiel bei der Quellencodierung  von digitalen (also wert– und zeitdiskreten) Nachrichtenquellen. Man spricht in diesem Zusammenhang auch von Datenkomprimierung.

• Dabei wird versucht, die Redundanz natürlicher Digitalquellen wie zum Beispiel Messdaten, Texte oder Sprach– und Bilddateien (nach Digitalisierung) durch Umcodierung zu vermindern, um diese effizienter speichern und übertragen zu können.
• Meist ist die Quellencodierung mit einer Änderung des Symbolumfangs verbunden. Im Folgenden sei die Ausgangsfolge stets binär.

Im Einzelnen werden behandelt:

• die unterschiedlichen Ziele von Quellencodierung, Kanalcodierung  und Leitungscodierung,
• verlustbehaftete  Codierverfahren für analoge Quellen, zum Beispiel GIF, TIFF, JPEG, PNG, MP3,
• das Quellencodierungstheorem, das eine Grenze für die mittlere Codewortlänge angibt,
• die häufig angewandte Datenkompression nach Lempel, Ziv  und Welch,
• der Huffman–Code  als die bekannteste und effizienteste Form der Entropiecodierung,
• der Shannon–Fano–Code  sowie die arithmetische Codierung – ebenfalls Entropiecodierer,
• die Lauflängencodierung  sowie die Burrows-Wheeler Transformation  (BWT).

Weitere Informationen zum Thema sowie Aufgaben, Simulationen und Programmierübungen finden Sie im Versuch „Wertdiskrete Informationstheorie” des Praktikums „Simulation Digitaler Übertragungssysteme ”. Diese (ehemalige) LNT-Lehrveranstaltung an der TU München basiert auf

• dem Windows-Programm WDIT  ⇒  Link verweist auf die ZIP-Version des Programms; und
• der zugehörigen Praktikumsanleitung  ⇒  Link verweist auf die PDF-Version.

Quellencodierung – Kanalcodierung – Leitungscodierung

Wir betrachten für die Beschreibungen in diesem zweiten Kapitel das folgende digitale Übertragungsmodell:

• Das Quellensignal $q(t)$ kann ebenso wie das Sinkensignal $v(t)$ sowohl analog als auch digital sein. Alle anderen Signale in diesem Blockschaltbild – auch die hier nicht explizit benannten – sind Digitalsignale.
• Insbesondere sind auch die Signale $x(t)$ und $y(t)$ am Eingang und Ausgang des „Digitalen Kanals” digital und können deshalb auch durch die Symbolfolgen $〈x_ν〉$ und $〈y_ν〉$ vollständig beschrieben werden.
• Der „Digitale Kanal” beinhaltet neben dem Übertragungsmedium und den Störungen (Rauschen) auch Komponenten des Senders (Modulator, Sendeimpulsformer, usw.) und des Empfängers (Demodulator, Empfangsfilter bzw. Detektor, Entscheider).
• Das Kapitel Beschreibungsgrößen digitaler Kanalmodelle im Buch„Digitalsignalübertragung” beschreibt die Modellierung des „Digitalen Kanals” .

Vereinfachtes Modell eines Nachrichtenübertragungssystems

Wie aus diesem Blockschaltbild zu erkennen ist, unterscheidet man je nach Zielrichtung zwischen drei verschiedenen Arten von Codierung, jeweils realisiert durch den sendeseitigen Codierer (Coder) und den zugehörigen Decodierer (Decoder) beim Empfänger:

Die Aufgabe der Quellencodierung ist die Redundanzreduktion zur Datenkomprimierung, wie sie beispielsweise in der Bildcodierung Anwendung findet. Durch Ausnutzung statistischer Bindungen zwischen den einzelnen Punkten eines Bildes bzw. zwischen den Helligkeitswerten eines Bildpunktes zu verschiedenen Zeiten (bei Bewegtbildsequenzen) können Verfahren entwickelt werden, die bei nahezu gleicher Bildqualität zu einer merklichen Verminderung der Datenmenge (gemessen in Bit oder Byte) führen. Ein einfaches Beispiel hierfür ist die differentielle Pulscodemodulation (DPCM).

Bei der Kanalcodierung erzielt man demgegenüber dadurch eine merkliche Verbesserung des Übertragungsverhaltens, dass eine beim Sender gezielt hinzugefügte Redundanz empfängerseitig zur Erkennung und Korrektur von Übertragungsfehlern genutzt wird. Solche Codes, deren wichtigste Vertreter Blockcodes, Faltungscodes und Turbocodes sind, haben besonders bei stark gestörten Kanälen eine große Bedeutung. Je größer die relative Redundanz des codierten Signals ist, desto besser sind die Korrektureigenschaften des Codes, allerdings bei verringerter Nutzdatenrate.

Eine Leitungscodierung – manchmal auch als Übertragungscodierung  bezeichnet – verwendet man, um das Sendesignal durch eine Umcodierung der Quellensymbole an die spektralen Eigenschaften von Kanal und Empfangseinrichtungen anzupassen. Beispielsweise muss bei einem (analogen) Übertragungskanal, über den kein Gleichsignal übertragen werden kann – für den also $H_{\rm K}(f = 0) = 0$ gilt – durch Leitungscodierung sicher gestellt werden, dass die Codesymbolfolge keine langen Folgen gleicher Polarität beinhaltet.

Im Mittelpunkt des vorliegenden Kapitels steht die verlustfreie Quellencodierung, die ausgehend von der Quellensymbolfolge $〈q_ν〉$ und basierend auf den Ergebnissen der Informationstheorie eine datenkomprimierte Codesymbolfolge $〈c_ν〉$ generiert.

• Der Kanalcodierung ist in unserem Tutorial ein eigenes Buch mit folgendem Inhalt gewidmet.
• Die Leitungscodierung wird im Kapitel „Codierte und mehrstufige Übertragung” des Buches Digitalsignalübertragung eingehend behandelt.

Anmerkung:   Wir verwenden hier einheitlich „$\nu$” als Laufvariable einer Symbolfolge. Eigentlich müssten für $〈q_ν〉$, $〈c_ν〉$ und $〈x_ν〉$ unterschiedliche Indizes verwendet werden, wenn die Raten nicht übereinstimmen.

Verlustbehaftete Quellencodierung für Bilder

Zur Digitalisierung analoger Quellensignale wie Sprache, Musik oder Bilder können nur verlustbehaftete Quellencodierverfahren verwendet werden. Bereits die Speicherung eines Fotos im BMP–Format ist aufgrund von Abtastung, Quantisierung und der endlichen Farbtiefe stets mit einem Informationsverlust verbunden.

Es gibt es aber auch für Bilder eine Vielzahl von Kompressionsverfahren, die zu deutlich kleineren Bilddateien als „BMP” führen, zum Beispiel:

• GIF (Graphics Interchange Format ), 1987 von Steve Wilhite entwickelt.
• JPEG – ein Format, das 1992 von der Joint Photographie Experts Group vorgestellt wurde und heute der Standard für Digitalkameras ist. Endung:   „jpeg” bzw. „jpg”.
• TIFF (Tagged Image File Format), um 1990 von Aldus Corp. (jetzt Adobe) und Microsoft entwickelt, ist noch heute der Quasi–Standard für druckreife Bilder höchster Qualität.
• PNG (Portable Network Graphics), 1995 von Thomas Boutell und Tom Lane entworfen als Ersatz für das durch Patentforderungen belastete GIF–Format, ist weniger komplex als TIFF.

Diese Kompressionsverfahren nutzen teilweise

• Vektorquantisierung zur Redundanzminderung korrelierter Bildpunkte,
• gleichzeitig die verlustlosen Kompressionsalgorithmen nach Huffman und Lempel/Ziv,
• eventuell auch Transformationscodierungen basierend auf DFT (Diskrete Fouriertransformation ) und DCT (Diskrete Cosinustransformation ),
• danach Quantisierung und Übertragung im transformierten Bereich.

Wir vergleichen nun die Auswirkungen zweier Kompressionsverfahren auf die subjektive Qualität von Fotos und Grafiken, nämlich:

• JPEG (mit Komprimierungsfaktor 8) und
• PNG (mit Komprimierungsfaktor 24)

$\text{Beispiel 1:}$  Im oberen Teil der folgenden Grafik sehen Sie zwei Komprimierungen eines Fotos. Das Format JPEG (linke Darstellung) ermöglicht gegenüber der pixelweisen Abspeicherung einen Komprimierungsfaktor von $8$ bis $15$ bei (nahezu) verlustfreier Komprimierung. Selbst mit dem Komprimierunsfaktor $35$ kann das Ergebnis noch als „gut” bezeichnet werden. Bei den meisten Digitalkameras für den Consumer–Bereich ist JPEG das voreingestellte Speicherformat.

Vergleich zwischen JPEG– und PNG–Komprimierung

Das rechts dargestellte Bild wurde mit PNG komprimiert. Die Qualität ist vergleichbar mit dem linken JPEG–Bild, obwohl die Komprimierung um etwa den Faktor 3 stärker ist. Dagegen erzielt PNG ein schlechteres Komprimierungsergebnis als JPEG, wenn das Foto sehr viele Farbstufungen enthält.

Auch bei Strichzeichnungen mit Beschriftungen ist PNG besser geeignet als JPEG (untere Bilder). Die Qualität der JPEG–Komprimierung (links) ist deutlich schlechter als das PNG–Resultat, obwohl die resultierende Dateigröße etwa dreimal so groß ist. Insbesondere Schriften wirken „verwaschen”.

Anmerkung:   Aufgrund technischer Einschränkungen bei $\rm LNTwww$ mussten alle Grafiken als PNG gespeichert werden.

• In obiger Grafik bedeutet also „JPEG” die PNG–Konvertierung einer zuvor mit JPEG komprimierten Datei.
• Der damit zusammenhängende Verlust ist jedoch vernachlässigbar.

Verlustbehaftete Quellencodierung für Audiosignale

Ein erstes Beispiel für die Quellencodierung für Sprache und Musik ist die 1938 erfundene Pulscodemodulation (PCM), die aus einem analogen Quellensignal $q(t)$ die Codesymbolfolge $〈c_ν〉$ extrahiert, entsprechend den drei Verarbeitungsblöcken

Prinzip der Pulscodemodulation (PCM)

• Abtastung,
• Quantisierung, und
• PCM–Codierung.

Die Grafik verdeutlicht das PCM–Prinzip. Die Bildbeschreibung findet man auf den ersten Seiten des Kapitels Pulscodemodulation im Buch„Modulationsverfahren”.

Wegen der erforderlichen Bandbegrenzung und der Quantisierung ist diese Umformung stets verlustbehaftet. Das bedeutet:

• Die Codefolge $〈c_ν〉$ beinhaltet weniger Information als das Quellensignal $q(t)$.
• Das Sinkensignal $v(t)$ unterscheidet sich deshalb grundsätzlich von $q(t)$.
• Meist ist die Abweichung allerdings nicht sehr groß.

Wir nennen nun beispielhaft zwei auf Pulscodemodulation aufbauende Übertragungsverfahren.

$\text{Beispiel 2:}$  Die folgenden Daten sind der GSM–Spezifikation entnommen:

• Wird ein Sprachsignal spektral auf die Bandbreite $B = 4 \, \rm kHz$   ⇒   Abtastrate $f_{\rm A} = 8 \, \rm kHz$ begrenzt, so ergibt sich bei Quantisierung mit $13 \, \rm Bit$   ⇒   Quantisierungsstufenzahl $M = 2^{13} = 8192$ ein binärer Datenstrom der Datenrate $R = 104 \, \rm kbit/s$.
• Der Quantisierungsrauschabstand beträgt dann $20 · \lg M ≈ 78 \, \rm dB$.
• Bei Quantisierung mit $16 \, \rm Bit$ erhöht sich dieser auf $96 \, \rm dB$. Gleichzeitig steigt dadurch die erforderliche Datenrate auf $R = 128 \, \rm kbit/s$.

Die Auswirkungen einer Bandbegrenzung verdeutlicht das interaktive Applet Einfluss einer Bandbegrenzung bei Sprache und Musik.

$\text{Beispiel 3:}$  Der Standard ISDN (Integrated Services Digital Network ) für Telefonie über Zweidrahtleitung basiert ebenfalls auf dem PCM–Prinzip, wobei jedem Teilnehmer zwei B–Kanäle (Bearer Channels ) mit je  $64 \, \rm kbit/s$   ⇒   $M = 2^{8} = 256$ und ein D–Kanal (Data Channel ) mit  $ 16 \, \rm kbit/s$ zur Verfügung gestellt wird.

• Die Nettodatenrate beträgt somit $R_{\rm Netto} = 144 \, \rm kbit/s$.
• Unter Berücksichtigung der Kanalcodierung und der Steuerbits (aus organisatorischen Gründen erforderlich) kommt man auf die ISDN–Bruttodatenrate von $R_{\rm Brutto} = 192 \, \rm kbit/s$.

Im Mobilfunk konnten sehr große Datenraten oft (noch) nicht bewältigt werden. Hier wurden in den 1990er–Jahren Sprachcodierverfahren entwickelt, die zu einer Datenkomprimierung um den Faktor $8$ und mehr führten. Zu erwähnen sind aus heutiger Sicht:

• der Enhanced Full–Rate Codec (EFR), der pro Sprachrahmen von $20\, \rm ms$ genau $244 \, \rm Bit$ extrahiert (Datenrate: $12.2 \, \rm kbit/s$); erreicht wird diese Datenkomprimierung um mehr als den Faktor $8$ durch die Aneinanderreihung mehrerer Verfahren:

1.  Linear Predictive Coding (LPC, Kurzzeitprädiktion),
2.  Long Term Prediction (LTP, Langzeitprädiktion) und
3.  Regular Pulse Excitation (RPE);

• der Adaptive Multi–Rate Codec (AMR), der auf ACELP (Algebraic Code Excited Linear Prediction) basiert und mehrere Modi zwischen $12.2 \, \rm kbit/s$ (EFR) und $4.75 \, \rm kbit/s$ bereit stellt, so dass bei schlechterer Kanalqualität eine verbesserte Kanalcodierung eingesetzt werden kann;
• der Wideband–AMR (WB–AMR) mit neun Modi zwischen $6.6 \, \rm kbit/s$ und $23.85 \, \rm kbit/s$. Dieser wird bei UMTS eingesetzt und ist für breitbandigere Signale zwischen $200 \, \rm Hz$ und $7 \, \rm kHz$ geeignet. Die Abtastung erfolgt mit $16 \, \rm kHz$, die Quantisierung mit $4 \, \rm Bit$.

• Alle diese Komprimierungsverfahren werden im Kapitel Sprachcodierung im Buch „Beispiele von Nachrichtensystemen” im Detail beschrieben.
• Das Audio–Interaktionsmodul Qualität verschiedener Sprach–Codecs bietet einen Vergleich dieser Codecs.

MPEG–2 Audio Layer III – kurz MP3

Das heute (2015) am weitesten verbreitete Kompressionsverfahren für Audiodateien ist MP3. Entwickelt wurde dieses Format ab 1982 am Fraunhofer–Institut für Integrierte Schaltungen (IIS) in Erlangen unter der Federführung von Prof. Hans–Georg Musmann in Zusammenarbeit mit der Friedrich Alexander Universität Erlangen–Nürnberg und den AT&T Bell Labs. Auch andere Institutionen machen diesbezügliche Patentansprüche geltend, so dass es seit 1998 zu verschiedene Klagen gab, die nach Kenntnis der Autoren noch nicht endgültig abgeschlossen sind.

Im Folgenden werden einige Maßnahmen genannt, die bei MP3 genutzt werden, um die Datenmenge gegenüber der Raw–Version im WAV–Format zu reduzieren. Die Zusammenstellung ist nicht vollständig. Eine umfassende Darstellung findet man zum Beispiel im Wikipedia Artikel hierzu.

• Das Audio–Kompressionsverfahren MP3 nutzt unter anderem auch psychoakustische Effekte der Wahrnehmung aus. So kann der Mensch zwei Töne erst ab einem gewissen Mindestunterschied der Tonhöhen voneinander unterscheiden. Man spricht von so genannten „Maskierungseffekten”.
• Die Maskierungseffekte ausnutzend werden bei MP3 Signalanteile, die für den Höreindruck minderwichtig sind, mit weniger Bit (verringerte Genauigkeit) gespeichert. Ein dominanter Ton bei $4 \, \rm kHz$ kann beispielsweise dazu führen, dass benachbarte Frequenzen bis zu $11 \, \rm kHz$ für das momentane Hörempfinden nur eine untergeordnete Bedeutung besitzen.
• Die größte Ersparnis der MP3–Codierung liegt aber daran, dass die Töne mit gerade so vielen Bits abgespeichert werden, dass das dadurch entstehende Quantisierungsrauschen noch maskiert wird und nicht hörbar ist.
• Weitere MP3–Kompressionsmechanismen sind die Ausnutzung der Korrelationen zwischen den beiden Kanälen eines Stereosignals durch Differenzbildung sowie die Huffman–Codierung des resultierenden Datenstroms. Beide Maßnahmen sind verlustlos.

Nachteil der MP3–Codierung ist, dass bei starker Kompression ungewollt auch „wichtige” Frequenzanteile erfasst werden und es dadurch zu hörbaren Fehlern kommt. Ferner ist es störend, dass aufgrund der blockweisen Anwendung des MP3–Verfahrens am Ende einer Datei Lücken entstehen können. Abhilfe schafft die Verwendung des so genannten LAME–Coders – ein Open–Source–Project – und eines entsprechenden Abspielprogramms.

Beschreibung verlustloser Quellencodierung – Voraussetzungen

Im Folgenden betrachten wir ausschließlich verlustlose Quellencodierverfahren und gehen dabei von folgenden Annahmen aus:

• Die digitale Quelle besitze den Symbolumfang $M$. Für die einzelnen Quellensymbole der Folge $〈q_ν〉$ gelte mit dem Symbolvorrat $\{q_μ\}$:

$$q_{\nu} \in \{ q_{\mu} \}\hspace{0.05cm}, \hspace{0.2cm}\mu = 1, \hspace{0.05cm}\text{...} \hspace{0.05cm}, M \hspace{0.05cm}. $$

• Die einzelnen Folgenelemente $q_ν$ können statistisch unabhängig sein oder auch statistische Bindungen aufweisen. Zunächst betrachten wir Nachrichtenquellen ohne Gedächtnis, die durch die Symbolwahrscheinlichkeiten vollständig charakterisiert sind; zum Beispiel:

$$M = 4\text{:} \ \ q_μ \in \{ {\rm A}, {\rm B}, {\rm C}, {\rm D} \}, \hspace{2.5cm} \text{mit den Wahrscheinlichkeiten } p_{\rm A}, p_{\rm B}, p_{\rm C}, p_{\rm D},$$

$$M = 8\text{:} \ \ q_μ \in \{ {\rm A}, {\rm B}, {\rm C}, {\rm D}, {\rm E}, {\rm F}, {\rm G}, {\rm H} \}, \hspace{0.5cm} \text{mit den Wahrscheinlichkeiten } p_{\rm A},\hspace{0.05cm}\text{...} \hspace{0.05cm} , p_{\rm H}.$$

• Der Quellencodierer ersetzt das Quellensymbol $q_μ$ durch das Codewort $\mathcal{C}(q_μ)$, bestehend aus $L_μ$ Codesymbolen eines neuen Alphabets mit dem Symbolumfang $D$ $\{0, 1$, ... , $D – 1\}$. Damit ergibt sich für die mittlere Codewortlänge:

$$L_{\rm M} = \sum_{\mu=1}^{M} \hspace{0.1cm} p_{\mu} \cdot L_{\mu} \hspace{0.05cm}, \hspace{0.2cm}{\rm mit} \hspace{0.2cm}p_{\mu} = {\rm Pr}(q_{\mu}) \hspace{0.05cm}. $$

$\text{Beispiel 4:}$  Wir betrachten zwei verschiedene Arten von Quellencodierung, jeweils mit den Parametern $M = 9$ und $D = 3$.

• Bei der ersten Codierung $\mathcal{C}_1(q_μ)$ entsprechend Zeile 2 (rote Darstellung) wird jedes Quellensymbol $q_μ$ durch zwei Ternärsymbole ($0$, $1$ oder $2$) ersetzt. Beispielsweise gilt die Zuordnung:

$$\rm A C F B I G ⇒ 00 \ 02 \ 12 \ 01 \ 22 \ 20.$$

• Bei dieser Codierung haben alle Codeworte $\mathcal{C}_1(q_μ)$ mit $1 ≤ μ ≤ 6$ die gleiche Länge $L_μ = 2$.
• Damit ist auch die mittlere Codewortlänge $L_{\rm M} = 2$.

Zwei Beispiele für Quellencodierung

• Dagegen gilt beim zweiten, dem blauen Quellencodierer $L_μ ∈ \{1, 2 \}$ und dementsprechend wird die mittlere Codewortlänge $L_{\rm M}$ kleiner sein als zwei Codesymbole pro Quellensymbol. Hier gilt die Zuordnung:

$$\rm A C F B I G ⇒ 0 \ 02 \ 12 \ 01 \ 22 \ 2$$

• Es ist offensichtlich, dass diese zweite Codesymbolfolge nicht eindeutig decodiert werden kann, da die Symbolfolge natürlich nicht die in diesem Text eingefügten Leerzeichen beinhaltet.

Kraftsche Ungleichung – Präfixfreie Codes

Codes zur Komprimierung einer gedächtnislosen wertdiskreten Quelle zeichnen sich dadurch aus, dass die einzelnen Symbole durch verschieden lange Codesymbolfolgen dargestellt werden:

$$L_{\mu} \ne {\rm const.} \hspace{0.4cm}(\mu = 1, \hspace{0.05cm}\text{...} \hspace{0.05cm}, M ) \hspace{0.05cm}.$$

Nur dann ist es möglich,

• dass die mittlere Codewortlänge minimal wird,
• falls die Quellensymbole nicht gleichwahrscheinlich sind.

Um eine eindeutige Decodierung zu ermöglichen, muss der Code zudem „präfixfrei” sein.

$\text{Definition:}$  Die Eigenschaft präfixfrei sagt aus, dass kein Codewort der Präfix (der Beginn) eines längeren Codewortes sein darf. Ein solcher präfixfreier Code ist sofort decodierbar.

• Der zweite (blaue) Code im Beispiel 4 ist nicht präfixfrei. Beispielsweise könnte die Codesymbolfolge „01” vom Decoder als $\rm AD$ interpretiert werden, aber ebenso als $\rm B$.
• Dagegen ist der rote Code präfixfrei, wobei hier die Präfixfreiheit wegen $L_μ = \rm const.$ nicht unbedingt erforderlich wäre.

$\text{Ohne Beweis:}$  Die notwendige Bedingung für die Existenz eines präfixfreien Codes wurde von Leon Kraft in seiner Master Thesis 1949 am Massachusetts Institute of Technology (MIT) angegeben :

$$\sum_{\mu=1}^{M} \hspace{0.2cm} D^{-L_{\mu} } \le 1 \hspace{0.05cm}.$$

$\text{Beispiel 5:}$  Überprüft man den zweiten (blauen) Code von Beispiel 4 mit $M = 9$ und $D = 3$, so erhält man:

$$3 \cdot 3^{-1} + 6 \cdot 3^{-2} = 1.667 > 1 \hspace{0.05cm}.$$

Daraus ist ersichtlich, dass dieser Code nicht präfixfrei sein kann.

$\text{Beispiel 6:}$  Betrachten wir den binären Code

$$\boldsymbol{\rm A } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 0 \hspace{0.05cm}, \hspace{0.2cm}\boldsymbol{\rm B } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 00 \hspace{0.05cm}, \hspace{0.2cm}\boldsymbol{\rm C } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 11 \hspace{0.05cm}, $$

so ist dieser offensichtlich nicht präfixfrei. Die Gleichung

$$1 \cdot 2^{-1} + 2 \cdot 2^{-2} = 1 $$

sagt also keinesfalls aus, dass dieser Code tatsächlich präfixfrei ist, sondern es bedeutet lediglich, dass es einen präfixfreien Code mit gleicher Längenverteilung gibt, zum Beispiel

$$\boldsymbol{\rm A } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 0 \hspace{0.05cm}, \hspace{0.2cm}\boldsymbol{\rm B } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 10 \hspace{0.05cm}, \hspace{0.2cm}\boldsymbol{\rm C } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 11 \hspace{0.05cm}.$$

Quellencodierungstheorem

Wir betrachten eine redundante Nachrichtenquelle mit dem Symbolvorrat $〈q_μ〉$, wobei die Laufvariable $μ$ alle Werte zwischen $1$ und dem Symbolumfang $M$ annimmt. Die Quellenentropie $H$ sei kleiner als der Nachrichtengehalt $H_0$.

Die Redundanz $H_0- H$ geht entweder zurück auf

• nicht gleichwahrscheinliche Symbole ⇒ $p_μ ≠ 1/M$, und/oder
• statistische Bindungen innerhalb der Folge $〈q_\nu〉$.

Ein Quellencodierer ersetzt das Quellensymbol $q_μ$ durch das binäre Codewort $\mathcal{C}(q_μ)$, bestehend aus $L_μ$ Binärsymbolen (Nullen oder Einsen). Damit ergibt sich die mittlere Codewortlänge zu

$$L_{\rm M} = \sum_{\mu=1}^{M} \hspace{0.2cm} p_{\mu} \cdot L_{\mu} \hspace{0.05cm}, \hspace{0.2cm}{\rm mit} \hspace{0.2cm}p_{\mu} = {\rm Pr}(q_{\mu}) \hspace{0.05cm}. $$

Für die hier beschriebene Quellencodierungsaufgabe kann folgende Grenze angegeben werden:

$\text{Definition:}$  Für die Möglichkeit der vollständigen Rekonstruktion der gesendeten Zeichenfolge aus der Binärfolge ist es nach dem so genannten Shannons Quellencodierungstheorem hinreichend, aber auch notwendig,

• dass man zur sendeseitigen Codierung im Mittel mindestens $H$ Binärsymbole pro Quellensymbol verwendet.

Das heißt, dass die mittlere Codewortlänge $L_{\rm M}$ auf keinen Fall kleiner sein kann als die Entropie $H$ der Quellensymbolfolge:   $L_{\rm M} \ge H \hspace{0.05cm}. $

Berücksichtigt der Quellencodierer nur die unterschiedlichen Auftrittswahrscheinlichkeiten, nicht aber die inneren statistischen Bindungen der Folge , dann gilt $L_{\rm M} ≥ H_1$   ⇒   erste Entropienäherung.

$\text{Beispiel 7:}$  Bei einer Quaternärquelle mit den Symbolwahrscheinlichkeiten

$$p_{\rm A} = 2^{-1}\hspace{0.05cm}, \hspace{0.2cm}p_{\rm B} = 2^{-2}\hspace{0.05cm}, \hspace{0.2cm}p_{\rm C} = p_{\rm D} = 2^{-3} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} H = H_1 = 1.75\,\, {\rm bit/Quellensymbol} $$

ergibt sich in obiger Gleichung das Gleichheitszeichen   ⇒   $L_M = H$, wenn man zum Beispiel folgende Zuordnung wählt:

$$\boldsymbol{\rm A } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 0 \hspace{0.05cm}, \hspace{0.2cm}\boldsymbol{\rm B } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 10 \hspace{0.05cm}, \hspace{0.2cm}\boldsymbol{\rm C } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 110 \hspace{0.05cm}, \hspace{0.2cm}\boldsymbol{\rm D }\hspace{0.15cm} \Rightarrow \hspace{0.15cm} 111 \hspace{0.05cm}. $$

Dagegen ergibt sich mit der gleichen Zuordnung und

$$p_{\rm A} = 0.4\hspace{0.05cm}, \hspace{0.2cm}p_{\rm B} = 0.3\hspace{0.05cm}, \hspace{0.2cm}p_{\rm C} = 0.2 \hspace{0.05cm}, \hspace{0.2cm}p_{\rm D} = 0.1\hspace{0.05cm} \hspace{0.3cm} \Rightarrow \hspace{0.3cm} H = 1.845\,\, {\rm bit/Quellensymbol}$$

die mittlere Codewortlänge

$$L_{\rm M} = 0.4 \cdot 1 + 0.3 \cdot 2 + 0.2 \cdot 3 + 0.1 \cdot 3 = 1.9\,\, {\rm bit/Quellensymbol}\hspace{0.05cm}. $$

Wegen der ungünstig gewählten Symbolwahrscheinlichkeiten (keine Zweierpotenzen) ist hier $L_{\rm M} > H$.

$\text{Beispiel 8:}$  Wir betrachten noch einige frühere Versuche der Quellencodierung für die Übertragung von natürlichen Texten, wobei wir von den in der Tabelle angegebenen Buchstabenhäufigkeiten ausgehen.

• In der Literatur findet man eine Vielzahl unterschiedlicher Häufigkeiten, auch deshalb, weil verschiedene Autoren ihre Untersuchungen für verschiedene Sprachen durchführten.
• Meist beginnt die Liste aber mit dem Leerzeichen (Blank) und „E” und endet mit Buchstaben wie „X”, „Y” und „Q”.

Buchstabencodierungen nach Bacon/Bandot, Morse und Huffman

Zu dieser Tabelle ist zu anzumerken:

• Die Entropie dieses Alphabets mit $M = 27$ Zeichen wird $H≈ 4 \, \rm bit/Zeichen$ betragen. Wir haben das nicht nachgerechnet. Francis Bacon hat aber schon 1623 einen Binärcode angegeben, bei dem jeder Buchstabe mit fünf Bit dargestellt wird:   $L_{\rm M} = 5$.
• Etwa 250 Jahre danach hat Jean-Maurice-Émile Baudot diesen Code übernommen, der später auch für die gesamte Telegrafie standardisiert wurde. Eine ihm wichtige Überlegung war, dass ein Code mit einheitlich fünf Binärzeichen pro Buchstabe für einen Feind schwerer zu dechiffrieren ist, da dieser aus der Häufigkeit des Auftretens keine Rückschlüsse auf das übertragene Zeichen ziehen kann.
• Die letzte Zeile in obiger Tabelle gibt einen beispielhaften Huffman–Code für obige Häufigkeitsverteilung an. Wahrscheinliche Zeichen wie „E” oder „N” und auch das „Blank” werden mit nur drei Bit dargestellt, das seltene „Q” dagegen mit 11 Bit. Die mittlere Codewortlänge $L_{\rm M} = H + ε$ ist geringfügig größer als $H$, wobei wir uns hier über die kleine positive Größe $ε$ nicht genauer auslassen wollen. Nur soviel: Es gibt keinen präfixfreien Code mit kleinerer mittlerer Wortlänge als den Huffman–Code.
• Auch Samuel Morse berücksichtigte bereits bei seinem Code für die Telegrafie in den 1830er Jahren die unterschiedlichen Häufigkeiten. Der Morse–Code eines jeden Zeichens besteht aus zwei bis vier Binärzeichen, die hier entsprechend der Anwendung mit Punkt („Kurz”) und Strich („Lang”) bezeichnet werden.
• Es ist offensichtlich, dass für den Morsecode entsprechend der vorletzten Zeile $L_{\rm M} < 4$ gelten wird. Dies hängt aber auch damit zusammen, dass dieser Code nicht präfixfrei ist. Zwischen jeder Kurz–Lang–Sequenz musste deshalb der Funker eine Pause einlegen, damit die Gegenstation das Funksignal auch entschlüsseln konnte.

Aufgaben zum Kapitel

Aufgabe 2.1: Codierung mit und ohne Verlust

Aufgabe 2.2: Kraftsche Ungleichung

Aufgabe 2.2Z: Mittlere Codewortlänge