Digitale AV-Technik
Prof. Uwe Hahne
Sommersemester 2026

Digitale AV-Technik - Aufgabenblatt 04

Kodieren und Dekodieren mit Huffman-Bäumen

Aufgabe 1: Kodieren mit einem gegebenen Huffman-Baum

Gegeben sei der folgende Huffman-Baum:

 ._      
/  \     
A  .___  
  /    \ 
  E   _. 
     /  \
     .  C
    / \  
    B D 

• Die Buchstaben sind die Blätter des Baums, und die Häufigkeit wurde bereits in diesem Baum berücksichtigt. Nutze die linke Seite des Baums für die 0 und die rechte Seite für die 1.

• Erstelle eine Kodierungstabelle, die jedem Buchstaben den entsprechenden Binärcode zuordnet.

  Symbol	Binärer Code
  A
  B
  C
  D
  E

• Kodieren: Kodiere mit Hilfe der Kodierungstabelle den Text BEAD und notieren Sie die Binärcodes.

  

• Dekodieren: Dekodieren Sie, wenn möglich, die folgenden Binärcodes mit dem gegebenen Baum. Ist es für alle Binärcodes möglich?

• 011

• 1010
• 00

Aufgabe 2: Erstellen eines kanonischen Huffman-Baums

Die Idee der kanonischen Huffman-Codierung besteht darin, die Codes so anzuordnen, dass sie bestimmten Regeln folgen, die eine kompakte Schreibweise und eine Rekonstruktion des Baums aus den Bitlängen ermöglichen.

1. Vorbereitung Wir behalten die Länge der Codes bei, aber ordnen die Codes aus Aufgabe 1 so an, dass sie aufsteigend sortiert sind, wobei die kürzeren Codes zuerst kommen, und bei gleicher Länge die Codes in alphabetischer Reihenfolge der Symbole sortiert sind:

   Symbol	Binärer Code	Code-Länge
   A	0	1
   		2
   		3
   		4
   		4

2. Umkodieren: Jeder der bestehenden Codes wird durch einen neuen Code derselben Länge ersetzt, wobei der folgende Algorithmus verwendet wird:

   • Das erste Symbol erhält ein Codewort, das die gleiche Länge wie das ursprüngliche Codewort hat, aber nur aus Nullen besteht.
   • Jedes nachfolgende Symbol erhält die nächste Binärzahl in der Reihenfolge, wobei sichergestellt wird, dass die folgenden Codes immer einen höheren Wert haben.
   • Wenn ein längeres Codewort erreicht wird, fügt man nach dem Inkrementieren Nullen an, bis die Ziellänge erreicht ist.

   Symbol	Binärer Code	Code-Länge
   A	0	1
   		2
   		3
   		4
   		4

3. Umsortieren: Die einzigen Teile, die noch übertragen werden müssen, sind die Bitlängen (Anzahl der Bits) für jedes Symbol. Fülle die Tabelle wieder alphabetisch sortiert aus:

   Symbol	Binärer Code	Code-Länge
   A	0	1
   B
   C
   D
   E

4. Kompakte Ausgabe: Prüfe ob anhand der folgenden kompakten Darstellung die ursprüngliche Codierung rekonstruiert werden kann:

   (1, 4, 3, 4, 2)
   

   

5. Überprüfung: Wenn das richtige Codebuch ermittelt wurde, sollte der folgende Code die gleiche Nachricht wie zuvor kodieren:

   • 11101001111 --> BEAD

Aufgabe 3

Gegeben ist die folgende Codierung einer neuen kanonischen Huffman Codetabelle.

(0,2,2), ('A','C','D','E')

Wie lautet die zugehörige Codetabelle?

Symbol	Code
A
C
D
E

Lösungen

Prüfe die Lösungen und korrigiere sie wenn nötig.

Lösung Aufgabe 1

1. Kodierungstabelle:

Symbol	Binärer Code
A	0
B	1100
C	111
D	1101
E	10

1. Kodieren des Textes "BEAD":

2. B = 1100, E = 10, A = 0, D = 1101 ⟶ Code: 11001001101

3. Dekodieren:

4. 011 ⟶ A? --> unvollständig, da 11 kein gültiger Code ist.
5. 1010 ⟶ EE
6. 00 ⟶ AA

Lösung Aufgabe 2

1. Vorbereitung

   Symbol	Binärer Code	Code-Länge
   A	0	1
   E	10	2
   C	111	3
   B	1100	4
   D	1101	4

2. Umkodieren

   Symbol	Binärer Code	Code-Länge
   A	0	1
   E	10	2
   C	110	3
   B	1110	4
   D	1111	4

3. Umsortieren

   Symbol	Binärer Code	Code-Länge
   A	0	1
   B	1110	4
   C	110	3
   D	1111	4
   E	10	2

4. Kompakte Ausgabe:

   (1, 4, 3, 4, 2) 
   
   A: Länge 1, Code 0
   B: Länge 4, Code 1110
   C: Länge 3, Code 110
   D: Länge 4, Code 1111
   E: Länge 2, Code 10
   

5. Überprüfung: Ja, die Nachricht BEAD wird mit der neuen Codetabelle wie folgt kodiert:

   • 11101001111 --> BEAD

Lösung Aufgabe 3

Um die Codetabelle zu erstellen, analysieren wir die gegebenen Informationen:

Die kanonische Huffman-Codetabelle ist in zwei Teile unterteilt:

1. Code-Längen: (0, 2, 2) – das bedeutet:

2. Es gibt 0 Symbole mit einer Code-Länge von 1.

3. Es gibt 2 Symbole mit einer Code-Länge von 2.

4. Es gibt 2 Symbole mit einer Code-Länge von 3.

5. Symbole: ('A', 'C', 'D', 'E') – die Symbole, die codiert werden sollen, sind in der Reihenfolge angegeben.

Schritte zur Erstellung der Codetabelle

1. Verteilung der Code-Längen auf die Symbole:
2. Da wir 0 Symbole mit einer Länge von 1 haben, gibt es keine Codes der Länge 1.
3. Die nächsten 2 Symbole erhalten Codes mit der Länge 2.

4. Die verbleibenden 2 Symbole erhalten Codes mit der Länge 3.

5. Kanonische Codes zuweisen:

6. Da dies ein kanonischer Huffman-Code ist, beginnen wir mit dem kürzesten Code und gehen der Reihe nach weiter, wobei wir die Binärwerte inkrementieren.

7. Der erste Code der Länge 2 beginnt bei 00, und wir erhöhen den Wert um 1 für das nächste Symbol.

8. Kanonische Code-Zuweisung für die Symbole:

9. Symbole mit einer Länge von 2:

   • A erhält 00
   • C erhält 01

10. Symbole mit einer Länge von 3:

    • D erhält 100
    • E erhält 101

Ergebnis: Codetabelle

Symbol	Code
A	00
C	01
D	100
E	101