Mathematik-Online-Lexikon: Zyklische Codes

	[Home] [Lexikon] [Aufgaben] [Tests] [Kurse] [Begleitmaterial] [Hinweise] [Mitwirkende] [Publikationen]
	Mathematik-Online-Lexikon:
	Zyklische Codes

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

Übersicht

Erzeugerpolynome.

Im folgenden sei $\mbox{$q=p^f$}$ eine Primzahlpotenz und $\mbox{$\mathbb{F}_q$}$ der Körper mit $\mbox{$q$}$ Elementen.

Ein linearer Code $\mbox{$C\subset\mathbb{F}_q^N$}$ heißt zyklisch, falls

$\mbox{$\displaystyle (c_0,\dots,c_{N-1})\in C\;\Rightarrow\;(c_{N-1},c_0,c_1,\dots,c_{N-2})\in C. $}$

Ein zyklischer Code wird durch ein Ideal in $\mbox{$B:=\mathbb{F}_q[X]/(X^N-1)\mathbb{F}_q[X]$}$ beschrieben; jedes Codewort $\mbox{$c=(c_0,\dots, c_{N-1})\in\mathbb{F}_q^N$}$ wird mit

$\mbox{$\displaystyle (c_0,c_1,\dots,c_n)= c_0 + c_1 X + \dots+c_{N-1}X^{N-1}\in B $}$

identifiziert.

Im folgendem sei $\mbox{$N$}$ kein Vielfaches von $\mbox{$p$}$ . Ausgehend von einer Faktorisierung in $\mbox{$\mathbb{F}_q[X]$}$

$\mbox{$\displaystyle X^N-1 = f_{(1)}(X)\cdots f_{(t)}(X) \in \mathbb{F}_q[X] $}$

in paarweise verschiedene, normierte und irreduzible $\mbox{$f_{(i)}\in\mathbb{F}_q[X]$}$ , sind die Ideale von $\mbox{$R$}$ von der Form

$\mbox{$\displaystyle f_{(i_1)}\cdots f_{(i_s)}R, $}$

wobei $\mbox{$0\leq s\leq t$}$ und $\mbox{$1\leq i_1<i_2<\dots<i_s\leq t$}$ .

Ein solches Polynom $\mbox{$g:=f_{(i_1)}\cdots f_{(i_s)}=\sum_{j=0}^{N-k}g_jX^j$}$ vom Grade $\mbox{$N-k$}$ heißt Erzeugerpolynom des zyklischen Codes $\mbox{$C_g:=gR\subseteq R$}$ mit Dimension $\mbox{$k$}$ . Eine Erzeugermatrix ist

$\mbox{$\displaystyle G_g:=\begin{pmatrix} g_0 & g_1 & \dots & g_{N-k} & \\ ... ... & & g_0 & g_1 & \dots & g_{N-k} \end{pmatrix}\in\mathbb{F}_q^{k\times N}. $}$

Das Polynom $\mbox{$h=\sum_{j=0}^{k}h_j X^j\in\mathbb{F}_p[X]$}$ mit $\mbox{$gh=X^N-1$}$ heißt Prüfpolynom von $\mbox{$C_g$}$ . Eine Prüfmatrix ist

$\mbox{$\displaystyle H_g:=\begin{pmatrix} h_k & & \\ h_{k-1} & \ddots & \... ...& \ddots & \vdots \\ & & h_0 \end{pmatrix}\in\mathbb{F}_q^{N\times(N-k)}. $}$

Minimalabstand bei zyklischen Codes.

Der Minimalabstand bei zyklischen Codes ist i.a. schwierig zu bestimmen; folgende Abschätzung ist jedoch bekannt.

Bezeichne $\mbox{$\varphi(N)$}$ die Anzahl der zu $\mbox{$N$}$ teilerfremden Zahlen in $\mbox{$\{1,\dots,N\}$}$ .

Ist $\mbox{$\alpha$}$ eine Nullstelle in $\mbox{$\mathbb{F}_{q^{\varphi(N)}}$}$ von $\mbox{$X^N-1\in\mathbb{F}_q[X]$}$ mit $\mbox{$N=\min\{n\in\mathbb{N}:\alpha^n=1\}$}$ , so heißt $\mbox{$\alpha$}$ eine primitive $\mbox{$N$}$ -te Einheitswurzel über $\mbox{$\mathbb{F}_q$}$ .

Sei ein zyklischer Code $\mbox{$C_g \subseteq R$}$ und eine primitve $\mbox{$N$}$ -te Einheitswurzel $\mbox{$\alpha$}$ gegeben. Gilt dann $\mbox{$g(\alpha^b)=0, g(\alpha^{b+1})=0, \dots, g(\alpha^{b+\delta-2})=0$}$ für eine Wahl von $\mbox{$b\in\mathbb{N}$}$ , $\mbox{$\delta \geq 2$}$ so folgt $\mbox{$d(C_g) \geq \delta$}$ .

Codierung bei zyklischen Codes.

Um bei einem zyklischen Code $\mbox{$C_g$}$ mit $\mbox{$g=\sum_{j=0}^{N-k}g_jX^j$}$ , Länge $\mbox{$N$}$ und Dimension $\mbox{$k$}$ ein Informationswort $\mbox{$u=(u_0,\dots,u_{k-1})\in\mathbb{F}_q^k$}$ einem Codewort $\mbox{$c=(c_0,\dots, c_{N-1})\in\mathbb{F}_q^N$}$ zuzuweisen, können die Kontrollbits mit Hilfe von Polynomdivision berechnet werden. Dabei wird das Informationswort zunächst als Element aus $\mbox{$\mathbb{F}_q[X]$}$ dargestellt,

$\mbox{$\displaystyle u(X) := X^{N-k} \sum_{j=0}^{k-1} u_jX^j. $}$

Polynomdivision von $\mbox{$u(X)$}$ durch $\mbox{$g(X)$}$ ergibt einen Rest $\mbox{$r(X)=\sum_{j=0}^{N-k-1}r_jX^j\in\mathbb{F}_q[X]$}$ .

Man verwendet dann als Codewort $\mbox{$c = (-r_0,\dots,-r_{N-k-1},u_0,\dots,u_{k-1})$}$ .

Unvollständiges Decodieren.

Gegeben sei ein Erzeugerpolynom $\mbox{$g$}$ für den zyklischen Code $\mbox{$C_g \subseteq R$}$ der Länge $\mbox{$N$}$ so, daß mit einer primitiven $\mbox{$N$}$ -ten Einheitswurzel $\mbox{$\alpha\in\mathbb{F}_{q^{\varphi(N)}}$}$ und $\mbox{$\delta \geq 2$}$ das Erzeugerpolynom die Nullstellen $\mbox{$g(\alpha^b) = g(\alpha^{b+1}) = \dots = g(\alpha^{b+\delta -2}) = 0$}$ hat. Ist $\mbox{$\delta = 2t+1$}$ , so gilt $\mbox{$d(C_g)\geq 2t+1$}$ und es können bis zu $\mbox{$t$}$ Fehler decodiert werden. Allerdings gibt es i.a. Elemente $\mbox{$a\in\mathbb{F}_q^N$}$ , die nicht decodiert werden können.

Das Verfahren wird besonders übersichtlich, wenn folgende Vereinfachungen vorausgesetzt werden. Seien $\mbox{$\alpha,\dots,\alpha^{2t}$}$ Nullstellen von $\mbox{$g$}$ . Es seien ferner das Codewort $\mbox{$c=(c_0,c_1,\dots,c_{N-1})$}$ und das empfangene Wort

$\mbox{$\displaystyle r = (r_0,r_1,\dots,r_{N-1}) &=& r_0 + r_1X + \cdots + r_NX^{N-1} $}$

in höchstens $\mbox{$t$}$ Stellen verschieden.

Dann können Koeffizienten für die Polynome

$\mbox{$\displaystyle \begin{array}{rcl} \sigma &=& \sum_{j=0}^t \sigma_j X^j\vspace*{1mm}\\ \omega &=& \sum_{j=0}^t \omega_j X^j, \end{array}$}$

wobei $\mbox{$\sigma_0=1$}$ und $\mbox{$\omega_0=0$}$ vorausgesetzt werden können, durch Lösen eines Gleichungssystems in $\mbox{$\mathbb{F}_q$}$ eindeutig so bestimmt werden, daß die Potenzreihenentwicklung von $\mbox{$\frac{\omega(X)}{\sigma(X)}$}$ mit $\mbox{$\sum_{l=1}^{2t} r(\alpha^l)X^l$}$ beginnt, und der Grad von $\mbox{$\omega$}$ kleiner oder gleich dem Grad von von $\mbox{$\sigma$}$ ist.

Ist $\mbox{$\sigma(\alpha^{-i})=0$}$ , so ist die $\mbox{$i$}$ -te Stelle des empfangenen Wortes durch die Übertragung verlorengegangen und wird durch

$\mbox{$\displaystyle c_i = r_i + \frac{\omega(\alpha^{-i})\alpha^i}{\sigma'(\alpha^{-i})} $}$

korrigiert, wobei $\mbox{$\sigma'(X)$}$ die Ableitung nach $\mbox{$X$}$ von $\mbox{$\sigma(X)\in\mathbb{F}_q[X]$}$ bezeichnet.

(Autoren: Künzer/Meister/Nebe)

Beispiel:

Zyklischer Code

[Verweise]

automatisch erstellt am 25. 1. 2006