Informationstheorie/Allgemeine Beschreibung - Versionsgeschichte

Guenter am 13. Juli 2021 um 14:01 Uhr

2021-07-13T14:01:23Z

Guenter am 26. Juni 2021 um 14:12 Uhr

2021-06-26T14:12:51Z

Guenter am 26. Juni 2021 um 12:40 Uhr

2021-06-26T12:40:40Z

Guenter am 25. Juni 2021 um 15:40 Uhr

2021-06-25T15:40:18Z

Guenter am 25. Juni 2021 um 13:25 Uhr

2021-06-25T13:25:02Z

Änderungen zeigen

Guenter am 21. Januar 2020 um 16:22 Uhr

2020-01-21T16:22:00Z

Änderungen zeigen

Guenter am 20. Januar 2020 um 09:31 Uhr

2020-01-20T09:31:04Z

Änderungen zeigen

Guenter am 23. September 2018 um 12:41 Uhr

2018-09-23T12:41:07Z

Guenter am 23. September 2018 um 12:31 Uhr

2018-09-23T12:31:49Z

Guenter am 20. September 2018 um 15:59 Uhr

2018-09-20T15:59:37Z

Änderungen zeigen

@@ Zeile 15: / Zeile 15: @@
 Im Einzelnen werden behandelt:
-*die unterschiedlichen Ziele von&nbsp; &raquo;Quellencodierung&laquo;,&nbsp; &raquo;Kanalcodierung&laquo;&nbsp; und&nbsp; &raquo;Leitungscodierung&laquo;,
+:*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,
+:*&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,
+:*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;,
+:*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;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,
+:*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).
+:*die&nbsp; &raquo;Lauflängencodierung&laquo;&nbsp; sowie die&nbsp; &raquo;Burrows-Wheeler Transformation&laquo;&nbsp; (BWT).
 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
+:*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.
+:*der zugehörigen&nbsp; [http://www.lntwww.de/downloads/Sonstiges/Texte/Wertdiskrete_Informationstheorie.pdf Praktikumsanleitung]  &nbsp;&rArr;&nbsp; Link verweist auf die PDF-Version.

@@ Zeile 263: / Zeile 263: @@
 ==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 der Nachrichtengehalt&nbsp; $H_0$.
+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$.
-Die Redundanz&nbsp; $(H_0- H)$&nbsp; geht entweder zurück auf
+Die Redundanz&nbsp; $(H_0- H)$&nbsp; ist entweder zurückzuführen
-*nicht gleichwahrscheinliche Symbole &nbsp;  ⇒  &nbsp; $p_μ ≠ 1/M$,&nbsp; und/oder
+*auf nicht gleichwahrscheinliche Symbole &nbsp;  ⇒  &nbsp; $p_μ ≠ 1/M$,&nbsp; und/oder
-*statistische Bindungen innerhalb der Folge&nbsp; $〈q_\nu〉$.
+*auf statistische Bindungen innerhalb der Folge&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
+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}. $$
-Für die hier beschriebene Quellencodierungsaufgabe kann folgende&nbsp; '''Grenze'''&nbsp; 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
+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.
-*man zur sendeseitigen Codierung im Mittel mindestens&nbsp; $H$&nbsp; Binärsymbole pro Quellensymbol verwendet.
+*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}. $
-*die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; auf keinen Fall kleiner sein kann als die Entropie&nbsp; $H$&nbsp; der Quellensymbolfolge: &nbsp;
+*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;
-:$$L_{\rm M} \ge H  \hspace{0.05cm}. $$
+*Berücksichtigt der Quellencodierer nur die unterschiedlichen Auftrittswahrscheinlichkeiten, nicht aber die inneren statistischen Bindungen der Folge , dann gilt&nbsp; $L_{\rm M} ≥ H_1$ &nbsp;  ⇒ &nbsp;  [[Informationstheorie/Nachrichtenquellen_mit_Gedächtnis#Entropie_hinsichtlich_Zweiertupel|erste Entropienäherung]].}}
@@ Zeile 316: / Zeile 314: @@
 Wegen der ungünstig gewählten Symbolwahrscheinlichkeiten (keine Zweierpotenzen) ist hier $L_{\rm M} > H$.}}
 {{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 unterschiedliche Häufigkeitsangaben,&nbsp; auch deshalb,&nbsp; weil die Untersuchungen für verschiedene Sprachen durchgeführt wurden.
 *Meist beginnt die Liste aber mit dem Leerzeichen (Blank) sowie „E” und endet mit Buchstaben wie „X”,&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 wird: &nbsp; $L_{\rm M} = 5$.
+*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 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.
+*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.}}

@@ Zeile 184: / Zeile 184: @@
 :$$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''':
+*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}. $$
 {{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{Beispiel 4:}$&nbsp;  Wir betrachten zwei verschiedene Arten von Quellencodierung,&nbsp; jeweils mit den Parametern&nbsp; $M = 9$&nbsp; und&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:
+[[Datei:P_ID2316__Inf_T_2_1_S3_Ganz_neu.png|right|frame|Zwei Beispiele für Quellencodierung]]
 : $$\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$.
-[[Datei:P_ID2316__Inf_T_2_1_S3_Ganz_neu.png|center|frame|Zwei Beispiele für Quellencodierung]]
+*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.$$
@@ Zeile 227: / Zeile 227: @@
 {{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 :
+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}.$$}}

@@ Zeile 52: / Zeile 52: @@
 *Der Kanalcodierung ist in unserem Tutorial ein eigenes Buch mit folgendem&nbsp; [[Kanalcodierung|Inhalt]]&nbsp; gewidmet.
-*Die Leitungscodierung wird im Kapitel$&nbsp; &bdquo;Codierte und mehrstufige Übertragung&rdquo;$&nbsp; des Buches&nbsp; [[Digitalsignalübertragung]]&nbsp; eingehend behandelt.
+*Die Leitungscodierung wird im Kapitel&nbsp; &bdquo;Codierte und mehrstufige Übertragung&rdquo;&nbsp; des Buches&nbsp; [[Digitalsignalübertragung]]&nbsp; eingehend behandelt.
@@ Zeile 109: / Zeile 109: @@
 ==Verlustbehaftete Quellencodierung  für Audiosignale==
 <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
+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
 [[Datei:P_ID2925__Mod_T_4_1_S1_neu.png|right|frame|Prinzip der Pulscodemodulation (PCM)]]
 *Abtastung,
@@ Zeile 116: / Zeile 116: @@
-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;.
+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;.
@@ Zeile 139: / Zeile 139: @@
 {{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;)&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.
+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$.
+*Die Nettodatenrate beträgt somit&nbsp;
-*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$.}}
+:$$R_{\rm Netto} = 144 \, \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:
+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; ('''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:
+*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; ('''LPC''', Kurzzeitprädiktion),
+:# &nbsp;"Linear Predictive Coding"&nbsp; $\rm (LPC$,&nbsp; Kurzzeitprädiktion$)$,
-:# &nbsp;''Long Term Prediction''&nbsp; ('''LTP''', Langzeitprädiktion) und
+:# &nbsp;"Long Term Prediction"&nbsp; $\rm (LTP$,&nbsp; Langzeitprädiktion$)$,
-:# &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;
+*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; ('''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$.
+*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$.

@@ Zeile 144: / Zeile 144: @@
 :# &nbsp;''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 \, \rm  kbit/s$ (EFR) und $4.75 \, \rm  kbit/s$ bereit stellt, so dass bei schlechterer Kanalqualität eine verbesserte Kanalcodierung eingesetzt werden kann;
-*der [[Beispiele_von_Nachrichtensystemen/Sprachcodierung|Wideband–AMR]] ('''WB–AMR''') mit neun Modi zwischen $6.6 \, \rm  kbit/s$ und $23.85 \, \rm  kbit/s$. Dieser wird bei [[Beispiele_von_Nachrichtensystemen/Allgemeine_Beschreibung_von_UMTS|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$.
+*der [[Beispiele_von_Nachrichtensystemen/Sprachcodierung#Verschiedene_Sprachcodierverfahren|Wideband–AMR]] ('''WB–AMR''') mit neun Modi zwischen $6.6 \, \rm  kbit/s$ und $23.85 \, \rm  kbit/s$. Dieser wird bei [[Beispiele_von_Nachrichtensystemen/Allgemeine_Beschreibung_von_UMTS|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$.

@@ Zeile 172: / Zeile 172: @@
 :$$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 $q_ν$ können statistisch unabhängig sein oder auch statistische Bindungen aufweisen. Zunächst betrachten wir '''Nachrichtenquellen ohne Gedächtnis''', die durch die Symbolwahrscheinlichkeiten vollständig charakterisiert sind, zum Beispiel:
-:$$M = 4\text{:} \  \    q_μ \in \{ {\rm A},  {\rm B},  {\rm C},  {\rm D} \}, \hspace{2.5cm} \text{mit den Wahrscheinlichkeiten } p_{\rm A}, p_{\rm B}, p_{\rm C}, p_{\rm D},$$
+:$$M = 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}.$$
+:$$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''':
@@ Zeile 181: / Zeile 181: @@
 {{GraueBox|TEXT=
-$\text{Beispiel 4:}$&nbsp;
+$\text{Beispiel 4:}$&nbsp;  Wir betrachten zwei verschiedene Arten von Quellencodierung, jeweils mit den Parametern $M = 9$ und $D = 3$.
 *Bei der ersten Codierung $\mathcal{C}_1(q_μ)$ entsprechend Zeile 2 (rote Darstellung) wird jedes Quellensymbol $q_μ$ durch zwei Ternärsymbole ($0$, $1$ oder $2$) ersetzt. Beispielsweise gilt die Zuordnung:
-: $$\rm A C F B I G ⇒ 00 \ 02 \ 12 \ 01 \ 22 \ 20.$$
+: $$\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$.
@@ Zeile 193: / Zeile 192: @@
 *Dagegen gilt beim zweiten, dem blauen Quellencodierer $L_μ ∈ \{1, 2 \}$ und dementsprechend wird die mittlere Codewortlänge  $L_{\rm M}$  kleiner sein als zwei Codesymbole pro Quellensymbol. Hier gilt die Zuordnung:
-: $$\rm A C F B I G ⇒ 0 \ 02 \ 12 \ 01 \ 22 \ 2$$
+: $$\rm A C F B I G \ ⇒ \ 0 \ 02 \ 12 \ 01 \ 22 \ 2$$
-*Es ist offensichtlich, dass diese zweite Codesymbolfolge nicht eindeutig decodiert werden kann, da die Symbolfolge natürlich nicht die in diesem Text eingefügten Leerzeichen beinhaltet. }}
+*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 ==
 <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}\text{...} \hspace{0.05cm}, M ) \hspace{0.05cm}.$$
@@ Zeile 272: / Zeile 271: @@
 {{BlaueBox|TEXT=
-$\text{Definition:}$&nbsp;
+$\text{Theorem:}$&nbsp;
-Für die Möglichkeit der vollständigen Rekonstruktion der gesendeten Zeichenfolge aus der Binärfolge ist es nach dem so genannten '''Shannons Quellencodierungstheorem''' hinreichend, aber auch notwendig,
+Für die Möglichkeit der vollständigen Rekonstruktion der gesendeten Zeichenfolge aus der Binärfolge ist es  hinreichend, aber auch notwendig, dass
-*dass man zur sendeseitigen Codierung im Mittel mindestens $H$ Binärsymbole pro Quellensymbol verwendet.
+*man zur sendeseitigen Codierung im Mittel mindestens $H$ Binärsymbole pro Quellensymbol verwendet.
 {{GraueBox|TEXT=
@@ Zeile 324: / Zeile 323: @@
 *Die Entropie dieses Alphabets mit $M = 27$ Zeichen wird $H≈ 4 \, \rm bit/Zeichen$ betragen. Wir haben das nicht nachgerechnet. [https://de.wikipedia.org/wiki/Francis_Bacon Francis Bacon] hat aber schon 1623 einen Binärcode angegeben, bei dem jeder Buchstabe mit fünf Bit dargestellt wird: &nbsp; $L_{\rm M} = 5$.
 *Etwa 250 Jahre danach hat [https://de.wikipedia.org/wiki/Baudot-Code 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 [[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 $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.
+*Die letzte Zeile in obiger Tabelle 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.
 *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 entsprechend der vorletzten Zeile  $L_{\rm M} < 4$ gelten wird. Dies hängt aber auch damit zusammen, dass dieser Code nicht präfixfrei ist. Zwischen jeder Kurz–Lang–Sequenz musste deshalb der Funker eine Pause einlegen, damit die Gegenstation das Funksignal auch entschlüsseln konnte.}}