Praktische Bestimmung von Polynomen mit beliebig großer Hamming-Distanz
BCH-Code zum Anfassen
Fortsetzung des Artikels von Teil 1
1.2 Erweiterung des binären Galois-Feldes zum GF(2m)
Ganz allgemein lässt sich nachweisen, dass ein Galois-Feld GF(p) zu einem Feld GF(pm) mit pm Elementen, falls m eine Ganzzahl ist, erweitert werden kann. Die Elemente von GF(pm) werden dann als Symbole oder Zeichen mit m-fachen Elementen des Feldes GF(p) gebildet. Von besonderem Interesse ist wiederum der erweiterte Raum GF(2m) mit den binären 2m m-Tupel als Elemente des Feldes. Das Feld GF(2m) besitzt dann gemäß Regel 1 ein primitives Element a mit der Ordnung 2m – 1 für das die Glg. (2) gilt. Die sämtlichen 2m - 1 Zeichen ≠ 0 lassen sich dann durch die Potenzen von a bilden. Zusammen mit dem Null-Element erhält man dann die Gesamtheit des Feldes GF(2m) gemäß der Darstellung (3).
a^(2m – 1) + 1 = 0 (2)
GF(2m) = {0, a^0 = 1, a^1, a^2… a^(2m – 3), a^(2m – 2)} (3)
Die linke Seite der Glg. (2) ist durch a + 1 teilbar und das Produkt wird durch die Glg. (4) dargestellt. Der zweite Produktterm in der Glg. (4) stellt ein Maximalpolynom (Koeffizienten der sämtlichen Potenzen von a des Polynoms sind gleich 1) (2m – 2)ten Grades dar. Es ist selbstverständlich, dass für a = 1 (Einselement) die Glg. (4) erfüllt wird. Wohlgemerkt wird a durch einen m-Tupel der binären Elemente dargestellt. Wie genau dieser beschaffen ist, soll uns zunächst nicht beschäftigen. Für a ≠ 1 muss der zweite Term auf der rechten Seite der Glg. (4) Null werden, damit die Glg. (4) ihre Gültigkeit behält. In der Tat lässt sich das Maximalpolynom (2m – 2)ten Grades in irreduzibele Faktoren zerlegen. Ein Grossteil dieser Polynome sind primitive Polynome mten Grades mit einer Zykluslänge von 2m – 1. [3] Es wird im Abschnitt 2.4 gezeigt, dass jedes Element von GF(2m) außer 0 und 1 die Wurzel des Maximalpolynom (2m – 2)ten Grades darstellt. Somit hat die Glg. (4) stets ihre Gültigkeit. Das ganze soll nun an einem exemplarischen Beispiel mit m = 4 verdeutlicht werden.
a^(2m – 1) + 1 = (a + 1) x (a^(2m – 2) + a^(2m – 3) + …. + a^1 + 1) (4)
1.3 Bestimmung des Feldes GF(24)
Auffällig ist die Gleichheit der Ordnung eines primitiven Elementes von GF(2m) und der Zykluslänge eines primitiven Polynoms mten Grades. Beide betragen 2m – 1. Daher ist es nicht verwunderlich, dass zur Konstruktion eines GF(2m) ein primitives Polynom mten Grades herangezogen wird. Für m = 4 gibt es zwei primitive Polynome 4ten Grades, 13h und 19h. Für die Polynome wird hier eine Hexadezimal Darstellung gewählt. 19h (1 1001) repräsentiert das Polynom x4 + x3 + 1. Das Feld GF(2m) für m = 4 beinhaltet 16 4-Bit Tupeln (die Elemente des Feldes). Man kann ein Element auch als einen Vektor eines 4 dimensionalen Raumes betrachten. Mit vier linear unabhängigen Vektoren lässt sich so ein Raum vollständig beschreiben. D. h. wir können 4 Elemente (a0, a1, a2, a3) des Feldes frei definieren. Willkürlich wird die folgende Konvention in Anlehnung an Lin / Costello gewählt: [2]
a0 = 1000, a1 = 0100, a2 = 0010, a3 = 0001
| GF(24) Generator-Polynom 19h x4 + x3 + 1 | GF(24) Generator-Polynom 13h x4 + x + 1 | ||||||||||
| Element | Binäre Darstellung 4-Tupel | Polynom- Darstellung | Element | Binäre Darstellung 4-Tupel | Polynom- Darstellung | ||||||
| a0 = 1 | 1 | 0 | 0 | 0 | 1 | b0 = 1 | 1 | 0 | 0 | 0 | 1 |
| a1 | 0 | 1 | 0 | 0 | a | b1 | 0 | 1 | 0 | 0 | b |
| a2 | 0 | 0 | 1 | 0 | a2 | b2 | 0 | 0 | 1 | 0 | b2 |
| a3 | 0 | 0 | 0 | 1 | a3 | b3 | 0 | 0 | 0 | 1 | b3 |
| a4 | 1 | 0 | 0 | 1 | a3 + 1 | b4 | 1 | 1 | 0 | 0 | b + 1 |
| a5 | 1 | 1 | 0 | 1 | a3 + a + 1 | b5 | 0 | 1 | 1 | 0 | b2 + b |
| a6 | 1 | 1 | 1 | 1 | a3 + a2 + a + 1 | b6 | 0 | 0 | 1 | 1 | b3 + b2 |
| a7 | 1 | 1 | 1 | 0 | a2 + a + 1 | b7 | 1 | 1 | 0 | 1 | b3 + b + 1 |
| a8 | 0 | 1 | 1 | 1 | a3 + a2 + a | b8 | 1 | 0 | 1 | 0 | b2 + 1 |
| a9 | 1 | 0 | 1 | 0 | a2 + 1 | b9 | 0 | 1 | 0 | 1 | b3 + b |
| a10 | 0 | 1 | 0 | 1 | a3 + a | b10 | 1 | 1 | 1 | 0 | b2 + b + 1 |
| a11 | 1 | 0 | 1 | 1 | a3 + a2 + 1 | b11 | 0 | 1 | 1 | 1 | b3 + b2 + b |
| a12 | 1 | 1 | 0 | 0 | a + 1 | b12 | 1 | 1 | 1 | 1 | b3 + b2 + b + 1 |
| a13 | 0 | 1 | 1 | 0 | a2 + a | b13 | 1 | 0 | 1 | 1 | b3 + b2 + 1 |
| a14 | 0 | 0 | 1 | 1 | a3 + a2 | b14 | 1 | 0 | 0 | 1 | b3 + 1 |
| a15 = 1 | 1 | 0 | 0 | 0 | 1 | b15 = 1 | 1 | 0 | 0 | 0 | 1 |
| Tabelle III Konstruktion eines Galois-Feldes GF(24) | |||||||||||
Die vierte Potenz von a wird mit Hilfe des Polynoms 19h, a4 + a3 + 1 = 0 gebildet und dem Wert von a3 + 1 = 1001 zugewiesen. Nach diesem Schema wird dann a5 = a3 + a + 1 =1101. Man beachte, die Addition wird gemäß modulo 2 durchgeführt und für die Multiplikation werden die Potenzen von a addiert und dann wird die modulo 15 (n = 2m – 1) Operation durchgeführt. In der Tabelle III sind die 15 Elemente ≠ 0 des Feldes GF(24) zusammengestellt. Zur Konstruktion des Feldes wurde das erste Mal das Generator-Polynom 19h und das zweite Mal das Polynom 13h eingesetzt. Beide Felder sind vollkommen gleichwertig und können wahlweise genutzt werden. Entscheidet man sich einmal für eine bestimmte Ausführung, so muss konsequent nur diese im weiteren Verlauf verwendet werden. Erwartungsgemäß stellt man fest, dass ein beliebiges Element des Feldes aus einer linear Kombination der ersten 4 Elemente der Tabelle (die linear unabhängigen Elemente) gebildet wird. Es gibt zwei Darstellungsmöglichkeiten. Man kann entweder die Elemente als ein binäres m-Tupel betrachten oder aber auch als Polynomreste, die durch die Division mit dem Generator-Polynom entstehen. ai ist dann gleich ai modulo g(a).
- BCH-Code zum Anfassen
- 1.2 Erweiterung des binären Galois-Feldes zum GF(2m)
- 4. Ein fiktiver BCH-Code
- 2. Bestimmung der Gesamtheit der irreduzibeln Polynome
- 1.4 Wurzeln des Polynoms
- 5. Die wichtigen Eigenschaften der Polynome
- 7. Zusammenfassung
Das könnte Sie auch interessieren
