Mo Logo [Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
Mathematik-Online-Aufgabensammlung: Zyklischer Code zu

Aufgabe 282: Zyklischer Code

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Ein zyklischer Code $ \mbox{$C_g$}$ der Länge $ \mbox{$N=9$}$ über $ \mbox{$\mathbb{F}_8$}$ werde durch $ \mbox{$g = X^4 + \alpha^4 X^3 + \alpha^3 X^2 + \alpha^2 X + 1$}$ erzeugt, wobei $ \mbox{$\alpha\in\mathbb{F}_8$}$ die Gleichung $ \mbox{$\alpha^3 + \alpha + 1 = 0$}$ erfüllt.

  1. Stelle die Zech-Logarithmentafel für $ \mbox{$\mathbb{F}_8$}$ bzgl. $ \mbox{$\alpha$}$ auf.

  2. Berechne das Prüfpolynom $ \mbox{$h$}$.

  3. Sei $ \mbox{$\beta\in\mathbb{F}_{64}$}$ ein Element, für welches $ \mbox{$\beta^2+\alpha \beta + 1 = 0$}$ gilt. Zeige, daß $ \mbox{$\beta$}$ eine primitive $ \mbox{$9$}$-te Einheitswurzel ist.

  4. Gib $ \mbox{$A,B\in\mathbb{N}$}$ an mit $ \mbox{$B-A\leq 2$}$ und $ \mbox{$A \leq d(C_g) \leq B$}$.

  5. Codiere $ \mbox{$(1, \alpha^3, \alpha^2, \alpha, \alpha^4)$}$.

  6. Decodiere $ \mbox{$(1, \alpha^4, \alpha, 0, \alpha, \alpha^4, 1, 0, \alpha)$}$ unter Verwendung des unvollständigen Decodierens. Gib den Fehlervektor an.

  1. Wir erhalten

    $ \mbox{$X$}$ $ \mbox{$0$}$ $ \mbox{$1$}$ $ \mbox{$\alpha$}$ $ \mbox{$\alpha^2$}$ $ \mbox{$\alpha^3$}$ $ \mbox{$\alpha^4$}$ $ \mbox{$\alpha^5$}$ $ \mbox{$\alpha^6$}$
    $ \mbox{$X+1$}$ $ \mbox{$1$}$ $ \mbox{$0$}$ $ \mbox{$\alpha^3$}$ $ \mbox{$\alpha^6$}$ $ \mbox{$\alpha$}$ $ \mbox{$\alpha^5$}$ $ \mbox{$\alpha^4$}$ $ \mbox{$\alpha^2$}$

  2. Polynomdivision ergibt $ \mbox{$h = (X^9-1) : g = X^5 + \alpha^4 X^4 + X^3 + X^2 + \alpha^4 X + 1$}$.

  3. Unter Beachtung der Relation für $ \mbox{$\beta$}$ gilt
    $ \mbox{$\displaystyle \begin{array}{rcl} \beta^3 &=& \alpha + \alpha^6 \beta \\ \beta^9 &=& (\alpha + \alpha^6 \beta)^3\\ &=& 1\;. \end{array} $}$
    Wäre $ \mbox{$\beta$}$ in $ \mbox{$\mathbb{F}_8$}$, so wäre $ \mbox{$\beta^9=1$}$ in der multiplikativen Gruppe $ \mbox{$\mathbb{F}_8^\ast$}$, diese ist jedoch zyklisch mit $ \mbox{$7$}$ Elementen, woraus $ \mbox{$\beta = 1$}$ folgte. Damit wäre $ \mbox{$0 = \beta^2 + \alpha\beta+1 =\alpha$}$. Also ist $ \mbox{$\beta\not\in\mathbb{F}_8$}$. Mithin ist $ \mbox{$\{1,\beta\}$}$ linear unabhängig über $ \mbox{$\mathbb{F}_8$}$. Somit ist $ \mbox{$\beta^3\neq 1$}$.

  4. Aus der Erzeugermatrix entnimmt man $ \mbox{$d(C_g) \leq 5$}$. Da $ \mbox{$g(\beta) = g(\beta^2) = 0$}$ ist, wird $ \mbox{$d(C_g) \geq 3$}$. Für diese Berechnung verwende man folgende Tabelle

    $ \mbox{$\displaystyle \begin{array}{rclcr} \beta^0 &=& 1 & & \\ \beta^1 &... ...alpha^3 &+& \alpha^6\beta \\ \beta^8 &=& \alpha &+&\beta\\ \end{array} $}$

  5. Mit $ \mbox{$u = X^4 + \alpha^3 X^5 + \alpha^2 X^6 + \alpha X^7 + \alpha^4 X^8$}$ wird $ \mbox{$u = g f + \alpha^6 X^2 + \alpha^5 X + \alpha^2$}$. Damit wird zu $ \mbox{$(\alpha^2, \alpha^5, \alpha^6, 0, 1, \alpha^3, \alpha^2, \alpha, \alpha^4)$}$ codiert.

  6. Sei $ \mbox{$r = 1 + \alpha^4 X + \alpha X^2 + \alpha X^4 + \alpha^4 X^5 + X^6 + \alpha X^8$}$. Da nur $ \mbox{$d(C_g) \geq 3$}$ bekannt ist, nehmen wir an, daß $ \mbox{$t=1$}$. Für $ \mbox{$\omega = 0 + \omega_1 X$}$ und $ \mbox{$\sigma = 1 + \sigma_1 X$}$ ergibt der Ansatz
    $ \mbox{$\displaystyle \frac{\omega_1X}{1+\sigma_1X} \;=\; r(\beta)X + r(\beta^2) + O(X^3) $}$
    $ \mbox{$\omega = r(\beta)X $}$ und $ \mbox{$\sigma = 1 + \frac{r(\beta^2)}{r(\beta)}X$}$.

    Es ist $ \mbox{$\omega(\beta^{-i}) = 0$}$ genau dann, wenn an $ \mbox{$i$}$-ter Stelle ein Fehler aufgetreten ist.

    Es ist $ \mbox{$\omega(\beta^{-8}) = 0$}$ (und sonst nicht), und damit wird

    $ \mbox{$\displaystyle E_8 = \frac{\omega(\beta^{-8})\beta^8}{r(\beta^2)/r(\beta)} = \alpha. $}$
    Das korrigierte Codewort ist $ \mbox{$(1, \alpha^4, \alpha, 0, \alpha, \alpha^4, 1, 0, 0)$}$, was zu $ \mbox{$(\alpha, \alpha^4, 1, 0, 0)$}$ decodiert wird. Der Fehlervektor ist $ \mbox{$(0,0,0,0,0,0,0,0,\alpha)$}$.

(Autoren: Künzer/Meister/Nebe)
[Zurück zur Aufgabe]
  automatisch erstellt am 7.  6. 2005