IKT:Klausur 2012-23-07

Klausur im Wortlaut Link

Beachten Sie: Der Lösungsweg der einzelnen Aufgaben muss klar erkennbar sein! Rechnen Sie mit einer Genauigkeit von drei Stellen nach dem Komma!

Aufgabe 1

Die Zeichen der Quelle X haben die Auftrittswahrscheinlichkeit

$ p(x_i) = (0.1, 0.25, 0.14, 0.1, 0.04, 0.14, 0.03, 0.02, 0.18) $

Geben Sie eine Quellenkodierung an, die eine Koderedundanz $ R_K < 0.1 bit/QZ $ besitzt. Wieviel Prozent an Speicherplatz spart man mit der gewählten Quellenkodierung gegenüber einer gleichmäßigen Kodierung ein? Wo ist die Grenze möglicher Einsparung?

Aufgabe 2

Für das Erreichen einer gesicherten Übertragung ist ein HAMMING-Gruppenkode anzuwenden. Das Quellenalphabet umfasst 50 Zeichen.

a) Berechnen Sie die Parameter $ (n, l, d_{min}) $ des Kodes. Wieviel Kanalkodewörter sind im Kodealphabet A maximal definiert?

b) Bilden Sie für das Quellenkodewort $ a* $, in Polynomschreibweise $ a^*(x) = x^3 + 1 $, das Kanalkodewort.

c) Dekodieren Sie, wenn möglich, das Empfangswort b = a XOR e. Das Fehlermuster e, in Polynomschreibweise $ e(x) = x^8 + x^7 + x^6 + x^5 $, ist bekannt. Erklären Sie das Ergebnis!

Aufgabe 3

Eine Quelle hat einen Zeichenvorrat von 50 QZ. Für die Informationsübertragung steht ein gestörter Binärkanal $ p(x_0) = p(x_1) $ mit den Fehlerwahrscheinlichkeiten $ p(y_1|x_0) = 0.1 $ und $ p(y_0|x_1) = 0.05 $ sowie eine Bandbreite von $ B = 2kHz $ zur Verfügung.

a) Bestimmen Sie die maximal mögliche Quellensymbolfrequenz $ f_Q $ bei gesicherter Übertragung!

b) Wie groß ist bei Umsetzung gesicherter Übertragung die notwendig aufzubringende Redundanz $ Δ_l $?

c) Wie beeinflusst der zur Anwendung kommende HAMMING-Kode aus Aufgabe 2 die Quellensymbolfrequenz $ f_Q $? Vergleichen Sie mit a) und b)!

Aufgabe 4

Beantworten Sie in knapper Form die folgenden Fragen!(auf dem Aufgabenblatt lösen!)

a) Was charakterisiert eine Markow-Quelle?

b) Ist $ A^* = {10, 0, 111, 100, 101} $ dekodierbar?

c)Was bedeutet *quasi fehlerfreie Übertragung*?

d) Nennen Sie die Stufen der Quantisierung!

e) Was besagt die Eigenschaft *Abgeschlossenheit*?

f) Paritätskode für $ l = 5 $? $ (n, l, d_{min}) $ bestimmen

Aufgabe 5

a) Eine Quelle hat einen Zeichenvorrat von 50 QZ. Die Übertragung erfolgt über einen gestörten Kanal. Fehlermuster mit einem Gewicht $ w(e) <= 5 $ sollen deshalb sicher erkennbar sein.

Verwenden Sie einen BCH-Kode! Leiten Sie das Generatorpolynom $ g(x) $ auf der Basis von $ µ = 0 $ und einem geeignet gewählten Grad eines primitiven Modularpolynoms $ M(x) $ ab. Notieren Sie $ (n, l, d_min) $!

b) Arbeiten Sie mit dem verkürzten (6, 3, 3)BCH-Kode, $ M(x) = x^3 + x^2 + 1 $ ist primitiv! Der Kode ist systematisch aufgestellt. Bilden Sie für ein gewähltes a* (nicht Nullfolge!) das entsprechende Kanalkodewort (in Binär- und Polynomschreibweise). Zeigen Sie an einem Beispiel, dass der Kode nicht zyklisch ist!

Lösung (ohne Gewähr)

Aufgabe 1: mit Shannon-Fano oder Huffman. Bei Shannon-Fano kommt man auf $ l_m = 2.89, H_m = 2.85 -> R_k = 0.04 $

Aufgabe 2: a) (10,6,3) , k mit Hamming Schranke berechnen b) a = (0001001100), zuerst Bestimmungsgleichungen für die Kontrollstellen k aus der Kontrollmatrix erstellen. c) b = (0110101100)

Aufgabe 3: a) $ f_q = (2*B * H_T) / (l * H_k) = (2 * 2000 * 0.62) / (6 * 1) = 413,33 $, b) $ n = l + Δl -> Δl = 3,68 $ c) $ f_q = v_s / n = 400, Δl = k = 4 $

Aufgabe 4: kann mal wer anderes hier einfügen - habe keinen bock mehr darauf

Aufgabe 5: a) Gegeben ist: l = 6 (ld 50) und f_e = 5. Also ist d_entwurf = 6. Somit ergibt sich für g(x) = kgv(m_0, m_1, m_2, m_3, m_4) Nun muss man die Zyklen, also die Nullstellen von den Modularpolynomen aufstellen. für m_0 wäre das α⁰. Für m_1 wird das etwas schwieriger, da man hier nicht genau weiß bis wohin man den Zyklus aufstellen muss. Da man weiß das l = 6 kann man schon mal vermuten das n > 6 ist. Also versucht man das ganze einfach mal mit n=7. Da kommt als Zyklus für m_1 1,2 und 4 heraus (jeweils ohne α). m_2 und m_4 entfällt, m_3 hat den Zyklus 3,6,5. Somit hätte man als Kodeparameter (13,6,8). Nun fällt auf das 13 > 7, also war n = 7 falsch. Also probiert man das ganze nochmal für n=15 und kommt dann auf (15,6,6).

b) a* = 101 a = 101110 mit Divisionsverfahren erstellt. Wenn der Code zyklisch wäre müsste man nun einfach bei dem Codewort 101110 alle Zeichen eine Stelle verschieben und somit wieder ein Codewort erhalten, sprich 011101 müsste auch wieder Codewort sein. Da der Code systematisch ist wäre das Quellenwort dazu 011. Wenn man aber nun mit 011 das Divisionsverfahren anwendet kommt man auf das Codewort 011010 und somit nicht auf das ursprüngliche Codewort, also ist der Code nicht zyklisch.