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

Lineare Algebra II - Übungsblatt 10

Aufgabe 1: Sei K ein Körper und V := K[x]_{≤n−1} der Vektorraum aller Polynome vom Grad kleiner gleich n − 1 (inkl. Nullpolynom). Für i, j ∈ {0, 1, …, n − 1} definiert

x^{i} · x^{j} := \{ \begin{matrix}x^{i+j} & falls 0 ≤ i + j < n \\ x^{i+j−n} & falls i + j ≥ n \end{matrix}

eine Multiplikation, die V zu einem Ring macht. Zeigen Sie, dass V ein Hauptidealring ist und dass jedes vom Nullideal verschiedene Ideal von einem Polynom erzeugt wird, das x^{n} − 1 teilt.

Aufgabe 2: Sei C ⊆ 𝔽_{q}^{n} ein zyklischer [n, k, d]-Code.

a) Zeigen Sie, dass C eine Parity-Check-Matrix der Form

( \begin{matrix}0 & … & & 0 & h_{k} & … & h_{1} & h_{0} \\ 0 & … & 0 & h_{k} & … & h_{1} & h_{0} & 0 \\ ⋮ & ... & & & & & ... & ⋮ \\ 0 & h_{k} & … & h_{1} & h_{0} & 0 & … & 0 \\ h_{k} & … & h_{1} & h_{0} & 0 & & … & 0 \end{matrix} )

mit h_{0}, h_{1}, …, h_{k} ∈ 𝔽_{q} besitzt.

b) Folgern Sie, dass C^{⊥} ebenfalls ein zyklischer Code ist.

Aufgabe 3: Zeigen Sie, dass die folgenden Aussagen für einen [n, k, d]-Code C äquivalent sind.

a) C ist ein MDS-Code.

b) Jeweils n − k Spalten der Parity-Check-Matrix sind linear unabhängig.

c) Jeweils k Spalten der Generator-Matrix sind linear unabhängig.

d) Jede k × k Unterdeterminante der Generator-Matrix ist verschieden von null.

Aufgabe 4: Sei C ⊂ (𝔽_{q})^{8} ein ein-Fehler-korrigierender Code. Bei der Kodierung eines fortlaufenden Datenstroms entstehen die Codewörter

⋮
(a_{1}, a_{2}, …, a_{8})
(b_{1}, b_{2}, …, b_{8})
⋮
(h_{1}, h_{2}, …, h_{8})
⋮

welche komponentenweise in der folgenden Reihenfolge durch einen störanfälligen Kanal übertragen werden:

…, a_{1}, b_{1}, …, h_{1}, a_{2}, b_{2}, …, h_{2}, …, a_{8}, b_{8}, …, h_{8}, …

Man spricht vom Interleaving der Codewörter. Wie viele aufeinanderfolgende Fehler (bei der Übertragung einer Komponente) können korrigiert werden?

[Aufgabe 5 auf Seite 2] Aufgabe 5: (*) (Einfach! Lösung durch Anwenden der Definitionen und Rechnen modulo 11)

Ein Reed-Solomon-Code über 𝔽_{11} = ℤ_{11}.

a) Bestimmen Sie die kleinste primitive Restklasse ᾱ in 𝔽_{11}, d.h. die kleinste Zahl α ∈ 0, 1, 2, …, 10 mit

{α(mod 11), α^{2}(mod 11), …, α^{10}(mod 11)} = {1, 2, …, 10}.

b) Berechnen Sie das Generatorpolynom des Reed-Solomon-Codes der Länge 10 mit Designabstand δ = 6. Verwenden Sie das primitive Element aus Aufgabenteil a).

c) Bestimmen Sie eine Parity-Check-Matrix H zum Code aus Aufgabenteil b) [Tipp: vgl. Beweis zu 23.38, α = β].

d) Kodieren Sie das Wort (0, 1, 2, 3, 4) [vgl. 23.36] und rechnen Sie nach, dass das erhaltende Codewort den Parity-Check erfüllt.