Startseite > Kommunikation > BCH-Code zum Anfassen

Praktische Bestimmung von Polynomen mit beliebig großer Hamming-Distanz

BCH-Code zum Anfassen

15. Oktober 2007, 9:10 Uhr | Kamal Merchant

▶ Diesen Artikel anhören

Fortsetzung des Artikels von Teil 4

1.4 Wurzeln des Polynoms

Die bisherige Betrachtung ist sehr gewöhnungsbedürftig, denn in der Praxis arbeitet man immer mit Polynomen über dem GF(2) mit den Elementen 0 und 1. Die Koeffizienten von Polynomen können auch nur die Werte 0 oder 1 annehmen. Was bedeutet es nun, wenn man sagt: „Das Polynom hat eine Wurzel in GF(2^m)?“ Dieser Umstand ist vergleichbar mit der Erweiterung von reellen Zahlen zu komplexen Zahlen. Einem Anfänger kommt es sehr fremd vor, wenn er zum ersten Mal hört, dass die Glg. x² + 3 = 0, zwei komplexe Wurzeln x = ± i√3 besitzt. Man kann mit Hilfe der Tabelle III sehr leicht verifizieren, dass das Element a eine Wurzel des Polynoms x⁴ + x³ + 1 darstellt. Das Verständnis wird dadurch erleichtert, wenn man zunächst die Polynom-Darstellung der Elemente betrachtet. Für die Modulo 2 Addition ist bekannt, dass eine Addition mit sich selbst stets eine Null liefert (x + x = 0). Dies muss ja auch zwangsläufig so sein, denn zur Bestimmung des Feldes GF(2⁴) wurde das Polynom x⁴ + x³ + 1 herangezogen. Es ist interessant zu bemerken, dass die irreduzibeln Polynome m^ten Grades allgemein keine Wurzel in GF(2) besitzen. Sie besitzen dafür m Wurzeln im erweiterten Raum GF(2^m).

Das Polynom x^(2^m – 1) + 1 hat 2^m – 1 Wurzeln. Jedes der Elemente aⁱ ≠ 0 des erweiterten Feldes GF(2^m) stellt eine Wurzel des Polynoms x^(2^m – 1) + 1 dar, da ( aⁱ )^(2^m – 1) = (a^(2^m – 1)) ⁱ = 1ⁱ = 1 gilt. Unter Betrachtung dieser Tatsache liefert die Glg. (4) neue Erkenntnisse. Es kann daraus abgeleitet werden, dass die 2^m – 2 Wurzeln des Maximalpolynom (2^m – 2)^ten Grades durch die Elemente, mit Ausnahme von 0 und 1, des Feldes GF(2^m) darstellt werden können. Das Ergebnis ist durch die Glg. (5) dargestellt. Die Produktbildung in der Glg. (5) erstreckt sich für i = 1 bis 2^m – 2. Diese Glg. liefert den ersten Hinweis auf einen BCH-Code, denn ein Maximalpolynom des geraden Grades gehört zu den BCH-Codes. Man kannte diese Polynome schon lange vor der Entdeckung des BCH-Codes. Es wurde leider keine Kenntnis davon genommen, da sie trotz ihrer hohen Hamming-Distanz nur ein einziges Informationsbit übertragen können.

(x^(2^m – 2) + x^(2^m – 3) + …. + x^1 + 1) = ∏(x – aⁱ) (5)

1.4.2 Deutung der Wurzeln

Für m = 4 nimmt 2^m – 2 den Wert von 14 an. Das Maximalpolynom wird dann gleich 7FFFh und hat den Grad 14. Das Polynom hat vier irreduzibele Faktoren, 19h, 1Fh, 7h und 13h. Die primitiven Polynome mit der Zykluslänge 2^m – 1 = 15 wurden im vorigen Abschnitt bereits behandelt. Das nichtprimitive Polynom 1Fh 4^ten Grades hat eine Zykluslänge von 5 (ein Teiler von 2^m – 1 = 15). Das letzte Polynom 7h ist zwar primitiv hat aber einen kleineren Grad als m, nämlich 2. Seine Zykluslänge beträgt 3, auch ein Teiler von 2^m – 1. a³ ist einer der Wurzeln des Polynoms 1Fh und a⁵ ist einer der Wurzeln von 7h. Diese Polynome werden durch die Gleichungen (8) bzw. (9) dargestellt.

x⁴ + x³ + x² + x + 1 = (x + a³) * (x + a⁶) *(x + a¹²) * (x + a⁹) (8)

x² + x + 1 = (x + a⁵) * (x + a¹⁰) (9)

In der Tabelle IV sind sämtliche Wurzeln von irreduzibeln Faktoren des Maximalpolynoms 7FFFh zusammengestellt.

Polynom	Grad	Zykluslänge n	primitiv	Wurzeln	Anzahl
19h, x⁴ + x³ + 1	4	15	ja	a, a², a⁴, a⁸	4
1Fh, x⁴ + x³ + x² + x + 1	4	5 = 15 /3	nein	a³, a⁶, a¹², a⁹	4
7h, x² + x + 1	2	3 = 15 /5	ja	a⁵, a¹⁰	2
13h, x⁴ + x + 1	4	15	ja	a⁷, a¹⁴, a¹³, a¹¹	4
Tabelle IV Die Wurzeln der irreduzibeln Polynome 4^ten Grades

Die Tabelle IV zeigt deutlich, dass die Gesamtheit der Elemente (ausgenommen 0 und 1) eines erweiterten Galois-Feldes GF(2^m) exakt wieder als die Wurzeln von irreduzibeln Polynomen m^ten Grades vorkommen. Damit werden auch gleichzeitig die sämtlichen irreduzibeln Polynome m^ten Grades erfasst. Für das betrachtete Beispiel mit m = 4 gibt es keine weiteren irreduzblen Polynome, als die in der Tabelle IV aufgelistet sind. Auffällig ist, dass darunter gelegentlich auch irreduzibele Polynome mit einem kleineren Grad als m gefunden werden. Die 2^m – 2 Elemente (aⁱ, i = 1 bis 2^m – 2) zusammen mit 0 und 1 definieren das Galois-Feld GF(2^m) vollständig. In Anlehnung an die allgemeine Literatur, werden diese Elemente ab jetzt als Wurzel aⁱ des Polynoms bezeichnet. Kennt man eine Wurzel aⁱ und das komplette Galois-Feld GF(2^m), so lässt sich das zugehörige Polynom rückwärts berechnen, ohne eine Kenntnis davon zu besitzen. Z. B. mit der Wurzel a⁷ kann das zugehörige primitiv Polynom gemäß Glg. (7) berechnet werden. Die so gewonnenen Polynome sind vom kleinsten Grad über dem GF(2) und werden daher als Minimalpolynome der Wurzeln, aus denen sie berechnet wurden, bezeichnet. Dass es sich dabei um ein Polynom kleinsten Grades über dem GF(2) handelt ist selbstverständlich, da das Minimalpolynom aus einer einzigen Wurzel und ihrer konjugierten Wurzeln, gebildet wurde. Die wichtigsten Eigenschaften von Minimalpolynomen sind: ^[4]

Minimalpolynom einer beliebigen Wurzel aⁱ ist irreduzibel vom Grad r <= m
Zu jedem aⁱ existiert genau ein Minimalpolynom
Die Ordnung der Wurzel ai und die Zykluslänge n_minpol des zugehörigen Minimalpolynoms wird durch die Glg. (10) bestimmt. (ggT = größte gemeinsame Teiler)

n_minpol = (2^m – 1) / ggT(2^m – 1, i) (10)