G. Nebe, M. Kirschmer

Gitter und Codes, WS 08/09

Lösung 5

Aufgabe 1.

(a) Sei α eine Nullstelle von f(X) (in einem genügend großen Körper, z.B. 𝔽_{8}). Da f(X) irreduzibel ist, hat α Ordnung 7. Damit sind auch α^{2} und α^{4} Nullstellen von f(X). Damit haben wir alle 3 Nullstellen von f(X) bestimmt. Insbesondere gibt es nur zwei aufeinanderfolgende Nullstellen. Daher ist der designierte Minimalabstand 3.

(b) Aus (a) folgt d(C) ≥ 3. Weiter ist (1, 1, 0, 1, 0, 0, 0) ∈ C und hat Gewicht 3. Daher ist d(C) ≤ 3. Zusammen folgt, daß d(C) = 3 gerade der designierte Minimalabstand ist.

(c) Der Minimalabstand ist d(C) = 3, die Länge ist N = 7. Die Hammingschranke ergibt sich für diese Parameter zu 7 − log_{2}(V_{2}(7, 1)) = 7 − log_{2}(\binom{7}{0} + \binom{7}{1}) = 7 − 3 = 4. Die Dimension von C ist ebenfalls gleich 4. Die Hammingschranke, die eine obere Schranke für diese Dimension darstellt, wird also angenommen.

Aufgabe 2. Sei f(X) das Erzeugerpolynom eines solchen Codes und α ≠ 1 eine Nullstelle von f(X). Insbesondere hat α Ordnung 11. Damit sind auch die folgenden Potenzen

α, α^{3}, α^{9}, α^{27} = α^{5}, α^{15} = α^{4}, α^{12} = α

Nullstellen von f(X). Der Grad von f(X) ist 11 − 6 = 5, also haben wir bereits alle Nullstellen von f(X) bestimmt und gezeigt, daß f(X) irreduzibel ist (ohne f(X) zu kennen!). Es gibt insbesondere 3 aufeinanderfolgende Nullstellen. Damit ist der designierte Minimalabstand 4.

Aufgabe 3.

(a) Das zu codierende Wort x := (0, 1, 0, 0, 0, ω, 0, 0) entspricht dem repräsentierenden Polynom X^{6} + ωX^{2} (repräsentierend modulo X^{15} − 1). Es ist also (X^{6} + ωX^{2}) · X^{deg g} mit Rest durch g(X) zu teilen.

Wir erhalten X^{13} + ωX^{9} = (X^{7} + X^{6} + ω^{2}X^{4} + X^{2} + ωX + ω) · ∗ + (X^{5} + ω^{2}X^{3} + ω^{2}X + 1), wobei uns ∗ nicht interessiert.

Der Rest ist also X^{5}+ω^{2}X^{3}+ω^{2}X+1. Dieser entspricht den Kontrollsymbolen (0, 1, 0, ω^{2}, 0, ω^{2}, 1).

Daher wird x zu (0, 1, 0, 0, 0, ω, 0, 0, 0, 1, 0, ω^{2}, 0, ω^{2}, 1) codiert.

(b) Durch Probieren faktorisiert man g(X) in die irreduziblen Faktoren

g(X) = (X + ω)(X^{2} + X + ω)(X^{2} + X + ω^{2})(X^{2} + ω^{2}X + 1) .

Sei nun α eine primitive 15. Einheitswurzel. Ohne Einschränkung hat α das Minimalpolynom X^{4} + X + 1. Weiter ist α^{5} ∈ {ω, ω^{2}}. Indem man eventuell α durch α^{8} ersetzt (dies ändert das Minimalpolynom nicht) dürfen wir α^{5} = ω voraussetzen. Mit dieser Identifikation erhalten wir die Nullstellen der einzelnen Faktoren. Es ergibt sich: (Beachte mit x ist stets auch x^{4} eine Nullstelle von g(X).)

f_{1}(X) := X + w hat die Nullstelle ω = α^{5}. f_{2}(X) := X^{2} + X + ω = X^{2} + X + α^{5} hat die Nullstelle α und damit auch α^{4}. f_{3}(X) := X^{2} + X + ω^{2} = Frob(f_{2}(X)) daher die Nullstellen α^{2} und α^{8}. f_{4}(X) := X^{2} + ω^{2}X + 1 hat die Nullstellen α^{3} und α^{12}.

Also sind α, α^{2}, α^{3}, α^{4}, α^{5} fünf aufeinanderfolgende Nullstellen, welche zu den verschiedenen Polynomen f_{1}, …, f_{4} gehören. Damit ist der designierte Minimalabstand 6. (Es ist sogar d(C) ≥ 6 und das Codewort aus Teil (a) zeigt d(C) = 6.)

Es können maximal ⌊\frac{6−1}{2}⌋ = 2 Fehler korrigiert werden.

(c) Sei t = 2; vgl. (b). Das empfangene Wort entspricht dem Polynom

r(X) := X^{13} + ω^{2}X^{11} + ωX^{9} + ωX^{5} + ω^{2}X^{3} + ω^{2}X + 1 ∈ 𝔽_{4}[X] .

Wir müssen Polynome ω(Z) = ∑_{i=0}^{t} ω_{i}Z^{i} und σ(Z) = ∑_{i=0}^{t} σ_{i}Z^{i} in 𝔽_{16}[Z] so bestimmen, daß

σ_{0} = 1
ω_{0} = 0
ω(Z) ≡ σ(Z) · (∑_{i=1}^{2t} r(α^{i})Z^{i}) mod Z^{2t+1}.

(Vorsicht! Das Polynom ω(X) ist nicht zu verwechseln mit dem Element ω ∈ 𝔽_{4}.)

Zum Auswerten von r(X) schreiben wir wieder r(X) = X^{13} +α^{10}X^{11} +α^{5}X^{9} +α^{5}X^{5} +α^{10}X^{3} + α^{10}X + 1. Wir erhalten

r(α) = α^{13}
r(α^{2}) = α
r(α^{3}) = α^{9}
r(α^{4}) = r(α)^{4} = α^{7} .

Aus

ω_{2}Z^{2} + ω_{1}Z ≡ (σ_{2}Z^{2} + σ_{1}Z + 1)(r(α^{4})Z^{4} + r(α^{3})Z^{3} + r(α^{2})Z^{2} + r(α)Z) mod Z^{5}

folgen per Koeffizientenvergleich die zu erfüllenden Bedingungen

ω_{1} = r(α)  =α^{13}
ω_{2} = σ_{1}r(α) + r(α^{2})  =α^{13}σ_{1} + α
0 = σ_{2}r(α) + σ_{1}r(α^{2}) + r(α^{3})  =α^{13}σ_{2} + ασ_{1} + α^{9}
0 = σ_{2}r(α^{2}) + σ_{1}r(α^{3}) + r(α^{4})  =ασ_{2} + α^{9}σ_{1} + α^{7}

Die letzten beiden Bedingungen bilden ein lineares Gleichungssystem in den Unbestimmten σ_{1} und σ_{2}. Dieses besitzt die eindeutige Lösung (σ_{1}, σ_{2}) = (α^{3}, α). Einsetzen in die ersten beiden Gleichungen liefert (ω_{1}, ω_{2}) = (α^{13}, 0).

Damit ist σ(Z) = αZ^{2} + α^{3}Z + 1 und ω(Z) = α^{13}Z. Die Nullstellen von σ(Z) sind α^{4} und α^{10} wie man leicht ausprobiert. Es sind also der 4. und 10. Koeffizient des empfangenen Wortes zu korrigieren:

Es ist \frac{−ω(α^{4})α^{−4}}{σ′(α^{4})} = α^{10} = \frac{−ω(α^{10})α^{−10}}{σ′(α^{10})} . Das (wahrscheinlich) gesendete Codewort ist demnach das Wort, welches r(X) − (ω^{2}X^{15−4} + ω^{2}X^{15−10}) = X^{13} + ωX^{9} + X^{5} + ω^{2}X^{3} + ω^{2}X + 1 entspricht. Dieses ist (0, 1, 0, 0, 0, ω, 0, 0, 0, 1, 0, ω^{2}, 0, ω^{2}, 1) und liegt nach Teil (a) im Code.

Aufgabe 4.

(a) Sortieren wor die Codewörter von C nach der Anzahl der auftretenden 0 bzw. 1-Einträge, so

ergibt sich:

Codewörter  zugehöriges Monom
(0, 0, 0, 0, 0)  X_{0}^{5}
(1, 0, −1, 1, 0)  X_{0}^{2}X_{1}^{2}X_{−1}^{1}
(−1, 0, 1, −1, 0)  X_{0}^{2}X_{1}X_{−1}^{2}
(0, −1, 1, 1, 1), (1, 1, 1, 0, −1) X_{0}X_{1}^{3}X_{−1}
(−1, 1, 0, 1, −1), (1, −1, 0, −1, 1) X_{0}X_{1}^{2}X_{−1}^{2}
(0, 1, −1, −1, −1), (−1, −1, −1, 0, 1) X_{0}X_{1}X_{−1}^{3}

Also ist

p_{C}(X_{0}, X_{1}, X_{−1}) = X_{0}^{5} + X_{0}^{2}X_{1}^{2}X_{−1}^{1} + X_{0}^{2}X_{1}X_{−1}^{2} + 2X_{0}X_{1}^{3}X_{−1} + 2X_{0}X_{1}^{2}X_{−1}^{2} + 2X_{0}X_{1}X_{−1}^{3} .

Ist nun ζ_{3} = \frac{−1+\sqrt{−3}}{2} eine primitive dritte Einheitswurzel, so erhalten wir mit der MacWilliams-Identität (und einem Computeralgebrasystem):

p_{C^{⊥}}(X_{0}, X_{1}, X_{−1}) = \frac{1}{|C|}p_{C}(X_{0} + X_{1} + X_{−1}, X_{0} + ζ_{3}X_{1} + ζ_{3}^{2}X_{−1}, X_{0} + ζ_{3}^{2}X_{1} + ζ_{3}X_{−1})

= X_{0}^{5} + X_{0}^{3}X_{1}^{2} + X_{0}^{3}X_{−1}^{2} + 2X_{0}^{2}X_{1}^{3} + 5X_{0}^{2}X_{1}^{2}X_{−1} + 5X_{0}^{2}X_{1}X_{−1}^{2} + 2X_{0}^{2}X_{−1}^{3}

+ 2X_{0}X_{1}^{3}X_{−1} + 2X_{0}X_{1}^{2}X_{−1}^{2} + 2X_{0}X_{1}X_{−1}^{3} + X_{1}^{4}X_{−1} + X_{1}^{3}X_{−1}^{2} + X_{1}^{2}X_{−1}^{3} + X_{1}X_{−1}^{4}

(b) Aus obiger Tabelle oder von p_{C} liest man h_{C}(X, Y) = X^{5} + 2X^{2}Y^{3} + 6XY^{4} ab. Mit der MacWilliams-Identität oder aus p_{C^{⊥}} folgt h_{C^{⊥}}(X, Y) = X^{5} +2X^{3}Y^{2} +14X^{2}Y^{3} +6XY^{4} +4Y^{5}.