Galois Feld: Polynom als Matrix darstellen

Neue Frage »

28.06.2009, 19:35	Psi	Auf diesen Beitrag antworten »
Galois Feld: Polynom als Matrix darstellen Hallo zusammen, als "Neuer" stell ich mich mal schnell vor: Ich heiße Achim, bin 28 Jahre alt, wohne in Bayern (Oberfranken, um genau zu sein) und bin Informatiker von Beruf. Meine Frage hat allerdings jetzt nix direkt mit meinem Beruf zu tun, sondern ich bin auf das Problem aufmerksam geworden, als ich mich aus Interesse mal in die Reed-Solomon Codes eingelesen hab. Nachdem ich also etwa 3 Stunden mit Zettel und Stift vergeblich versucht hab, die Lösung nachzuvollziehen, und dann weitere 3 Stunden nach einem Ansatz gesucht habe, der mich weiter bringt, muss ich feststellen, dass ich entweder den Wald vor lauter Bäumen nicht mehr sehe oder das Hirn auswechseln sollte. Bei der Suche bin ich dann auch auf das Board hier gestoßen und war recht angenehm überrascht, deswegen hab ich mich gleich mal registriert (und dann natürlich auch gleich ne Frage ): Es geht um Galois Felder, speziell $\begin{eqnarray} GF(2^3) \end{eqnarray}$ und $\begin{eqnarray} GF(2^4) \end{eqnarray}$ . $\begin{eqnarray} \mathbb F_8 \end{eqnarray}$ oder $\begin{eqnarray} GF(2^3) \end{eqnarray}$ wird erzeugt durch das Polynom $\begin{eqnarray} P_3(x) = x^3+x+1 \end{eqnarray}$ , $\begin{eqnarray} \mathbb F_{16} \end{eqnarray}$ oder $\begin{eqnarray} GF(2^4) \end{eqnarray}$ wird erzeugt durch das Polynom $\begin{eqnarray} P_4(x) = x^4+x+1 \end{eqnarray}$ . Die Elemente des Körpers lassen sich ja als Polynome darstellen, die als Koeffizienten nur 0 oder 1 haben (Binärsystem). Ein beliebiges Element aus $\begin{eqnarray} \mathbb F_8 \end{eqnarray}$ ist daher ein Polynom 2. Grades der Form $\begin{eqnarray} \sum_{i=0}^2~a_i x^i = a_0 + a_1 x + a_2 x^2 \end{eqnarray}$ mit x=2. Jetzt wird es interessant: Die Multiplikation des Ganzen findet "modulo" $\begin{eqnarray} P_3 \end{eqnarray}$ statt, also sieht der Term folgendermaßen aus: $\begin{eqnarray} c(x) = a(x)b(x)\ mod\ P_3(x) = (a_0 + a_1 x + a_2 x^2)(b_0 + b_1 x + b_2 x^2)\ mod\ (x^3 + x + 1) \end{eqnarray}$ Das lässt sich jetzt natürlich mit etwas Aufwand rechnen, allerdings bin ich auf die Möglichkeit gestoßen, das Ganze bequem als Matrixmultiplikation durchzuführen. Das sieht dann so aus: $\begin{eqnarray} \begin{bmatrix} c_0 \\ c_1 \\ c_2 \end{bmatrix} = \begin{bmatrix} a_0 & a_2 & a_1 \\ a_1 & a_0+a_2 & a_2+a_1 \\ a_2 & a_1 & a_0 + a_2 \end{bmatrix} \begin{bmatrix} b_0 \\ b_1 \\ b_2 \end{bmatrix} \end{eqnarray}$ Was ich jetzt gerne wüsste: Wie zum Geier kommt die Matrix für $\begin{eqnarray} a(x) \end{eqnarray}$ zustande? Ich habe zwar durch Nachrechnen (fast) aller Möglichkeiten geprüft, dass sie offensichtlich für die Multiplikation im Körper korrekt ist, aber mir ist nicht klar, wie sie enstanden ist. Ich habe alle Möglichkeiten, die mir eingefallen sind, versucht, wie ich $\begin{eqnarray} P_3(x) \end{eqnarray}$ und $\begin{eqnarray} a(x) \end{eqnarray}$ zu dieser Matrix zusammenrechne, aber irgendwie bring ich nur Quatsch zustande. Zum anderen würde mich interessieren, wie dann analog die Matrix für $\begin{eqnarray} \mathbb F_{16} \end{eqnarray*}$ errechnen kann. Wenn mich nicht alles täuscht, müsste das ja dann eine 4x4 Matrix ergeben. Wär für jede Hilfe dankbar, ich verzweifel langsam... Gruß Achim
28.06.2009, 19:42	kiste	Auf diesen Beitrag antworten »
Willkommen Die Matrix bekommt man dadurch dass man die allgemeinen Polynome a(x)b(x) ausrechnet. Dann reduziert man modulo $\begin{eqnarray} x^3+x+1 \end{eqnarray}$ . D.h. man ersetzt $\begin{eqnarray} x^3 = x+1 \end{eqnarray}$ (Beachte -1=1) und $\begin{eqnarray} x^4 = x^2+x \end{eqnarray*}$ . Dannach kommt man durch Koeffizientenvergleich auf die Matrix
28.06.2009, 20:29	Psi	Auf diesen Beitrag antworten »
Ich hab das jetzt mal so versucht, wie Du gesagt hast, aber das ergibt immer noch keinen Sinn (irgendwas mach ich da verkehrt): $\begin{eqnarray} a(x)b(x) =\\ a_0b_0 + a_0b_1x + a_0b_2x^2 \\ +a_1b_0x + a_1b_1x^2 + a_1b_2x^3 \\ +a_2b_0x^2 + a_2b_1x^3 + a_2b_2x^4 \end{eqnarray}$ Zusammengefasst: $\begin{eqnarray} a_0b_0 + a_0a_1b_0b_1x + a_0a_1a_2b_0b_1b_2x^2 + a_1a_2b_1b_2x^3 + a_2b_2x^4 \end{eqnarray}$ Die Modulodivision wie Du sie vorschlägst kenn ich nicht, ich kenn lediglich die normale Polynomdivision... Wenn ich jetzt so vorgehe, wie Du sagst, kommt im nächsten Schritt folgendes heraus: $\begin{eqnarray} a_0b_0 + a_0a_1b_0b_1x + a_0a_1a_2b_0b_1b_2x^2 + a_1a_2b_1b_2(x+1) + a_2b_2(x^2+x) \end{eqnarray}$ Aufgelöst: $\begin{eqnarray} a_0b_0 + a_0a_1b_0b_1x + a_0a_1a_2b_0b_1b_2x^2 + a_1a_2b_1b_2x+ a_1a_2b_1b_2 + a_2b_2x^2 + a_2b_2x \end{eqnarray}$ Jetzt alle "doppelten" streichen (sind ja in $\begin{eqnarray} \mathbb Z_2 \end{eqnarray}$ ): $\begin{eqnarray} a_0b_0a_1a_2b_1b_2 + a_0b_0x + a_0a_1b_0b_1x^2 \end{eqnarray}$ Lustigerweise kommt bei mir mit Polynomdivision ein bissl was anderes raus, aber ich brauch wohl nen größeren Flipchart -.- Mein Ergebnis war dieses: $\begin{eqnarray} a_0b_0a_1a_2b_1b_2 + a_0b_0x + a_0a_1b_2x^2 \end{eqnarray}$ Welches jetzt auch richtig sein mag - sei es das erste - ist soweit gut und schön, wie bringt mich das jetzt auf die Matrix? Denn die ganzen $\begin{eqnarray} b_0, b_1, b_2 \end{eqnarray*}$ tauchen da ja net auf... Wie stell ich den Koeffizientenvergleich hier an? Danke & Gruß Achim
28.06.2009, 20:38	kiste	Auf diesen Beitrag antworten »
Wie du zusammenfasst ist mir ein riesengroßes Rätsel. Zum Beispiel ist doch niemals $\begin{eqnarray} a_0b_1x + a_1b_0x = a_0b_1a_1b_0x \end{eqnarray}$ . Das dannach nichts sinnvolles rauskommen kann ist dann klar
28.06.2009, 21:13	Psi	Auf diesen Beitrag antworten »
Da sieht man wie verplant ich inzwischen bin. Ok, da muss ich dann jetzt erstmal komplett neu anfangen... Vielleicht kannst Du mir trotzdem nen Tip geben, wie die Koeffizienten zu vergleichen sind? Ein Link irgendwohin wäre schon hilfreich... solange es nicht auf die Wikipedia ist, die hilft mir da recht wenig zum Bilden dieser Matrix auf Basis des Koeffizientenvergleichs
28.06.2009, 21:19	kiste	Auf diesen Beitrag antworten »
Zuerst schaust du dir jedes Monom(also x^i) separat an. Da hast du dann eine Summe über $\begin{eqnarray} a_ib_j \end{eqnarray}$ , beispielsweise $\begin{eqnarray} a_0b_0+a_2b_0 +a_1b_1 + a_2b_2 + a_1b_2 \end{eqnarray}$ (frei erfunden hat nichts mit der Aufgabe zu tun). Dann schreibst du in die Matrix eben die Zeile $\begin{eqnarray} \begin{pmatrix} a_0+a_2 & a_1 & a_2+a_1\end{pmatrix} \end{eqnarray}$ an Zeilennummer i+1
Anzeige

28.06.2009, 22:00	Psi	Auf diesen Beitrag antworten »
Ah, das ergibt Sinn. Jetzt schau ich mal, ob das Ganze so auch passt. Ich vermute mal, ich hab wieder irgendeinen Dreher im Kopf, aber folgendes kommt bei mir raus (Schritt für Schritt), wenn ich richtig zusammenfasse: Also ausgehend von $\begin{eqnarray} a_0b_0 + a_0b_1x + a_0b_2x^2\\+a_1b_0x + a_1b_1x^2 + a_1b_2x^3\\+a_2b_0x^2+a_2b_1x^3+a_2b_2x^4 \end{eqnarray}$ Setze ich jetzt ein: $\begin{eqnarray} x^3 = x + 1 \end{eqnarray}$ und das Ganze nochmal $\begin{eqnarray} x \end{eqnarray}$ $\begin{eqnarray} x^4 = x^2 + x \end{eqnarray}$ und substituiere entsprechend oben (mit Zwischenschritt): $\begin{eqnarray} a_0b_0 + a_0b_1x + a_0b_2x^2\\+a_1b_0x + a_1b_1x^2 + a_1b_2(x+1)\\+a_2b_0x^2+a_2b_1(x+1)+a_2b_2(x^2+x) \end{eqnarray}$ Ausmultipliziert: $\begin{eqnarray} a_0b_0 + a_0b_1x + a_0b_2x^2\\+a_1b_0x + a_1b_1x^2 + a_1b_2x + a_1b_2\\+a_2b_0x^2+a_2b_1x+a_2b_1+a_2b_2x^2+a_2b_2x \end{eqnarray}$ Umgestellt und ausgeklammert (teilweise): $\begin{eqnarray} a_0b_0 +a_2b_1 + a_1b_2 \\ + (a_1b_0 + a_0b_1 +a_2b_1+ a_1b_2 +a_2b_2)x \\ +(a_2b_0 + a_1b_1 + a_0b_2 +a_2b_2)x^2 \end{eqnarray}$ Und jetzt noch die b-Koeffizienten ausklammern: $\begin{eqnarray} (a_0)b_0 +(a_2)b_1 + (a_1)b_2 \\ + \left[ (a_1)b_0 + (a_0 + a_2)b_1+ (a_1+a_2)b_2\right]x \\ +\left[(a_2)b_0 + (a_1)b_1 + (a_0 +a_2)b_2\right]x^2 \end{eqnarray}$ Wenn man sich jetzt die Ausdrücke in runden Klammern anschaut und die einfach so wie sie da stehen in eine Matrix einträgt, erhält man: $\begin{eqnarray} \begin{vmatrix} a_0 & a_2 & a_1 \\ a_1 & a_0+a_2 & a_1+a_2 \\ a_2 & a_1 & a_0+a_2 \end{vmatrix} \end{eqnarray}$ Wahnsinn. Ich bin natürlich nicht auf die Idee gekommen, dass man z.B. $\begin{eqnarray} a_0b_1 \end{eqnarray}$ und $\begin{eqnarray} a_2b_1 \end{eqnarray}$ zusammenfassen kann, bzw. dass die Spalten der Matrix durch den Index der b- Koeffizienten gebildet werden könnten. Leuchtet ein und erspart dem PC viel Rechenzeit. Der Vollständigkeit halber werde ich morgen noch die Matrix für $\begin{eqnarray} \mathbb F_{16} \end{eqnarray*}$ herleiten und hier posten, aber schonmal vielen, vielen Dank für die Hilfe.
28.06.2009, 22:03	kiste	Auf diesen Beitrag antworten »
Das ganze hab ich übrigens an der Form der Matrix erkannt. Dieses Ausklammern ist genau das was die Matrix macht. Deine Rechnung ist jetzt natürlich ok
28.06.2009, 22:17	Psi	Auf diesen Beitrag antworten »
Aber die Art des Modulo- Rechnens war mir neu. Setzt man immer einfach den höchsten Exponenten des Divisors gleich dem Rest des Terms oder muss ich gegebenenfalls mehrere Ersetzungen vornehmen?
28.06.2009, 22:51	kiste	Auf diesen Beitrag antworten »
Nein das ging nur wegen Charakteristik 2. Ansonsten gilt für modulo $\begin{eqnarray} x^n + a_{n-1}x^{n-1}+\ldots + a_1x + a_0 \end{eqnarray}$ eben $\begin{eqnarray} x^n = - a_{n-1}x^{n-1}-\ldots - a_1x - a_0 \end{eqnarray}$ . Die Relation führt man solange aus bis man nur noch Monome von Grad kleiner n hat.
29.06.2009, 01:02	Psi	Auf diesen Beitrag antworten »
Ok klar, normalerweise packst Du den höchsten Faktor auf die andere Seite, dadurch ergibt sich natürlich für den restlichen Term ein negatives Vorzeichen, aber ich sprach jetzt schon von der Charakteristik 2. Bezüglich der Matrix in $\begin{eqnarray} \mathbb F_{16} \end{eqnarray}$ übrigens auch Charakterisik 2 bin ich zu folgender Lösung gekommen: Wie gesagt wird der Körper erzeugt durch $\begin{eqnarray} P(x) = x^4+x+1 \end{eqnarray}$ . Die Elemente des Körpers werden durch Polynome der Form $\begin{eqnarray} \sum_{n=0}^3~a_n x^n = a_0 + a_1 x + a_2 x^2 + a_3 x^2 \end{eqnarray}$ dargestellt. Um jetzt die Multiplikation zweier Elemente in $\begin{eqnarray} \mathbb F_{16} \end{eqnarray}$ mittels einer Matrix bewerkstelligen zu können, geht man analog vor: $\begin{eqnarray} c(x) = a(x)b(x)\ mod\ p(x) = (a_0 + a_1 x + a_2 x^2 + a_3 x^3)(b_0 + b_1 x + b_2 x^2 + b_3 x^3)\ mod\ (x^4+x+1) \end{eqnarray}$ Aus $\begin{eqnarray} a(x) b(x) \end{eqnarray}$ erhält man: $\begin{eqnarray} a_0b_0+a_0b_1x+a_0b_2x^2+a_0b_3x^3 \end{eqnarray}$ $\begin{eqnarray} +a_1b_0x+a_1b_1x^2+a_1b_2x^3+a_1b_3x^4 \end{eqnarray}$ $\begin{eqnarray} +a_2b_0x^2+a_2b_1x^3+a_2b_2x^4+a_2b_3x^5 \end{eqnarray}$ $\begin{eqnarray} +a_3b_0x^3+a_3b_1x^4+a_3b_2x^5+a_3b_3x^6 \end{eqnarray}$ Das Ganze modulo $\begin{eqnarray} P(x) \end{eqnarray}$ ergibt dann: $\begin{eqnarray} a_0b_0+a_3b_1+a_2b_2+a_1b_3 \end{eqnarray}$ $\begin{eqnarray} +a_1b_0x+a_0b_1x+a_3b_1x+a_2b_2x+a_3b_2x+a_1b_3x+a_2b_3x \end{eqnarray}$ $\begin{eqnarray} +a_2b_0x^2+a_1b_1x^2+a_0b_2x^2+a_3b_2x^2+a_2b_3x^2+a_3b_3x^2 \end{eqnarray}$ $\begin{eqnarray} +a_3b_0x^3+a_2b_1x^3+a_1b_2x^3+a_0b_3x^3+a_3b_3x^3 \end{eqnarray}$ Wiederum die Koeffizienten von b(x) ausmultipliziert dargestellt: $\begin{eqnarray} (a_0)b_0+(a_3)b_1+(a_2)b_2+(a_1)b_3 \end{eqnarray}$ $\begin{eqnarray} +(a_1)b_0x+(a_0+a_3)b_1x+(a_2+a_3)b_2x+(a_1+a_2)b_3x \end{eqnarray}$ $\begin{eqnarray} +(a_2)b_0x^2+(a_1)b_1x^2+(a_0+a_3)b_2x^2+(a_2+a_3)b_3x^2 \end{eqnarray}$ $\begin{eqnarray} +(a_3)b_0x^3+(a_2)b_1x^3+(a_1)b_2x^3+(a_0+a_3)b_3x^3 \end{eqnarray}$ Und die sich daraus schlussendlich ergebende Matrix: $\begin{eqnarray} \begin{bmatrix} a_0 & a_3 & a_2 & a_1 \\ a_1 & a_0+a_3 & a_2+a_3 & a_1+a_2 \\ a_2 & a_1 & a_0+a_3 & a_2+a_3 \\ a_3 & a_2 & a_1 & a_0 + a_3\end{bmatrix} \end{eqnarray*}$ Gruß Achim

Neue Frage »

Antworten »

Galois Feld: Polynom als Matrix darstellen

Verwandte Themen