Informationstheorie/Allgemeine Beschreibung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(32 dazwischenliegende Versionen von 4 Benutzern werden nicht angezeigt)
Zeile 5: Zeile 5:
 
|Nächste Seite=Komprimierung nach Lempel, Ziv und Welch
 
|Nächste Seite=Komprimierung nach Lempel, Ziv und Welch
 
}}
 
}}
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.
 
  
 +
== # ÜBERBLICK ZUM ZWEITEN HAUPTKAPITEL # ==
 +
<br>
 +
Anwendung findet die Shannonsche Informationstheorie zum Beispiel bei der&nbsp; '''Quellencodierung'''&nbsp; von digitalen (also wert– und zeitdiskreten) Nachrichtenquellen.&nbsp; Man spricht in diesem Zusammenhang auch von&nbsp; '''Datenkomprimierung'''.
 +
*Dabei wird versucht, die Redundanz natürlicher Digitalquellen wie zum Beispiel Messdaten, Texte oder Sprach– und Bilddateien&nbsp; (nach Digitalisierung)&nbsp; durch Umcodierung zu vermindern, um diese effizienter speichern und übertragen zu können.
 +
*Meist ist die Quellencodierung mit einer Änderung des Symbolumfangs verbunden.&nbsp; Im Folgenden sei die Ausgangsfolge stets binär.
  
Weitere Informationen zum Thema sowie Aufgaben, Simulationen und Programmierübungen finden Sie im Versuch &bdquo;Wertdiskrete Informationstheorie&rdquo; des Praktikums „Simulation Digitaler Übertragungssysteme ”. Diese (ehemalige) LNT-Lehrveranstaltung an der TU München basiert auf
 
  
*dem Windows-Programm [http://www.lntwww.de/downloads/Sonstiges/Programme/WDIT.zip WDIT] &nbsp;&rArr;&nbsp; Link verweist auf die ZIP-Version des Programms; und
+
Im Einzelnen werden behandelt:
*der zugehörigen [http://www.lntwww.de/downloads/Sonstiges/Texte/Wertdiskrete_Informationstheorie.pdf Praktikumsanleitung]  &nbsp;&rArr;&nbsp; Link verweist auf die PDF-Version.
 
  
 +
:*Die unterschiedlichen Ziele von&nbsp; &raquo;Quellencodierung&laquo;,&nbsp; &raquo;Kanalcodierung&laquo;&nbsp; und&nbsp; &raquo;Leitungscodierung&laquo;,
 +
:*&raquo;verlustbehaftete Codierverfahren&laquo;&nbsp; für analoge Quellen, zum Beispiel GIF, TIFF, JPEG, PNG, MP3,
 +
:*das&nbsp; &raquo;Quellencodierungstheorem&laquo;, das eine Grenze für die mittlere Codewortlänge angibt,
 +
:*die häufig angewandte&nbsp; &raquo;Datenkompression nach Lempel, Ziv und Welch&laquo;,
 +
:*der&nbsp; &raquo;Huffman–Code&laquo;&nbsp; als die bekannteste und effizienteste Form der Entropiecodierung,
 +
:*der&nbsp; &raquo;Shannon–Fano–Code&laquo;&nbsp; sowie die&nbsp; &raquo;arithmetische Codierung&laquo; – beide gehören ebenfalls zur Klasse der Entropiecodierer,
 +
:*die&nbsp; &raquo;Lauflängencodierung&laquo;&nbsp; sowie die&nbsp; &raquo;Burrows-Wheeler Transformation&laquo;&nbsp; (BWT).
  
Der erste Abschnitt &bdquo;Allgemeine Beschreibung&rdquo; ist wie folgt gegliedert:
+
 
 +
Weitere Informationen zum Thema sowie Aufgaben, Simulationen und Programmierübungen finden Sie im Versuch &bdquo;Wertdiskrete Informationstheorie&rdquo; des Praktikums „Simulation Digitaler Übertragungssysteme ”.&nbsp; Diese (ehemalige) LNT-Lehrveranstaltung an der TU München basiert auf
 +
 
 +
:*dem Windows-Programm&nbsp; [http://www.lntwww.de/downloads/Sonstiges/Programme/WDIT.zip WDIT] &nbsp;&rArr;&nbsp; Link verweist auf die ZIP-Version des Programms,&nbsp; und
 +
:*der zugehörigen&nbsp; [http://www.lntwww.de/downloads/Sonstiges/Texte/Wertdiskrete_Informationstheorie.pdf Praktikumsanleitung]  &nbsp;&rArr;&nbsp; Link verweist auf die PDF-Version.
  
  
 
==Quellencodierung – Kanalcodierung – Leitungscodierung  ==
 
==Quellencodierung – Kanalcodierung – Leitungscodierung  ==
 
+
<br>
 
Wir betrachten für die Beschreibungen in diesem zweiten Kapitel das folgende digitale Übertragungsmodell:
 
Wir betrachten für die Beschreibungen in diesem zweiten Kapitel das folgende digitale Übertragungsmodell:
 +
[[Datei:P_ID2315__Inf_T_2_1_S1_neu.png|right|frame|Vereinfachtes Modell eines Nachrichtenübertragungssystems]]
  
[[Datei:P_ID2315__Inf_T_2_1_S1_neu.png|Vereinfachtes Modell eines Nachrichtenübertragungssystems]]
+
*Das Quellensignal&nbsp; $q(t)$&nbsp; kann ebenso wie das Sinkensignal&nbsp; $v(t)$&nbsp; sowohl analog als auch digital sein.&nbsp; Alle anderen Signale in diesem Blockschaltbild – auch die hier nicht explizit benannten – sind Digitalsignale.
 +
*Insbesondere sind auch die Signale&nbsp; $x(t)$&nbsp; und&nbsp; $y(t)$&nbsp; am Eingang und Ausgang des „Digitalen Kanals” digital und können deshalb auch durch die Symbolfolgen&nbsp; $〈x_ν〉$&nbsp; und&nbsp; $〈y_ν〉$&nbsp; 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&nbsp; [[Digitalsignalübertragung/Beschreibungsgrößen_digitaler_Kanalmodelle|Beschreibungsgrößen digitaler Kanalmodelle]]&nbsp; im Buch &bdquo;Digitalsignalübertragung&rdquo; beschreibt die Modellierung des  „Digitalen Kanals” .
 +
<br clear=all>
 +
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:
  
Zu diesem Modell ist zu bemerken:
+
Die Aufgabe der&nbsp; '''Quellencodierung'''&nbsp; ist die Redundanzreduktion zur Datenkomprimierung, wie sie beispielsweise in der Bildcodierung Anwendung findet.&nbsp; Durch Ausnutzung statistischer Bindungen zwischen den einzelnen Punkten eines Bildes bzw. zwischen den Helligkeitswerten eines Bildpunktes&nbsp; (bei Bewegtbildsequenzen  zu verschiedenen Zeiten)&nbsp; können Verfahren entwickelt werden, die bei nahezu gleicher Bildqualität zu einer merklichen Verminderung der Datenmenge (gemessen in Bit oder Byte) führen.&nbsp; Ein einfaches Beispiel hierfür ist die&nbsp; &raquo;differentielle Pulscodemodulation&laquo; &nbsp; (DPCM).
*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). Zur Modellierung des Digitalen Kanals sei auf das Kapitel [[Digitalsignalübertragung/Beschreibungsgrößen_digitaler_Kanalmodelle|Beschreibungsgrößen digitaler Kanalmodelle]] im Buch&bdquo;Digitalsignalübertragung&rdquo; verwiesen.
 
  
 +
Bei der&nbsp; '''Kanalcodierung'''&nbsp; 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.&nbsp; Solche Codes, deren wichtigste Vertreter Blockcodes, Faltungscodes und Turbocodes sind, haben besonders bei stark gestörten Kanälen eine große Bedeutung.&nbsp; Je größer die relative Redundanz des codierten Signals ist, desto besser sind die Korrektureigenschaften des Codes, allerdings bei verringerter Nutzdatenrate.
  
Wie aus dem obigen 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 Decoder beim Empfänger:
+
Eine&nbsp; '''Leitungscodierung'''&nbsp; – manchmal auch&nbsp; "Übertragungscodierung"&nbsp; genannt – verwendet man, um das Sendesignal durch eine Umcodierung der Quellensymbole an die spektralen Eigenschaften von Kanal und Empfangseinrichtungen anzupassen.&nbsp; Beispielsweise muss bei einem (analogen) Übertragungskanal, über den kein Gleichsignal übertragen werden kann – für den also&nbsp; $H_{\rm K}(f = 0) = 0$&nbsp; gilt – durch Leitungscodierung sicher gestellt werden, dass die Codesymbolfolge keine langen Folgen gleicher Polarität beinhaltet.
*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 Übertragungskanal, über den kein Gleichsignal übertragen werden kann – für den also $H_{\rm K}(f = 0) = 0$ gilt – durch Übertragungscodierung sichergestellt 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_ν〉$ eine datenkomprimierte Codesymbolfolge $〈c_ν〉$  generiert, basierend auf den Ergebnissen der Informationstheorie.
+
Im Mittelpunkt des vorliegenden Kapitels steht die verlustfreie Quellencodierung, die ausgehend von der Quellensymbolfolge&nbsp; $〈q_ν〉$&nbsp; und basierend auf den Ergebnissen der Informationstheorie eine datenkomprimierte Codesymbolfolge&nbsp; $〈c_ν〉$&nbsp; generiert.
  
*Der Kanalcodierung ist in unserem Tutorial ein eigenes Buch mit folgendem [[Kanalcodierung|Inhalt]] gewidmet.  
+
*Der Kanalcodierung ist in unserem Tutorial ein eigenes Buch mit folgendem&nbsp; [[Kanalcodierung|Inhalt]]&nbsp; gewidmet.  
*Die Leitungscodierung wird im Kapitel &bdquo;Codierte und mehrstufige Übertragung&rdquo; des Buches [[Digitalsignalübertragung/Grundlagen_der_codierten_Übertragung| Digitalsignalübertragung]] eingehend behandelt.
+
*Die Leitungscodierung wird im Kapitel&nbsp; &bdquo;Codierte und mehrstufige Übertragung&rdquo;&nbsp; des Buches&nbsp; [[Digitalsignalübertragung]]&nbsp; 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.
+
''Anmerkung'': &nbsp; Wir verwenden hier einheitlich „$\nu$” als Laufvariable einer Symbolfolge.&nbsp; Eigentlich müssten für&nbsp; $〈q_ν〉$,&nbsp; $〈c_ν〉$&nbsp; und&nbsp; $〈x_ν〉$&nbsp; unterschiedliche Indizes verwendet werden, wenn die Raten nicht übereinstimmen.
  
  
 
==Verlustbehaftete Quellencodierung  für Bilder==
 
==Verlustbehaftete Quellencodierung  für Bilder==
 +
<br>
 +
Zur Digitalisierung analoger Quellensignale wie Sprache, Musik oder Bilder können nur verlustbehaftete Quellencodierverfahren verwendet werden.&nbsp; Bereits die Speicherung eines Fotos im&nbsp; [https://de.wikipedia.org/wiki/Windows_Bitmap BMP]–Format ist aufgrund von Abtastung, Quantisierung und der endlichen Farbtiefe stets mit einem Informationsverlust verbunden.
  
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:
 +
*[https://en.wikipedia.org/wiki/GIF GIF]&nbsp; ("Graphics Interchange Format"&nbsp;), 1987 von Steve Wilhite entwickelt.
 +
*[https://de.wikipedia.org/wiki/JPEG JPEG]&nbsp; – ein Format, das 1992 von der&nbsp; "Joint Photographie Experts Group"&nbsp; vorgestellt wurde und heute der Standard für Digitalkameras ist.&nbsp; Endung: &nbsp; „jpeg” bzw. „jpg”.
 +
*[https://de.wikipedia.org/wiki/Tagged_Image_File_Format TIFF]&nbsp; ("Tagged Image File Format"), um 1990 von Aldus Corp. (jetzt Adobe) und Microsoft entwickelt, noch heute Quasi–Standard für druckreife Bilder höchster Qualität.
 +
*[https://de.wikipedia.org/wiki/Portable_Network_Graphics PNG]&nbsp; ("Portable Network Graphics"), 1995 von T. Boutell & T. Lane entworfen als Ersatz für das durch Patentforderungen belastete GIF–Format, weniger komplex als TIFF.
  
Es gibt es aber auch  für Bilder eine Vielzahl von Kompressionsverfahren, die zu deutlich kleineren Bilddateien als „BMP” führen, zum Beispiel:
 
*[https://en.wikipedia.org/wiki/GIF GIF] (''Graphics Interchange Format''), 1987 von Steve Wilhite entwickelt.
 
*[https://de.wikipedia.org/wiki/JPEG 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”.
 
*[https://de.wikipedia.org/wiki/Tagged_Image_File_Format 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.
 
*[https://de.wikipedia.org/wiki/Portable_Network_Graphics PNG] (''Portable Network Graphics''), 1995 von Thomas Boutell und Tom Lane entworfen als Ersatz für das durch Patentforderungen belastete GIF–Format; weniger komplex als TIFF.
 
  
 +
Diese Kompressionsverfahren nutzen teilweise
 +
*Vektorquantisierung zur Redundanzminderung korrelierter Bildpunkte,
 +
*gleichzeitig die verlustlosen Kompressionsalgorithmen nach&nbsp; [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus|Huffman]]&nbsp; und&nbsp; [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch|Lempel/Ziv]],
 +
*eventuell auch Transformationscodierungen basierend auf DFT&nbsp; (Diskrete Fouriertransformation)&nbsp; und&nbsp; DCT&nbsp; (Diskrete Cosinustransformation),
 +
*danach Quantisierung und Übertragung im transformierten Bereich.
  
Diese Kompressionsverfahren nutzen teilweise Vektorquantisierung zur Redundanzminderung korrelierter Bildpunkte, gleichzeitig die verlustlosen Kompressionsalgorithmen nach [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus|Huffman]] und [[Informationstheorie/Komprimierung_nach_Lempel,_Ziv_und_Welch#Statische_und_dynamische_W.C3.B6rterbuchtechniken|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:
 
Wir vergleichen nun die Auswirkungen zweier Kompressionsverfahren auf die subjektive Qualität von Fotos und Grafiken, nämlich:
*JPEG (mit Komprimierungsfaktor 8) und
+
*$\rm JPEG$&nbsp; $($mit Komprimierungsfaktor&nbsp; $8)$,&nbsp; und
*PNG (mit Komprimierungsfaktor 24)
+
*$\rm PNG$&nbsp; $($mit Komprimierungsfaktor&nbsp; $24)$.
  
  
{{Beispiel}}
+
{{GraueBox|TEXT=
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 Faktor 35 kann das Ergebnis noch als „gut” bezeichnet werden.
+
$\text{Beispiel 1:}$&nbsp;
 +
Im oberen Teil der folgenden Grafik sehen Sie zwei Komprimierungen eines Fotos.
 +
[[Datei:P_ID2920__Inf_T_2_1_S2_neu.png|right|frame|Vergleich zwischen JPEG– und PNG–Komprimierung]]
 +
Das Format&nbsp; $\rm JPEG$&nbsp; (linke Darstellung) ermöglicht gegenüber der pixelweisen Abspeicherung einen Komprimierungsfaktor von&nbsp; $8$&nbsp; bis&nbsp; $15$&nbsp; bei (nahezu) verlustfreier Komprimierung.  
 +
*Selbst mit dem Komprimierungsfaktor&nbsp; $35$&nbsp; kann das Ergebnis noch als „gut” bezeichnet werden.
 +
*Bei den meisten Digitalkameras für den Consumer–Bereich ist &bdquo;JPEG&rdquo; das voreingestellte Speicherformat.
  
[[Datei:P_ID2920__Inf_T_2_1_S2_neu.png|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. Bei den meisten Digitalkameras für den Consumer–Bereich ist JPEG das voreingestellte Speicherformat.
+
Das rechts dargestellte Bild wurde mit&nbsp; $\rm PNG$&nbsp; komprimiert.  
 +
*Die Qualität ist vergleichbar mit dem linken JPEG–Bild, obwohl die Komprimierung um etwa den Faktor&nbsp; $3$&nbsp; 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 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.  
+
Auch bei Strichzeichnungen mit Beschriftungen ist PNG besser geeignet als JPEG (untere Bilder).&nbsp;
+
*Die JPEG–Qualität (links) ist deutlich schlechter als das PNG–Resultat, obwohl die resultierende Dateigröße dreimal so groß ist.
{{end}}
+
*Insbesondere Schriften wirken „verwaschen”.
 +
<br clear=all>
 +
''Anmerkung'': &nbsp; Aufgrund technischer Einschränkungen bei&nbsp; $\rm LNTwww$&nbsp; mussten alle Grafiken als &bdquo;PNG&rdquo; 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. }}
  
 
   
 
   
Zeile 81: Zeile 107:
 
 
 
 
 
 
 
 
==Verlustbehaftete Quellencodierung  ==
+
==Verlustbehaftete Quellencodierung  für Audiosignale==
 
+
<br>
Ein erstes Beispiel für Quellencodierung ist die 1938 erfundene [https://de.wikipedia.org/wiki/Puls-Code-Modulation Pulscodemodulation] (PCM), die aus einem analogen Quellensignal q(t) durch
+
Ein erstes Beispiel für die Quellencodierung für Sprache und Musik ist die 1938 erfundene&nbsp; [https://de.wikipedia.org/wiki/Puls-Code-Modulation Pulscodemodulation]&nbsp; $\rm (PCM)$, die aus einem analogen Quellensignal&nbsp; $q(t)$&nbsp; die Codesymbolfolge&nbsp; $〈c_ν〉$&nbsp; extrahiert, entsprechend den drei Verarbeitungsblöcken
*Abtastung
+
[[Datei:P_ID2925__Mod_T_4_1_S1_neu.png|right|frame|Prinzip der Pulscodemodulation (PCM)]]
*Quantisierung
+
*Abtastung,
*PCM–Codierung
+
*Quantisierung, und
 
+
*PCM–Codierung.
 
 
die Codesymbolfolge $〈c_ν〉$ extrahiert. Wegen der erforderlichen Bandbegrenzung und der Quantisierung ist diese Umformung jedoch stets verlustbehaftet. Das bedeutet, dass die codierte Folge $〈c_ν〉$ nicht die gesamte Information des Quellensignals $q(t)$ beinhaltet, und dass sich das Sinkensignal $v(t)$ grundsätzlich von $q(t)$ unterscheidet. Meist ist die Abweichung allerdings nicht sehr groß.
 
 
 
[[Datei:P_ID2925__Mod_T_4_1_S1_neu.png|Prinzip der PCM]]
 
 
 
Die Grafik verdeutlicht das PCM–Prinzip. Die zugehörige Bildbeschreibung findet man auf den ersten Seiten des Kapitels [[Modulationsverfahren/Pulscodemodulation|Pulscodemodulation]] im Buch&bdqoü;Modulationsverfahren&rdquo;.
 
 
 
{{GraueBox|
 
Hinweis: Die Wiedergabegeschwindigkeit der Videos kann verändert werden. Firefox bietet nach einem Rechtsklick aufs Video ein Untermenü an, für Google Chrome kann man z.B. das Plugin "Video Speed Controller" installieren.
 
}}
 
  
  
{{GraueBox|
+
Die Grafik verdeutlicht das PCM–Prinzip.&nbsp; Eine ausführliche Beschreibung findet man auf den ersten Seiten des Kapitels&nbsp; [[Modulationsverfahren/Pulscodemodulation|Pulscodemodulation]]&nbsp; im Buch &bdquo;Modulationsverfahren&rdquo;.  
'''Beispiel''': Wird ein Sprachsignal spektral auf die Bandbreite $B$ = 4 kHz  ⇒  Abtastrate $f_A$ = 8 kHz begrenzt, so ergibt sich bei Quantisierung mit 13 Bit  ⇒  Quantisierungsstufenzahl M = $2^13$ = 8192 ein binärer Datenstrom der Datenrate $R$ = 104 kbit/s. Die Daten entstammen der [[Beispiele_von_Nachrichtensystemen/Gesamtes_GSM–Übertragungssystem#Komponenten_der_Sprach.E2.80.93_und_Daten.C3.BCbertragung|GSM–Spezifikation]].
 
Der Quantisierungsrauschabstand beträgt dann 20 · lg $M$ ≈ 78 dB. Bei Quantisierung mit 16 Bit würde sich dieser auf etwa 96 dB erhöhen, aber gleichzeizig steigt dadurch die erforderliche Datenrate auf 128 kbit/s. Die Auswirkungen der Bandbegrenzung auf ein Sprachsignal bzw. Musiksignal können Sie sich mit dem folgenden Interaktionsmodul verdeutlichen:
 
Einfluss einer Bandbegrenzung bei Sprache und Musik.
 
}}
 
  
  
{{GraueBox}}
+
Wegen der erforderlichen Bandbegrenzung und der Quantisierung ist diese Umformung stets verlustbehaftet.&nbsp; Das bedeutet:
Wird ein Sprachsignal spektral auf die Bandbreite $B$ = 4 kHz ⇒  Abtastrate $f_A$ = 8 kHz begrenzt, so ergibt sich bei Quantisierung mit 13 Bit  ⇒  Quantisierungsstufenzahl M = $2^13$ = 8192 ein binärer Datenstrom der Datenrate $R$ = 104 kbit/s. Die Daten entstammen der [[Beispiele_von_Nachrichtensystemen/Gesamtes_GSM–Übertragungssystem#Komponenten_der_Sprach.E2.80.93_und_Daten.C3.BCbertragung|GSM–Spezifikation]].
+
*Die Codefolge&nbsp; $〈c_ν〉$&nbsp; hat weniger Information als das Signal&nbsp; $q(t)$.
Der Quantisierungsrauschabstand beträgt dann 20 · lg $M$ ≈ 78 dB. Bei Quantisierung mit 16 Bit würde sich dieser auf etwa 96 dB erhöhen, aber gleichzeizig steigt dadurch die erforderliche Datenrate auf 128 kbit/s. Die Auswirkungen der Bandbegrenzung auf ein Sprachsignal bzw. Musiksignal können Sie sich mit dem folgenden Interaktionsmodul verdeutlichen:
+
*Das Sinkensignal&nbsp; $v(t)$&nbsp; unterscheidet sich grundsätzlich von&nbsp; $q(t)$.  
Einfluss einer Bandbegrenzung bei Sprache und Musik
+
*Meist ist die Abweichung allerdings nicht sehr groß.
 +
<br clear=all>
 +
Wir nennen nun beispielhaft zwei auf Pulscodemodulation aufbauende Übertragungsverfahren.
  
{{end}}
+
{{GraueBox|TEXT=
 +
$\text{Beispiel 2:}$&nbsp; 
 +
Die folgenden Daten sind der&nbsp; [[Beispiele_von_Nachrichtensystemen/Gesamtes_GSM–Übertragungssystem#Komponenten_der_Sprach.E2.80.93_und_Daten.C3.BCbertragung|GSM–Spezifikation]]&nbsp; entnommen:
 +
*Wird ein Sprachsignal spektral auf die Bandbreite&nbsp; $B = 4 \, \rm kHz$ &nbsp; ⇒  &nbsp; Abtastrate $f_{\rm A} = 8 \, \rm kHz$&nbsp; begrenzt, so ergibt sich bei Quantisierung mit&nbsp; $13 \, \rm Bit$  &nbsp; ⇒  &nbsp;  Quantisierungsstufenzahl&nbsp; $M = 2^{13} = 8192$&nbsp; ein binärer Datenstrom der Datenrate&nbsp; $R = 104 \, \rm  kbit/s$.
 +
*Der Quantisierungsrauschabstand beträgt dann&nbsp; $20 · \lg M ≈ 78 \, \rm dB$.
 +
*Bei Quantisierung mit&nbsp; $16 \, \rm Bit$&nbsp; erhöht sich dieser auf&nbsp; $96 \, \rm dB$.&nbsp; Gleichzeitig steigt dadurch allerdings die erforderliche Datenrate auf&nbsp; $R = 128 \, \rm kbit/s$.
  
{{Beispiel}}
 
Wird ein Sprachsignal spektral auf die Bandbreite $B = 4 \, \rm kHz$ &nbsp; ⇒  &nbsp; Abtastrate $f_{\rm A} = 8 \, \rm kHz$ begrenzt, so ergibt sich bei Quantisierung mit $13 \, \rm Bit$  &nbsp; ⇒  &nbsp;  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$. Diese Daten entstammen der [[Beispiele_von_Nachrichtensystemen/Gesamtes_GSM–Übertragungssystem#Komponenten_der_Sprach.E2.80.93_und_Daten.C3.BCbertragung|GSM–Spezifikation]].
 
  
Bei Quantisierung mit $16 \, \rm Bit$ würde sich dieser auf etwa $96 \, \rm dB$ erhöhen, aber gleichzeizig steigt dadurch die erforderliche Datenrate auf $128 \, \rm kbit/s$. Die Auswirkungen der Bandbegrenzung auf ein Sprachsignal bzw. Musiksignal können Sie sich mit dem Interaktionsmodul [[Einfluss einer Bandbegrenzung bei Sprache und Musik]] verdeutlichen.
+
Die Auswirkungen einer Bandbegrenzung verdeutlicht das interaktive Applet&nbsp; [[Applets:Bandbegrenzung|Einfluss einer Bandbegrenzung bei Sprache und Musik]].}}
  
{{end}}
 
  
 +
{{GraueBox|TEXT=
 +
$\text{Beispiel 3:}$&nbsp; 
 +
Der Standard&nbsp; [[Beispiele_von_Nachrichtensystemen/Allgemeine_Beschreibung_von_ISDN|ISDN]]&nbsp; ("Integrated Services Digital Network")&nbsp; für Telefonie über Zweidrahtleitung basiert ebenfalls auf dem PCM–Prinzip, wobei jedem Teilnehmer zwei B–Kanäle&nbsp; ("Bearer Channels")&nbsp; mit je &nbsp;$64 \, \rm  kbit/s$ &nbsp; ⇒ &nbsp; $M = 2^{8} = 256$&nbsp; und ein D–Kanal&nbsp; ("Data Channel")&nbsp; mit &nbsp;$ 16 \, \rm  kbit/s$&nbsp; zur Verfügung gestellt wird.
 +
*Die Nettodatenrate beträgt somit&nbsp;
 +
:$$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&nbsp;
 +
:$$R_{\rm Brutto} = 192 \, \rm  kbit/s.$$}}
  
Der Standard [[Beispiele_von_Nachrichtensystemen/Allgemeine_Beschreibung_von_ISDN|ISDN]] (''Integrated Services Digital Network'') für Telefonie über Zweidrahtleitung basiert auf dem PCM–Prinzip, wobei jedem Teilnehmer zwei B–Kanäle (''Bearer Channels'') mit je 64 kbit/s  ⇒  $M$ = $2^8$ = 256 und ein D–Kanal (Data Channel) mit 16 kbit/s zur Verfügung gestellt wird. Die Nettodatenrate beträgt somit 144 kbit/s. Unter Berücksichtigung der Kanalcodierung und der Steuerbits (aus organisatorischen Gründen erforderlich) kommt man auf die ISDN–Bruttodatenrate von 192 kbit/s.
 
  
 +
Im Mobilfunk konnten anfangs sehr große Datenraten (noch) nicht bewältigt werden.&nbsp; Hier wurden in den 1990er–Jahren Sprachcodierverfahren entwickelt, die zu einer Datenkomprimierung um den Faktor&nbsp; $8$&nbsp; und mehr führten.&nbsp; Zu erwähnen sind aus heutiger Sicht:
 +
*Der&nbsp; [[Beispiele_von_Nachrichtensystemen/Sprachcodierung#Halfrate_Vocoder_und_Enhanced_Fullrate_Codec|Enhanced Full–Rate Codec]]&nbsp; $\rm (EFR)$, der pro Sprachrahmen von&nbsp; $20\, \rm  ms$&nbsp; genau&nbsp; $244 \, \rm  Bit$&nbsp; extrahiert&nbsp; $($Datenrate:&nbsp; $12.2 \, \rm  kbit/s)$; <br>erreicht wird diese Datenkomprimierung um mehr als den Faktor&nbsp; $8$&nbsp; durch die Aneinanderreihung mehrerer Verfahren:
 +
:# &nbsp;"Linear Predictive Coding"&nbsp; $\rm (LPC$,&nbsp; Kurzzeitprädiktion$)$,
 +
:# &nbsp;"Long Term Prediction"&nbsp; $\rm (LTP$,&nbsp; Langzeitprädiktion$)$,
 +
:# &nbsp;"Regular Pulse Excitation"&nbsp; $\rm (RPE)$.
 +
*Der&nbsp; [[Beispiele_von_Nachrichtensystemen/Sprachcodierung#Adaptive_Multi.E2.80.93Rate_Codec|Adaptive Multi–Rate Codec]]&nbsp; $\rm (AMR)$, der auf&nbsp; [[Beispiele_von_Nachrichtensystemen/Sprachcodierung#Algebraic_Code_Excited_Linear_Prediction|$\rm ACELP$]]&nbsp; ("Algebraic Code Excited Linear Prediction") basiert und mehrere Modi zwischen&nbsp; $12.2 \, \rm  kbit/s$&nbsp; $\rm (EFR)$&nbsp; und&nbsp; $4.75 \, \rm  kbit/s$&nbsp; bereit stellt, so dass bei schlechterer Kanalqualität eine verbesserte Kanalcodierung eingesetzt werden kann.
 +
*Der&nbsp; [[Beispiele_von_Nachrichtensystemen/Sprachcodierung#Verschiedene_Sprachcodierverfahren|Wideband–AMR]]&nbsp; $\rm (WB-AMR)$&nbsp; mit neun Modi zwischen&nbsp; $6.6 \, \rm  kbit/s$&nbsp; und&nbsp; $23.85 \, \rm  kbit/s$.&nbsp; Dieser wird bei&nbsp; [[Beispiele_von_Nachrichtensystemen/Allgemeine_Beschreibung_von_UMTS|UMTS]]&nbsp; eingesetzt und ist für breitbandigere Signale zwischen&nbsp; $200 \, \rm  Hz$&nbsp; und&nbsp; $7 \, \rm  kHz$&nbsp; geeignet.&nbsp; Die Abtastung erfolgt mit&nbsp; $16 \, \rm  kHz$, die Quantisierung mit&nbsp; $4 \, \rm  Bit$.
  
Im Mobilfunk können 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ühren. Zu erwähnen sind aus heutiger Sicht:
 
*der [[Beispiele_von_Nachrichtensystemen/Sprachcodierung#Halfrate_Vocoder_und_Enhanced_Fullrate_Codec|Enhanced Full–Rate Codec]] (EFR), der pro Sprachrahmen von 20 ms genau 244 Bit extrahiert (Datenrate: 12.2 kbit/s); erreicht wird diese Datenkomprimierung um mehr als den Faktor 8 durch die Aneinanderreihung mehrerer Verfahren: ''Linear Predictive Coding'' (LPC, Kurzzeitprädiktion), ''Long Term Prediction'' (LTP, Langzeitprädiktion) und ''Regular Pulse Excitation'' (RPE);
 
*der [[Beispiele_von_Nachrichtensystemen/Sprachcodierung#Adaptive_Multi.E2.80.93Rate_Codec|Adaptive Multi–Rate Codec]] (AMR), der auf [[Beispiele_von_Nachrichtensystemen/Sprachcodierung#Algebraic_Code_Excited_Linear_Prediction|ACELP]] (''Algebraic Code Excited Linear Prediction'') basiert und mehrere Modi zwischen 12.2 kbit/s (EFR) und 4.75 kbit/s bereit stellt, so dass bei schlechterer Kanalqualität eine verbesserte Kanalcodierung eingesetzt werden kann;
 
*der [[Beispiele_von_Nachrichtensystemen/Sprachcodierung|Wideband–AMR]] (WB–AMR) mit neun Modi zwischen 6.6 kbit/s und 23.85 kbit/s. Dieser wird bei UMTS eingesetzt und ist für breitbandigere Signale zwischen 200 Hz und 7 kHz geeignet. Die Abtastung erfolgt mit 16 kHz, die Quantisierung mit 4 Bit.
 
  
 +
Alle diese Komprimierungsverfahren werden im Kapitel&nbsp; [[Beispiele_von_Nachrichtensystemen/Sprachcodierung|Sprachcodierung]]&nbsp; im Buch &bdquo;Beispiele von Nachrichtensystemen&rdquo; im Detail beschrieben.&nbsp; Das Audio–Modul&nbsp; [[Applets:Qualität_verschiedener_Sprach–Codecs_(Applet)|Qualität verschiedener Sprach–Codecs]]&nbsp; ermöglicht einen subjektiven Vergleich dieser Codecs.
  
Das Audio–Interaktionsmodul Qualität verschiedener Sprach–Codecs vergleicht diese Codecs.
 
  
 
==MPEG–2 Audio Layer III – kurz MP3  ==
 
==MPEG–2 Audio Layer III – kurz MP3  ==
 +
<br>
 +
Das heute (2015) am weitesten verbreitete Kompressionsverfahren für Audiodateien ist&nbsp; [https://de.wikipedia.org/wiki/MP3 MP3].&nbsp; Entwickelt wurde dieses Format ab 1982 am Fraunhofer–Institut für Integrierte Schaltungen (IIS) in Erlangen unter der Federführung von Prof.&nbsp; [https://de.wikipedia.org/wiki/Hans-Georg_Musmann Hans–Georg Musmann]&nbsp; in Zusammenarbeit mit der Friedrich Alexander Universität Erlangen–Nürnberg und den AT&T Bell Labs.&nbsp; 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.
  
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 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&nbsp; [https://en.wikipedia.org/wiki/WAV WAV]–Format zu reduzieren.&nbsp; Die Zusammenstellung ist nicht vollständig.&nbsp; Eine umfassende Darstellung findet man zum Beispiel in einem&nbsp; [https://de.wikipedia.org/wiki/MP3 Wikipedia Artikel]&nbsp; hierzu.
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 [https://de.wikipedia.org/wiki/MP3 Wikipedia Artikel] hierzu.
+
*Das Audio–Kompressionsverfahren &bdquo;MP3&rdquo; nutzt unter anderem auch psychoakustische Effekte der Wahrnehmung aus.&nbsp; So kann der Mensch zwei Töne erst ab einem gewissen Mindestunterschied der Tonhöhen voneinander unterscheiden.&nbsp; Man spricht von so genannten „Maskierungseffekten”.
*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öhe 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.&nbsp; Ein dominanter Ton bei&nbsp; $4 \,  \rm kHz$&nbsp; kann beispielsweise dazu führen, dass benachbarte Frequenzen bis zu&nbsp; $11 \,  \rm kHz$&nbsp; für das momentane Hörempfinden nur eine untergeordnete Bedeutung besitzen.
*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 kHz kann beispielsweise dazu führen, dass benachbarte Frequenzen bis zu 11 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&nbsp; [[Modulationsverfahren/Pulscodemodulation#Quantisierung_und_Quantisierungsrauschen|Quantisierungsrauschen]]&nbsp; noch maskiert wird und nicht hörbar ist.
*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 [[Modulationsverfahren/Pulscodemodulation#Quantisierung_und_Quantisierungsrauschen|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&nbsp; [[Informationstheorie/Entropiecodierung_nach_Huffman|Huffman–Codierung]]&nbsp; des resultierenden Datenstroms.&nbsp; Beide Maßnahmen sind verlustlos.
*Weitere MP3–Kompressionsmechanismen sind die Ausnutzung der Korrelationen zwischen den beiden Kanälen eines Stereosignals durch Differenzbildung sowie die [[Informationstheorie/Entropiecodierung_nach_Huffman|Huffman–Codierung]] des resultierenden Datenstroms. Beide Maßnahmen sind verlustlos.
 
  
  
Nachteil der MP3–Codierung ist, dass bei starker Kompression auch „wichtige” Frequenzanteile von der Kompression 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.
+
Nachteil der MP3–Codierung ist, dass bei starker Kompression ungewollt auch „wichtige” Frequenzanteile erfasst werden und es dadurch zu hörbaren Fehlern kommt.&nbsp; Ferner ist es störend, dass aufgrund der blockweisen Anwendung des MP3–Verfahrens am Ende einer Datei Lücken entstehen können.&nbsp; Abhilfe schafft die Verwendung des so genannten&nbsp; [https://en.wikipedia.org/wiki/LAME LAME]–Coders – ein ''Open–Source–Project'' – und eines entsprechenden Abspielprogramms.
  
 
   
 
   
==Voraussetzungen für Kapitel 2  ==
+
==Beschreibung verlustloser  Quellencodierung &ndash; Voraussetzungen==
 
+
<br>
 
Im Folgenden betrachten wir ausschließlich verlustlose Quellencodierverfahren und gehen dabei von folgenden Annahmen aus:
 
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_μ$ }:
+
*Die digitale Quelle besitze den Symbolumfang&nbsp; $M$.&nbsp; Für die einzelnen Quellensymbole der Folge&nbsp; $〈q_ν〉$&nbsp; gelte mit dem Symbolvorrat&nbsp; $\{q_μ\}$:
 
   
 
   
$$q_{\nu} \in \{ q_{\mu} \}\hspace{0.05cm}, \hspace{0.2cm}\mu = 1, ... \hspace{0.05cm}, M  \hspace{0.05cm}. $$
+
:$$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:
+
:Die einzelnen Folgenelemente&nbsp; $q_ν$&nbsp; können statistisch unabhängig sein oder auch statistische Bindungen aufweisen.&nbsp;
: $M$ = 4:   $q_μ$ ∈ {'''A''', '''B''', '''C''', '''D'''},         mit den Wahrscheinlichkeiten $p_A$, $p_B$, $p_C$, $p_D$,
+
* Zunächst betrachten wir&nbsp; '''Nachrichtenquellen ohne Gedächtnis''', die allein durch die Symbolwahrscheinlichkeiten vollständig charakterisiert sind, zum Beispiel:
: $M$ = 8:   $q_μ$ ∈ {'''A''', '''B''', '''C''', '''D''', '''E''', '''F''', '''G''', '''H'''}, Wahrscheinlichkeiten $p_A$, ... , $p_H$.
+
:$$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},$$
*Der Quellencodierer ersetzt das Quellensymbol durch das Codewort $C(q_μ)$, bestehend aus $L_μ$ Codesymbolen eines neuen Alphabets {0, 1, ... , $D$ – 1} mit dem Symbolumfang $D$. Damit ergibt sich für die '''mittlere Codewortlänge''':
+
:$$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&nbsp; $q_μ$&nbsp; durch das Codewort&nbsp; $\mathcal{C}(q_μ)$, bestehend aus&nbsp; $L_μ$&nbsp; Codesymbolen eines neuen Alphabets mit dem Symbolumfang&nbsp; $D$&nbsp; $\{0, \ 1$, ... ,&nbsp; $D - 1\}$.&nbsp; Damit ergibt sich für die&nbsp; '''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}. $$
+
:$$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}. $$
  
{{Beispiel}}
+
{{GraueBox|TEXT=
Wir betrachten zwei verschiedene Quellencodierungen, jeweils mit den Parametern $M$ = 9 und $D$ = 3. Bei der ersten Codierung $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:
+
$\text{Beispiel 4:}$&nbsp;  Wir betrachten zwei verschiedene Arten von Quellencodierung,&nbsp; jeweils mit den Parametern&nbsp; $M = 9$&nbsp; und&nbsp; $D = 3$.
: '''A C F B I G''' ⇒ 00 02 12 01 22 20
 
Bei dieser Codierung haben alle Codeworte $C_1(q_μ)$ mit 1 ≤ $μ$ ≤ 9 die gleiche Länge $L_μ$ = 2. Damit ist auch die mittlere Codewortlänge $L_M$ = 2.
 
  
[[Datei:P_ID2316__Inf_T_2_1_S3_Ganz_neu.png|Zwei Beispiele für Quellencodierung]]
+
[[Datei:P_ID2316__Inf_T_2_1_S3_Ganz_neu.png|right|frame|Zwei Beispiele für Quellencodierung]]
  
Dagegen gilt beim zweiten, dem blauen Quellencodierer $L_μ$ ∈ {1, 2} und dementsprechend wird die mittlere Codewortlänge kleiner sein als zwei Codesymbole pro Quellensymbol. Hier gilt die Zuordnung:
+
*Bei der Codierung&nbsp; $\mathcal{C}_1(q_μ)$&nbsp; gemäß der (roten) Zeile 2 der Tabelle wird jedes Quellensymbol&nbsp; $q_μ$&nbsp; durch zwei Ternärsymbole&nbsp; $(0$,&nbsp; $1$&nbsp; oder&nbsp; $2)$&nbsp; ersetzt.&nbsp; Beispielsweise gilt die Zuordnung:
: '''A C F B I G''' 0 02 12 01 22 2.
+
: $$\rm A C F B I G \ \ 00 \ 02 \ 12 \ 01 \ 22 \ 20.$$
Es ist offensichtlich, dass diese zweite Codesymbolfolge nicht eindeutig decodiert werden kann.
+
*Bei dieser Codierung haben alle Codeworte&nbsp; $\mathcal{C}_1(q_μ)$&nbsp; mit&nbsp; $1 ≤ μ ≤ 6$&nbsp; die gleiche Länge&nbsp; $L_μ = 2$.&nbsp; Damit ist auch die mittlere Codewortlänge&nbsp; $L_{\rm M} = 2$.
  
{{end}}
+
 
 +
*Beim blauen Quellencodierer gilt&nbsp; $L_μ ∈ \{1, \ 2 \}$.&nbsp; Hier ist die mittlere Codewortlänge&nbsp;  $L_{\rm M}$&nbsp;  kleiner als zwei Codesymbole pro Quellensymbol, und es 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 ==
 
==Kraftsche Ungleichung – Präfixfreie Codes ==
 
+
<br>
Codes zur Komprimierung einer gedächtnislosen wertdiskreten Quelle zeichnen sich dadurch aus, dass die einzelnen Symbole durch verschieden lange Codesymbolfolgen dargestellt werden:
+
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}, M ) \hspace{0.05cm}.$$
+
:$$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,
 
Nur dann ist es möglich,
*dass die '''mittlere Codewortlänge minimal''' wird,
+
*dass die&nbsp; '''mittlere Codewortlänge minimal'''&nbsp; wird,
*falls die '''Quellensymbole nicht gleichwahrscheinlich''' sind.
+
*falls die&nbsp; '''Quellensymbole nicht gleichwahrscheinlich'''&nbsp; sind.
  
  
 
Um eine eindeutige Decodierung zu ermöglichen, muss der Code zudem „präfixfrei” sein.
 
Um eine eindeutige Decodierung zu ermöglichen, muss der Code zudem „präfixfrei” sein.
  
{{Definition}}
+
{{BlaueBox|TEXT=
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.
+
$\text{Definition:}$&nbsp; Die Eigenschaft&nbsp; '''präfixfrei'''&nbsp; sagt aus, dass kein Codewort der Präfix (Beginn) eines längeren Codewortes sein darf.&nbsp; Ein solcher Code ist sofort decodierbar.}}
  
{{end}}
 
  
 +
*Der blaue Code im&nbsp; [[Informationstheorie/Allgemeine_Beschreibung#Beschreibung_verlustloser_Quellencodierung_.E2.80.93_Voraussetzungen|Beispiel 4]]&nbsp; ist nicht präfixfrei.&nbsp; Beispielsweise könnte die Codesymbolfolge „01” vom Decoder als&nbsp; $\rm AD$&nbsp; interpretiert werden, aber ebenso als&nbsp; $\rm B$.
 +
*Dagegen ist der rote Code präfixfrei, wobei hier die Präfixfreiheit wegen&nbsp; $L_μ = \rm const.$&nbsp; nicht unbedingt erforderlich wäre.
  
Der zweite (blaue) Code im Beispiel ist nicht präfixfrei. Beispielsweise könnte die Codesymbolfolge „01” vom Decoder als '''AD''' interpretiert werden, aber ebenso als '''B'''. Dagegen ist der rote Code präfixfrei, wobei hier die Präfixfreiheit wegen $L_μ$ = const. nicht unbedingt erforderlich wäre.
+
 
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. :
+
{{BlaueBox|TEXT=
 +
$\text{Ohne Beweis:}$&nbsp; 
 +
Die notwendige&nbsp; '''Bedingung für die Existenz eines präfixfreien Codes'''&nbsp; wurde von Leon Kraft in seiner Master Thesis 1949 am&nbsp; Massachusetts Institute of Technology&nbsp; (MIT) angegeben:
 
   
 
   
$$\sum_{\mu=1}^{M} \hspace{0.2cm} D^{-L_{\mu}} \le 1 \hspace{0.05cm}.$$
+
:$$\sum_{\mu=1}^{M} \hspace{0.2cm} D^{-L_{\mu} } \le 1 \hspace{0.05cm}.$$}}
 +
 
  
{{Beispiel}}
+
{{GraueBox|TEXT=
Überprüft man den zweiten (blauen) Code des betrachteten Beispiels mit $M$ = 9 und $D$ = 3, so erhält man:
+
$\text{Beispiel 5:}$&nbsp; 
 +
Überprüft man den zweiten (blauen) Code von&nbsp;  [[Informationstheorie/Allgemeine_Beschreibung#Beschreibung_verlustloser_Quellencodierung_.E2.80.93_Voraussetzungen|Beispiel 4]]&nbsp; mit&nbsp; $M = 9$&nbsp; und&nbsp; $D = 3$, so erhält man:
 
   
 
   
$$3 \cdot 3^{-1} + 6 \cdot 3^{-2} = 1.667 > 1 \hspace{0.05cm}.$$
+
:$$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.
 
  
{{end}}
+
Daraus ist ersichtlich, dass dieser Code nicht präfixfrei sein kann.}}
  
  
{{Beispiel}}
+
{{GraueBox|TEXT=
Betrachten wir den binären Code
+
$\text{Beispiel 6:}$&nbsp;  Betrachten wir den binären Code
 
   
 
   
$$\boldsymbol{{\rm A }} \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 0  
+
:$$\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 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}, \hspace{0.2cm}\boldsymbol{\rm C } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 11
 
\hspace{0.05cm}, $$
 
\hspace{0.05cm}, $$
  
so ist dieser offensichtlich nicht präfixfrei. Die Gleichung
+
so ist dieser offensichtlich nicht präfixfrei.&nbsp; Die Gleichung
 
   
 
   
$$1 \cdot 2^{-1} + 2 \cdot 2^{-2} =  1 $$
+
:$$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
 
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  
+
:$$\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 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}, \hspace{0.2cm}\boldsymbol{\rm C } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 11
\hspace{0.05cm}.$$
+
\hspace{0.05cm}.$$}}
 
 
 
 
{{end}}
 
  
  
 
==Quellencodierungstheorem==   
 
==Quellencodierungstheorem==   
 +
<br>
 +
Wir betrachten nun eine redundante Nachrichtenquelle mit dem Symbolvorrat&nbsp; $〈q_μ〉$, wobei die Laufvariable&nbsp; $μ$&nbsp; alle Werte zwischen&nbsp; $1$&nbsp; und dem Symbolumfang&nbsp; $M$&nbsp; annimmt.&nbsp; Die Quellenentropie&nbsp; $H$&nbsp; sei kleiner als&nbsp; $H_0=\log_2 \ M$.
  
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&nbsp; $(H_0- H)$&nbsp; ist entweder zurückzuführen
Die Redundanz $H_0$ – $H$ geht entweder zurück
+
*auf nicht gleichwahrscheinliche Symbole &nbsp;  &nbsp; $p_μ ≠ 1/M$,&nbsp; und/oder
*auf nicht gleichwahrscheinliche Symbole     $p_μ$ ≠ 1/ $M$, und/oder
+
*auf statistische Bindungen innerhalb der Folge&nbsp; $〈q_\nu〉$.
*auf statistische Bindungen innerhalb der Folge $〈qμ〉$.
 
  
  
Ein Quellencodierer ersetzt das Quellensymbol $q_μ$ durch das binäre Codewort $C(q_μ)$, bestehend aus $L_μ$ Binärsymbolen (Nullen oder Einsen). Damit ergibt sich die mittlere Codewortlänge zu
+
Ein Quellencodierer ersetzt das Quellensymbol&nbsp; $q_μ$&nbsp; durch das binäre Codewort&nbsp; $\mathcal{C}(q_μ)$, bestehend aus&nbsp; $L_μ$&nbsp; Binärsymbolen&nbsp; (Nullen oder Einsen).&nbsp; 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}. $$
+
:$$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:
+
Für die hier beschriebene Quellencodierungsaufgabe kann die folgende notwendige Bedingung angegeben werden:
  
 +
{{BlaueBox|TEXT=
 +
$\text{Theorem:}$&nbsp; 
 +
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&nbsp; $H$&nbsp; Binärsymbole pro Quellensymbol verwendet.
  
{{Definition}}
+
*Die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; kann auf keinen Fall kleiner sein kann als die Entropie&nbsp; $H$&nbsp; der Quellensymbolfolge: &nbsp; $L_{\rm M} \ge H  \hspace{0.05cm}. $
'''Shannons Quellencodierungstheorem''': Für die vollständige Rekonstruktion der gesendeten Zeichenfolge aus der Binärfolge ist es hinreichend, aber auch notwendig, dass man zur sendeseitigen Codierung im Mittel $H$ Binärsymbole pro Quellensymbol verwendet. Das heißt, dass die mittlere Codewortlänge auf keinen Fall kleiner sein kann als die Entropie $H$ der Quellensymbolfolge:
 
 
$$L_{\rm M} \ge H  \hspace{0.05cm}. $$
 
  
{{end}}
+
*Man bezeichnet diese Gesetzmäßigkeit als das&nbsp; ''' Quellencodierungstheorem''', das auf&nbsp; [https://de.wikipedia.org/wiki/Claude_Shannon Claude Elwood Shannon]&nbsp; zurückgeht.&nbsp;
 +
*Berücksichtigt der Quellencodierer nur die unterschiedlichen Auftrittswahrscheinlichkeiten, nicht aber die inneren statistischen Bindungen der Folge , dann gilt&nbsp; $L_{\rm M} ≥ H_1$ &nbsp;  ⇒ &nbsp;  [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Entropie_hinsichtlich_Zweiertupel|erste Entropienäherung]].}}
  
  
Berücksichtigt der Quellencodierer nur die unterschiedlichen Auftrittswahrscheinlichkeiten, nicht aber die inneren statistischen Bindungen, dann gilt $L_M ≥ H_1$  ⇒  [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Entropie_hinsichtlich_Zweiertupel|erste Entropienäherung]].
+
{{GraueBox|TEXT=
 
+
$\text{Beispiel 7:}$&nbsp; 
 
 
{{Beispiel}}
 
 
Bei einer Quaternärquelle mit den Symbolwahrscheinlichkeiten
 
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}
+
:$$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} $$
 
\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:
+
ergibt sich in obiger Gleichung das Gleichheitszeichen  &nbsp; ⇒  &nbsp; $L_{\rm M} = H$, wenn man zum Beispiel folgende Zuordnung wählt:
 
   
 
   
$$\boldsymbol{{\rm A }} \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 0  
+
:$$\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 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 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}, \hspace{0.2cm}\boldsymbol{\rm D }\hspace{0.15cm} \Rightarrow \hspace{0.15cm} 111
 
\hspace{0.05cm}. $$
 
\hspace{0.05cm}. $$
  
 
Dagegen ergibt sich mit der gleichen Zuordnung und
 
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
+
:$$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.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}$$
 
\hspace{0.3cm} \Rightarrow \hspace{0.3cm} H = 1.845\,\, {\rm bit/Quellensymbol}$$
Zeile 280: Zeile 309:
 
die mittlere Codewortlänge
 
die mittlere Codewortlänge
 
   
 
   
$$L_{\rm M} = 0.4 \cdot 1 + 0.3 \cdot 2 + 0.2 \cdot 3 + 0.1 \cdot 3  
+
:$$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}. $$
 
= 1.9\,\, {\rm bit/Quellensymbol}\hspace{0.05cm}. $$
  
Wegen der ungünstigen Symbolwahrscheinlichkeiten (keine Zweierpotenzen) ist hier $L_M > H$.
+
Wegen der ungünstig gewählten Symbolwahrscheinlichkeiten (keine Zweierpotenzen) ist hier $L_{\rm M} > H$.}}
  
{{end}}
 
  
 +
[[Datei:P_ID2323__Inf_T_2_1_S6_ganz_neu.png|right|frame|Buchstabencodierungen nach Bacon/Bandot, Morse und Huffman]]
  
Es folgt ein zweites Beispiel, wobei die Quellensymbolfolge einen natürlichen Text beschreibt.
+
{{GraueBox|TEXT=
 +
$\text{Beispiel 8:}$&nbsp; 
 +
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, teilweise deutlich verschiedene Häufigkeitsangaben,&nbsp; auch deshalb,&nbsp; weil diese 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”,&nbsp; „Y”&nbsp; und&nbsp; „Q”.
 +
<br clear=all>
 +
Zu dieser Tabelle ist zu anzumerken:
 +
*Die Entropie dieses Alphabets mit&nbsp; $M = 27$&nbsp; Zeichen wird&nbsp; $H≈ 4 \, \rm bit/Zeichen$&nbsp; betragen.&nbsp; Wir haben das nicht nachgerechnet.&nbsp; [https://de.wikipedia.org/wiki/Francis_Bacon Francis Bacon]&nbsp; hat aber schon 1623 einen Binärcode angegeben, bei dem jeder Buchstabe mit fünf Bit dargestellt wurde: &nbsp; $L_{\rm M} = 5$.
 +
*Etwa 250 Jahre danach hat&nbsp; [https://de.wikipedia.org/wiki/Baudot-Code Jean-Maurice-Émile Baudot]&nbsp; diesen Code übernommen, der später auch für die gesamte Telegrafie standardisiert wurde.&nbsp; 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&nbsp; [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus|Huffman–Code]]&nbsp; für obige Häufigkeitsverteilung an.&nbsp; Wahrscheinliche Zeichen wie „E” oder „N” und auch das „Blank” werden mit nur drei Bit dargestellt, das seltene „Q” dagegen mit&nbsp; $11$ Bit.
 +
*Die mittlere Codewortlänge &nbsp;$L_{\rm M} = H + ε$&nbsp; ist geringfügig größer als&nbsp; $H$, wobei wir uns hier über die kleine positive Größe&nbsp; $ε$&nbsp; nicht genauer auslassen wollen.&nbsp; Nur soviel: &nbsp; Es gibt keinen präfixfreien Code mit kleinerer mittlerer Wortlänge als den Huffman–Code.
 +
*Auch&nbsp; [https://de.wikipedia.org/wiki/Morsezeichen Samuel Morse]&nbsp; berücksichtigte bereits bei seinem Code für die Telegrafie in den 1840er Jahren die unterschiedlichen Häufigkeiten.&nbsp; 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&nbsp;  $L_{\rm M} < 4$&nbsp; gelten wird.&nbsp; Dies hängt aber damit zusammen, dass dieser Code nicht präfixfrei ist.&nbsp; Zwischen jeder Kurz–Lang–Sequenz musste deshalb der Funker eine Pause einlegen, damit die Gegenstation das Funksignal auch entschlüsseln konnte.}}
 +
  
{{Beispiel}}
+
==Aufgaben zum Kapitel==
Beispiel 2: Betrachten wir noch frühere Versuche der Quellencodierung für die Übertragung von 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”.
+
<br>
 
+
[[Aufgaben:2.1 Codierung mit und ohne Verlust|Aufgabe 2.1: Codierung mit und ohne Verlust]]
[[Datei:P_ID2323__Inf_T_2_1_S6_ganz_neu.png|Buchstabencodierungen nach Bacon/Bandot, Morse und Huffman]]
 
 
 
Zu obiger Tabelle ist zu bemerken:
 
*Die Entropie dieses Alphabets mit $M$ = 27 Zeichen wird $H$ ≈ 4 bit/Zeichen betragen. Wir haben das nicht nachgerechnet. Bacon hat aber schon 1623 einen Binärcode angegeben, bei dem jeder Buchstabe mit fünf Bit dargestellt wird: $L_M$ = 5.
 
*Etwa 250 Jahre danach hat [https://de.wikipedia.org/wiki/Baudot-Code 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 gibt einen beispielhaften [[Informationstheorie/Entropiecodierung_nach_Huffman#Der_Huffman.E2.80.93Algorithmus|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 ist geringfügig größer als $H$ ⇒ $L_M$ = $H + ε$, wobei wir uns hier über das $ε$ nicht auslassen wollen. Nur soviel: Es gibt keinen präfixfreien Code mit kleinerer mittlerer Wortlänge als den Huffman–Code.
 
*Auch [https://de.wikipedia.org/wiki/Morsezeichen 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 $L_M$ < 4 gelten wird. Dies hängt aber auch damit zusammen, dass dieser 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.
 
 
 
{{end}}
 
 
  
== Aufgaben zu Kapitel 2.1 ==
+
[[Aufgaben:2.2 Kraftsche Ungleichung|Aufgabe 2.2: Kraftsche Ungleichung]]
  
 +
[[Aufgaben:2.2Z Mittlere Codewortlänge|Aufgabe 2.2Z: Mittlere Codewortlänge]]
  
  
 
{{Display}}
 
{{Display}}

Aktuelle Version vom 13. Juli 2021, 15:01 Uhr

# Ü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:

Vereinfachtes Modell eines Nachrichtenübertragungssystems
  • 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” .


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  (bei Bewegtbildsequenzen zu verschiedenen Zeiten)  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  "Übertragungscodierung"  genannt – 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 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, 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:

  • $\rm JPEG$  $($mit Komprimierungsfaktor  $8)$,  und
  • $\rm 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  $\rm JPEG$  (linke Darstellung) ermöglicht gegenüber der pixelweisen Abspeicherung einen Komprimierungsfaktor von  $8$  bis  $15$  bei (nahezu) verlustfreier Komprimierung.

  • Selbst mit dem Komprimierungsfaktor  $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  $\rm 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 JPEG–Qualität (links) ist deutlich schlechter als das PNG–Resultat, obwohl die resultierende Dateigröße 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  $\rm (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 Beschreibung 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 anfangs sehr große Datenraten (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  $\rm (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"  $\rm (LPC$,  Kurzzeitprädiktion$)$,
  2.  "Long Term Prediction"  $\rm (LTP$,  Langzeitprädiktion$)$,
  3.  "Regular Pulse Excitation"  $\rm (RPE)$.
  • Der  Adaptive Multi–Rate Codec  $\rm (AMR)$, der auf  $\rm ACELP$  ("Algebraic Code Excited Linear Prediction") basiert und mehrere Modi zwischen  $12.2 \, \rm kbit/s$  $\rm (EFR)$  und  $4.75 \, \rm kbit/s$  bereit stellt, so dass bei schlechterer Kanalqualität eine verbesserte Kanalcodierung eingesetzt werden kann.
  • Der  Wideband–AMR  $\rm (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$.

Zwei Beispiele für Quellencodierung
  • Bei der Codierung  $\mathcal{C}_1(q_μ)$  gemäß der (roten) Zeile 2 der 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$.


  • Beim blauen Quellencodierer gilt  $L_μ ∈ \{1, \ 2 \}$.  Hier ist die mittlere Codewortlänge  $L_{\rm M}$  kleiner als zwei Codesymbole pro Quellensymbol, und es 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  $H_0=\log_2 \ M$.

Die Redundanz  $(H_0- H)$  ist entweder zurückzuführen

  • auf nicht gleichwahrscheinliche Symbole   ⇒   $p_μ ≠ 1/M$,  und/oder
  • auf 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 die folgende notwendige Bedingung 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}$  kann 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 das  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$.


Buchstabencodierungen nach Bacon/Bandot, Morse und Huffman

$\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, teilweise deutlich verschiedene Häufigkeitsangaben,  auch deshalb,  weil diese 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”.


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 wurde:   $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 1840er 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