X. Übungsblatt – Aufgabe X

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

Vorgehensweise:1. Tabelle mit Häufigkeiten der Buchstaben erstellen2. while (noch nicht zusammengefasste Elemente)

do Fasse kleinste Elemente zu neuem zusammen

Übung zu Grundlagen der Technischen Informatik

X. Übungsblatt – Aufgabe X

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

Vorgehensweise:1. Tabelle mit Häufigkeiten der Buchstaben erstellen2. while (noch nicht zusammengefasste Elemente)

do Fasse kleinste Elemente zu neuem zusammen

Übung zu Grundlagen der Technischen Informatik

Buchstabe K D L R S I M B AAnzahl 1 1 1 2 2 2 2 3 7

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

K und D zusammenfassen => neues Element der Größe 2

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

K und D zusammenfassen => neues Element der Größe 2

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

L und KD zusammenfassen => neues Element der Größe 3

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

L und KD zusammenfassen => neues Element der Größe 3

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

R und S & I und M zusammenfassen=> 2 neue Elemente der Größe 4

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

R und S & I und M zusammenfassen=> 2 neue Elemente der Größe 4

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

LKD und B zusammenfassen => neues Element der Größe 6

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

LKD und B zusammenfassen => neues Element der Größe 6

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

RS und IM zusammenfassen => neues Element der Größe 8

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

a) Erstellen Sie den Huffman-Codierungsbaum für die folgendeZeichenkette: ABRAKADABRASIMSALABIM

2. Übungsblatt – Aufgabe 5

b) Wie viel Bits werden durch diese Codierung im Vergleich zu einer Codierung mit einer festen Codewort-Länge eingespart?

Übung zu Grundlagen der Technischen Informatik

X. Übungsblatt – Aufgabe X

b) Wie viel Bits werden durch diese Codierung im Vergleich zu einer Codierung mit einer festen Codewort-Länge eingespart?

Bei Codierung mit fester Codewort-Länge:Es gibt 9 verschiedene Zeichen deren Codierung mindestens je 4 Bit erfordern. Bei 21 Zeichen sind das 84 Bit.

Übung zu Grundlagen der Technischen Informatik

X. Übungsblatt – Aufgabe X

b) Wie viel Bits werden durch diese Codierung im Vergleich zu einer Codierung mit einer festen Codewort-Länge eingespart?

Rechts siehtman das Ergebnis derHuffman-Codierung.

Übung zu Grundlagen der Technischen Informatik

Zeichen Code Länge * AnzahlA 11 14

B 101 9

R 000 6

K 10010 5

D 10011 5

S 001 6

I 010 6

M 011 6

L 1000 4

Summe: 61

X. Übungsblatt – Aufgabe X

b) Wie viel Bits werden durch diese Codierung im Vergleich zu einer Codierung mit einer festen Codewort-Länge eingespart?

Ergebnis: Man spart 84 Bit - 61 Bit = 23 Bit.

Übung zu Grundlagen der Technischen Informatik

Zeichen Code Länge * AnzahlA 11 14

B 101 9

R 000 6

K 10010 5

D 10011 5

S 001 6

I 010 6

M 011 6

L 1000 4

Summe: 61

X. Übungsblatt – Aufgabe X

c) Wie viel Bits sind minimal nötig?

Übung zu Grundlagen der Technischen Informatik

X. Übungsblatt – Aufgabe X

c) Wie viel Bits sind minimal nötig?

Die minimale Bitlänge ist:

Übung zu Grundlagen der Technischen Informatik

)#(henzahlGesamtzeic

sdesZeichenld

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

Anzahl rel. Anteil Bitlänge7 0,333 1,59

3 0,143 2,81

2 0,095 3,39

1 0,048 4,39

c) Wie viel Bits sind minimal nötig?

Die minimale Bitlänge ist: )#(henzahlGesamtzeic

sdesZeichenld

Zeichen Anzahl BitlängeA 7 1,59

B 3 2,81

S 2 3,39

R 2 3,39

M 2 3,39

I 2 3,39

L 1 4,39

D 1 4,39

K 1 4,39

c) Wie viel Bits sind minimal nötig?

Die minimale Bitlänge ist:

Multipliziert man die Bitlänge mit der Summe der Zeichen gleicher Anzahl,so erhält man die jeweiligenSummenbitlängen. Die Summedavon ist die minimale Anzahl Bitsdie zur Codierung benötigt werden.

1,59 * 7 + 2,81 * 3 + 3,39 * 8 + 4,39 * 3 = 59,83

X. Übungsblatt – Aufgabe X

Übung zu Grundlagen der Technischen Informatik

Anzahl Bitlänge7 1,59

3 2,81

2 3,39

1 4,39

)#(henzahlGesamtzeic

sdesZeichenld

X. Übungsblatt – Aufgabe X

c) Wie viel Prozent schlechter ist der Huffman-Code?

Übung zu Grundlagen der Technischen Informatik

X. Übungsblatt – Aufgabe X

c) Wie viel Prozent schlechter ist der Huffman-Code?

→ Der Huffman-Code ist 2,041% schlechter als dieOptimale Codierung

Übung zu Grundlagen der Technischen Informatik

02041,06178,591