7.4 Übungsaufgaben

Aufgabe 7.4.1
(Kodebaum)
-> Seite §

Gegeben seien folgende 4 Kanalkodes:

	x1	x2	x3	x4	Dekodieren
C1(xi)	0	01	011	100	01100
C2(xi)	00	01	10	11	00101001
C3(xi)	0	10	110	111	01010110
C4(xi)	0	01	011	111	01111100011

1. Anstelle in Tabellenform können Kodes mit Kodebäumen beschrieben werden. Stellen Sie die Kodebäume für die 4 Kodes auf!
2. Begründen Sie warum welche Kodes dekodierbar sind und dekodieren Sie die gegebene Kodesequenz!
3. Man unterscheidet die gegebenen Kodes in Blockkodes und in Präfixkodes. Klassifizieren Sie die 4 Kodes entsprechend!

Aufgabe 7.4.2
(Huffman)
-> Seite §

Gegeben seien die 5 Symbole einer Nachrichtenquelle:

X	A	B	C	D	E
p(xi)	0,13	0,10	0,16	0,37	0,24

1. Erstellen Sie mit einen optimalen präfixfreien Huffman-Kode über einen grafischen Kodebaum!
2. Wie groß ist die mittlere Kodewortlänge?
3. Wie groß ist die Effizienz der Kodierung?
4. Was ändert sich, wenn die Wahrscheinlichkeit von p(B) = 0,08 und p(D) = 0,39 geringfügig verändert werden?

   X	A	B	C	D	E
   p(xi )	0,13	0,08	0,16	0,39	0,24

   Konstruieren Sie wieder einen Kodebaum!

5. Berechnen Sie wieder die mittlere Kodewortlänge und die Effizienz der Kodierung!

Hilfe:

Die Regeln des binären Huffmann-Algorithmus sind:

1. Start: Sortiere die Endknoten (aktive Knoten) mit den Quellsymbolen x_i nach deren Wahrscheinlichkeiten p(x_i) und weise ihnen die Wahrscheinlichkeiten zu.
2. Loop:
   • Verbinde die 2 Knoten mit den niedrigsten Wahrscheinlichkeiten.
   • Deaktiviere diese 2 Knoten.
   • Aktiviere den neu entstandenen Knoten.
   • Weise ihm die Summe der beiden Wahrscheinlichkeiten zu.
3. Gehe zu Loop, falls noch ein aktiver Knoten existiert.

Aufgabe 7.4.3
(Kodierung)
-> Seite §

Gegeben sei der folgende 2-aus-5-Kode, der die Dezimalzahlen 0–9 wie folgt binär kodiert:

xi	w = c(xi)						xi	w = c(xi)
1	1	1	0	0	0		6	0	0	1	1	0
2	1	0	1	0	0		7	1	0	0	0	1
3	0	1	1	0	0		8	0	1	0	0	1
4	1	0	0	1	0		9	0	0	1	0	1
5	0	1	0	1	0		0	0	0	0	1	1

Beantworten Sie folgende Fragen unter der Voraussetzung, daß die Zeichen des Eingangsalphabets gleichwahrscheinlich auftreten:

1. Wieviele Zeichen hat das Eingangsalphabet X?
2. Wieviele Zeichen hat das Ausgangsalphabet Y?
3. Aus wievielen Kodewörtern besteht der Kode und wieviele Wörter sind maximal mit 5 Bit Wortlänge möglich?
4. Wie groß ist die mittlere Wortlänge?
5. Ist der Kode eindeutig dekodierbar?
6. Bestimmen Sie die Quellenentropie und deren maximale Entropie!
7. Bestimmen Sie die Ausgangsentropie und deren maximale Entropie!
8. Bestimmen Sie die Hammingdistanz der Kodierung! Welche Fehler können damit erkannz und / oder korrigiert werden?
9. Bestimmen Sie die Redundanz der Kodierung!

Aufgabe 7.4.4
(Hamming-Distanz)
-> Seite §

Gegeben sei der folgende 4-aus-7 Kode, mit 8 Kodewörtern und der Blocklänge 7:

Bit

Bit

	6	5	4	3	2	1	0			6	5	4	3	2	1	0
x1	0	0	0	0	0	0	0		x5	1	0	0	1	1	1	0
x2	1	1	1	0	1	0	0		x6	0	1	0	0	1	1	1
x3	0	1	1	1	0	1	0		x7	1	0	1	0	0	1	1
x4	0	0	1	1	1	0	1		x8	1	1	0	1	0	0	1

1. Wie viele mögliche gültige Kodewörter gibt es?
2. Wie groß ist die Hamming-Distanz des Kodes?
3. Wieviele Bitfehler können erkannt werden?
4. Wieviele Bitfehler können korrigiert werden?
5. Untersuchen Sie folgende Verfälschungen bei x₄ auf Erkennbarbeit und Korrigierbarkeit:

   Bit

   		6	5	4	3	2	1	0
   	x 4	0	0	1	1	1	0	1
   1.	x4,1	1	1	0	0	0	1	0
   2.	x4,2	1	0	0	1	1	1	0
   3.	x4,3	0	1	1	1	1	0	1

Aufgabe 7.4.5
(Gray-Kode)
-> Seite §

Gegeben seien folgende BCD-Kodes mit je 10 Kodewörtern

		Binär					Gray 1					Gray 2
0		0	0	0	0		0	0	0	0		0	0	0	0
1		0	0	0	1		0	0	0	1		0	0	0	1
2		0	0	1	0		0	0	1	1		0	0	1	1
3		0	0	1	1		0	0	1	0		0	0	1	0
4		0	1	0	0		0	1	1	0		0	1	1	0
5		0	1	0	1		0	1	1	1		1	1	1	0
6		0	1	1	0		0	1	0	1		1	1	1	1
7		0	1	1	1		0	1	0	0		1	1	0	1
8		1	0	0	0		1	1	0	0		1	1	0	0
9		1	0	0	1		1	1	0	1		1	0	0	0

1. Stellen Sie die Kodes in einem Tableau dar, das einem Karnaugh-Veitch-Diagramm ähnelt!
2. Was bedeutet „einschrittig“ bei einem Gray-Kode?
3. Was unterscheidet die Kodes hinsichtlich möglicher 1-Bit-Fehler?

Aufgabe 7.4.6
(Verwürfler)
-> Seite §

Gegeben sei die Eingangsfolge 11011000, d.h. x_i = 1 + x⁻¹ + x⁻³ + x⁻⁴.

1. Verwürfeln Sie die Eingangsfolge mit dem CCITT Polynom 1 + x⁻⁶ + x⁻⁷. Wie lautet die Ausgangsfolge?
2. Skizieren Sie eine Schieberegisteranordnung für die Codierung und Dekodierung mit dem CCITT Polynom!

Aufgabe 7.4.7
(PCM-Signal)
-> Seite §

Gegeben sei das analoge Signal in Abb. 7.4.1. Die höchste Signalfrequenz beträgt 4kHz.

---

Abbildung 7.4.1: Analoges Signal zur HDB3-Codierung

---

1. Wie groß muß die Abtastfrequenz f_A mindestens gewählt werden? Bestimmen Sie für die kleinstmögliche Abtastfrequenz die Abtastrate T_A!
2. Zeichnen Sie die Abtastzeitpunkte in Abb. 7.4.1 ein und bestimmen Sie die analogen Amplituden des Signals an den Abtastzeitpunkten.
3. Quantisieren Sie das Signal linear mit 4 Bit, wobei als kleinste analoge Stufe 1 Volt aufgelöst werden soll. Wie groß ist der Mittelwert des binären Signals?
4. Wie groß ist die Übertragungsrate des Signals? Wieso beträgt die Übertragungsrate eines digitalisierten Sprachsignals bei der Telekom 64kBit∕s?
5. Wie groß sind ist der relative Quantisierungsfehler bei kleinen und großen Amplituden? Wie kann man diese Quantisierungsverzerrungen bei kleinen Amplituden verkleinern?
6. Verwenden Sie den AMI-Kode zur Codierung des Signals und bestimmen Sie wieder den Mittelwert der Symbolfolge. Gehen Sie davon aus, das das letzte Symbol eine „−1“ und die RDS = 0 sind.
7. Verwenden Sie den HDB3-Kode zur Kodierung des Signals. Welche Vorteile bietet dieser Kode?