Prof. Dr. M. Kreuzer Abgabetermin: Montag, 7. Juli 2003, 12:00 Uhr

Lineare Algebra II - Übungsblatt 9

Aufgabe 1: Ein binärer Code C ⊆ 𝔽_{2}^{6} sei gegeben durch die Generatormatrix

( \begin{matrix}1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 \end{matrix} )

Erstellen Sie das sogenannte Standard Array - das ist eine Tabelle, in der aller Wörter des 𝔽_{2}^{6} aufgelistet sind - nach folgenden Instruktionen:

1. In die erste Zeile schreiben Sie die Codewörter, wobei (0, 0, 0, 0, 0, 0) ganz links stehen soll.

2. Beginnen Sie die nächste Zeile mit einem Wort, das unter allen noch nicht aufgelisteten Wörtern ein minimales Hamming-Gewicht aufweist. (erster Eintrag der zweite Zeile z.B. (1, 0, 0, 0, 0, 0))

3. Vervollständigen Sie die Zeile: Der Eintrag in der j-ten Spalte ist die Summe des ersten Wortes derselben Zeile und des ersten (Code-)Wortes derselben Spalte.

4. Wiederholen Sie die Schritte 2 und 3 bis alle Wörter in der Tabelle aufgelistet sind. Bei richtiger Durchführung liefert dieses Verfahren eine (rechteckige) Tabelle, in der jedes

Wort genau einmal aufgelistet ist. Warum gibt es keine doppelten Einträge? Warum ist die Tabelle rechteckig? Welche linear algebraische Struktur besitzt die Menge der Wörter der ersten Zeile? Welche algebraische Struktur besitzt die Menge der Wörter einer anderen Zeile? Wie kann man mit dieser Tabelle decodieren, wenn man annimmt, dass weniger Bitfehler wahrscheinlicher sind als mehr Bitfehler?

Decodieren Sie die empfangenen Nachrichten

a) (1,1,0,1,0,1)

b) (0,1,1,0,1,1)

c) (0,1,1,1,0,0)

Aufgabe 2: Sei C ⊆ 𝔽_{3}^{3} ein linearer Code mit Generatormatrix ( \begin{matrix}1 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} ).

a) Beschreiben Sie die Geometrie von 𝔽_{3}^{3}: Wieviele Punkte gibt es? Wieviele Punkte liegen auf einer Geraden? Wieviele Geraden durch den Nullpunkt gibt es?

b) Stellen Sie C graphisch dar.

c) Beschreiben Sie den dualen Code von C sowohl algebraisch als auch geometrisch.

d) Beweisen oder widerlegen Sie: Es gibt einen nichttrivialen Ringhomomorphismus 𝔽_{3}^{3} → ℝ^{3}.

Aufgabe 3:

a) Sei V ein endlich-dimensionaler ℝ-Vektorraum mit Basis V = (v_{1}, …, v_{n}) und sei V^{∗} = (v_{1}^{∗}, …, v_{n}^{∗}) die duale Basis von V^{∗}. Sei ϕ_{V}: V → V^{∗} die lineare Abbildung, die durch v_{i} ↦ v_{i}^{∗}, 1 ≤ i ≤ n definiert ist. Zeigen Sie, dass ϕ_{V} von der Basiswahl abhängt. Mit anderen Worten, es gibt eine zweite Basis W mit ϕ_{V} ≠ ϕ_{W}.

b) Sei nun zusätzlich auf V ein Skalarprodukt ⟨ , ⟩ gegeben. Zeigen Sie, dass ϕ_{V} = ϕ_{W} für alle Orthonormalbasen V und W gilt.

c) Teil a) besagt, dass i.a. ϕ_{V} erst definiert werden kann, nachdem eine Basis V gewählt worden ist. Dahingegen besagt Teil b), dass im Falle eines euklidischen Vektorraums die Abbildung ϕ_{V} unabhängig von der Wahl einer Orthonormalbasis V ist. Definieren Sie ϕ = ϕ_{V} ohne eine Orthonormalbasis zu erwähnen.

Aufgabe 4: Sei K = 𝔽_{q} der Körper mit q Elementen.

a) Aus wie vielen Vektoren besteht der Vektorraum K^{n}?

b) Wie viele verschiedene Linearkombinationen kann man aus i linear unabhängigen Vektoren in K^{n} bilden?

c) Wie viele invertierbare Matrizen gibt es in Mat_{K}(n)?

Aufgabe 5: (*) (Auch für MAPLE-Anfänger geeignet!!! Programm auf der LinA-II-Homepage.) Verwenden Sie das MAPLE-Programm BSC, dass den binären symmetrischen Kanal simuliert. Ein binärer symmetrischer Kanal überträgt ein Bit nach dem anderen (Eingabe: 0 oder 1, Ausgabe: 0 oder 1). Die Wahrscheinlichkeit, dass ein Bit fehlerhaft übertragen wird (0 ↦ 1 bzw. 1 ↦ 0) sei p.

a) Studieren Sie die Prozedur kanaltest(n,p). Testen Sie MAPLEs Zufallszahlengenerator, indem Sie 10.000 Binärsymbole durch den Kanal mit Bitfehlerwahrscheinlichkeit p = 0, 1, p = 0, 15, p = 0, 2,…, p = 0, 45 senden. Wie viele der empfangenen Bits sind fehlerhaft? (Tipp: Entfernen Sie die ersten beiden print-Befehle bevor Sie größere Bit-Anzahlen verwenden.)

b) Senden Sie 10.000 Datenbits durch den Kanal mit Hilfe des Wiederholungscodes 1 ↦ 111, 0 ↦ 000; d.h. es werden 30.000 Codebits durch den Kanal gesendet. Decodieren Sie die empfangenen Dreierblöcke mit einer Mehrheitsentscheidung (z.B. aaa ↦ a,aba ↦ a, abb ↦ b). Welcher Anteil der decodierten Datenbits ist fehlerhaft? Verwenden Sie die Bitfehlerwahrscheinlichkeiten p = 0, 1, …, p = 0, 45. (Tipp: Prozedur kanal3codiert)

c) Wie Aufgabenteil b), aber mit dem Wiederholungscode 1 ↦ 11111. Stellen Sie die Ergebnisse in einem (!) Diagramm graphisch dar.