M. Kreuzer Sommersemester 02 A. Fischer

Übungsaufgaben zur Vorlesung “Lineare Algebra II” für Lehramt

Blatt 11 Abgabe bis 2.7.02 um 10.00 Uhr

Aufgabe 1

Ein binärer Code C ⊆ 𝔽_{2}^{7} sei gegeben durch die Erzeugendenmatrix G := ( \begin{matrix}1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{matrix} )

Dekodieren Sie die folgenden empfangenen Nachrichten:

a) (1101011)

b) (0110111)

c) (0111000)

Aufgabe 2

Bestimmen Sie die Parameter des Codes von Aufgabe 1.

Aufgabe 3 Sei C ⊆ 𝔽_{2}^{2n+1} ein binärer Code der Dimension n mit C ⊆ C^{⊥}. Beschreiben Sie die Menge

C^{⊥} \ C.

Tipp: Zeigen Sie zuerst < c, (1, 1, ..., 1) >= 0 für alle c ∈ C.

Aufgabe 4

Sei C ⊆ 𝔽_{p}^{n} ein k-dimensionaler linearer Code, dessen Erzeugendenmatrix G keine Spalte enthalte, die aus lauter Nullen besteht. Beweisen Sie, dass ∑_{c∈C} δ(c, 0) = n(p − 1)p^{k−1} gilt.

Tipp: Zeigen Sie, dass genau p^{k−1} Codewörter an der i-ten Stelle eine Null haben.

**Aufgabe 5**: Majoritäts-Logik-Codierung

Sei C ein binärer [n, k, d]-Code. Vektoren v_{1}, ..., v_{r} ∈ C^{⊥} heißen orthogonal bzgl. Position i, wenn sie an der i-ten Position eine 1 haben und wenn an den anderen Positionen stets mindestens ein Vektor keine Null hat.

a) Seien v_{1}, ..., v_{r} ∈ C^{⊥} orthogonal bzgl. Position i. Ein empfangenes Wort w = (w_{1}, ..., w_{n}) enthalte t ≤ \frac{r}{2} Fehler. Zeigen Sie < w, v_{j} >≠ 0 für ≤ t Indizes j, falls w_{i} korrekt, und für ≥ r − t + 1 Indizes j, falls w_{i} nicht korrekt ist.

b) Folgern Sie einen Algorithmus, der entscheidet, ob w_{i} korrekt ist oder nicht. Wie kann man w_{i} ggf. korrigieren?

c) Finden Sie zu dem Code C mit Erzeugermatrix M := ( \begin{matrix}0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix} ) drei

Vektoren v_{1}, v_{2}, v_{3} ∈ C^{⊥}, die bzgl. Position 1 orthogonal sind.

d) Schreiben Sie eine Maple-Funktion MLDecode(v), die im Fall c) die Majoritäts-Logik-Dekodierung der ersten Position durchführt.