IKT:Scheinklausur 2005-08-01
(Schein-)Klausur IKT 01.08.2005
Aufgabe 1 (12 Punkte):
Für eine diskrete Quelle ist das Auftrittsverhalten der Quellenzeichen mit $ p(x_{i+1}) = 1/2 * p(x_i) $ $ (i = 1,2,...,7) $ und $ p(x_8) = p(x_7) $ bekannt. Die Zeichen werden mit einer Frequenz von $ f_Q $ = 1000 QZ/s übertragen.
a) Warum muss $ p(x_1) $ = 1/2 sein?
b) Welche Kanalkapazität muss ein angeschlossener Binärkanal haben? Nutzen Sie eine Optimalkodierung!
c) Reicht die gewählte Kodierung zum Erhalt einer redundanzfreien Kodierung aus? Begründen Sie Ihre Antwort!
d) Um wieviel Prozent ist die benötigte Kanalkapazität höher, wenn alle Zeichen gleichwahrscheinlich auftreten.
Aufgabe 2 (11 Punkte):
Ein Spannungsmesser liefert Messwerte im Abstand von 0,1 ms in einem Amplitudenbereich von 0 V bis 1 V in Schritten von 1 mV. Alle Messwerte haben die gleiche Wahrscheinlichkeit. Die Übertragung erfolgt über einen Binärkanal. Zur Sicherung einer "fehlerfreien" Übertragung ist ein einfehlerkorrigierender HAMMING-Kode zu verwenden.
a) Entwerfen Sie die Kontrollmatrix und leiten sie aus dieser die notwendigen Bestimmungsgleichungen für die Berechnung der redundanten Stellen ab. Unter welcher Bedingung wäre der Kode dichtgepackt? Bilden Sie für ein gewähltes Quellenkodewort a* das Kanalkodewort a!
b) Wie groß ist die erforderliche Schrittgeschwindigkeit $ v_s $?
Aufgabe 3 (14 Punkte):
Für die Informationsübertragung steht ein einseitig gestörter Binärkanal mit der Schrittfehlerwahrscheinlichkeit $ p_s = 5 * 10^{-2} $ und der Übertragungsgeschwindigkeit $ v_\ddot u $ = 2400 bit/s zur Verfügung. Das Alphabet der Quelle besteht aus 200 gleichverteilt auftretenden Quellenzeichen.
a) Bestimmen Sie die maximal möglichen Quellensymbolfrequenzen $ f_Q $ bei gesicherter und ungesicherter Übertragung! Am Kanaleingang sei $ p(x_0) = p(x_1) $ angenommen.
b) Wie sehen für gesicherte und ungesicherte Übertragung die Abschätzung der Kodeparameter (n,l,k) aus?
Aufgabe 4 (8 Punkte):
Beantworten Sie in knapper Form folgende Fragen!
a) Was ist ein algebraischer Kode?
b) Was ist ein systematischer Kode?
c) Was ist ein primitives Polynom?
d) Ist redundanzfreie Quellenkodierung möglich?
Aufgabe 5 (15 Punkte):
Ein zyklischer Kode ist mit dem Generatorpolynom $ g(x) = x^8 + x^7 + x^6 + x^4 + 1 $ beschrieben. Das zugehörige Modularpolynom ist primitiv und lautet $ M(x) = x^4 + x + 1 $.
a) Es sind die Kodeparameter n, l und k sowie der Minimalabstand $ d_{min} $ zu bestimmen.
b) Geben Sie alle erkennbaren Fehler an! Welche von diesen Fehlern können korrekt rekonstruiert werden?
c) Berechnen Sie für das Quellenkodepolynom $ a*(x) = x^5 + x^2 + x $ das Kodepolynom a(x) und geben Sie dafür auch die Koeffizientenfolge a an.
d) Überprüfen Sie, ob das Fehlermuster e = (000011101000100) bei der Auswertung von b erkennbar ist (b = a xor e) (nimm a aus Aufgabenteil c))! Werten Sie das Ergebnis!
Lösungen
Aufgabe 1:
a)
| $ p(x_1) $ = 1/2 |
| $ p(x_2) $ = 1/2 * $ p(x_1) $ = 1/4 |
| $ p(x_3) $ = 1/2 * $ p(x_2) $ = 1/8 |
| $ p(x_4) $ = 1/2 * $ p(x_3) $ = 1/16 |
| $ p(x_5) $ = 1/2 * $ p(x_4) $ = 1/32 |
| $ p(x_6) $ = 1/2 * $ p(x_5) $ = 1/64 |
| $ p(x_7) $ = 1/2 * $ p(x_6) $ = 1/128 |
| $ p(x_8) $ = $ p(x_7) $ = 1/128 |
Da die Summe über alle Auftrittswahrscheinlichkeiten $ p(x_i) $ (i = 1,...,8) 1 sein muss, kann $ p(x_1) $ nur 1/2 sein (ansonsten würde sich stets ein Wert ungleich 1 ergeben).
b)
$ I_{KQ} $ <= C
$ f_Q * l_m * H_k $ <= C
$ l_m $ soll aufgrund einer Optimalkodierung bestimmt werden.
Shannon-Fano (Huffman wäre ebenfalls korrekt):
| $ p(x_i) $ | $ l_i $ | |||||||||
| 1/2 | 0 | 1 | ||||||||
| - | - | - | - | - | - | - | ||||
| 1/4 | 1 | 0 | 2 | |||||||
| - | - | - | - | - | - | |||||
| 1/8 | 1 | 1 | 0 | 3 | ||||||
| - | - | - | - | - | ||||||
| 1/16 | 1 | 1 | 1 | 0 | 4 | |||||
| - | - | - | - | |||||||
| 1/32 | 1 | 1 | 1 | 1 | 0 | 5 | ||||
| - | - | - | ||||||||
| 1/64 | 1 | 1 | 1 | 1 | 1 | 0 | 6 | |||
| - | - | |||||||||
| 1/128 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 7 | ||
| - | ||||||||||
| 1/128 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 7 |
$ l_m = \sum_{i=1}^8 {p(x_i) * l_i} $
$ l_m $ = 1/2 * 1 + 1/4 * 2 + ... + 1/128 * 7 = 1,984 KZ/QZ
C >= 1000 QZ/s * 1 bit/KZ * 1,984 KZ/QZ
C >= 1984 bit/s
Die Kanalkapazität muss mindestens 1984 bit/s betragen.
c)
$ H_Q = \sum_{i=1}^8 {p(x_i) * \operatorname{ld}\, \frac{1}{p(x_i)}} $
$ H_Q $ = 1/2 * ld 2 + 1/4 * ld 4 + ... + 1/128 * ld 128 = 1,984 bit/QZ
$ R_k $ = $ l_m * H_k - H_Q $
$ R_k $ = 1,984 KZ/QZ * 1 bit/KZ - 1,984 bit/QZ = 0 bit/QZ
Die gewählte Kodierung ist redundanzfrei, reicht also aus.
d)
Eine Quelle mit 8 gleichwahrscheinlichen Ereignissen lässt sich trivialerweise redundanzfrei kodieren.
$ l_m $ = 3 KZ/QZ
$ C_2 $ >= 1000 QZ/s * 3 KZ/QZ * 1 bit/KZ
$ C_2 $ >= 3000 bit/s
$ C_2/C $ = 3000/1984 = 1,512
Die benötigte Kanalkapazität steigt also um 51,2%.
Aufgabe 2:
(a)
N = 1001 --> l = $ \lceil ld N \rceil $ = 10
$ d_{min} $ = 3 --> $ f_k $ = 1
Berechnung von k über die Hammingschranke: l+k über i muss kleiner gleich $ 2^k $ sein.
k >= 4
MIt den Werten kann man nun die Kontrollmatrix aufstellen: n = 14, k = 4
$ H_{4x14} $ =
| $ l_{10} $ | $ l_{9} $ | $ l_{8} $ | $ l_{7} $ | $ l_{6} $ | $ l_{5} $ | $ k_{4} $ | $ l_{4} $ | $ l_{3} $ | $ l_{2} $ | $ k_{3} $ | $ l_{1} $ | $ k_{2} $ | $ k_{1} $ |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
$ k_1 = l_1 + l_2 + l_4 + l_5 + l_7 + l_9 $
$ k_2 = l_1 + l_3 + l_4 + l_6 + l_7 + l_{10} $
$ k_3 = l_2 + l_3 + l_4 + l_8 + l_9 + l_{10} $
$ k_4 = l_5 + l_6 + l_7 + l_8 + l_9 + l_{10} $
Der Kode wäre dichtgepackt, wenn die Gleichheit bei der Hamming-Schranke gelten würde.
$ a^* $ = (1 0 1 1 1 0 1 0 0 1)
a = (1 0 1 1 1 0 0 1 0 1 0 1 1 1), $ k_1 $ = 1, $ k_2 $ = 1, $ k_3 $ = 1, $ k_4 $ = 0
(b)
$ v_s = \frac{v_\ddot u}{H_K} $
Im Binärkanal gilt deswegen $ v_s = v_\ddot u $
$ v_s = v_\ddot u = f_Q*n $
