Grundlagen der Informationstheorie und Kodierung

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?

AEtwa 1,85 Bit
B1,9 Bit
C2 Bit

Antwort und Erläuterung anzeigen

Antwort: B. 1,9 Bit

Bei der Huffman-Kodierung werden wiederholt die beiden kleinsten Wahrscheinlichkeiten zusammengefasst: 0,1 und 0,2 ergeben 0,3, dann 0,3 und 0,3 ergeben 0,6, und zuletzt werden 0,6 und 0,4 zusammengefasst. Die Codewortlängen sind also 1 für A, 2 für B und 3 Bit für C und D. Die mittlere Codewortlänge beträgt 0,4 × 1 + 0,3 × 2 + 0,2 × 3 + 0,1 × 3 = 1,9 Bit.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Grundlagen der Informationstheorie und Kodierung

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?
Welche Aussage über den Zusammenhang zwischen verlustfreier Kompression und der Entropie einer Quelle ist richtig?
Die 40 Zeichen lange Zeichenkette AAAAAAAAAAAABBBBCCCCCCCCCCCCCCCCCCCCDDDD (12-mal A, 4-mal B, 20-mal C, 4-mal D) wird mit einer Lauflängenkodierung komprimiert, die jede Folge gleicher Zeichen als Paar „Zeichen (1 Byte) und Anzahl (1 Byte)“ darstellt. Die ursprüngliche Zeichenkette belegt 1 Byte pro Zeichen, und die Kompressionsrate sei „Größe nach der Kompression ÷ Größe vor der Kompression“. Wie groß ist die Kompressionsrate?