Was ist Kraft-Ungleichung?

Die Ungleichung Σ 2^(−lᵢ) ≤ 1, die notwendige und hinreichende Bedingung dafür, dass ein Präfixcode aus 0 und 1 mit den Codewortlängen l₁, l₂, …, lₙ existiert. Man versteht sie leicht, wenn man bedenkt, dass ein Codewort der Länge l alle Bitfolgen sperrt, die mit ihm beginnen, und damit 2^(−l) des Ganzen belegt. Zum Beispiel ergibt sich für die Längen 1, 2, 3, 3 genau die Summe 1, und sie lassen sich als 0, 10, 110, 111 realisieren. Jeder eindeutig dekodierbare Code erfüllt diese Ungleichung (Satz von McMillan); bei der Wahl der Codewortlängen genügt es daher, unter den Präfixcodes zu suchen.

Japanische Bezeichnung: クラフトの不等式

„Kraft-Ungleichung“ kommt in 2 Übungsfragen aus 1 Themen vor, z. B. Grundlagen der Informationstheorie und Kodierung.

Fachgebiet: Grundlagen der Informationstheorie und Kodierung

Jetzt üben: Fragen zu Kraft-Ungleichung

Den 4 Symbolen A bis D sollen Codewörter der folgenden Längen (in Bit) zugeordnet werden, sodass ein Präfixcode aus 0 und 1 entsteht. Mit welcher Kombination von Codewortlängen ist das möglich?

AA: 1, B: 2, C: 3, D: 3
BA: 1, B: 2, C: 2, D: 3
CA: 1, B: 1, C: 2, D: 3

Antwort und Erläuterung anzeigen

Antwort: A. A: 1, B: 2, C: 3, D: 3

Ein Präfixcode mit den Codewortlängen l₁, l₂, … lässt sich genau dann bilden, wenn die Kraft-Ungleichung Σ 2^(−lᵢ) ≤ 1 erfüllt ist. Für 1, 2, 3, 3 ist 1/2 + 1/4 + 1/8 + 1/8 = 1, also ist er möglich, zum Beispiel als 0, 10, 110, 111. Für 1, 2, 2, 3 ergibt sich 1/2 + 1/4 + 1/4 + 1/8 = 9/8 und für 1, 1, 2, 3 ergibt sich 1/2 + 1/2 + 1/4 + 1/8 = 11/8; beide Summen sind größer als 1, also ist es nicht möglich.

Es wird ein Präfixcode aus 0 und 1 aufgebaut. Die Codewörter 00 und 01 der Länge 2 sind bereits vergeben. Wie viele Codewörter der Länge 3 lassen sich höchstens hinzufügen, ohne die Präfixbedingung zu verletzen?

Antwort und Erläuterung anzeigen

Antwort: A. 4

Es gibt 2³ = 8 Bitfolgen der Länge 3, doch die 4 mit 00 oder 01 beginnenden, 000, 001, 010 und 011, sind nicht verwendbar. Die restlichen 4, 100, 101, 110 und 111, stehen weder zu 00 noch zu 01 in einer Präfixbeziehung und können alle hinzugefügt werden. Auch die Kraft-Ungleichung liefert aus 2/4 + n/8 ≤ 1 die Bedingung n ≤ 4.

„Kraft-Ungleichung“ in den Erläuterungen

Ein Präfixcode mit den Codewortlängen l₁, l₂, … lässt sich genau dann bilden, wenn die Kraft-Ungleichung Σ 2^(−lᵢ) ≤ 1 erfüllt ist.
Den 4 Symbolen A bis D sollen Codewörter der folgenden Läng…
Auch die Kraft-Ungleichung liefert aus 2/4 + n/8 ≤ 1 die Bedingung n ≤ 4.
Es wird ein Präfixcode aus 0 und 1 aufgebaut. Die Codewörte…

Was ist Kraft-Ungleichung?

Jetzt üben: Fragen zu Kraft-Ungleichung

Den 4 Symbolen A bis D sollen Codewörter der folgenden Längen (in Bit) zugeordnet werden, sodass ein Präfixcode aus 0 und 1 entsteht. Mit welcher Kombination von Codewortlängen ist das möglich?

Es wird ein Präfixcode aus 0 und 1 aufgebaut. Die Codewörter 00 und 01 der Länge 2 sind bereits vergeben. Wie viele Codewörter der Länge 3 lassen sich höchstens hinzufügen, ohne die Präfixbedingung zu verletzen?

„Kraft-Ungleichung“ in den Erläuterungen

Fragen mit „Kraft-Ungleichung“ (2)

Verwandte Begriffe