Aufgaben:Aufgabe 2.2Z: Mittlere Codewortlänge: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(11 dazwischenliegende Versionen von 3 Benutzern werden nicht angezeigt)
Zeile 1: Zeile 1:
  
{{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Allgemeine Beschreibung
+
{{quiz-Header|Buchseite=Informationstheorie/Allgemeine Beschreibung
 
}}
 
}}
  
[[Datei:P_ID2417__Inf_Z_2_2.png|right|]]
+
[[Datei:P_ID2417__Inf_Z_2_2.png|right|frame|Tabelle zur Quellencodierung]]
:Ziel von Datenkomprimierung ist es, die Nachricht einer Quelle mit möglichst wenigen Binärzeichen darzustellen.
+
Ziel von Datenkomprimierung ist es, die Nachricht einer Quelle mit möglichst wenigen Binärzeichen darzustellen.
  
:Wir betrachten hier eine wertdiskrete Nachrichtenquelle mit dem Symbolvorrat {<b>A</b>, <b>B</b>, <b>C</b>, <b>D</b>} &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Symbolumfang <i>M</i> = 4 und den Auftrittswahrscheinlichkeiten
+
Wir betrachten hier eine wertdiskrete Nachrichtenquelle mit dem Symbolvorrat&nbsp; $\rm \{ A, \ B, \ C, \ D\}$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Symbolumfang&nbsp; $M = 4$&nbsp; und den Auftrittswahrscheinlichkeiten
 +
:*$p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} =  1/4$&nbsp; (Teilaufgabe 1),
 +
:* $p_{\rm A} = 1/2, \,  p_{\rm B} = 1/4, \, p_{\rm C} = p_{\rm D} =  1/8$&nbsp;  (ab Teilaufgabe 2).
  
:* <i>p</i><sub>A</sub> = <i>p</i><sub>B</sub> = <i>p</i><sub>C</sub> = <i>p</i><sub>D</sub> = 1/4 (Teilaufgabe 1),
 
  
:* <i>p</i><sub>A</sub> = 1/2, <i>p</i><sub>B</sub> = 1/4, <i>p</i><sub>C</sub> = <i>p</i><sub>D</sub> = 1/8 (ab Teilaufgabe 2).
+
Vorausgesetzt wird, dass es zwischen den einzelnen Quellensymbolen keine statistischen Bindungen gibt.
  
:Vorausgesetzt wird, dass es zwischen den Quellensymbolen keine statistischen Bindungen gibt.
+
Ein Maß für die Güte eines Komprimierungsverfahrens ist die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp;  mit der Zusatzeinheit &bdquo;bit/Quellensymbol&rdquo;.  
  
:Ein Maß für die Güte eines Komprimierungsverfahrens ist die mittlere Codewortlänge <i>L</i><sub>M</Sub> mit der Zusatzeinheit &bdquo;bit/Quellensymbol&rdquo;. Vorgegeben sind drei Zuordnungen. Anzumerken ist:
+
Vorgegeben sind drei Zuordnungen. Anzumerken ist:
 +
* Jeder dieser Binärcodes&nbsp; $\rm C1$,&nbsp; $\rm C2$&nbsp; und&nbsp; $\rm C3$&nbsp; ist für eine spezielle Quellenstatistik ausgelegt.
 +
* Alle Codes sind präfixfrei und somit ohne weitere Angabe sofort decodierbar.
  
:* Jeder dieser Binärcodes C1, C2 und C3 ist für eine spezielle Quellenstatistik ausgelegt.
 
  
:* Alle codes sind präfixfrei und somit ohne weitere Angabe sofort decodierbar.
 
  
:<b>Hinweis:</b> Die Aufgabe bezieht sich auf das Kapitel 2.1.
+
 
 +
 
 +
''Hinweis:''
 +
*Die Aufgabe gehört zum  Kapitel&nbsp; [[Informationstheorie/Allgemeine_Beschreibung|Allgemeine Beschreibung der Quellencodierung]].
 +
  
  
Zeile 26: Zeile 31:
  
 
<quiz display=simple>
 
<quiz display=simple>
{Bestimmen Sie die mittlere Codewortlänge für <i>p</i><sub>A</sub> = <i>p</i><sub>B</sub> = <i>p</i><sub>C</sub> = <i>p</i><sub>D</sub> = 1/4.
+
{Bestimmen Sie die mittlere Codewortlänge&nbsp; $L_{\rm M}$&nbsp; für&nbsp; $p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} = 1/4$.
 
|type="{}"}
 
|type="{}"}
$C1:\ \ L_M$ = { 2 3% } $bit/Quellensymbol$
+
$\text{C1:}\ \ L_{\rm M} \ = \ $ { 2 1% } $\ \rm bit/Quellensymbol$
$C2:\ \ L_M$ = { 2.25 3% } $bit/Quellensymbol$
+
$\text{C2:}\ \ L_{\rm M} \ \ $ { 2.25 1% } $\ \rm bit/Quellensymbol$
$C3:\ \ L_M$ = { 2.25 3% } $bit/Quellensymbol$
+
$\text{C3:}\ \ L_{\rm M} \ =  \ $ { 2.25 1% } $\ \rm bit/Quellensymbol$
  
  
{Welche Werte ergeben sich für <i>p</i><sub>A</Sub> = 1/2, <i>p</i><sub>B</Sub> = 1/4, <i>p</i><sub>C</sub> = <i>p</i><sub>D</sub> = 1/8.
+
{Welche Werte ergeben sich für&nbsp; $p_{\rm A} = 1/2, \,  p_{\rm B} = 1/4, \, p_{\rm C} = p_{\rm D} = 1/8$?
 
|type="{}"}
 
|type="{}"}
$C1:\ \ L_M$ = { 2 3% } $bit/Quellensymbol$
+
$\text{C1:}\ \ L_{\rm M} \ =  \ $ { 2 1% } $\ \rm bit/Quellensymbol$
$C2:\ \ L_M$ = { 1.75 3% } $bit/Quellensymbol$
+
$\text{C2:}\ \ L_{\rm M} \ =  \ $ { 1.75 1% } $\ \rm bit/Quellensymbol$
$C3:\ \ L_M$ = { 2.5 3% } $bit/Quellensymbol$
+
$\text{C3:}\ \ L_{\rm M} \ =  \ $ { 2.5 1% } $\ \rm bit/Quellensymbol$
  
  
Zeile 46: Zeile 51:
  
  
{Für die spezielle Quellenfolge <b>ADBDCBCBADCA</b> ergibt sich die Codefolge <b>001101111001100100111000</b>. Welcher Code wurde verwendet?
+
{Für die spezielle Quellensymbolfolge&nbsp; $\rm ADBDCBCBADCA$&nbsp; ergibt sich die Codesymbolfolge&nbsp; $\rm 001101111001100100111000$.
|type="[]"}
+
<br>Welcher Code wurde verwendet?
+ der Code C1,
+
|type="()"}
- der Code C2.
+
+ Der Code&nbsp;  $\rm C1$,
 +
- der Code&nbsp; $\rm C2$.
  
  
{Nach Codierung mit C3 erhält man <b>001101111001100100111000</b>. Wie lautet die zugehörige Quellensymbolfolge?
+
{Nach Codierung mit&nbsp; $\rm C3$&nbsp; erhält man&nbsp; $\rm 001101111001100100111000$.&nbsp; Wie lautet die zugehörige Quellensymbolfolge?
|type="[]"}
+
|type="()"}
- <b>AACDBACABADAAA ....</b>
+
- $\rm AACDBACABADAAA$ ...
+ <b>ACBCCCACAACCD ....</b>
+
+ $\rm ACBCCCACAACCD$ ...
  
  
Zeile 63: Zeile 69:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<b>1.</b>&nbsp;&nbsp;Die mittlere Codewortlänge ergibt sich allgemein zu
+
'''(1)'''&nbsp; Die mittlere Codewortlänge ergibt sich allgemein zu
 
:$$L_{\rm M} = p_{\rm A} \cdot L_{\rm A} + p_{\rm B} \cdot L_{\rm B}+ p_{\rm C} \cdot L_{\rm C} + p_{\rm D} \cdot L_{\rm D}
 
:$$L_{\rm M} = p_{\rm A} \cdot L_{\rm A} + p_{\rm B} \cdot L_{\rm B}+ p_{\rm C} \cdot L_{\rm C} + p_{\rm D} \cdot L_{\rm D}
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
:Sind die vier Quellensymbole gleichwahrscheinlich (alle Wahrscheinlichkeiten genau 1/4), so kann dafür auch geschrieben werden:
+
Sind die vier Quellensymbole gleichwahrscheinlich&nbsp; $($alle Wahrscheinlichkeiten genau&nbsp; $1/4)$, so kann dafür auch geschrieben werden:
:$$L_{\rm M} = 1/4 \cdot [ L_{\rm A} + L_{\rm B}+ L_{\rm C} + L_{\rm D}]
+
:$$L_{\rm M} = 1/4 \cdot ( L_{\rm A} + L_{\rm B}+ L_{\rm C} + L_{\rm D})
 
\hspace{0.05cm}.$$
 
\hspace{0.05cm}.$$
:* Code C1:&nbsp;&nbsp;&nbsp; <i>L</i><sub>M</sub> <u>= 2.00 bit/Quellensymbol</u>,
+
* $\text{Code C1:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2.00}\ \rm bit/Quellensymbol$,
 +
* $\text{Code C2:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2.25}\ \rm bit/Quellensymbol$
 +
* $\text{Code C3:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2.25}\ \rm bit/Quellensymbol$.
 +
 
 +
 
 +
 
 +
'''(2)'''&nbsp; Mit der Codetabelle&nbsp; $\text{C1}$&nbsp; ergibt sich unabhängig von den Symbolwahrscheinlichkeiten stets die mittlere Codewortlänge&nbsp; $L_{\rm M} \hspace{0.15cm}\underline{= 2}\ \ \rm bit/Quellensymbol$.
 +
 
 +
Für die beiden anderen Codes erhält man:
 +
* $\text{Code C2:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} = 1/2 \cdot 1 + 1/4 \cdot 2 + 1/8 \cdot 3 + 1/8 \cdot 3 \hspace{0.15cm}\underline{= 1.75}\ \rm bit/Quellensymbol$,
 +
* $\text{Code C3:}$&nbsp;&nbsp;&nbsp; $L_{\rm M} = 1/2 \cdot 3 + 1/4 \cdot 2 + 1/8 \cdot 1 + 1/8 \cdot 3 \hspace{0.15cm}\underline{= 2.50}\ \rm bit/Quellensymbol$.
 +
 
 +
 
 +
Man erkennt aus dem Beispiel das Prinzip:
 +
*Wahrscheinliche Symbole werden durch wenige Binärsymbole dargestellt, unwahrscheinliche durch mehr.
 +
*Bei gleichwahrscheinlichen Symbolen wählt man am besten auch die Codewortlängen gleich.
 +
 
  
:* Code C2:&nbsp;&nbsp;&nbsp; <i>L</i><sub>M</sub> <u>= 2.25 bit/Quellensymbol</u>,
 
  
:* Code C3:&nbsp;&nbsp;&nbsp; <i>L</i><sub>M</sub> <u>= 2.25 bit/Quellensymbol</u>.
 
  
:<b>2.</b>&nbsp;&nbsp;Mit der Codetabelle <i>C</i>1 ergibt sich unabhängig von den Symbolwahrscheinlichkeiten stets die mittlere Codewortlänge <i>L</i><sub>M</Sub> <u>= 2 bit/Quellensymbol</u>. Für die beiden anderen Codes erhält man
+
'''(3)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>:
 +
*Der Code&nbsp; $\text{C1}$&nbsp; mit einheitlicher Länge aller Codeworte ist präfixfrei,
 +
*aber auch andere Codes können präfixfrei sein, zum Beispiel die Codes&nbsp;  $\text{C2}$&nbsp; und&nbsp;  $\text{C3}$.
  
:* Code C2:&nbsp;&nbsp;&nbsp; <i>L</i><sub>M</sub> = 1/2 &middot; 1 + 1/4 &middot; 2 + 1/8 &middot; 3 + 1/8 &middot; 3 = <u>1.75 bit/Quellensymbol</u>,
 
  
:* Code C3:&nbsp;&nbsp;&nbsp; <i>L</i><sub>M</sub> = 1/2 &middot; 3 + 1/4 &middot; 2 + 1/8 &middot; 1 + 1/8 &middot; 3 = <u>2.50 bit/Quellensymbol</u>.
 
  
:Man erkennt aus dem Beispiel das Prinzip: Wahrscheinliche Symbole werden durch wenige Binärsymbole dargestellt und unwahrscheinliche durch mehr. Bei gleichwahrscheinlichen Symbolen wählt man am besten auch die Codewortlängen gleich.
+
'''(4)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 1</u>:  
 +
*Bereits aus &bdquo;00&rdquo; am Anfang erkennt man, dass der Code&nbsp; $\text{C2}$&nbsp; hier nicht in Frage kommt, da sonst die Quellensymbolfolge mit &bdquo;AA&rdquo; beginnen müsste.
 +
*Tatsächlich wurde der Code&nbsp; $\text{C1}$&nbsp; verwendet.
  
:<b>3.</b>&nbsp;&nbsp;Richtig ist <u>Lösungsvorschlag 1</u>. Ein Code mit einheitlicher Länge aller Codeworte ist zwar präfixfrei, aber auch andere Codes können präfixfrei sein, zum Beispiel die Codes C2 und C3.
 
  
:<b>4.</b>&nbsp;&nbsp;Bereits aus &bdquo;00&rdquo; am Anfang erkennt man, dass der Code C2 hier nicht in Frage kommt, da sonst die Quellensymbolfolge mit &bdquo;AA&rdquo; beginnen müsste. Tatsächlich wurde der <u>Code C1</u> verwendet.
 
  
:<b>5.</b>&nbsp;&nbsp;Richtig ist der <u>Lösungsvorschlag 2</u>. Der erste Lösungsvorschlag gibt die Quellensymbolfolge für den Code C2 an, wenn die Codesymbolfolge <b>001101111001100100111000</b> lauten würde.
+
'''(5)'''&nbsp; Richtig ist der <u>Lösungsvorschlag 2</u>:
 +
*Der erste Lösungsvorschlag gibt dagegen die Quellensymbolfolge für den Code&nbsp; $\text{C2}$&nbsp; an, wenn die Codesymbolfolge&nbsp; $\rm 001101111001100100111000$&nbsp; lauten würde.
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

Aktuelle Version vom 7. Juli 2021, 15:53 Uhr

Tabelle zur Quellencodierung

Ziel von Datenkomprimierung ist es, die Nachricht einer Quelle mit möglichst wenigen Binärzeichen darzustellen.

Wir betrachten hier eine wertdiskrete Nachrichtenquelle mit dem Symbolvorrat  $\rm \{ A, \ B, \ C, \ D\}$   ⇒   Symbolumfang  $M = 4$  und den Auftrittswahrscheinlichkeiten

  • $p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} = 1/4$  (Teilaufgabe 1),
  • $p_{\rm A} = 1/2, \, p_{\rm B} = 1/4, \, p_{\rm C} = p_{\rm D} = 1/8$  (ab Teilaufgabe 2).


Vorausgesetzt wird, dass es zwischen den einzelnen Quellensymbolen keine statistischen Bindungen gibt.

Ein Maß für die Güte eines Komprimierungsverfahrens ist die mittlere Codewortlänge  $L_{\rm M}$  mit der Zusatzeinheit „bit/Quellensymbol”.

Vorgegeben sind drei Zuordnungen. Anzumerken ist:

  • Jeder dieser Binärcodes  $\rm C1$,  $\rm C2$  und  $\rm C3$  ist für eine spezielle Quellenstatistik ausgelegt.
  • Alle Codes sind präfixfrei und somit ohne weitere Angabe sofort decodierbar.



Hinweis:


Fragebogen

1

Bestimmen Sie die mittlere Codewortlänge  $L_{\rm M}$  für  $p_{\rm A} = p_{\rm B} = p_{\rm C} = p_{\rm D} = 1/4$.

$\text{C1:}\ \ L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$
$\text{C2:}\ \ L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$
$\text{C3:}\ \ L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

2

Welche Werte ergeben sich für  $p_{\rm A} = 1/2, \, p_{\rm B} = 1/4, \, p_{\rm C} = p_{\rm D} = 1/8$?

$\text{C1:}\ \ L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$
$\text{C2:}\ \ L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$
$\text{C3:}\ \ L_{\rm M} \ = \ $

$\ \rm bit/Quellensymbol$

3

Woran erkennt man präfixfreie Codes?

Kein Codewort ist der Beginn eines anderen Codewortes.
Alle Codeworte haben gleiche Länge.

4

Für die spezielle Quellensymbolfolge  $\rm ADBDCBCBADCA$  ergibt sich die Codesymbolfolge  $\rm 001101111001100100111000$.
Welcher Code wurde verwendet?

Der Code  $\rm C1$,
der Code  $\rm C2$.

5

Nach Codierung mit  $\rm C3$  erhält man  $\rm 001101111001100100111000$.  Wie lautet die zugehörige Quellensymbolfolge?

$\rm AACDBACABADAAA$ ...
$\rm ACBCCCACAACCD$ ...


Musterlösung

(1)  Die mittlere Codewortlänge ergibt sich allgemein zu

$$L_{\rm M} = p_{\rm A} \cdot L_{\rm A} + p_{\rm B} \cdot L_{\rm B}+ p_{\rm C} \cdot L_{\rm C} + p_{\rm D} \cdot L_{\rm D} \hspace{0.05cm}.$$

Sind die vier Quellensymbole gleichwahrscheinlich  $($alle Wahrscheinlichkeiten genau  $1/4)$, so kann dafür auch geschrieben werden:

$$L_{\rm M} = 1/4 \cdot ( L_{\rm A} + L_{\rm B}+ L_{\rm C} + L_{\rm D}) \hspace{0.05cm}.$$
  • $\text{Code C1:}$    $L_{\rm M} \hspace{0.15cm}\underline{= 2.00}\ \rm bit/Quellensymbol$,
  • $\text{Code C2:}$    $L_{\rm M} \hspace{0.15cm}\underline{= 2.25}\ \rm bit/Quellensymbol$
  • $\text{Code C3:}$    $L_{\rm M} \hspace{0.15cm}\underline{= 2.25}\ \rm bit/Quellensymbol$.


(2)  Mit der Codetabelle  $\text{C1}$  ergibt sich unabhängig von den Symbolwahrscheinlichkeiten stets die mittlere Codewortlänge  $L_{\rm M} \hspace{0.15cm}\underline{= 2}\ \ \rm bit/Quellensymbol$.

Für die beiden anderen Codes erhält man:

  • $\text{Code C2:}$    $L_{\rm M} = 1/2 \cdot 1 + 1/4 \cdot 2 + 1/8 \cdot 3 + 1/8 \cdot 3 \hspace{0.15cm}\underline{= 1.75}\ \rm bit/Quellensymbol$,
  • $\text{Code C3:}$    $L_{\rm M} = 1/2 \cdot 3 + 1/4 \cdot 2 + 1/8 \cdot 1 + 1/8 \cdot 3 \hspace{0.15cm}\underline{= 2.50}\ \rm bit/Quellensymbol$.


Man erkennt aus dem Beispiel das Prinzip:

  • Wahrscheinliche Symbole werden durch wenige Binärsymbole dargestellt, unwahrscheinliche durch mehr.
  • Bei gleichwahrscheinlichen Symbolen wählt man am besten auch die Codewortlängen gleich.



(3)  Richtig ist der Lösungsvorschlag 1:

  • Der Code  $\text{C1}$  mit einheitlicher Länge aller Codeworte ist präfixfrei,
  • aber auch andere Codes können präfixfrei sein, zum Beispiel die Codes  $\text{C2}$  und  $\text{C3}$.


(4)  Richtig ist der Lösungsvorschlag 1:

  • Bereits aus „00” am Anfang erkennt man, dass der Code  $\text{C2}$  hier nicht in Frage kommt, da sonst die Quellensymbolfolge mit „AA” beginnen müsste.
  • Tatsächlich wurde der Code  $\text{C1}$  verwendet.


(5)  Richtig ist der Lösungsvorschlag 2:

  • Der erste Lösungsvorschlag gibt dagegen die Quellensymbolfolge für den Code  $\text{C2}$  an, wenn die Codesymbolfolge  $\rm 001101111001100100111000$  lauten würde.