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 = 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.