Aufgabe 2.2: Kraftsche Ungleichung
Aus LNTwww
Version vom 5. Oktober 2016, 17:26 Uhr von Nabil (Diskussion | Beiträge) (Die Seite wurde neu angelegt: „ {{quiz-Header|Buchseite=Informationstheorie und Quellencodierung/Allgemeine Beschreibung }} right| :In der rechten Abbildun…“)
- In der rechten Abbildung sind einige beispielhafte Binär– und Ternärcodes angegeben.
- Beim Binärcode B1 werden alle möglichen Quellensymbole qμ (mit Laufindex μ = 1, ... , 8) durch jeweils eine Codesymbolfolge 〈cμ〉 einheitlicher Länge Lμ = 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 sind,
- und die Länge Lμ 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 (N1 = N2 = N3 = 1) und zwei Codeworte haben die Länge Lμ = 4 (N4 = 2).
- 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:
- $$\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μ,
- Lμ die Länge des zum Quellensymbol qμ gehörigen Codewortes cμ,
- D = 2 einen Binärcode (0 oder 1) und D = 3 einen Ternärcode (0, 1, 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 bezieht sich auf das Kapitel 2.1.
Fragebogen
Musterlösung
- 1. Für die angegebenen Binärcodes gilt:
- B1: 8 · 2–3 = 1 ⇒ Bedingung erfüllt,
- B2: 1 · 2–1 + 1 · 2–2 + 1 · 2–3 + 2 · 2–4 = 1 ⇒ Bedingung erfüllt,
- B3: 1 · 2–1 + 1 · 2–2 + 1 · 2–3 + 2 · 2–4 = 1 ⇒ Bedingung erfüllt,
- B4: 1 · 2–1 + 1 · 2–2 + 2 · 2–3 + 1 · 2–4 = 17/16 ⇒ Bedingung nicht erfüllt.
- 2. 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 „10” der Beginn des Codewortes „1011”. Dagegen sind die Codes B1 und B2 präfixfrei.
- 3. Richtig sind die Antworten 1 und 3. Der Code T2 ist dagegen nicht präfixfrei, da „1” der Beginn des Codewortes „10” ist. Die Kraftsche Ungleichung wird von allen drei Codes erfüllt.
- 4. Ni gibt an, wieviele Codeworte mit i Symbolen es im Code gibt. Für den Code 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 N1 = 1 und N2 = 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 210, 211, 212, 220, 221 und 222.
- 6. 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 S(T3) ≤ 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 (N1 = 2, N2 = 2, N3 = 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 T5 (N1 = 2, N2 = 2, N3 = 1, N4 = 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 T6 (N1 = 2, N2 = 2, N3 = 2, N4 = 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 9 Codeworte des präfixfreien Codes T6: 0, 1, 20, 21, 220, 221, 2220, 2221 und 2222.