Verkürzung eines Codes

08.05.2010, 18:58

Lancelot

Verkürzung eines Codes

Hallo,

ich habe eine Frage, die sich mit fehlerkorrigierenden Codes beschäftigt, vielleicht könnt ihr mir weiterhelfen.

Für einen linearen Code C über dem Alphabet A ist der um eine Stelle verkürzte Code C* definiert als
$\begin{eqnarray*} C^* = \{ x_2 ... x_n | 0x_2 ... x_n\in C \} \end{eqnarray*}$

Aufgabenstellung: Zeige, dass ein um i Stellen $\begin{eqnarray*} 1 <= i <= n-1 \end{eqnarray*}$ verkürzter Code C* eines zyklischen Codes C i.a. nicht zyklisch ist, C* allerdings als Ideal im Faktorring A[x]/(f(x)) mit geeignetem Polynom f(x) aufgefasst werden kann.

Also der erste Teil ist relativ einfach:
zB der von der folgende Code erzeugte zyklische Code ist nach dem er um eine Stelle verkürzt wurde, nicht mehr zyklisch.
$\begin{eqnarray*} \begin{pmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \end{pmatrix} wird \ zu \begin{pmatrix}1 & 0 & 1 \end{pmatrix} \end{eqnarray*}$

Aber beim zweiten Teil bin ich mir nicht mehr sicher.
Ich habe das Polynom $\begin{eqnarray*} f(x) = x^{k-i} \end{eqnarray*}$ betrachtet, wobei k die Dimension des Codes ist, also die Anzahl der Nachrichtenstellen oder Zeilen der Generatormatrix.

Wenn ich nach diesem Polynom ausfaktorisiere erhalte ich einen Polynomring A[x]/(f(x)) der gleich viele Elemente wie mein verkürzter Code hat.
Das entspricht in dem Streichen von i ersten Zeilen und Spalten in der Generatormatrix.

Nun habe ich mir überlegt, dass, die Codewörter des neuen Codes ja bereits im alten enthalten sind. Nach einem Shift der Stellen eines Codewortes nach rechts, oder einer Multiplikaiton mit x, bleiben alle Codewörter in meinem Code, solange sie nicht über die höchste zulässige Potenz (x^(k-i)) hinauswachsen, da sie bereits zuvor in meinem Code waren und dieser ja zyklisch ist.
Alle Stellen die eine zu hohe Potenz von x erhalten, werden durch die Wahl des Polynoms auf das Nullelement in meine Code abgebildet.

Da zyklische Codes linear sind, sind auch Linearkombination von meinen Shifts enthalten und daraus folgt, dass mein Code ein Ideal ist, da er unter Multiplkationen mit beliebigen Polynomen abgeschlossen ist.

Wenn ich mehr als k Stellen streiche, können an den ersten i Stellen nur dann 0en stehen, wenn es sich um das 0-Wort handelt. Dieser Code ist natürlich zyklisch.

Tja, vielleicht habt ihr eine Idee was ich übersehen habe, für mich ist dies Argumentation noch etwas zu schwammig, obwohl ich glaube, dass sie stimmt.

Habt vielen Dank

10.05.2010, 20:08

Mystic

Auf diesen Beitrag antworten »

RE: Verkürzung eines Codes

Zitat:

Original von Lancelot
Tja, vielleicht habt ihr eine Idee was ich übersehen habe, für mich ist dies Argumentation noch etwas zu schwammig, obwohl ich glaube, dass sie stimmt.

Ja, sehr, sehr schwammig ist sie jedenfalls, ob sie stimmt, vermag ich auch nach wiederholtem Durchlesen nicht zu beurteilen... Vielleicht kannst ja du es, nachdem du meine Argumentation dazu gelesen hast...

Der ursprüngliche Code C hat als zyklischer Code ein Generatorpolynom g(x), welches Teiler von $\begin{eqnarray*} x^n-1 \end{eqnarray*}$ ist... Nun ist c(x) (in Polynomdarstellung) genau dann in dem um i Stellen verkürzten Code C*, wenn es sowohl durch $\begin{eqnarray*} x^i \end{eqnarray*}$ als auch durch g(x), und damit auch $\begin{eqnarray*} kgV(x^i,g(x))=x^ig(x) \end{eqnarray*}$ teilbar ist... Damit ist

$\begin{eqnarray*} C^{\ast} =(x^ig(x)) \end{eqnarray*}$

und da das erzeugende Poynom wegen i>0 nicht mehr $\begin{eqnarray*} x^n-1 \end{eqnarray*}$ teilt, ist C* auch nicht mehr zyklisch...

Neue Frage »

Antworten »

Verkürzung eines Codes

Verwandte Themen