IKT:Scheinklausur 2004-08-05

Aufgabe 1

1. Einfache Quelle (in der Aufgabe etwas umständlich formuliert) für die man jeweils die Entropie angeben soll.

1.1 $ p(x_i) = (0,75; 0,125; 0,125) $

1.2 $ p(x_i) = (0,75; 0,25) $

1.3 $ p(x_i) = (1) $

Aufgabe 2

2. Gestörter Binärkanal mit: $ p(1|0) = 0,1; p(0|1) = 0,25 $ Am Kanaleingang treten auf: $ p(0) = 0,2 $; $ p(1) = 0,8 $

2.1 Kanalmodell zeichnen

2.2 Entropie am Ausgang und Störentropie/Irrelevanz berechnen

2.3 Die auftretende Transinformation ist zu berechnen

2.4 Berechnung der Entropie am Eingang

Aufgabe 3

3. Eine Quelle mit 5 Zuständen $ p(x_i) = (0,1; 0,4; 0,15; 0,2; 0,15) $ sendet 3200 Zeichen/Sekunde durch einen symmetrisch gestörten Binärkanal mit $ p_s = 0,05 $ und $ B = 5kHz $

3.1 Ein Code ist gesucht, so daß ohne Informationsverlust übertragen werden kann - also $ (I_{KQ} \le C) $ gilt - wobei ein gleichwahrscheinliches Auftreten der Binärzeichen am Kanaleingang für die Berechnung von $ H_T $ angenommen werden darf

3.2 Gefragt ist die Redundanz des Codes aus Teil 1

3.3 Wie ist die minimal mögliche Codewortlänge und wie kann man diese erreichen?

Aufgabe 4

4. Gegeben ist hier ein BCH-Kode mit dem Generatorpolynom $ g(x) = m_0(x) * m_1(x) * m_3(x) * m_5(x) $ und dem Modularpolynom $ M(x) = x^5 + x^2 +1 $ Gesucht sind alle Codeparameter ($ n_{max}; k; l_{max}; |A^*|; d_{min} $)

Aufgabe 5

5. Das Quellenkodewort $ a^* = (10010010011) $ soll so kodiert werden, daß mindestens 3-fach Fehler erkennbar sind.

5.1 Generatorpolynom berechnen (Liste primitiver Polynome war gegeben); dazu dann n, l und k angeben

5.2 Welche weitere Eigenschaft bezüglich der Fehlererkennung hat der Code aus Teil 1

5.3 Welche maximale Länge der Quellenkodewörter, die durch diesen Kode geschützt werden können, ist möglich?

5.4 Das Quellencodewort $ a^* = (110111011010) $ ist mithilfe des Divisionsverfahren und des Codes aus Teil 1 zu kodieren

5.5 Die Folge $ b(x) = x^{14} + x^{13} + x^{11} + x^{10} + x^2 + 1 $ wurde empfangen

5.5.1 Ist für den Fall $ b \in A $ (b ist korrektes Codewort) eine eindeutige Dekodierung (Rückgewinnung des Quellenkodewortes) für den Empfänger möglich? Begründen Sie ihre Antwort!

5.5.2 Überprüfen Sie die Folge auf Übertagungsfehler und erklären Sie das Ergebnis!

---

Lösungen

Aufgabe 1

1.1 $ H_m = 1,06 bit $

1.2 $ H_m = 0,81 bit $

1.3 $ H_m = H_0 = 0 bit $

Aufgabe 2

2.2 $ H(Y) = 0,958 bit $ $ H(Y|X) = 0,7428 bit $

2.3 $ H_T = 0,2152 bit $

2.4 $ H(X) = 0,722 bit $

Aufgabe 3

3.1 $ l_{max} = 2,23 Zeichen $ Das ist nur mit Hilfe der Huffman-Optimalkodierung möglich (mit Shannon-Fano erhalte ich $ l_m = 2,25 Zeichen $)

Der zugehörige Code lautet dann:

0,4  => 1
0,2  => 000
0,15 => 001
0,15 => 010
0,1  => 011

$ l_m = 2,2 Zeichen $

3.2 $ R_k = 0,054 bit $

3.3 $ l_{min} = H = 2,15 Zeichen $ und wird durch Optimalkodierung einer erweiterten Form der Quelle erreicht.

Aufgabe 4

$ n_{max}=31 $
$ k=16 $
$ l_{max}=15 $
$ |A*|=2^{15} $
$ d_{min}=8 $
Anmerkung: $ |A*| $ bezeichnet dabei die Anzahl der möglichen Quellwörter

Aufgabe 5

5.1 Da eine 3-Fehler-Erkennung gefordert wird, braucht der Code mindestens ein $ d_{min} $ von 4. Der einfachste/am schnellsten zu konstruierende Code, der dies leistet ist ein Ambramson-Code: $ g(x) = x^6 + x^5 + x^3 + x^2 + x + 1 $

Die Codeparameter lauten dann: $ n=17; l=11; k=6 $

5.2 Er erkennt Fehlerbündel bis maximal der Länge 6

5.3 $ l_{max}=25 Zeichen $

5.4 $ a = (110111011010011000) $

5.5.1 Nein! Der aufgetretene Fehler könnte genau einem Codewort entsprechen und wäre damit nicht erkennbar. Außerdem ist das verwendete Kodierungsverfahren (Divisions- oder Multiplikationsverfahren) nicht bekannt und eine Dekodierung daher ausgeschlossen.

5.5.2 $ r(x) \ne 0 $ Also ist die empfangene Zeichenfolge kein gültiges Kanalcodewort. Eine Überprüfung der Parität (da ein Abramson-Code verwendet wurde) ergibt eine gerade Parität, daher handelt es sich um einen Fehler, den der verwendete Code nicht korrigieren kann.