Difference between revisions of "Information Theory/General Description"

From LNTwww
(34 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
 
{{Header
 
{{Header
|Untermenü=Quellencodierung – Datenkomprimierung
+
|Untermenü=Source Coding - Data Compression
|Vorherige Seite=Natürliche wertdiskrete Nachrichtenquellen
+
|Vorherige Seite=Natural Discrete Sources
 
|Nächste Seite=Komprimierung nach Lempel, Ziv und Welch
 
|Nächste Seite=Komprimierung nach Lempel, Ziv und Welch
 
}}
 
}}
  
== # Ü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 (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.&nbsp; Im Folgenden sei die Ausgangsfolge stets binär.
 
  
 +
== # OVERVIEW OF THE SECOND MAIN CHAPTER # ==
 +
<br>&nbsp;
 +
Shannon's Information Theory is applied, for example, in the&nbsp; '''Source coding''' of digital&nbsp; (i.e. discrete-value and discrete-time)&nbsp; message sources.&nbsp;  In this context, one also speaks of&nbsp; '''Data compression'''.
  
Im Einzelnen werden behandelt:
+
*Attempts are made to reduce the redundancy of natural digital sources such as measurement data, texts, or voice and image files&nbsp; (after digitization)&nbsp; by recoding them, so that they can be stored and transmitted more efficiently.
 +
*In most cases, source encoding is associated with a change of the symbol set size.&nbsp; in the following, the output sequence is always binary.
  
*die unterschiedlichen Ziele von ''Quellencodierung'', ''Kanalcodierung''&nbsp; und ''Leitungscodierung'',
 
*''verlustbehaftete''&nbsp; 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''&nbsp; und ''Welch'',
 
*der ''Huffman–Code''&nbsp; als die bekannteste und effizienteste Form der Entropiecodierung,
 
*der ''Shannon–Fano–Code''&nbsp; sowie die ''arithmetische Codierung'' – beide gehören ebenfalls zur Klasse der Entropiecodierer,
 
*die ''Lauflängencodierung''&nbsp; sowie die ''Burrows-Wheeler Transformation''&nbsp; (BWT).
 
  
 +
The following is a detailed discussion:
  
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
+
:*The different destinations of&nbsp; &raquo;source coding&laquo;,&nbsp; &raquo;channel coding&laquo;&nbsp; and&nbsp; &raquo;line coding&laquo;,
 +
:*&raquo;lossy encoding methods&laquo;&nbsp; for analog sources, for example GIF, TIFF, JPEG, PNG, MP3,
 +
:*the&nbsp; &raquo;source encoding theorem&laquo;, which specifies a limit for the average codeword length,
 +
:*the frequently used data compression according to&nbsp; &raquo;Lempel, Ziv and Welch&laquo;,
 +
:*the&nbsp; &raquo;Huffman code&laquo;&nbsp; as the best known and most efficient form of entropy coding,
 +
:*the&nbsp; &raquo;Shannon-Fano code&laquo;&nbsp; as well as the&nbsp; &raquo;arithmetic coding&laquo; - both belong to the class of entropy encoders as well,
 +
:*the&nbsp; &raquo;run-length coding&laquo;&nbsp; (RLC)&nbsp; and the&nbsp; &raquo;Burrows-Wheeler transformation&laquo;&nbsp; (BWT).
  
*dem Windows-Programm&nbsp; [http://en.lntwww.de/downloads/Sonstiges/Programme/WDIT.zip WDIT] &nbsp;&rArr;&nbsp; Link verweist auf die ZIP-Version des Programms; und
 
*der zugehörigen&nbsp; [http://en.lntwww.de/downloads/Sonstiges/Texte/Wertdiskrete_Informationstheorie.pdf Praktikumsanleitung]  &nbsp;&rArr;&nbsp; Link verweist auf die PDF-Version.
 
  
  
==Quellencodierung – Kanalcodierung – Leitungscodierung  ==
+
== Source coding - Channel coding - Line coding ==
 
<br>
 
<br>
Wir betrachten für die Beschreibungen in diesem zweiten Kapitel das folgende digitale Übertragungsmodell:
+
For the descriptions in this second chapter we consider the following model of a digital transmission system:
*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.
+
[[File:EN_Inf_T_2_1_S1_v2.png|right|frame|Simplified model of a digital transmission system]]
*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” .
 
  
 +
*The source signal&nbsp; $q(t)$&nbsp; can be analog as well as digital, just like the sink signal&nbsp; $v(t)$.&nbsp; All other signals in this block diagram, even those not explicitly named here, are digital.
 +
*In particular, also the signals&nbsp; $x(t)$&nbsp; and&nbsp; $y(t)$&nbsp; at the input and output of the&nbsp; "digital channel"&nbsp; are digital and can therefore also be described completely by the symbol sequences&nbsp; $〈x_ν〉$&nbsp; and&nbsp; $〈y_ν〉$.
 +
*The&nbsp; "digital channel"&nbsp; includes not only the transmission medium and interference (noise) but also components of the transmitter&nbsp; (modulator, transmitter pulse shaper, etc.)&nbsp; and the receiver&nbsp; (demodulator, receive filter, detector, decision maker).
 +
*The chapter&nbsp; [[Digital_Signal_Transmission/Parameters of Digital Channel Models|Parameters of Digital Channel Models]]&nbsp; in the book&nbsp; "Digital Signal Transmission"&nbsp; describes the modeling of the&nbsp; "digital channel".
 +
<br clear=all>
 +
As can be seen from this block diagram, there are three different types of coding, depending on the target direction.&nbsp; Each of which is realized by the&nbsp; "encoder"&nbsp; on the transmission side and the corresponding&nbsp; "decoder"&nbsp; at the receiver:
  
[[File:P_ID2315__Inf_T_2_1_S1_neu.png|center|frame|Vereinfachtes Modell eines Nachrichtenübertragungssystems]]
+
Task of the&nbsp; '''source coding'''&nbsp; is the reduction of redundancy for data compression, as it is used for example in image coding.&nbsp; By using correlations between the individual points of an image or between the brightness values of a pixel at different times&nbsp; (for moving picture sequences)&nbsp; procedures can be developed which lead to a noticeable reduction of the amount of data (measured in bit or byte) with nearly the same picture quality.&nbsp; A simple example is the&nbsp; &raquo;differential pulse code modulation&laquo;&nbsp; (DPCM).
  
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:
+
With&nbsp; '''channel coding'''&nbsp; on the other hand, a noticeable improvement of the transmission behavior is achieved by using a redundancy specifically added at the transmitter to detect and correct transmission errors at the receiver side.&nbsp; Such codes, whose most important representatives are&nbsp; &raquo;block codes&laquo;,&nbsp; &raquo;convolutional codes&laquo;&nbsp; and&nbsp; &raquo;turbo codes&laquo;,&nbsp; are of great importance, especially for heavily disturbed channels.&nbsp; The greater the relative redundancy of the coded signal, the better the correction properties of the code, but at a reduced payload data rate.
  
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 zu verschiedenen Zeiten&nbsp; (bei Bewegtbildsequenzen)&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 ''differentielle Pulscodemodulation''&nbsp; (DPCM).
+
'''Line coding'''&nbsp; is used to adapt the transmission signal&nbsp; $x(t)$&nbsp; to the spectral characteristics of the channel and the receiving equipment by recoding the source symbols. &nbsp; For example, in the case of an&nbsp; (analog)&nbsp; transmission channel over which no direct signal can be transmitted, for which thus&nbsp; $H_{\rm K}(f = 0) = 0$, it must be ensured by line coding that the code symbol sequence does not contain long sequences of the same polarity.
  
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. Je größer die relative Redundanz des codierten Signals ist, desto besser sind die Korrektureigenschaften des Codes, allerdings bei verringerter Nutzdatenrate.
+
The focus of this chapter is on lossless source coding, which generates a data-compressed code symbol sequence&nbsp; $〈c_ν〉$&nbsp; starting from the source symbol sequence&nbsp; $〈q_ν〉$&nbsp; and based on the results of information theory.
  
Eine&nbsp; '''Leitungscodierung'''&nbsp; – manchmal auch als ''Übertragungscodierung''&nbsp; bezeichnet – 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.
+
* Channel coding is the subject of a separate book in our tutorial with the following&nbsp; [[Channel_Coding|Content]]&nbsp;.  
 +
*The channel coding is discussed in detail in the chapter "Coded and multilevel transmission" of the book&nbsp; [[Digital_Signal_Transmission]]&nbsp;.
  
  
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.
+
''Note'': &nbsp; We uniformly use&nbsp; "$\nu$"&nbsp; here as a control variable of a symbol sequence.&nbsp; Normally, for&nbsp; $〈q_ν〉$,&nbsp; $〈c_ν〉$&nbsp; and&nbsp; $〈x_ν〉$&nbsp; different indices should be used if the rates do not match.
  
*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&nbsp; [[Digitalsignalübertragung]]&nbsp; eingehend behandelt.
 
  
 +
== Lossy source coding for images==
 +
<br>
 +
For digitizing analog source signals such as speech, music or pictures, only lossy source coding methods can be used.&nbsp; Even the storage of a photo in&nbsp; [https://en.wikipedia.org/wiki/BMP_file_format BMP]&nbsp; format is always associated with a loss of information due to sampling, quantization and the finite color depth.
  
''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.
+
However, there are also a number of compression methods for images that result in much smaller image files than&nbsp; "BMP", for example:
 
+
*[https://en.wikipedia.org/wiki/GIF GIF]&nbsp; ("Graphics Interchange Format"), developed by Steve Wilhite in 1987.
 +
*[https://en.wikipedia.org/wiki/JPEG JPEG]&nbsp; - a format that was introduced in 1992 by the&nbsp; "Joint Photography Experts Group"&nbsp; and is now the standard for digital cameras.&nbsp; Ending: &nbsp; "jpeg"&nbsp; or&nbsp; "jpg".
 +
*[https://en.wikipedia.org/wiki/TIFF TIFF]&nbsp; ("Tagged Image File Format"), around 1990 by Aldus Corp. (now Adobe) and Microsoft, still the quasi-standard for print-ready images of the highest quality.
 +
*[https://en.wikipedia.org/wiki/Portable_Network_Graphics PNG]&nbsp; ("Portable Network Graphics"), designed in 1995 by T. Boutell and T. Lane as a replacement for the patent-encumbered GIF format, is less complex than TIFF.
  
==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.
 
  
Es gibt aber auch  für Bilder eine Vielzahl von Kompressionsverfahren, die zu deutlich kleineren Bilddateien als „BMP” führen, zum Beispiel:
+
These compression methods partly use
*[https://en.wikipedia.org/wiki/GIF GIF]&nbsp; (''Graphics Interchange Format''&nbsp;), 1987 von Steve Wilhite entwickelt.
+
*vector quantization for redundancy reduction of correlated pixels,  
*[https://de.wikipedia.org/wiki/JPEG JPEG]&nbsp; – ein Format, das 1992 von der ''Joint Photographie Experts Group''&nbsp; vorgestellt wurde und heute der Standard für Digitalkameras ist.&nbsp; Endung: &nbsp; „jpeg” bzw. „jpg”.
+
*at the same time the lossless compression algorithms according to&nbsp; [[Information_Theory/Entropy Coding According to Huffman#The_Huffman.E2.80.93Algorithm|Huffman]]&nbsp; and&nbsp; [[Information_Theory/Compression According to Lempel, Ziv and Welch|Lempel/Ziv]],  
*[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 der Quasi–Standard für druckreife Bilder höchster Qualität.
+
*possibly also transformation coding based on DFT&nbsp; ("Discrete Fourier Transform")&nbsp; and&nbsp; DCT&nbsp; ("Discrete Cosine Transform"),  
*[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, ist weniger komplex als TIFF.
+
*then quantization and transfer in the transformed range.
  
  
Diese Kompressionsverfahren nutzen teilweise
+
We now compare the effects of two compression methods on the subjective quality of photos and graphics, namely:
*Vektorquantisierung zur Redundanzminderung korrelierter Bildpunkte,  
+
*$\rm JPEG$&nbsp; $($with compression factor&nbsp; $8)$,&nbsp; and
*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]],
+
*$\rm PNG$&nbsp; $($with compression factor&nbsp; $24)$.
*eventuell auch Transformationscodierungen basierend auf DFT&nbsp; (''Diskrete Fouriertransformation''&nbsp;)&nbsp; und&nbsp; DCT&nbsp; (''Diskrete Cosinustransformation''&nbsp;),
 
*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:
+
{{GraueBox|TEXT=
*'''JPEG'''&nbsp; $($mit Komprimierungsfaktor&nbsp; $8)$,&nbsp; und
+
$\text{Example 1:}$&nbsp;
*'''PNG'''&nbsp; $($mit Komprimierungsfaktor&nbsp; $24)$.
+
In the upper part of the graphic you can see two compressions of a photo.
 +
[[File:EN_Inf_T_2_1_S2.png|right|frame|Compare JPEG and PNG compression]]
 +
The format&nbsp; $\rm JPEG$ &nbsp; (left image) allows a compression factor of&nbsp; $8$&nbsp; to&nbsp; $15$&nbsp; with (nearly) lossless compression.
 +
*Even with the compression factor&nbsp; $35$&nbsp; the result can still be called&nbsp; "good".
 +
*For most consumer digital cameras, "JPEG"&nbsp; is the default storage format.
  
  
{{GraueBox|TEXT=
+
The image shown on the right was compressed with&nbsp; $\rm PNG$.  
$\text{Beispiel 1:}$&nbsp;
+
*The quality is similar to the JPEG result, although the compression is about&nbsp; $3$&nbsp; stronger.  
Im oberen Teil der folgenden Grafik sehen Sie zwei Komprimierungen eines Fotos.
+
*In contrast, PNG achieves a worse compression result than JPEG if the photo contains a lot of color gradations.  
[[File:P_ID2920__Inf_T_2_1_S2_neu.png|right|frame|Vergleich zwischen JPEG– und PNG–Komprimierung]]
 
Das Format&nbsp; '''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 Komprimierunsfaktor&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.
 
  
  
Das rechts dargestellte Bild wurde mit&nbsp; '''PNG'''&nbsp; komprimiert.
+
PNG is also better suited for line drawings with captions than JPEG (compare the lower images).&nbsp;  
*Die Qualität ist vergleichbar mit dem linken JPEG–Bild, obwohl die Komprimierung um etwa den Faktor&nbsp; $3$ stärker ist.
+
*The quality of the JPEG compression (on the left) is significantly worse than the PNG result, although the resulting file size is about three times as large.&nbsp;  
*Dagegen erzielt PNG ein schlechteres Komprimierungsergebnis als JPEG, wenn das Foto sehr viele Farbstufungen enthält.  
+
*Especially fonts look "washed out".
 
<br clear=all>
 
<br clear=all>
Auch bei Strichzeichnungen mit Beschriftungen ist PNG besser geeignet als JPEG (untere Bilder).&nbsp; Die Qualität der JPEG–Komprimierung (links) ist deutlich schlechter als das PNG–Resultat, obwohl die resultierende Dateigröße etwa dreimal so groß ist.&nbsp; Insbesondere Schriften wirken „verwaschen”.
+
''Note'': &nbsp; Due to technical limitations of&nbsp; $\rm LNTww$&nbsp; all graphics had to be saved as&nbsp; "PNG".
 +
*In the above graphic, "JPEG" means the PNG conversion of a file previously compressed with&nbsp; "JPEG".
 +
*However, the associated loss is negligible. }}
  
''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. }}
 
  
 
   
 
   
Line 105: Line 103:
 
 
 
 
 
 
 
 
==Verlustbehaftete Quellencodierung  für Audiosignale==
+
== Lossy source coding for audio signals==
 
<br>
 
<br>
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; (PCM), die aus einem analogen Quellensignal&nbsp; $q(t)$&nbsp; die Codesymbolfolge&nbsp; $〈c_ν〉$&nbsp; extrahiert, entsprechend den drei Verarbeitungsblöcken
+
A first example of source coding for speech and music is the&nbsp; [https://en.wikipedia.org/wiki/Pulse-code_modulation pulse-code modulation]&nbsp; $\rm (PCM)$, invented in 1938, which extracts the code symbol sequence&nbsp; $〈c_ν〉 $&nbsp;from an analog source signal&nbsp; $q(t)$, corresponding to the three processing blocks
[[File:P_ID2925__Mod_T_4_1_S1_neu.png|right|frame|Prinzip der Pulscodemodulation (PCM)]]
+
[[File:EN_Mod_T_4_1_S1_v2.png|right|frame|Prinzip der Pulscodemodulation (PCM)]]  
*Abtastung,
+
*Sampling,
*Quantisierung, und
+
*Quantization,  
*PCM–Codierung.
+
*PCM encoding.
 +
 
 +
 
 +
The graphic illustrates the PCM principle.&nbsp; A detailed description of the picture can be found on the first pages of the chapter&nbsp; [[Modulation_Methods/Pulse Code Modulation|Pulse-code modulation]]&nbsp; in the book&nbsp; "Modulation Methods".  
  
  
Die Grafik verdeutlicht das PCM–Prinzip.&nbsp; Eine ausführliche Bildbeschreibung findet man auf den ersten Seiten des Kapitels&nbsp; [[Modulationsverfahren/Pulscodemodulation|Pulscodemodulation]]&nbsp; im Buch&bdquo;Modulationsverfahren&rdquo;.  
+
Because of the necessary band limitation and quantization, this transformation is always lossy.&nbsp; That means
 +
*The code sequence&nbsp; $〈c_ν〉$&nbsp; has less information than the source signal&nbsp; $q(t)$.
 +
*The sink signal&nbsp; $v(t)$&nbsp; is fundamentally different from&nbsp; $q(t)$.
 +
*Mostly, however, the deviation is not very large.
  
  
Wegen der erforderlichen Bandbegrenzung und der Quantisierung ist diese Umformung stets verlustbehaftet.&nbsp; Das bedeutet:
+
We will now mention two transmission methods based on pulse code modulation as examples.
*Die Codefolge&nbsp; $〈c_ν〉$&nbsp;  hat weniger Information als das Signal&nbsp; $q(t)$.
 
*Das Sinkensignal&nbsp; $v(t)$&nbsp; unterscheidet sich grundsätzlich von&nbsp; $q(t)$.
 
*Meist ist die Abweichung allerdings nicht sehr groß.
 
 
<br clear=all>
 
<br clear=all>
Wir nennen nun beispielhaft zwei auf Pulscodemodulation aufbauende Übertragungsverfahren.
 
 
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 2:}$&nbsp;   
+
$\text{Example 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:
+
The following data is taken from the&nbsp; [[Examples_of_Communication_Systems/Entire GSM Transmission System#Components_of_Language.E2.80.93_and_Data.C3.BCtransmission|GSM specification]]:
*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$.  
+
*If a speech signal is spectrally limited to the bandwidth&nbsp; $B = 4 \, \rm kHz$ &nbsp; ⇒ &nbsp; sampling rate $f_{\rm A} = 8 \, \rm kHz$&nbsp; with a quantization of $13 \, \rm bit$ &nbsp; ⇒ &nbsp; number of quantization levels&nbsp; $M = 2^{13} = 8192$&nbsp; a binary data stream of data rate&nbsp; $R = 104 \, \rm kbit/s$ results.  
*Der Quantisierungsrauschabstand beträgt dann&nbsp; $20 · \lg M ≈ 78 \, \rm dB$.  
+
*The quantization noise ratio is then&nbsp; $20 \cdot \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$.  
+
*For quantization with&nbsp; $16 \, \rm bit$&nbsp; this increases to&nbsp; $96 \, \rm dB$.&nbsp; At the same time, however, the required data rate increases to&nbsp; $R = 128 \, \rm kbit/s$.  
  
  
Die Auswirkungen einer Bandbegrenzung verdeutlicht das interaktive Applet&nbsp; [[Applets:Bandbegrenzung|Einfluss einer Bandbegrenzung bei Sprache und Musik]].}}
+
The following (German language) interactive SWF applet illustrates the effects of a bandwidth limitation:<br> &nbsp; &nbsp; &nbsp; [[Applets:Bandwidth Limitation|Einfluss einer Bandbegrenzung bei Sprache und Musik]]&nbsp;&rArr;  &nbsp;  "Impact of a Bandwidth Limitation for Speech and Music" .}}
  
  
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 3:}$&nbsp;   
+
$\text{Example 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;)&nbsp; mit je &nbsp;$64 \, \rm kbit/s$ &nbsp; ⇒ &nbsp; $M = 2^{8} = 256$&nbsp; und ein D–Kanal&nbsp; (''Data Channel''&nbsp;)&nbsp; mit &nbsp;$ 16 \, \rm kbit/s$&nbsp; zur Verfügung gestellt wird.  
+
The standard&nbsp; [[Examples_of_Communication_Systems/General_Description_of_ISDN|ISDN]]&nbsp; ("Integrated Services Digital Network") for telephony via two-wire line is also based on the PCM principle, whereby each user is assigned two B-channels&nbsp; (''Bearer Channels''&nbsp;)&nbsp; with &nbsp;$64 \, \rm kbit/s$ &nbsp; ⇒ &nbsp; $M = 2^{8} = 256$&nbsp; and a D-channel&nbsp; (''Data Channel''&nbsp;)&nbsp; with &nbsp;$ 16 \, \rm kbit/s$.  
*Die Nettodatenrate beträgt somit&nbsp; $R_{\rm Netto} = 144 \, \rm kbit/s$.  
+
*The net data rate is thus&nbsp; $R_{\rm net} = 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$.}}
+
*In consideration of the channel coding and the control bits (required for organizational reasons), the ISDN gross data rate of&nbsp; $R_{\rm gross} = 192 \, \rm kbit/s$.}}
  
  
Im Mobilfunk konnten sehr große Datenraten oft (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:
+
In mobile communications, very high data rates often could not (yet) be handled.&nbsp; In the 1990s, voice coding procedures were developed that led to data compression by the factor&nbsp; $8$&nbsp; and more.&nbsp; From today's point of view, it is worth mentioning:
*der&nbsp; [[Beispiele_von_Nachrichtensystemen/Sprachcodierung#Halfrate_Vocoder_und_Enhanced_Fullrate_Codec|Enhanced Full–Rate Codec]]&nbsp; ('''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:  
+
*The&nbsp; [[Examples_of_Communication_Systems/Voice Coding#Halfrate_Vocoder_and_Enhanced_Fullrate_Codec|Enhanced Full-Rate Codec]]&nbsp; $\rm (EFR)$, which extracts&nbsp; exactly&nbsp; $244 \, \rm bit$&nbsp; for each speech frame of&nbsp; $20\, \rm ms$&nbsp;$($Data rate: &nbsp; $12. 2 \, \rm kbit/s)$; <br> this data compression of more than the factor&nbsp; $8$&nbsp; is achieved by stringing together several procedures:  
:# &nbsp;''Linear Predictive Coding''&nbsp; ('''LPC''', Kurzzeitprädiktion),  
+
:# &nbsp;Linear Predictive Coding&nbsp; $\rm (LPC$, short term prediction$)$,  
:# &nbsp;''Long Term Prediction''&nbsp; ('''LTP''', Langzeitprädiktion) und
+
:# &nbsp;Long Term Prediction&nbsp; $\rm (LTP)$,  
:# &nbsp;''Regular Pulse Excitation''&nbsp; ('''RPE''');
+
:# &nbsp;Regular Pulse Excitation&nbsp; $\rm (RPE)$.
*der&nbsp; [[Beispiele_von_Nachrichtensystemen/Sprachcodierung#Adaptive_Multi.E2.80.93Rate_Codec|Adaptive Multi–Rate Codec]]&nbsp; ('''AMR'''), der auf&nbsp; [[Beispiele_von_Nachrichtensystemen/Sprachcodierung#Algebraic_Code_Excited_Linear_Prediction|ACELP]]&nbsp; (''Algebraic Code Excited Linear Prediction'') basiert und mehrere Modi zwischen&nbsp; $12.2 \, \rm kbit/s$&nbsp; (EFR) und&nbsp; $4.75 \, \rm kbit/s$&nbsp; bereit stellt, so dass bei schlechterer Kanalqualität eine verbesserte Kanalcodierung eingesetzt werden kann;
+
*The&nbsp; [[Examples_of_Communication_Systems/Voice Coding#Adaptive_Multi.E2.80. 93Rate_Codec|Adaptive Multi-Rate Codec]]&nbsp; $\rm (AMR)$&nbsp; based on&nbsp; [[Examples_of_Communication_Systems/Voice Coding#Algebraic_Code_Excited_Linear_Prediction|$\rm ACELP$]]&nbsp; ("Algebraic Code Excited Linear Prediction")&nbsp; and several modes between&nbsp; $12. 2 \, \rm kbit/s$&nbsp; $\rm (EFR)$&nbsp; and&nbsp; $4.75 \, \rm kbit/s$&nbsp; so that improved channel coding can be used in case of poorer channel quality.
*der&nbsp; [[Beispiele_von_Nachrichtensystemen/Sprachcodierung#Verschiedene_Sprachcodierverfahren|Wideband–AMR]]&nbsp; ('''WB–AMR''') 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$.
+
*The&nbsp; [[Examples_of_Communication_Systems/Voice Coding#Various_Language Coding Methods|Wideband-AMR]]&nbsp; $\rm (WB-AMR)$&nbsp; with nine modes between&nbsp; $6.6 \, \rm kbit/s$&nbsp; and&nbsp; $23.85 \, \rm kbit/s$. &nbsp; This is used with&nbsp; [[Examples_of_Communication_Systems/General_Description_of_UMTS|UMTS]]&nbsp; and is suitable for broadband signals between&nbsp; $200 \, \rm Hz$&nbsp; and&nbsp; $7 \, \rm kHz$. &nbsp; Sampling is done with&nbsp; $16 \, \rm kHz$, quantization with&nbsp; $4 \, \rm 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.
+
All these compression methods are described in detail in the chapter&nbsp; [[Examples_of_Communication_Systems/Voice Coding|Voice Coding]]&nbsp; of the book "Examples of Communication Systems" &nbsp; The (German language) audio module&nbsp; [[Applets:Quality of different voice codecs (Applet)|"Qualität verschiedener Sprach-Codecs"]] &nbsp; &rArr; &nbsp; "Quality of different voice codecs"&nbsp; allows a subjective comparison of these codecs.
  
  
==MPEG–2 Audio Layer III – kurz MP3 ==
+
==MPEG-2 Audio Layer III - short "MP3" ==
 
<br>
 
<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.
+
Today (2015) the most common compression method for audio files is&nbsp; [https://en.wikipedia.org/wiki/MP3 MP3].&nbsp; This format was developed from 1982 on at the Fraunhofer Institute for Integrated Circuits (IIS) in Erlangen under the direction of Professor&nbsp; [https://www.tnt.uni-hannover.de/en/staff/musmann/ Hans-Georg Musmann]&nbsp; in collaboration with the Friedrich Alexander University Erlangen-Nuremberg and AT&T Bell Labs.&nbsp; Other institutions are also asserting patent claims in this regard, so that since 1998 various lawsuits have been filed which, to the authors' knowledge, have not yet been finally concluded.
  
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.
+
In the following some measures are called, which are used with&nbsp; "MP3", in order to reduce the data quantity in relation to the raw version in the&nbsp; [https://en.wikipedia.org/wiki/WAV "wav"]-format.&nbsp; The compilation is not complete.&nbsp; A comprehensive representation about this can be found for example in a&nbsp; [https://en.wikipedia.org/wiki/MP3 Wikipedia article].
*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”.
+
*The audio compression method&nbsp; "MP3"&nbsp; uses among other things psychoacoustic effects of perception.&nbsp; So a person can only distinguish two sounds from each other from a certain minimum difference in pitch.&nbsp; One speaks of so-called&nbsp; "masking effects".
*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.
+
*Using the masking effects, signal components that are less important for the auditory impression are stored with less bits (reduced accuracy).&nbsp; A dominant tone at&nbsp; $4 \, \rm kHz$&nbsp; can, for example, cause neighboring frequencies to be of only minor importance for the current auditory sensation up to&nbsp; $11 \, \rm kHz$.
*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.
+
*The greatest advantage of MP3 coding, however, is that the sounds are stored with just enough bits so that the resulting&nbsp; [[Modulation_Methods/Pulse_Code_Modulation#Quantization_and_quantization_noise|quantization noise]]&nbsp; is still masked and is not audible.
*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.
+
*Other MP3 compression mechanisms are the exploitation of the correlations between the two channels of a stereo signal by difference formation as well as the&nbsp; [[Information_Theory/Entropy Coding According to Huffman|Huffman Coding]]&nbsp; of the resulting data stream.&nbsp; Both measures are lossless.
  
  
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.
+
A disadvantage of the MP3 coding is that with strong compression also&nbsp; "important"&nbsp; frequency components are unintentionally captured and thus audible errors occur.&nbsp; Furthermore it is disturbing that due to the blockwise application of the MP3 procedure gaps can occur at the end of a file.&nbsp; A remedy is the use of the so-called&nbsp; [https://en.wikipedia.org/wiki/LAME "LAME coder"]&nbsp; and a corresponding player.
  
 
   
 
   
==Beschreibung verlustloser  Quellencodierung &ndash; Voraussetzungen==
+
==Description of lossless source encoding &ndash; Requirements==
 
<br>
 
<br>
Im Folgenden betrachten wir ausschließlich verlustlose Quellencodierverfahren und gehen dabei von folgenden Annahmen aus:
+
In the following, we only consider lossless source coding methods and make the following assumptions:
*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_μ\}$:
+
*The digital source has the symbol set size&nbsp; $M$.&nbsp; For the individual source symbols of the sequence&nbsp; $〈q_ν〉$&nbsp; applies with the symbol set&nbsp; $\{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}. $$
+
:$$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&nbsp; $q_ν$&nbsp; können statistisch unabhängig sein oder auch statistische Bindungen aufweisen.&nbsp;
+
The individual sequence elements&nbsp; $q_ν$&nbsp; may can be&nbsp; "statistically independent"&nbsp; or&nbsp; "statistically dependent".
* Zunächst betrachten wir&nbsp; '''Nachrichtenquellen ohne Gedächtnis''', die allein durch die Symbolwahrscheinlichkeiten vollständig charakterisiert sind, zum Beispiel:
+
* First we consider&nbsp; '''discrete sources without memory''', which are fully characterized by the symbol probabilities alone, for example:
:$$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 = 4\text{:} \  \  \  q_μ \in \{ {\rm A}, \ {\rm B}, \ {\rm C}, \ {\rm D} \}, \hspace{3.0cm} \text{with the probabilities}\ 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}.$$
+
:$$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{with the probabilities }\ 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''':
+
*The source encoder replaces the source symbol&nbsp; $q_μ$&nbsp; with the code word&nbsp; $\mathcal{C}(q_μ)$, <br>consisting of&nbsp; $L_μ$&nbsp; code symbols of a new alphabet with the symbol set size&nbsp; $D$&nbsp; $\{0, \ 1$, ... ,&nbsp; $D - 1\}$.&nbsp; This gives the&nbsp; '''average code word length''':
 
   
 
   
 
:$$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}. $$
  
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 4:}$&nbsp; Wir betrachten zwei verschiedene Arten von Quellencodierung, jeweils mit den Parametern&nbsp; $M = 9$&nbsp; und&nbsp; $D = 3$.
+
$\text{Example 4:}$&nbsp; We consider two different types of source encoding, each with parameters&nbsp; $M = 9$&nbsp; and&nbsp; $D = 3$.
  
*Bei der ersten Codierung&nbsp; $\mathcal{C}_1(q_μ)$&nbsp; gemäß Zeile 2 (rote Darstellung) der unteren 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:
+
[[File:EN_Inf_T_2_1_S3_v2.png|right|frame|Two examples of source encoding]]
 +
 
 +
*In the first encoding&nbsp; $\mathcal{C}_1(q_μ)$&nbsp; according to line 2 (red) of the table, each source symbol&nbsp; $q_μ$&nbsp; is replaced by two ternary symbols&nbsp; $(0$,&nbsp; $1$&nbsp; or&nbsp; $2)$.&nbsp; &nbsp; Here we have for example the mapping:  
 
: $$\rm A C F B I G \ ⇒ \ 00 \ 02 \ 12 \ 01 \ 22 \ 20.$$
 
: $$\rm A C F B I G \ ⇒ \ 00 \ 02 \ 12 \ 01 \ 22 \ 20.$$
*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$.
+
*With this coding, all code words&nbsp; $\mathcal{C}_1(q_μ)$&nbsp; with&nbsp; $1 ≤ μ ≤ 6$&nbsp; have the same length&nbsp; $L_μ = 2$.&nbsp; Thus, the average code word length is&nbsp; $L_{\rm M} = 2$.
  
  
[[File:P_ID2316__Inf_T_2_1_S3_Ganz_neu.png|center|frame|Zwei Beispiele für Quellencodierung]]
+
*For the second, the blue source encoder holds&nbsp; $L_μ ∈ \{1, 2 \}$.&nbsp; Accordingly, the average code word length&nbsp; $L_{\rm M}$&nbsp; will be less than two code symbols per source symbol.&nbsp; For example, the mapping:  
 
 
*Dagegen gilt beim zweiten, dem blauen Quellencodierer&nbsp; $L_μ ∈ \{1, 2 \}$&nbsp; und dementsprechend wird die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; kleiner sein als zwei Codesymbole pro Quellensymbol. Hier gilt die Zuordnung:
 
 
: $$\rm A C F B I G \ ⇒ \ 0 \ 02 \ 12 \ 01 \ 22 \ 2.$$
 
: $$\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. }}
+
*It is obvious that this code symbol sequence cannot be decoded unambiguously, since the symbol sequence naturally does not include the spaces inserted in this text for display reasons. }}
 
   
 
   
  
==Kraftsche Ungleichung – Präfixfreie Codes ==
+
==Kraft–McMillan inequality - Prefix-free codes ==
 
<br>
 
<br>
Binäre Codes zur Komprimierung einer gedächtnislosen wertdiskreten Quelle zeichnen sich dadurch aus, dass die einzelnen Symbole durch verschieden lange Codesymbolfolgen dargestellt werden:
+
Binary codes for compressing a memoryless discrete-value source are characterized by the fact that the individual symbols are represented by code symbol sequences of different lengths:
 
   
 
   
 
:$$L_{\mu} \ne {\rm const.}  \hspace{0.4cm}(\mu = 1, \hspace{0.05cm}\text{...} \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,
+
Only then it is possible,
*dass die&nbsp; '''mittlere Codewortlänge minimal'''&nbsp; wird,
+
*that the&nbsp; '''average code word length becomes minimal''',
*falls die&nbsp; '''Quellensymbole nicht gleichwahrscheinlich'''&nbsp; sind.
+
*if the&nbsp; '''source symbols are not equally probable'''.
  
  
Um eine eindeutige Decodierung zu ermöglichen, muss der Code zudem „präfixfrei” sein.
+
To enable a unique decoding, the code must also be "prefix-free".
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
$\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.}}
+
$\text{Definition:}$&nbsp; The property&nbsp; '''prefix-free'''&nbsp; indicates that no codeword may be the prefix (beginning) of a longer codeword.&nbsp; Such a codeword is immediately decodable.}}
 
 
 
 
*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.
 
  
 +
*The blue code in&nbsp; [[Information_Theory/General_Description#Description_of_lossless_source_encoding_.E2.80.93_Prerequisites|Example 4]]&nbsp; is not prefix-free.&nbsp; For example, the code symbol sequence "01" could be interpreted by the decoder as&nbsp; $\rm AD$&nbsp; but also as&nbsp; $\rm B$.
 +
*The red code, on the other hand, is prefix-free, although prefix freedom would not be absolutely necessary here because of&nbsp; $L_μ = \rm const.$
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
$\text{Ohne Beweis:}$&nbsp;   
+
$\text{Without proof:}$&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 :
+
The necessary&nbsp; '''condition for the existence of a prefix-free code'''&nbsp; was specified by Leon Kraft in his Master Thesis 1949 at the&nbsp; Massachusetts Institute of Technology&nbsp; (MIT):
 
   
 
   
 
:$$\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}.$$}}
Line 229: Line 226:
  
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 5:}$&nbsp;   
+
$\text{Example 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:
+
If you check the second (blue) code of&nbsp; [[Information_Theory/General_Description#Description of lossless source encoding.E2.80.93_Requirements|Example 4]]&nbsp; with&nbsp; $M = 9$&nbsp; and&nbsp; $D = 3$, you get:
 
   
 
   
 
:$$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.}}
+
From this you can see that this code cannot be prefix-free }}
  
  
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 6:}$&nbsp; Betrachten wir den binären Code
+
$\text{Example 6:}$&nbsp; Let's now look at the binary code
 
   
 
   
 
:$$\boldsymbol{\rm A } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 0  
 
:$$\boldsymbol{\rm A } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 0  
Line 245: Line 242:
 
\hspace{0.05cm}, $$
 
\hspace{0.05cm}, $$
  
so ist dieser offensichtlich nicht präfixfrei.&nbsp; Die Gleichung
+
it is obviously not prefix-free.&nbsp; The equation
 
   
 
   
:$$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
+
does not mean that this code is actually prefix-free, it just means that there is a prefix-free code with the same length distribution, for example
 
    
 
    
 
:$$\boldsymbol{\rm A } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 0  
 
:$$\boldsymbol{\rm A } \hspace{0.15cm} \Rightarrow \hspace{0.15cm} 0  
Line 257: Line 254:
  
  
==Quellencodierungstheorem==   
+
== Source coding theorem==   
 
<br>
 
<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 der Nachrichtengehalt&nbsp; $H_0$.
+
We now look at a redundant discrete  source with the symbol set&nbsp; $〈q_μ〉$, where the control variable&nbsp; $μ$&nbsp; takes all values between&nbsp; $1$&nbsp; and the symbol set size&nbsp; $M$.&nbsp; The source entropy&nbsp; $H$&nbsp; is smaller than&nbsp; $H_0= \log_2 \hspace{0.1cm} M$.
  
Die Redundanz&nbsp; $(H_0- H)$&nbsp; geht entweder zurück auf
+
The redundancy&nbsp; $(H_0- H)$&nbsp; is either caused by
*nicht gleichwahrscheinliche Symbole &nbsp; &nbsp; $p_μ ≠ 1/M$,&nbsp; und/oder
+
*not equally probable symbols &nbsp; ⇒ &nbsp; $p_μ ≠ 1/M$,&nbsp; and/or
*statistische Bindungen innerhalb der Folge&nbsp; $〈q_\nu〉$.
+
*statistical bonds within the sequence&nbsp; $〈q_\nu〉$.
  
  
Ein Quellencodierer ersetzt das Quellensymbol&nbsp; $q_μ$&nbsp; durch das binäre Codewort&nbsp; $\mathcal{C}(q_μ)$, bestehend aus&nbsp; $L_μ$&nbsp; Binärsymbolen (Nullen oder Einsen).&nbsp; Damit ergibt sich die mittlere Codewortlänge zu
+
A source encoder replaces the source symbol&nbsp; $q_μ$&nbsp; with the codeword&nbsp; $\mathcal{C}(q_μ)$, consisting of&nbsp; $L_μ$&nbsp; binary symbols (zeros or ones).&nbsp; This results in an average codeword length:
 
   
 
   
:$$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 with} \hspace{0.2cm}p_{\mu} = {\rm Pr}(q_{\mu}) \hspace{0.05cm}. $$
  
Für die hier beschriebene Quellencodierungsaufgabe kann folgende&nbsp; '''Grenze'''&nbsp; angegeben werden:
+
For the source encoding task described here the following requirement can be specified:
  
 
{{BlaueBox|TEXT=
 
{{BlaueBox|TEXT=
 
$\text{Theorem:}$&nbsp;   
 
$\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
+
For the possibility of a complete reconstruction of the sent string from the binary sequence it is sufficient, but also necessary, that for encoding on the transmitting side at least&nbsp; $H$&nbsp; binary symbols per source symbol are used.  
 
 
*man zur sendeseitigen Codierung im Mittel mindestens&nbsp; $H$&nbsp; Binärsymbole pro Quellensymbol verwendet.  
 
  
*die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; auf keinen Fall kleiner sein kann als die Entropie&nbsp; $H$&nbsp; der Quellensymbolfolge: &nbsp;  
+
*The average code word length&nbsp; $L_{\rm M}$&nbsp; cannot be smaller than the entropy&nbsp; $H$&nbsp; of the source symbol sequence: &nbsp; $L_{\rm M} \ge H \hspace{0.05cm}. $
:$$L_{\rm M} \ge H \hspace{0.05cm}. $$
 
  
Man bezeichnet diese Gesetzmäßigkeit als&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]].}}
+
*This regularity is called&nbsp; ''' Source Coding Theorem''', which goes back to&nbsp; [https://en.wikipedia.org/wiki/Claude_Shannon Claude Elwood Shannon].&nbsp; &nbsp;  
 +
*If the source coder considers only the different symbol probabilities, but not the correlation between symbols, then&nbsp; $L_{\rm M} ≥ H_1$ &nbsp; ⇒ &nbsp; [[Information_Theory/Sources with Memory#Entropy with respect to two-tuples|first entropy approximation]].}}
  
  
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 7:}$&nbsp;   
+
$\text{Example 7:}$&nbsp;   
Bei einer Quaternärquelle mit den Symbolwahrscheinlichkeiten
+
For a quaternary source with the symbol probabilities
 
   
 
   
 
:$$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/source\hspace{0.15cm} symbol} $$
  
ergibt sich in obiger Gleichung das Gleichheitszeichen  &nbsp; ⇒ &nbsp; $L_{\rm M} = H$, wenn man zum Beispiel folgende Zuordnung wählt:
+
equality in the above equation &nbsp; ⇒ &nbsp; $L_{\rm M} = H$ results, if for example the following assignment is chosen:
 
   
 
   
 
:$$\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
+
In contrast, with the same mapping and
 
   
 
   
 
:$$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/source\hspace{0.15cm}symbol}$$
  
die mittlere Codewortlänge
+
the average code word length
 
   
 
   
 
:$$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/source\hspace{0.15cm}symbol}\hspace{0.05cm}. $$
  
Wegen der ungünstig gewählten Symbolwahrscheinlichkeiten (keine Zweierpotenzen) ist hier $L_{\rm M} > H$.}}
+
Because of the unfavorably chosen symbol probabilities (no powers of two)&nbsp; &rArr; &nbsp;  $L_{\rm M} > H$.}}
  
  
 +
[[File:EN_Inf_T_2_1_S6.png|right|frame|Character encodings according to Bacon/Bandot, Morse and Huffman]]
 
{{GraueBox|TEXT=
 
{{GraueBox|TEXT=
$\text{Beispiel 8:}$&nbsp;   
+
$\text{Example 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.  
+
We will look at some very early attempts at source encoding for the transmission of natural texts, based on the letter frequencies given in the table.  
*In der Literatur findet man viele unterschiedliche Häufigkeitsangaben,&nbsp; auch deshalb,&nbsp; weil die Untersuchungen für verschiedene Sprachen durchgeführt wurden.  
+
*In the literature many different frequencies are found,&nbsp; also because,&nbsp; the investigations were carried out for different languages.  
*Meist beginnt die Liste aber mit dem Leerzeichen (Blank) sowie „E” und endet mit Buchstaben wie „X”,&nbsp; „Y”&nbsp; und&nbsp; „Q”.
+
*Mostly, however, the list starts with the blank and&nbsp; "E"&nbsp; and ends with letters like&nbsp; "X",&nbsp; "Y"&nbsp; and&nbsp; "Q".
 
+
<br clear=all>
 
+
Please note the following about this table:
[[File:P_ID2323__Inf_T_2_1_S6_ganz_neu.png|center|frame|Buchstabencodierungen nach Bacon/Bandot, Morse und Huffman]]
+
*The entropy of this alphabet with&nbsp; $M = 27$&nbsp; characters will be&nbsp; $H≈ 4 \, \rm bit/character$.&nbsp; We have only estimated this value.&nbsp; [https://en.wikipedia.org/wiki/Francis_Bacon Francis Bacon]&nbsp; had already given a binary code in 1623, where each letter is represented by five bits: &nbsp; $L_{\rm M} = 5$.
 
+
*About 250 years later&nbsp; [https://en.wikipedia.org/wiki/Baudot_code Jean-Maurice-Émile Baudot]&nbsp; adopted this code, which was later standardized for the entire telegraphy.&nbsp; One consideration important to him was that a code with a uniform five binary characters per letter is more difficult for an enemy to decipher, since he cannot draw conclusions about the transmitted character from the frequency of its occurrence.
Zu dieser Tabelle ist zu anzumerken:
+
*The last line in the above table gives an exemplary&nbsp; [[Information_Theory/Entropy_Coding_According_to_Huffman#The_Huffman.E2.80.93Algorithm|Huffman code]]&nbsp; for the above frequency distribution.&nbsp; Probable characters like&nbsp; "E"&nbsp; or&nbsp; "N"&nbsp; and also the&nbsp; "Blank"&nbsp; are represented with three bits only, the rare&nbsp; "Q"&nbsp; on the other hand with eleven bits.  
*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 wird: &nbsp; $L_{\rm M} = 5$.
+
*The average code word length &nbsp;$L_{\rm M} = H + ε$&nbsp; is slightly larger than&nbsp; $H$, whereby we will not go into more detail here about the small positive quantity&nbsp; $ε$.&nbsp; &nbsp; Only this much: &nbsp; There is no prefix-free code with smaller average word length than the Huffman code.
*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.
+
*Also&nbsp; [https://en.wikipedia.org/wiki/Morse_code Samuel Morse]&nbsp; took into account the different frequencies in his code for telegraphy, already in the 1830s.&nbsp; The Morse code of each character consists of two to four binary characters, which are designated here according to the application with dot&nbsp; ("short")&nbsp; and bar&nbsp; ("long").
*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.  
+
*It is obvious that for the Morse code&nbsp; $L_{\rm M} < 4$&nbsp; will apply, according to the penultimate line.&nbsp; But this is connected with the fact that this code is not prefix-free.&nbsp; Therefore, the radio operator had to take a break between each&nbsp; "short-long"&nbsp; sequence so that the other station could decode the radio signal as well.}}
*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 1830er 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.}}
 
 
 
 
 
  
==Aufgaben zum Kapitel==
+
== Exercises for the chapter==
 
<br>
 
<br>
[[Aufgaben:2.1 Codierung mit und ohne Verlust|Aufgabe 2.1: Codierung mit und ohne Verlust]]
+
[[Aufgaben:Exercise_2.1:_Coding_with_and_without_Loss|Exercise 2.1: Coding with and without Loss]]
  
[[Aufgaben:2.2 Kraftsche Ungleichung|Aufgabe 2.2: Kraftsche Ungleichung]]
+
[[Aufgaben:Exercise_2.2:_Kraft–McMillan_Inequality|Exercise 2.2: Kraft–McMillan Inequality]]
  
[[Aufgaben:2.2Z Mittlere Codewortlänge|Aufgabe 2.2Z: Mittlere Codewortlänge]]
+
[[Aufgaben:Exercise_2.2Z:_Average_Code_Word_Length|Exercise 2.2Z: Average Code Word Length]]
  
  
 
{{Display}}
 
{{Display}}

Revision as of 15:04, 13 July 2021


# OVERVIEW OF THE SECOND MAIN CHAPTER #


  Shannon's Information Theory is applied, for example, in the  Source coding of digital  (i.e. discrete-value and discrete-time)  message sources.  In this context, one also speaks of  Data compression.

  • Attempts are made to reduce the redundancy of natural digital sources such as measurement data, texts, or voice and image files  (after digitization)  by recoding them, so that they can be stored and transmitted more efficiently.
  • In most cases, source encoding is associated with a change of the symbol set size.  in the following, the output sequence is always binary.


The following is a detailed discussion:

  • The different destinations of  »source coding«,  »channel coding«  and  »line coding«,
  • »lossy encoding methods«  for analog sources, for example GIF, TIFF, JPEG, PNG, MP3,
  • the  »source encoding theorem«, which specifies a limit for the average codeword length,
  • the frequently used data compression according to  »Lempel, Ziv and Welch«,
  • the  »Huffman code«  as the best known and most efficient form of entropy coding,
  • the  »Shannon-Fano code«  as well as the  »arithmetic coding« - both belong to the class of entropy encoders as well,
  • the  »run-length coding«  (RLC)  and the  »Burrows-Wheeler transformation«  (BWT).


Source coding - Channel coding - Line coding


For the descriptions in this second chapter we consider the following model of a digital transmission system:

Simplified model of a digital transmission system
  • The source signal  $q(t)$  can be analog as well as digital, just like the sink signal  $v(t)$.  All other signals in this block diagram, even those not explicitly named here, are digital.
  • In particular, also the signals  $x(t)$  and  $y(t)$  at the input and output of the  "digital channel"  are digital and can therefore also be described completely by the symbol sequences  $〈x_ν〉$  and  $〈y_ν〉$.
  • The  "digital channel"  includes not only the transmission medium and interference (noise) but also components of the transmitter  (modulator, transmitter pulse shaper, etc.)  and the receiver  (demodulator, receive filter, detector, decision maker).
  • The chapter  Parameters of Digital Channel Models  in the book  "Digital Signal Transmission"  describes the modeling of the  "digital channel".


As can be seen from this block diagram, there are three different types of coding, depending on the target direction.  Each of which is realized by the  "encoder"  on the transmission side and the corresponding  "decoder"  at the receiver:

Task of the  source coding  is the reduction of redundancy for data compression, as it is used for example in image coding.  By using correlations between the individual points of an image or between the brightness values of a pixel at different times  (for moving picture sequences)  procedures can be developed which lead to a noticeable reduction of the amount of data (measured in bit or byte) with nearly the same picture quality.  A simple example is the  »differential pulse code modulation«  (DPCM).

With  channel coding  on the other hand, a noticeable improvement of the transmission behavior is achieved by using a redundancy specifically added at the transmitter to detect and correct transmission errors at the receiver side.  Such codes, whose most important representatives are  »block codes«,  »convolutional codes«  and  »turbo codes«,  are of great importance, especially for heavily disturbed channels.  The greater the relative redundancy of the coded signal, the better the correction properties of the code, but at a reduced payload data rate.

Line coding  is used to adapt the transmission signal  $x(t)$  to the spectral characteristics of the channel and the receiving equipment by recoding the source symbols.   For example, in the case of an  (analog)  transmission channel over which no direct signal can be transmitted, for which thus  $H_{\rm K}(f = 0) = 0$, it must be ensured by line coding that the code symbol sequence does not contain long sequences of the same polarity.

The focus of this chapter is on lossless source coding, which generates a data-compressed code symbol sequence  $〈c_ν〉$  starting from the source symbol sequence  $〈q_ν〉$  and based on the results of information theory.

  • Channel coding is the subject of a separate book in our tutorial with the following  Content .
  • The channel coding is discussed in detail in the chapter "Coded and multilevel transmission" of the book  Digital Signal Transmission .


Note:   We uniformly use  "$\nu$"  here as a control variable of a symbol sequence.  Normally, for  $〈q_ν〉$,  $〈c_ν〉$  and  $〈x_ν〉$  different indices should be used if the rates do not match.


Lossy source coding for images


For digitizing analog source signals such as speech, music or pictures, only lossy source coding methods can be used.  Even the storage of a photo in  BMP  format is always associated with a loss of information due to sampling, quantization and the finite color depth.

However, there are also a number of compression methods for images that result in much smaller image files than  "BMP", for example:

  • GIF  ("Graphics Interchange Format"), developed by Steve Wilhite in 1987.
  • JPEG  - a format that was introduced in 1992 by the  "Joint Photography Experts Group"  and is now the standard for digital cameras.  Ending:   "jpeg"  or  "jpg".
  • TIFF  ("Tagged Image File Format"), around 1990 by Aldus Corp. (now Adobe) and Microsoft, still the quasi-standard for print-ready images of the highest quality.
  • PNG  ("Portable Network Graphics"), designed in 1995 by T. Boutell and T. Lane as a replacement for the patent-encumbered GIF format, is less complex than TIFF.


These compression methods partly use

  • vector quantization for redundancy reduction of correlated pixels,
  • at the same time the lossless compression algorithms according to  Huffman  and  Lempel/Ziv,
  • possibly also transformation coding based on DFT  ("Discrete Fourier Transform")  and  DCT  ("Discrete Cosine Transform"),
  • then quantization and transfer in the transformed range.


We now compare the effects of two compression methods on the subjective quality of photos and graphics, namely:

  • $\rm JPEG$  $($with compression factor  $8)$,  and
  • $\rm PNG$  $($with compression factor  $24)$.


$\text{Example 1:}$  In the upper part of the graphic you can see two compressions of a photo.

Compare JPEG and PNG compression

The format  $\rm JPEG$   (left image) allows a compression factor of  $8$  to  $15$  with (nearly) lossless compression.

  • Even with the compression factor  $35$  the result can still be called  "good".
  • For most consumer digital cameras, "JPEG"  is the default storage format.


The image shown on the right was compressed with  $\rm PNG$.

  • The quality is similar to the JPEG result, although the compression is about  $3$  stronger.
  • In contrast, PNG achieves a worse compression result than JPEG if the photo contains a lot of color gradations.


PNG is also better suited for line drawings with captions than JPEG (compare the lower images). 

  • The quality of the JPEG compression (on the left) is significantly worse than the PNG result, although the resulting file size is about three times as large. 
  • Especially fonts look "washed out".


Note:   Due to technical limitations of  $\rm LNTww$  all graphics had to be saved as  "PNG".

  • In the above graphic, "JPEG" means the PNG conversion of a file previously compressed with  "JPEG".
  • However, the associated loss is negligible.




Lossy source coding for audio signals


A first example of source coding for speech and music is the  pulse-code modulation  $\rm (PCM)$, invented in 1938, which extracts the code symbol sequence  $〈c_ν〉 $ from an analog source signal  $q(t)$, corresponding to the three processing blocks

Prinzip der Pulscodemodulation (PCM)
  • Sampling,
  • Quantization,
  • PCM encoding.


The graphic illustrates the PCM principle.  A detailed description of the picture can be found on the first pages of the chapter  Pulse-code modulation  in the book  "Modulation Methods".


Because of the necessary band limitation and quantization, this transformation is always lossy.  That means

  • The code sequence  $〈c_ν〉$  has less information than the source signal  $q(t)$.
  • The sink signal  $v(t)$  is fundamentally different from  $q(t)$.
  • Mostly, however, the deviation is not very large.


We will now mention two transmission methods based on pulse code modulation as examples.

$\text{Example 2:}$  The following data is taken from the  GSM specification:

  • If a speech signal is spectrally limited to the bandwidth  $B = 4 \, \rm kHz$   ⇒   sampling rate $f_{\rm A} = 8 \, \rm kHz$  with a quantization of $13 \, \rm bit$   ⇒   number of quantization levels  $M = 2^{13} = 8192$  a binary data stream of data rate  $R = 104 \, \rm kbit/s$ results.
  • The quantization noise ratio is then  $20 \cdot \lg M ≈ 78 \, \rm dB$.
  • For quantization with  $16 \, \rm bit$  this increases to  $96 \, \rm dB$.  At the same time, however, the required data rate increases to  $R = 128 \, \rm kbit/s$.


The following (German language) interactive SWF applet illustrates the effects of a bandwidth limitation:
      Einfluss einer Bandbegrenzung bei Sprache und Musik ⇒   "Impact of a Bandwidth Limitation for Speech and Music" .


$\text{Example 3:}$  The standard  ISDN  ("Integrated Services Digital Network") for telephony via two-wire line is also based on the PCM principle, whereby each user is assigned two B-channels  (Bearer Channels )  with  $64 \, \rm kbit/s$   ⇒   $M = 2^{8} = 256$  and a D-channel  (Data Channel )  with  $ 16 \, \rm kbit/s$.

  • The net data rate is thus  $R_{\rm net} = 144 \, \rm kbit/s$.
  • In consideration of the channel coding and the control bits (required for organizational reasons), the ISDN gross data rate of  $R_{\rm gross} = 192 \, \rm kbit/s$.


In mobile communications, very high data rates often could not (yet) be handled.  In the 1990s, voice coding procedures were developed that led to data compression by the factor  $8$  and more.  From today's point of view, it is worth mentioning:

  • The  Enhanced Full-Rate Codec  $\rm (EFR)$, which extracts  exactly  $244 \, \rm bit$  for each speech frame of  $20\, \rm ms$ $($Data rate:   $12. 2 \, \rm kbit/s)$;
    this data compression of more than the factor  $8$  is achieved by stringing together several procedures:
  1.  Linear Predictive Coding  $\rm (LPC$, short term prediction$)$,
  2.  Long Term Prediction  $\rm (LTP)$,
  3.  Regular Pulse Excitation  $\rm (RPE)$.
  • The  Adaptive Multi-Rate Codec  $\rm (AMR)$  based on  $\rm ACELP$  ("Algebraic Code Excited Linear Prediction")  and several modes between  $12. 2 \, \rm kbit/s$  $\rm (EFR)$  and  $4.75 \, \rm kbit/s$  so that improved channel coding can be used in case of poorer channel quality.
  • The  Wideband-AMR  $\rm (WB-AMR)$  with nine modes between  $6.6 \, \rm kbit/s$  and  $23.85 \, \rm kbit/s$.   This is used with  UMTS  and is suitable for broadband signals between  $200 \, \rm Hz$  and  $7 \, \rm kHz$.   Sampling is done with  $16 \, \rm kHz$, quantization with  $4 \, \rm bit$.


All these compression methods are described in detail in the chapter  Voice Coding  of the book "Examples of Communication Systems"   The (German language) audio module  "Qualität verschiedener Sprach-Codecs"   ⇒   "Quality of different voice codecs"  allows a subjective comparison of these codecs.


MPEG-2 Audio Layer III - short "MP3"


Today (2015) the most common compression method for audio files is  MP3.  This format was developed from 1982 on at the Fraunhofer Institute for Integrated Circuits (IIS) in Erlangen under the direction of Professor  Hans-Georg Musmann  in collaboration with the Friedrich Alexander University Erlangen-Nuremberg and AT&T Bell Labs.  Other institutions are also asserting patent claims in this regard, so that since 1998 various lawsuits have been filed which, to the authors' knowledge, have not yet been finally concluded.

In the following some measures are called, which are used with  "MP3", in order to reduce the data quantity in relation to the raw version in the  "wav"-format.  The compilation is not complete.  A comprehensive representation about this can be found for example in a  Wikipedia article.

  • The audio compression method  "MP3"  uses among other things psychoacoustic effects of perception.  So a person can only distinguish two sounds from each other from a certain minimum difference in pitch.  One speaks of so-called  "masking effects".
  • Using the masking effects, signal components that are less important for the auditory impression are stored with less bits (reduced accuracy).  A dominant tone at  $4 \, \rm kHz$  can, for example, cause neighboring frequencies to be of only minor importance for the current auditory sensation up to  $11 \, \rm kHz$.
  • The greatest advantage of MP3 coding, however, is that the sounds are stored with just enough bits so that the resulting  quantization noise  is still masked and is not audible.
  • Other MP3 compression mechanisms are the exploitation of the correlations between the two channels of a stereo signal by difference formation as well as the  Huffman Coding  of the resulting data stream.  Both measures are lossless.


A disadvantage of the MP3 coding is that with strong compression also  "important"  frequency components are unintentionally captured and thus audible errors occur.  Furthermore it is disturbing that due to the blockwise application of the MP3 procedure gaps can occur at the end of a file.  A remedy is the use of the so-called  "LAME coder"  and a corresponding player.


Description of lossless source encoding – Requirements


In the following, we only consider lossless source coding methods and make the following assumptions:

  • The digital source has the symbol set size  $M$.  For the individual source symbols of the sequence  $〈q_ν〉$  applies with the symbol set  $\{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}. $$

The individual sequence elements  $q_ν$  may can be  "statistically independent"  or  "statistically dependent".

  • First we consider  discrete sources without memory, which are fully characterized by the symbol probabilities alone, for example:
$$M = 4\text{:} \ \ \ q_μ \in \{ {\rm A}, \ {\rm B}, \ {\rm C}, \ {\rm D} \}, \hspace{3.0cm} \text{with the probabilities}\ 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{with the probabilities }\ p_{\rm A},\hspace{0.05cm}\text{...} \hspace{0.05cm} ,\ p_{\rm H}.$$
  • The source encoder replaces the source symbol  $q_μ$  with the code word  $\mathcal{C}(q_μ)$,
    consisting of  $L_μ$  code symbols of a new alphabet with the symbol set size  $D$  $\{0, \ 1$, ... ,  $D - 1\}$.  This gives the  average code word length:
$$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{Example 4:}$  We consider two different types of source encoding, each with parameters  $M = 9$  and  $D = 3$.

Two examples of source encoding
  • In the first encoding  $\mathcal{C}_1(q_μ)$  according to line 2 (red) of the table, each source symbol  $q_μ$  is replaced by two ternary symbols  $(0$,  $1$  or  $2)$.    Here we have for example the mapping:
$$\rm A C F B I G \ ⇒ \ 00 \ 02 \ 12 \ 01 \ 22 \ 20.$$
  • With this coding, all code words  $\mathcal{C}_1(q_μ)$  with  $1 ≤ μ ≤ 6$  have the same length  $L_μ = 2$.  Thus, the average code word length is  $L_{\rm M} = 2$.


  • For the second, the blue source encoder holds  $L_μ ∈ \{1, 2 \}$.  Accordingly, the average code word length  $L_{\rm M}$  will be less than two code symbols per source symbol.  For example, the mapping:
$$\rm A C F B I G \ ⇒ \ 0 \ 02 \ 12 \ 01 \ 22 \ 2.$$
  • It is obvious that this code symbol sequence cannot be decoded unambiguously, since the symbol sequence naturally does not include the spaces inserted in this text for display reasons.


Kraft–McMillan inequality - Prefix-free codes


Binary codes for compressing a memoryless discrete-value source are characterized by the fact that the individual symbols are represented by code symbol sequences of different lengths:

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

Only then it is possible,

  • that the  average code word length becomes minimal,
  • if the  source symbols are not equally probable.


To enable a unique decoding, the code must also be "prefix-free".

$\text{Definition:}$  The property  prefix-free  indicates that no codeword may be the prefix (beginning) of a longer codeword.  Such a codeword is immediately decodable.

  • The blue code in  Example 4  is not prefix-free.  For example, the code symbol sequence "01" could be interpreted by the decoder as  $\rm AD$  but also as  $\rm B$.
  • The red code, on the other hand, is prefix-free, although prefix freedom would not be absolutely necessary here because of  $L_μ = \rm const.$

$\text{Without proof:}$  The necessary  condition for the existence of a prefix-free code  was specified by Leon Kraft in his Master Thesis 1949 at the  Massachusetts Institute of Technology  (MIT):

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


$\text{Example 5:}$  If you check the second (blue) code of  Example 4  with  $M = 9$  and  $D = 3$, you get:

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

From this you can see that this code cannot be prefix-free


$\text{Example 6:}$  Let's now look at the binary 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}, $$

it is obviously not prefix-free.  The equation

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

does not mean that this code is actually prefix-free, it just means that there is a prefix-free code with the same length distribution, for example

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


Source coding theorem


We now look at a redundant discrete source with the symbol set  $〈q_μ〉$, where the control variable  $μ$  takes all values between  $1$  and the symbol set size  $M$.  The source entropy  $H$  is smaller than  $H_0= \log_2 \hspace{0.1cm} M$.

The redundancy  $(H_0- H)$  is either caused by

  • not equally probable symbols   ⇒   $p_μ ≠ 1/M$,  and/or
  • statistical bonds within the sequence  $〈q_\nu〉$.


A source encoder replaces the source symbol  $q_μ$  with the codeword  $\mathcal{C}(q_μ)$, consisting of  $L_μ$  binary symbols (zeros or ones).  This results in an average codeword length:

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

For the source encoding task described here the following requirement can be specified:

$\text{Theorem:}$  For the possibility of a complete reconstruction of the sent string from the binary sequence it is sufficient, but also necessary, that for encoding on the transmitting side at least  $H$  binary symbols per source symbol are used.

  • The average code word length  $L_{\rm M}$  cannot be smaller than the entropy  $H$  of the source symbol sequence:   $L_{\rm M} \ge H \hspace{0.05cm}. $
  • This regularity is called  Source Coding Theorem, which goes back to  Claude Elwood Shannon.   
  • If the source coder considers only the different symbol probabilities, but not the correlation between symbols, then  $L_{\rm M} ≥ H_1$   ⇒   first entropy approximation.


$\text{Example 7:}$  For a quaternary source with the symbol probabilities

$$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/source\hspace{0.15cm} symbol} $$

equality in the above equation   ⇒   $L_{\rm M} = H$ results, if for example the following assignment is chosen:

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

In contrast, with the same mapping and

$$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/source\hspace{0.15cm}symbol}$$

the average code word length

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

Because of the unfavorably chosen symbol probabilities (no powers of two)  ⇒   $L_{\rm M} > H$.


Character encodings according to Bacon/Bandot, Morse and Huffman

$\text{Example 8:}$  We will look at some very early attempts at source encoding for the transmission of natural texts, based on the letter frequencies given in the table.

  • In the literature many different frequencies are found,  also because,  the investigations were carried out for different languages.
  • Mostly, however, the list starts with the blank and  "E"  and ends with letters like  "X",  "Y"  and  "Q".


Please note the following about this table:

  • The entropy of this alphabet with  $M = 27$  characters will be  $H≈ 4 \, \rm bit/character$.  We have only estimated this value.  Francis Bacon  had already given a binary code in 1623, where each letter is represented by five bits:   $L_{\rm M} = 5$.
  • About 250 years later  Jean-Maurice-Émile Baudot  adopted this code, which was later standardized for the entire telegraphy.  One consideration important to him was that a code with a uniform five binary characters per letter is more difficult for an enemy to decipher, since he cannot draw conclusions about the transmitted character from the frequency of its occurrence.
  • The last line in the above table gives an exemplary  Huffman code  for the above frequency distribution.  Probable characters like  "E"  or  "N"  and also the  "Blank"  are represented with three bits only, the rare  "Q"  on the other hand with eleven bits.
  • The average code word length  $L_{\rm M} = H + ε$  is slightly larger than  $H$, whereby we will not go into more detail here about the small positive quantity  $ε$.    Only this much:   There is no prefix-free code with smaller average word length than the Huffman code.
  • Also  Samuel Morse  took into account the different frequencies in his code for telegraphy, already in the 1830s.  The Morse code of each character consists of two to four binary characters, which are designated here according to the application with dot  ("short")  and bar  ("long").
  • It is obvious that for the Morse code  $L_{\rm M} < 4$  will apply, according to the penultimate line.  But this is connected with the fact that this code is not prefix-free.  Therefore, the radio operator had to take a break between each  "short-long"  sequence so that the other station could decode the radio signal as well.


Exercises for the chapter


Exercise 2.1: Coding with and without Loss

Exercise 2.2: Kraft–McMillan Inequality

Exercise 2.2Z: Average Code Word Length