Aufgaben:Aufgabe 2.2: Kraftsche Ungleichung: Unterschied zwischen den Versionen

Aus LNTwww
Wechseln zu:Navigation, Suche
 
(16 dazwischenliegende Versionen von 2 Benutzern werden nicht angezeigt)
Zeile 3: Zeile 3:
 
}}
 
}}
  
[[Datei:P_ID2416__Inf_A_2_2.png|right|]]
+
[[Datei:P_ID2416__Inf_A_2_2.png|right|frame|Vier Beispiele für Binärcodes und dazu drei Ternärcodes]]
:In der rechten Abbildung sind einige beispielhafte Binär– und Ternärcodes angegeben.
+
In der Abbildung sind einige beispielhafte Binär– und Ternärcodes angegeben.
  
:Beim Binärcode B1 werden alle möglichen Quellensymbole <i>q<sub>&mu;</sub></i> (mit Laufindex <i>&mu;</i> = 1, ... , 8) durch jeweils eine Codesymbolfolge &#9001;<i>c<sub>&mu;</sub></i>&#9002; einheitlicher Länge <i>L<sub>&mu;</sub></i> = 3 dargestellt. Dieser Code ist aus diesem Grund zur Datenkomprimierung ungeeignet.
+
*Beim Binärcode&nbsp; $\rm B1$&nbsp; werden alle möglichen Quellensymbole&nbsp; $q_\mu$&nbsp; $($mit Laufindex&nbsp; $\mu = 1$, ... , $8)$&nbsp; durch jeweils eine Codesymbolfolge&nbsp; $\langle c_\mu \rangle $&nbsp; einheitlicher Länge&nbsp; $L_\mu = 3$&nbsp; dargestellt.  
 +
*Dieser Code ist aus diesem Grund zur Datenkomprimierung ungeeignet.
  
:Die Möglichkeit zur Datenkomprimierung ergibt sich erst dann, wenn
 
  
:* die <i>M</i> Quellensymbole nicht gleichwahrscheinlich sind,
+
Die Möglichkeit zur Datenkomprimierung ergibt sich erst dann, wenn
 +
* die&nbsp; $M$&nbsp; Quellensymbole nicht gleichwahrscheinlich, und
 +
*die Länge&nbsp; $L_\mu$&nbsp; der Codeworte unterschiedlich sind.
  
:* und die Länge <i>L<sub>&mu;</sub></i> der Codeworte unterschiedlich sind.
 
  
:Diese Eigenschaft weist zum Beispiel der Binärcode B2 auf: Je ein Codewort hat hier die Länge 1, 2 und 3 (<i>N</i><sub>1</sub> = <i>N</i><sub>2</sub> = <i>N</i><sub>3</sub> = 1) und zwei Codeworte haben die Länge <i>L<sub>&mu;</sub></i> = 4 (<i>N</i><sub>4</sub> = 2).
+
Diese Eigenschaft weist zum Beispiel der Binärcode&nbsp;  $\rm B2$&nbsp; auf: &nbsp;
 +
*Je ein Codewort hat hier die Länge&nbsp; $1$,&nbsp; $2$&nbsp; bzw.&nbsp; $3$&nbsp; $(N_1 = 1,\ N_2 = 2,\ N_3 = 3)$.
 +
*Zwei Codeworte haben die Länge&nbsp; $L_\mu = 4$&nbsp; $(N_4 = N_5 = 4)$.
  
:Voraussetzung für die Decodierbarkeit eines solchen Codes ist, dass der Code präfixfrei ist.  Das heißt, dass kein Codewort der Präfix (der Beginn) eines längeren Codewortes sein darf.
 
  
:Eine notwendige Bedingung dafür, dass ein Code zur Datenkomprimierung präfixfrei sein kann, wurde 1949 von Leon Kraft angegeben, die Kraftsche Ungleichung:
+
Voraussetzung für die Decodierbarkeit eines solchen Codes ist, dass der Code&nbsp; '''präfixfrei'''&nbsp; ist.&nbsp; 
 +
*Das heißt, dass kein Codewort der Präfix (also der Beginn) eines längeren Codewortes sein darf.
 +
 
 +
*Eine notwendige Bedingung dafür, dass ein Code zur Datenkomprimierung präfixfrei sein kann, wurde 1949 von Leon Kraft angegeben, die so genannte&nbsp;  '''Kraftsche Ungleichung''':
 
:$$\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}.$$
:Hierbei bezeichnen
 
  
:* <i>M</i> die Anzahl der möglichen Quellensymbole <i>q<sub>&mu;</sub></i>,
+
Hierbei bezeichnen
 +
* $M$&nbsp; die Anzahl der möglichen Quellensymbole&nbsp; $q_\mu$ &nbsp; &rArr; &nbsp; &bdquo;Symbolumfang&rdquo;,
 +
* $L_\mu$&nbsp; die Länge des zum Quellensymbol&nbsp; $q_\mu$&nbsp; gehörigen Codewortes&nbsp;  $c_\mu$,
 +
* $D = 2$&nbsp; kennzeichnet einen Binärcode&nbsp; $(\rm 0$  oder&nbsp; $\rm 1)$&nbsp; und&nbsp; $D = 3$&nbsp; einen Ternärcode&nbsp; $(\rm 0$,&nbsp; $\rm 1$,&nbsp; $\rm 2)$.
 +
 
 +
 
 +
Ein Code kann nur dann präfixfrei sein, wenn die Kraftsche Ungleichung erfüllt ist.&nbsp; <br>Die Umkehrung gilt nicht: &nbsp; Wird die Kraftsche Ungleichung erfüllt, so bedeutet das noch lange nicht, dass dieser Code tatsächlich präfixfrei ist.
  
:* <i>L<sub>&mu;</sub></i> die Länge des zum Quellensymbol <i>q<sub>&mu;</sub></i> gehörigen Codewortes  <i>c<sub>&mu;</sub></i>,
 
  
:* <i>D</i> = 2 einen Binärcode (<b>0</b> oder <b>1</b>) und <i>D</i> = 3 einen Ternärcode (<b>0</b>, <b>1</b>, <b>2</b>).
 
  
:Ein Code kann nur dann präfixfrei sein, wenn die Kraftsche Ungleichung erfüllt ist. Die Umkehrung gilt nicht: Wird die Kraftsche Ungleichung erfüllt, so bedeutet das noch lange nicht, dass dieser Code tatsächlich präfixfrei ist.
 
  
:<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 38: Zeile 48:
 
{Welche der Binärcodes erfüllen die Kraftsche Ungleichung?
 
{Welche der Binärcodes erfüllen die Kraftsche Ungleichung?
 
|type="[]"}
 
|type="[]"}
+ B1,
+
+ $\rm B1$,
+ B2,
+
+ $\rm B2$,
- B3,
+
+ $\rm B3$,
- B4.
+
- $\rm B4$.
  
  
 
{Welche der vorgegebenen Binärcodes sind präfixfrei?
 
{Welche der vorgegebenen Binärcodes sind präfixfrei?
 
|type="[]"}
 
|type="[]"}
+ B1,
+
+ $\rm B1$,
+ B2,
+
+ $\rm B2$,
- B3,
+
- $\rm B3$,
- B4.
+
- $\rm B4$.
  
  
 
{Welche der vorgegebenen Ternärcodes sind präfixfrei?
 
{Welche der vorgegebenen Ternärcodes sind präfixfrei?
 
|type="[]"}
 
|type="[]"}
+ T1,
+
+ $\rm T1$,
- T2,
+
- $\rm T2$,
+ T3.
+
+ $\rm T3$.
  
  
{Wie lauten die Kenngrößen des Codes T1?
+
{Wie lauten die Kenngrößen des Ternärecodes&nbsp; $\rm T1$?
 
|type="{}"}
 
|type="{}"}
$Ternärecode\ T1:\ \ N_1$ = { 1 3% }
+
$ N_1 \ = \ $ { 1 }
$N_2$ = { 2 3% }
+
$ N_2 \ = \ $ { 2 }
$N_3$ = { 6 3% }
+
$ N_3 \ = \ $ { 6 }
  
  
{Wieviel 3&ndash;wertige Codeworte (<i>L<sub>&mu;</sub></i> = 3) könnte man hinzufügen, ohne dass sich an der Präfixfreiheit etwas ändert?
+
 
 +
{Wieviel dreiwertige Codeworte&nbsp; $(L_\mu = 3)$&nbsp; könnte man dem Code&nbsp; $\rm T1$&nbsp; hinzufügen, ohne dass sich an der Präfixfreiheit etwas ändert?
 
|type="{}"}
 
|type="{}"}
$Ternärecode\ \Delta N_3:\ \ N_1$ = { 6 3% }
+
$\Delta N_3 \ = \ $ { 6 }
  
  
{Der Ternärcode T3 soll auf insgesamt <i>N</i> = 9 Codeworte erweitert werden. Wie erreicht man das ohne Verletzung der Präfixfreiheit?
+
{Der Ternärcode&nbsp; $\rm T3$&nbsp; soll auf insgesamt&nbsp; $N = 9$&nbsp; Codeworte erweitert werden.&nbsp; Wie erreicht man das ohne Verletzung der Präfixfreiheit?
 
|type="[]"}
 
|type="[]"}
- Ergänzung um vier 3&ndash;wertige Codeworte.
+
- Ergänzung um vier dreiwertige Codeworte.
+ Ergänzung um vier 4&ndash;wertige Codeworte.
+
+ Ergänzung um vier vierwertige Codeworte.
+ Ergänzung um ein 3&ndash;wertiges und drei 4&ndash;wertige Codeworte.
+
+ Ergänzung um ein dreiwertiges und drei vierwertige Codeworte.
  
  
Zeile 83: Zeile 94:
 
===Musterlösung===
 
===Musterlösung===
 
{{ML-Kopf}}
 
{{ML-Kopf}}
:<b>1.</b>&nbsp;&nbsp;Für die angegebenen Binärcodes gilt:
+
'''(1)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 1, 2 und 3.</u>&nbsp; Für die angegebenen Binärcodes gilt:
 +
* $\rm B1$:&nbsp;&nbsp;&nbsp; $8 \cdot 2^{-3} = 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Bedingung erfüllt,
 +
* $\rm B2$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3}  + 2 \cdot 2^{-4}= 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Bedingung erfüllt,
 +
* $\rm B3$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3}  + 2 \cdot 2^{-4}= 1$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Bedingung erfüllt,
 +
* $\rm B4$:&nbsp;&nbsp;&nbsp; $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 2 \cdot 2^{-3}  + 1 \cdot 2^{-4}= 17/16$ &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Bedingung <u>nicht</u> erfüllt.
 +
 
 +
 
  
:* B1:&nbsp;&nbsp;&nbsp; 8 &middot; 2<sup>&ndash;3</sup> = 1 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Bedingung erfüllt,
+
'''(2)'''&nbsp; Richtig sind die <u>Lösungsvorschläge 1 und 2:</u>
 +
*Der Code&nbsp; $\rm B4$, der die Kraftsche Ungleichung nicht erfüllt, ist mit Sicherheit auch nicht präfixfrei.
 +
*Aber bei Erfüllung der Kraftschen Ungleichung ist noch nicht sicher, dass dieser Code auch präfixfrei ist.
 +
*Beim Code&nbsp; $\rm B3$&nbsp; ist &bdquo;10&rdquo; der Beginn des Codewortes &bdquo;1011&rdquo;.
 +
*Dagegen sind die Codes&nbsp; $\rm B1$&nbsp; und&nbsp; $\rm B2$&nbsp; tatsächlich präfixfrei.
  
:* B2:&nbsp;&nbsp;&nbsp; 1 &middot; 2<sup>&ndash;1</sup> + 1 &middot; 2<sup>&ndash;2</sup> + 1 &middot; 2<sup>&ndash;3</sup> + 2 &middot; 2<sup>&ndash;4</sup> = 1 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Bedingung erfüllt,
 
  
:* B3:&nbsp;&nbsp;&nbsp; 1 &middot; 2<sup>&ndash;1</sup> + 1 &middot; 2<sup>&ndash;2</sup> + 1 &middot; 2<sup>&ndash;3</sup> + 2 &middot; 2<sup>&ndash;4</sup> = 1 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Bedingung erfüllt,
 
  
:* B4:&nbsp;&nbsp;&nbsp; 1 &middot; 2<sup>&ndash;1</sup> + 1 &middot; 2<sup>&ndash;2</sup> + 2 &middot; 2<sup>&ndash;3</sup> + 1 &middot; 2<sup>&ndash;4</sup> = 17/16 &nbsp;&nbsp;&#8658;&nbsp;&nbsp; Bedingung <u>nicht</u> erfüllt.
+
'''(3)'''&nbsp; Richtig sind die <u>Antworten 1 und 3</u>:
 +
*Die Kraftsche Ungleichung wird von allen drei Codes erfüllt.
 +
*Wie aus der Tabelle hervorgeht, sind die Codes&nbsp; $\rm T1$&nbsp; und&nbsp; $\rm T3$&nbsp; tatsächlich präfixfrei.
 +
*Der Code&nbsp; $\rm T2$&nbsp; ist dagegen nicht präfixfrei, da &bdquo;1&rdquo; der Beginn des Codewortes &bdquo;10&rdquo; ist.  
  
:<b>2.</b>&nbsp;&nbsp;Der Code B4, der die Kraftsche Ungleichung nicht erfüllt, ist mit Sicherheit auch nicht präfixfrei. Aber bei Erfüllung der Kraftschen Ungleichung ist noch nicht sicher, dass dieser Code auch präfixfrei ist. Beim Code B3 ist &bdquo;10&rdquo; der Beginn des Codewortes &bdquo;1011&rdquo;. Dagegen sind die Codes <u>B1 und B2</u> präfixfrei.
 
  
:<b>3.</b>&nbsp;&nbsp;Richtig sind die <u>Antworten 1 und 3</u>. Der Code T2 ist dagegen nicht präfixfrei, da &bdquo;1&rdquo; der Beginn des Codewortes &bdquo;10&rdquo; ist. Die Kraftsche Ungleichung wird von allen drei Codes erfüllt.
 
  
:<b>4.</b>&nbsp;&nbsp;<i>N<sub>i</sub></i> gibt an, wieviele Codeworte  mit <i>i</i> Symbolen  es im Code gibt. Für den Code T1 gilt:
+
'''(4)'''&nbsp; $N_i$&nbsp; gibt an, wieviele Codeworte  mit&nbsp; $i$&nbsp; Symbolen  es im Code gibt.&nbsp; Für den Code&nbsp; $\rm T1$&nbsp; gilt:
 
:$$N_1 \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}, \hspace{0.2cm}N_2 \hspace{0.15cm}\underline{= 2}\hspace{0.05cm}, \hspace{0.2cm}N_3 \hspace{0.15cm}\underline{= 6}\hspace{0.05cm}.$$
 
:$$N_1 \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}, \hspace{0.2cm}N_2 \hspace{0.15cm}\underline{= 2}\hspace{0.05cm}, \hspace{0.2cm}N_3 \hspace{0.15cm}\underline{= 6}\hspace{0.05cm}.$$
  
:<b>5.</b>&nbsp;&nbsp;Nach der Kraftschen Ungleichung muss gelten
+
 
 +
 
 +
'''(5)'''&nbsp; Nach der Kraftschen Ungleichung muss gelten
 
:$$N_1 \cdot 3^{-1} + N_2 \cdot 3^{-2} + N_3 \cdot 3^{-3 } \le 1\hspace{0.05cm}.$$
 
:$$N_1 \cdot 3^{-1} + N_2 \cdot 3^{-2} + N_3 \cdot 3^{-3 } \le 1\hspace{0.05cm}.$$
:Bei gegebenem <i>N</i><sub>1</sub> = 1 und <i>N</i><sub>2</sub> = 2 wird dies erfüllt, solange gilt:
+
Bei gegebenem&nbsp; $N_1 = 1$&nbsp; und&nbsp;  $N_2 = 2$&nbsp; wird dies erfüllt, solange gilt:
 
:$$N_3 \cdot 3^{-3 } \le 1 - 1/3 - 2/9 = 4/9 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}N_3  \le 12 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm \Delta}\,N_3
 
:$$N_3 \cdot 3^{-3 } \le 1 - 1/3 - 2/9 = 4/9 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}N_3  \le 12 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm \Delta}\,N_3
 
\hspace{0.15cm}\underline{= 6}\hspace{0.05cm}.$$
 
\hspace{0.15cm}\underline{= 6}\hspace{0.05cm}.$$
:Die zusätzlichen Codeworte sind <b>210</b>, <b>211</b>, <b>212</b>, <b>220</b>, <b>221</b> und <b>222</b>.
+
Die zusätzlichen Codeworte sind&nbsp; $\rm 210, \,211, \,212, \,220, \,221, \,222$.
 +
 
  
:<b>6.</b>&nbsp;&nbsp;Für den Code T3 gilt:
 
:$$S({\rm T3})= 2 \cdot 3^{-1} + 2 \cdot 3^{-2} + 1 \cdot 3^{-3 } = {25}/{27}\hspace{0.05cm}.$$
 
:Wegen <i>S</i>(T3) &#8804; 1 erfüllt der Ternärcode T3 die Kraftsche Ungleichung und er ist zudem auch präfixfrei. Betrachten wir nun die vorgeschlagenen neuen Codes.
 
  
:* Code T4 (<i>N</i><sub>1</sub> = 2, <i>N</i><sub>2</sub> = 2, <i>N</i><sub>3</sub> = 5):
+
'''(6)'''&nbsp; Für den Code&nbsp; $\rm T3$&nbsp; gilt:  
 +
*$S({\rm T3})= 2 \cdot 3^{-1} + &nbsp;2 \cdot 3^{-2} + 1 \cdot 3^{-3 } = {25}/{27}\hspace{0.05cm}.$
 +
*Wegen&nbsp; $S({\rm T3}) \le 1$&nbsp; erfüllt der Ternärcode&nbsp; $\rm T3$&nbsp; die Kraftsche Ungleichung und er ist zudem auch präfixfrei.
 +
 
 +
 
 +
Betrachten wir nun die vorgeschlagenen neuen Codes.
 +
* Code $\rm T4$ $(N_1 = 2, \ N_2 = 2, \ N_3 = 5)$:
 
:$$S({\rm T4})= S({\rm T3}) + 4 \cdot 3^{-3 } = {29}/{27}\hspace{0.1cm} > \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T4 \hspace{0.15cm}ist\hspace{0.15cm} ungeeignet}\hspace{0.05cm},$$
 
:$$S({\rm T4})= S({\rm T3}) + 4 \cdot 3^{-3 } = {29}/{27}\hspace{0.1cm} > \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T4 \hspace{0.15cm}ist\hspace{0.15cm} ungeeignet}\hspace{0.05cm},$$
 
+
* Code $\rm T5$ $(N_1 = 2, \ N_2 = 2, \ N_3 = 1, \ N_4 = 4)$:
:* Code T5 (<i>N</i><sub>1</sub> = 2, <i>N</i><sub>2</sub> = 2, <i>N</i><sub>3</sub> = 1, <i>N</i><sub>4</sub> = 4):
 
 
:$$S({\rm T5})= S({\rm T3}) + 4 \cdot 3^{-4 } = {79}/{81}\hspace{0.1cm} < \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T5 \hspace{0.15cm}ist\hspace{0.15cm} geeignet}\hspace{0.05cm},$$
 
:$$S({\rm T5})= S({\rm T3}) + 4 \cdot 3^{-4 } = {79}/{81}\hspace{0.1cm} < \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T5 \hspace{0.15cm}ist\hspace{0.15cm} geeignet}\hspace{0.05cm},$$
 
+
* Code $\rm T6$ $(N_1 = 2, \ N_2 = 2, \ N_3 = 2, \ N_4 = 3)$:
:* Code T6 (<i>N</i><sub>1</sub> = 2, <i>N</i><sub>2</sub> = 2, <i>N</i><sub>3</sub> = 2, <i>N</i><sub>4</Sub> = 3):
 
 
:$$S({\rm T6})= S({\rm T3}) + 1 \cdot 3^{-3 } + 3 \cdot 3^{-4 } = \frac{75 + 3 + 3}{81}\hspace{0.1cm} = \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T6 \hspace{0.15cm}ist\hspace{0.15cm} geeignet}\hspace{0.05cm}.$$
 
:$$S({\rm T6})= S({\rm T3}) + 1 \cdot 3^{-3 } + 3 \cdot 3^{-4 } = \frac{75 + 3 + 3}{81}\hspace{0.1cm} = \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T6 \hspace{0.15cm}ist\hspace{0.15cm} geeignet}\hspace{0.05cm}.$$
  
:Richtig sind also die <u>zwei letzten</u> Lösungsvorschläge. Beispielsweise lauten die insgesamt 9 Codeworte des präfixfreien Codes T6: <b>0</b>, <b>1</b>, <b>20</b>, <b>21</b>, <b>220</b>, <b>221</b>, <b>2220</b>, <b>2221</b> und <b>2222</b>.
+
Richtig sind also die <u>zwei letzten</u> Lösungsvorschläge.  
 +
Beispielsweise lauten die insgesamt&nbsp; $N = 9$&nbsp; Codeworte des präfixfreien Codes&nbsp; $\rm T6$:
 +
:$$\rm 0, \, 1, \, 20, \,21, \,220, \,221, \,2220, \, 2221 , \,2222.$$
 
{{ML-Fuß}}
 
{{ML-Fuß}}
  

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

Vier Beispiele für Binärcodes und dazu drei Ternärcodes

In der Abbildung sind einige beispielhafte Binär– und Ternärcodes angegeben.

  • Beim Binärcode  $\rm B1$  werden alle möglichen Quellensymbole  $q_\mu$  $($mit Laufindex  $\mu = 1$, ... , $8)$  durch jeweils eine Codesymbolfolge  $\langle c_\mu \rangle $  einheitlicher Länge  $L_\mu = 3$  dargestellt.
  • Dieser Code ist aus diesem Grund zur Datenkomprimierung ungeeignet.


Die Möglichkeit zur Datenkomprimierung ergibt sich erst dann, wenn

  • die  $M$  Quellensymbole nicht gleichwahrscheinlich, und
  • die Länge  $L_\mu$  der Codeworte unterschiedlich sind.


Diese Eigenschaft weist zum Beispiel der Binärcode  $\rm B2$  auf:  

  • Je ein Codewort hat hier die Länge  $1$,  $2$  bzw.  $3$  $(N_1 = 1,\ N_2 = 2,\ N_3 = 3)$.
  • Zwei Codeworte haben die Länge  $L_\mu = 4$  $(N_4 = N_5 = 4)$.


Voraussetzung für die Decodierbarkeit eines solchen Codes ist, dass der Code  präfixfrei  ist. 

  • Das heißt, dass kein Codewort der Präfix (also der Beginn) eines längeren Codewortes sein darf.
  • Eine notwendige Bedingung dafür, dass ein Code zur Datenkomprimierung präfixfrei sein kann, wurde 1949 von Leon Kraft angegeben, die so genannte  Kraftsche Ungleichung:
$$\sum_{\mu=1}^{M} \hspace{0.2cm} D^{-L_{\mu}} \le 1 \hspace{0.05cm}.$$

Hierbei bezeichnen

  • $M$  die Anzahl der möglichen Quellensymbole  $q_\mu$   ⇒   „Symbolumfang”,
  • $L_\mu$  die Länge des zum Quellensymbol  $q_\mu$  gehörigen Codewortes  $c_\mu$,
  • $D = 2$  kennzeichnet einen Binärcode  $(\rm 0$ oder  $\rm 1)$  und  $D = 3$  einen Ternärcode  $(\rm 0$,  $\rm 1$,  $\rm 2)$.


Ein Code kann nur dann präfixfrei sein, wenn die Kraftsche Ungleichung erfüllt ist. 
Die Umkehrung gilt nicht:   Wird die Kraftsche Ungleichung erfüllt, so bedeutet das noch lange nicht, dass dieser Code tatsächlich präfixfrei ist.



Hinweis:


Fragebogen

1

Welche der Binärcodes erfüllen die Kraftsche Ungleichung?

$\rm B1$,
$\rm B2$,
$\rm B3$,
$\rm B4$.

2

Welche der vorgegebenen Binärcodes sind präfixfrei?

$\rm B1$,
$\rm B2$,
$\rm B3$,
$\rm B4$.

3

Welche der vorgegebenen Ternärcodes sind präfixfrei?

$\rm T1$,
$\rm T2$,
$\rm T3$.

4

Wie lauten die Kenngrößen des Ternärecodes  $\rm T1$?

$ N_1 \ = \ $

$ N_2 \ = \ $

$ N_3 \ = \ $

5

Wieviel dreiwertige Codeworte  $(L_\mu = 3)$  könnte man dem Code  $\rm T1$  hinzufügen, ohne dass sich an der Präfixfreiheit etwas ändert?

$\Delta N_3 \ = \ $

6

Der Ternärcode  $\rm T3$  soll auf insgesamt  $N = 9$  Codeworte erweitert werden.  Wie erreicht man das ohne Verletzung der Präfixfreiheit?

Ergänzung um vier dreiwertige Codeworte.
Ergänzung um vier vierwertige Codeworte.
Ergänzung um ein dreiwertiges und drei vierwertige Codeworte.


Musterlösung

(1)  Richtig sind die Lösungsvorschläge 1, 2 und 3.  Für die angegebenen Binärcodes gilt:

  • $\rm B1$:    $8 \cdot 2^{-3} = 1$   ⇒   Bedingung erfüllt,
  • $\rm B2$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} + 2 \cdot 2^{-4}= 1$   ⇒   Bedingung erfüllt,
  • $\rm B3$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 1 \cdot 2^{-3} + 2 \cdot 2^{-4}= 1$   ⇒   Bedingung erfüllt,
  • $\rm B4$:    $1 \cdot 2^{-1} + 1 \cdot 2^{-2} + 2 \cdot 2^{-3} + 1 \cdot 2^{-4}= 17/16$   ⇒   Bedingung nicht erfüllt.


(2)  Richtig sind die Lösungsvorschläge 1 und 2:

  • Der Code  $\rm B4$, der die Kraftsche Ungleichung nicht erfüllt, ist mit Sicherheit auch nicht präfixfrei.
  • Aber bei Erfüllung der Kraftschen Ungleichung ist noch nicht sicher, dass dieser Code auch präfixfrei ist.
  • Beim Code  $\rm B3$  ist „10” der Beginn des Codewortes „1011”.
  • Dagegen sind die Codes  $\rm B1$  und  $\rm B2$  tatsächlich präfixfrei.


(3)  Richtig sind die Antworten 1 und 3:

  • Die Kraftsche Ungleichung wird von allen drei Codes erfüllt.
  • Wie aus der Tabelle hervorgeht, sind die Codes  $\rm T1$  und  $\rm T3$  tatsächlich präfixfrei.
  • Der Code  $\rm T2$  ist dagegen nicht präfixfrei, da „1” der Beginn des Codewortes „10” ist.


(4)  $N_i$  gibt an, wieviele Codeworte mit  $i$  Symbolen es im Code gibt.  Für den Code  $\rm T1$  gilt:

$$N_1 \hspace{0.15cm}\underline{= 1}\hspace{0.05cm}, \hspace{0.2cm}N_2 \hspace{0.15cm}\underline{= 2}\hspace{0.05cm}, \hspace{0.2cm}N_3 \hspace{0.15cm}\underline{= 6}\hspace{0.05cm}.$$


(5)  Nach der Kraftschen Ungleichung muss gelten

$$N_1 \cdot 3^{-1} + N_2 \cdot 3^{-2} + N_3 \cdot 3^{-3 } \le 1\hspace{0.05cm}.$$

Bei gegebenem  $N_1 = 1$  und  $N_2 = 2$  wird dies erfüllt, solange gilt:

$$N_3 \cdot 3^{-3 } \le 1 - 1/3 - 2/9 = 4/9 \hspace{0.3cm} \Rightarrow \hspace{0.3cm}N_3 \le 12 \hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm \Delta}\,N_3 \hspace{0.15cm}\underline{= 6}\hspace{0.05cm}.$$

Die zusätzlichen Codeworte sind  $\rm 210, \,211, \,212, \,220, \,221, \,222$.


(6)  Für den Code  $\rm T3$  gilt:

  • $S({\rm T3})= 2 \cdot 3^{-1} +  2 \cdot 3^{-2} + 1 \cdot 3^{-3 } = {25}/{27}\hspace{0.05cm}.$
  • Wegen  $S({\rm T3}) \le 1$  erfüllt der Ternärcode  $\rm T3$  die Kraftsche Ungleichung und er ist zudem auch präfixfrei.


Betrachten wir nun die vorgeschlagenen neuen Codes.

  • Code $\rm T4$ $(N_1 = 2, \ N_2 = 2, \ N_3 = 5)$:
$$S({\rm T4})= S({\rm T3}) + 4 \cdot 3^{-3 } = {29}/{27}\hspace{0.1cm} > \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T4 \hspace{0.15cm}ist\hspace{0.15cm} ungeeignet}\hspace{0.05cm},$$
  • Code $\rm T5$ $(N_1 = 2, \ N_2 = 2, \ N_3 = 1, \ N_4 = 4)$:
$$S({\rm T5})= S({\rm T3}) + 4 \cdot 3^{-4 } = {79}/{81}\hspace{0.1cm} < \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T5 \hspace{0.15cm}ist\hspace{0.15cm} geeignet}\hspace{0.05cm},$$
  • Code $\rm T6$ $(N_1 = 2, \ N_2 = 2, \ N_3 = 2, \ N_4 = 3)$:
$$S({\rm T6})= S({\rm T3}) + 1 \cdot 3^{-3 } + 3 \cdot 3^{-4 } = \frac{75 + 3 + 3}{81}\hspace{0.1cm} = \hspace{0.1cm}1\hspace{0.3cm} \Rightarrow \hspace{0.3cm} {\rm T6 \hspace{0.15cm}ist\hspace{0.15cm} geeignet}\hspace{0.05cm}.$$

Richtig sind also die zwei letzten Lösungsvorschläge. Beispielsweise lauten die insgesamt  $N = 9$  Codeworte des präfixfreien Codes  $\rm T6$:

$$\rm 0, \, 1, \, 20, \,21, \,220, \,221, \,2220, \, 2221 , \,2222.$$