Aufgaben:Aufgabe 2.2: Kraftsche Ungleichung: Unterschied zwischen den Versionen
K (Guenter verschob die Seite 2.02 Kraftsche Ungleichung nach 2.2 Kraftsche Ungleichung) |
|||
(15 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 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}.$$ | :$$\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. <br>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:'' | ||
+ | *Die Aufgabe gehört zum Kapitel [[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$, |
− | + | + $\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 | + | {Wie lauten die Kenngrößen des Ternärecodes $\rm T1$? |
|type="{}"} | |type="{}"} | ||
− | $ | + | $ N_1 \ = \ $ { 1 } |
− | $N_2$ | + | $ N_2 \ = \ $ { 2 } |
− | $N_3$ | + | $ N_3 \ = \ $ { 6 } |
− | {Wieviel | + | |
+ | {Wieviel dreiwertige Codeworte $(L_\mu = 3)$ könnte man dem Code $\rm T1$ hinzufügen, ohne dass sich an der Präfixfreiheit etwas ändert? | ||
|type="{}"} | |type="{}"} | ||
− | $ | + | $\Delta N_3 \ = \ $ { 6 } |
− | {Der Ternärcode T3 soll auf insgesamt | + | {Der Ternärcode $\rm T3$ soll auf insgesamt $N = 9$ Codeworte erweitert werden. Wie erreicht man das ohne Verletzung der Präfixfreiheit? |
|type="[]"} | |type="[]"} | ||
− | - Ergänzung um vier | + | - Ergänzung um vier dreiwertige Codeworte. |
− | + Ergänzung um vier | + | + Ergänzung um vier vierwertige Codeworte. |
− | + Ergänzung um ein | + | + Ergänzung um ein dreiwertiges und drei vierwertige Codeworte. |
Zeile 83: | Zeile 94: | ||
===Musterlösung=== | ===Musterlösung=== | ||
{{ML-Kopf}} | {{ML-Kopf}} | ||
− | + | '''(1)''' Richtig sind die <u>Lösungsvorschläge 1, 2 und 3.</u> 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 <u>nicht</u> erfüllt. | ||
+ | |||
+ | |||
− | :* | + | '''(2)''' Richtig sind die <u>Lösungsvorschläge 1 und 2:</u> |
+ | *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 <u>Antworten 1 und 3</u>: | |
+ | *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}.$$ | :$$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}.$$ | :$$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 | :$$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 $\rm 210, \,211, \,212, \,220, \,221, \,222$. | |
+ | |||
− | |||
− | |||
− | |||
− | :* Code T4 ( | + | '''(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},$$ | :$$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},$$ | :$$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}.$$ | :$$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 $N = 9$ Codeworte des präfixfreien Codes $\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
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:
- Die Aufgabe gehört zum Kapitel Allgemeine Beschreibung der Quellencodierung.
Fragebogen
Musterlösung
- $\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.$$