Grundlagen der Informationstheorie und Kodierung

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.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Grundlagen der Informationstheorie und Kodierung

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?
Eine Quelle gibt die Symbole A, B, C und D unabhängig voneinander mit den Wahrscheinlichkeiten 0,4; 0,3; 0,2 und 0,1 aus und wird mit einem Huffman-Code kodiert. Wie groß ist die mittlere Codewortlänge pro Symbol?
Eine Quelle gibt die Symbole A bis E unabhängig voneinander mit den Wahrscheinlichkeiten 0,3; 0,25; 0,2; 0,15 und 0,1 aus und wird mit einem Huffman-Code kodiert. Je nachdem, welche von zwei gleichen Wahrscheinlichkeiten zuerst gewählt wird, können sich die Codewörter ändern, die mittlere Codewortlänge jedoch nicht. Wie groß ist die mittlere Codewortlänge pro Symbol?
Eine Quelle gibt die Symbole A, B und C unabhängig voneinander mit den Wahrscheinlichkeiten 0,6; 0,3 und 0,1 aus; ihre Entropie beträgt etwa 1,30 Bit. Welcher Wert liegt der Effizienz (Entropie ÷ mittlere Codewortlänge) am nächsten, wenn diese Quelle mit einem Huffman-Code kodiert wird?
Eine binäre Quelle gibt unabhängig voneinander 0 mit der Wahrscheinlichkeit 0,8 und 1 mit der Wahrscheinlichkeit 0,2 aus. Je 2 Symbole werden zusammengefasst; die 4 Kombinationen 00, 01, 10 und 11 werden jeweils als ein Symbol betrachtet und mit einem Huffman-Code kodiert. Wie groß ist die mittlere Codewortlänge pro ursprünglichem Symbol?