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 – beide gehören ebenfalls zur Klasse der 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 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,noch heute der Quasi–Standard für druckreife Bilder höchster Qualität.
• PNG  (Portable Network Graphics), 1995 von T. Boutell & T. 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.

Vergleich zwischen JPEG– und PNG–Komprimierung

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.

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.  Eine ausführliche 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_ν〉$  hat weniger Information als das Signal  $q(t)$.
• Das Sinkensignal  $v(t)$  unterscheidet sich 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 allerdings 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–Modul  Qualität verschiedener Sprach–Codecs  ermöglicht einen subjektiven 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 kam, 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 in einem  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 Bit 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 allein 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_μ)$  gemäß Zeile 2 (rote Darstellung) der unteren Tabelle 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 aus Darstellungsgründen eingefügten Leerzeichen beinhaltet.

Kraftsche Ungleichung – Präfixfreie Codes

Binäre 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 (Beginn) eines längeren Codewortes sein darf.  Ein solcher Code ist sofort decodierbar.

• Der 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 nun 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{Theorem:}$  Für die Möglichkeit der vollständigen Rekonstruktion der gesendeten Zeichenfolge aus der Binärfolge ist es hinreichend, aber auch notwendig, dass

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

• 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}. $$

Man bezeichnet diese Gesetzmäßigkeit als  Quellencodierungstheorem, das auf  Claude Elwood Shannon  zurückgeht.  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_{\rm 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 sehr frühe 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 viele unterschiedliche Häufigkeitsangaben,  auch deshalb,  weil die Untersuchungen für verschiedene Sprachen durchgeführt wurden.
• Meist beginnt die Liste aber mit dem Leerzeichen (Blank) sowie „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 gemäß der vorletzten Zeile  $L_{\rm M} < 4$  gelten wird.  Dies hängt aber 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