Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2014 / Codierungstheorie / Material / Skript Teil 7


Inhaltsbereich

Skript Teil 7

Plain Text icon skript9.txt — Plain Text, 9 KB (10102 bytes)

Dateiinhalt

Zyklische Codes
~~~~~~~~~~~~~~~

Der einfache Paritaets-Code hatte die Eigenschaft, dass zyklisches Vertauschen
der Zeichen in einem Codewort zu einem neuen Codewort fuehrt (denn, in der Tat,
aendert sich die Quersumme dadurch nicht). Wir wollen uns nun ausfuehrlicher
mit solchen, sogenannten "zyklischen Codes" beschaeftigen und auch die
mathematischen Hintergruende betrachten.

Wir hatten ja bereits mehrere Codes gesehen, deren Codewoerter am besten als
Polynome beschrieben werden koennen. In dieser Stunde werden wir stets

                        d-1     i
  (a_0,...,a_{d-1}) mit Sum a  X
                        i=0  i

identifizieren. Ausserdem werden wir uns vor allem fuer den Ring

  GF(q)[X]/(X^n-1)

interessieren. Dieser Ring ist offenbar ein n-dimensionaler GF(q)-VR,
weswegen wir ihn im folgenden mit GF(q)^n identifizieren. In diesem
Ring ist ein zyklisches Vertauschen der Zeichen eines Wortes (left
shift) gerade Multiplikation mit X.

Definition (zyklischer Code).
| Ein linearer Code C subset GF(q)^n == GF(q)[X]/(X^n-1) heist zyklischer Code,
| falls mit jedem c in C auch c * X in C ist.

Proposition
| Zyklische Codes sind genau die Ideale (von GF(q)[X]/(X^n-1)).
Beweis.
  Sei C subset GF(q)[X]/(X^n-1) zyklischer Code. Dann enthaelt C die 0
  und ist unter Summen abgeschlossen, da C UVR ("linearer Code"). Sei
  c in C und p = a_k X^k + ... + a_0 ein Polynom. Aus der Zyklizitaetsbedingung
  erhaelt man (durch Induktion nach k), dass auch X^k * c in C. Es ergibt
  sich p * c in C weil C GF(q)-VR.

  Sei andererseits I subset GF(q)[X]/(X^n-1) ein Ideal. Dann ist I offenbar
  GF(q)-UVR. Ausserdem ist mit c in I stets auch  X * c in I wegen der
  Idealitaetsbedingung.

Bemerkung
| GF(q)[X]/(X^n-1) ist nicht notwendig nullteilerfrei.
Beispiel
  In F2[X]/(X^2-1) gilt etwa (X^1+1)(X^1-1) = 0.

Satz: Sei n>=1 und g ein beliebiges Polynom. Die Repraesentanten (in
 GF(q)[X]/(X^n-1)) von Vielfachen von g bilden einen zyklischen
 Code. Ausserdem ist jeder zyklische Code von dieser Form und g kann
 sogar als Teiler von X^n-1 gewaehlt werden.

Beweis: Die Vielfachen von g bilden einen VR und sind unter
Multiplikation mit X abgeschlossen (ist r ein Vielfaches von g, dann
erst recht Xr). Sei umgekehrt C ein zyklischer Code und g ein
Repraesentant minimalen Grades in C, wobei aber g=/=0. Man dividiert
X^n-1 = qg+r. Es muss r=0 sein, sonst waere ja r ein Repraesentant
kleineren Grades (NB: qg und r sind aequivalent in
GF(q)[X]/(X^n-1)). Also ist g ein Teiler von X^n-1. Sei jetzt p
Repraesentant eines beliebigen Elementes von C. Man dividiert ebenso p
= qg+r und findet wiederum r=0. Also ist p Vielfaches von g. 
Definition
| Das g aus dem Satz oben heisst auch Generatorpolynom des zyklischen Codes.

Damit haben wir einen guten Ueberblick ueber alle zyklischen Codes. 

Beispiel 
  Wir wollen alle binaeren zyklischen Codes der Laenge 4 bestimmen. Dazu
  Faktorisieren wir X^4-1 ueber F_2. Es ist X^4-1=(X+1)^4. Und X^4-1 hat
  also folgende Teiler: 1, X+1, (X+1)^2, (X+1)^2, (X+1)^3 und (X+1)^4.
  Die zugehoerigen zyklischen Codes sind GF(q)^4, der Parity code (even 
  parity), { 0000, 1010, 0101, 1111}, {0000, 1111}, und 0.

Bemerkung
  Der odd-parity Code hat zwar die Eigenschaft, dass sich durch zyklisches
  Vertauschen der Buchstaben wieder ein Codewort ergibt, er ist aber nicht
  linear (z.B., weil er die 0 nicht enthaelt).
   
Wir erinnern uns daran, dass Reed-Solomon Codes voller Laenge auch beschrieben
werden koennen als

                                     q-2      j
   RS'(q,m) = { (c_0,...,c_{q-2}) |  Sum c  X    = 0 (mod r(X)) }
                                     j=0  j

wobei
   
         q-1-m 
          __          j
   r(X) = ||   (X - g   )  das Polynom vom Grad q-1-m in GF(q)[X]
          j=1
 
 
   mit Nullstellen genau g^1, g^2, ..., g^{q-1-m}.

Eine Konsequenz der oben gemachten Beobachtung ist, dass Reed Solomon
Codes (der kanonischen Laenge) stets zyklisch sind. In der Tat, fuer
0 =/= a in GF(q) gilt nach kleinem Fermat dass a^{q-1}-1=0. Also sind
alle (linearen) Faktoren von r auch Faktoren von X^{q-1}-1, und
damit r | X^{q-1}-1. Dies zeigt

Lemma
| RS'(q,m) Codes sind zyklische Codes.

Damit haben wir auch interessantere Beispiele fuer zyklische Codes.

Als naechstes interessieren wir uns dafuer, wie zyklische Codes als
lineare Codes aussehen.

Satz
 Sei C ein zyklischer Code der Laenge n mit Generatorpolynom g vom Grad r.

 Dann ist dim(C) = n - r und

      (g Xg X^2g ... X^{n-r-1}g)

 ist eine Generatormatrix von C, wobei X^ig fuer den Spaltenvektor der
 Koeffizienten von X^ig ist.

Beweis
  dim(C) <= n-r-1 ergibt sich direkt aus der Beschreibung von C als
  { g * p | deg(p) < n - deg(g) }. Fuer die andere Ungleichung und
  die Aussage ueber die Generatormatrix genuegen folgende Beobachtungen.

  -  X^kg in C, da C Ideal.
  
  -  g, X*g, ..., X^{n-r-1} * g in GF(q)[X]/(X^n-1) sind GF(q)-linear
         unabhaengig.
    (Betrachte den Grad der Repraesentanten von kleinstem Grad; dies zeigt,
     dass dies eine obere Dreiecksmatrix bezueglich der GF(q)-Basis 
     1, X, ..., X^{n-1} von GF(q)[X]/(X^n-1) ist.

Satz
| Seien h,g in GF(q)[X] so dass h*g = X^n-1 in GF(q)[X] und C der von g erzeugte
| zyklische Code der Laenge n.
|
| Dann gilt
|
|   c in C <=> h * c = 0 in GF(q)[X]/(X^n-1)
Beweis.
 "=>". c in C, dann g | c, also X^n-1 = h*g | h * c
 "<=". Sei c in GF(q)[X] mit h * c = 0 in GF(q)[X]/(X^n-1). 
        Dann gibt es q in GF(q)[X],
       so dass in GF(q)[X] gilt  h*c = q * g * h. Division durch h liefert
       die Behauptung (GF(q)[X] ist natuerlich ein Integritaetsring!).

Definitin
| Das Polynom h aus dem Satz heisst auch Kontrollpolynom des
| zyklischen Codes.

Um diese Information mit der Kontrollmatrix in Beziehung zu setzen, muessen wir
uns zunaechst ueberlegen, wie Multiplikation von Polynomen und unser 
pseudo-Skalarprodukt zusammenhaengen.

Fuer zwei Polynome Sum_i a_i X^i und Sum_j b_j X^j ist das Produkt
gerade Sum_{i,j} a_i b_j X^{i+j} oder, anders ausgedrueckt, 

   Sum_k Sum_{i+j=k} a_i b_j X^k

Sind beide Polynome vom Grad <n, so ist das Produkt vom Grad <= 2n -2;
insbesondere ist der Koeffizient bei X^{n-1} in GF(q)[X]/(X^n-1) gerade 
Sum_{i+j=n-1} a_i b_j. Damit bekommen wir folgenden Zusammenhang
zwischen Produkt von Polynomen und unserem pseudo-Skalarprodukt.

Definition
| Sei n eine natuerliche Zahl, die aus dem Kontext klar ist.
|
| Fuer p = Sum_i a_i X^i in GF(q)[X], deg(p) < n setzen wir
| rev(p) = Sum_i a_{n-1-i} X^i.

Proposition
| Ist p*q = 0 in GF(q)[X]/(X^n-1) so ist p _|_ rev(q).
Beweis
  Ist p*q = 0 in GF(q)[X]/(X^n-1), so ist auch der Koeffizient bei
  X^{n-1} gerade 0. Dieser ist aber gerade, wie oben gesehen,
  das pseudo-Skalarprodukt von p und rev(q).

Bemerkung
  Die Aussage in der Proposition oben ist *keine* aequivalenz. Etwa
  ist 1 _|_ X,  aber 1 * rev(X) = 1*1 =/= 0, aufgefasst als Polynome
  vom Grad kleiner 3, i.e., gelesen als Polynome in 1,X.

Satz
| Sei C ein zyklischer Code der Laenge n mit Konrollpolynom h vom Grad
| k, so ist
|
|  ( rev(h)  rev(X h) ... rev (X^{n-1-k}h)  )
|
| eine Kontrollmatrix von C.
Beweis
 Sei c in C. Dann ist auch  c * X^i in C und also 0 = (c * X^i) * h =
 c * (X^i * h). Damit sind also die einzelnen Zeilen orthogonal zu
 allen Kodewoertern. Ausserdem sind die Zeilen offenbar linear
 unabhaengig, so dass sich die Behauptung aus Dimensionsgruenden
 ergibt.

Da bei Code und dualen Code Generatormatrix und Kontrollmatrix einfach
vertauscht sind, lesen wir aus obiger Darstellung direkt den folgenden
Satz ab.

Satz
| Der duale Code eines zyklischen Code ist wieder zyklisch. Hat ferner
| C das Kontrollpolynom h, so ist rev(X^{n-1-k} h) ein
| Generatorpolynom.

Bemerkung
  rev(X^{n-1-k) h) = X^k h(X^-1)

Satz (BCH-Schranke)
| C zyklischer Code der Laenge n ueber GF(q) mit Generator g. Ferner
| sei ggT(n,q)=1 und a primitive n-te Einheitswurzel ueber GF(q) und
| es gelte
| 
|     b       b+1              b+d-2
|  g(a ) = g(a   ) = ... = g(a       ) = 0  fuer ein b >= 0 und 2 <= d <= n
|
| Dann hat C Minimaldistanz mindestens d.


Beispiel
  n=q-1, a Primitivwurzel von GF(q) (dann ist a primitive (q-1)-te
  Einheitswurzel und ggT(q-1,q)=1), b=1, d=q-m (dann
  b+d-2=1+q-m-2=q-1-m). Und als Generatorpolynom gerade
  (X-a)(X-a^2)*...*(X-a^{q-1-m}). Dieser Code ist dann gerade der
  RS'(q,m)-Reed-Solomon Code.

  Wir erhalten einen alternativen Beweis, dass dieser Code Distanz q-m
  hat.

Beweis (BCH-Schranke)
  Fuer beliebiges c in C gilt g|c. Also hat c auch alle Nullstellen
  von g, i.e., fuer b <= j <= b+d-2 gilt c(a^j)=0, was auch als

     (1 a^j a^{2j} ... a^{(n-1)j}) c = 0

  geschrieben werden kann. Alle Codeworte c in C erfuellen also die
  folgenden Gleichungen


     (  1    a^b        a^2b         ...   a^{(n-1)b}       )     
     |  1    a^{b+1}    a^{2(b+1)}   ...   a^{(n-1)(b+1)}   |   c    = 0   
     | ...                                    ...           |
     (  1    a^{b+d-2}  a^(2(n+d-2)} ...   a^{(n-1)(b+d-2)} )

  Nennen wir die Matrix H und betrachten den Code C' der durch H als
  Kontrollmatrix gegehen ist. Offenbar C subset C'. Damit genuegt es
  zu zeigen, dass C' die Minimaldistanz mindestens d hat. Dafuer
  wiederum reicht es zu zeigen, dass je d-1 Spalten linear unabhaengig 
  sind. Sei also x ... z so, dass (x^b ...)^T, ..., (z^b ...)^T die
  ausgewaehlten Spalten sind. Offenbar sind x ... z gerade d-1
  paarweise verschiedene Elemente von {1,a,a^2,...,a^(n-1)}; beachte
  dass a eine primitive n-te Einheitswurzel ist. Wir berechnen die
  Determinante der sich ergebenden Matrix

  | x^b        ...   z^b       |      b       b  | 1        ...  1       |
  | x^{b+1}    ...   z^{b+1}   |  =  x *...* z * | x        ...  z       |
  | ...               ...      |                 | ...          ...      |
  | x^{b+d-2}  ...   z^{b+d-2} |                 | x^{d-2}  ... z^{d-2}  |


     b      b  ----
  = x *...*z   | |  (x - x )  =/= 0  (Vandermonde'sche Determinante)
              i < j  i   j


  Damit ist alles gezeigt.


Bem: Ein Code, der die Bedingungen der BCH-Schranke erfuellt, heisst BCH-Code. 

Artikelaktionen


Funktionsleiste