Praktische Bestimmung von Polynomen mit beliebig großer Hamming-Distanz BCH-Code zum Anfassen

Seit der Entdeckung des BCH-Codes durch Hocquenghem 1959, und Bose und Chaudhuri 1960 wurde dieser sehr intensiv erforscht. Die umfangreiche Literatur zu diesem Thema ist leider sehr stark mathematisch orientiert. Die Thematik lässt sich jedoch in relativ einfacher und verständlicher Form darstellen. Es wurde hier der Versuch unternommen, diesen hoch interessanten Code so einfach wie möglich für einen Nicht-Mathematiker darzustellen.

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

Seit der Entdeckung des BCH-Codes durch Hocquenghem 1959, und Bose und Chaudhuri 1960 wurde dieser sehr intensiv erforscht. Die umfangreiche Literatur zu diesem Thema ist leider sehr stark mathematisch orientiert. Die Thematik lässt sich jedoch in relativ einfacher und verständlicher Form darstellen. Es wurde hier der Versuch unternommen, diesen hoch interessanten Code so einfach wie möglich für einen Nicht-Mathematiker darzustellen.

INHALT:
1. Mathematische Grundlagen 
    1.1 Galois-Felder GF(p)
    1.2 Erweiterung des binären Galois-Feldes zum GF(2m) 
    1.3 Bestimmung des Feldes GF(24) 
    1.4 Wurzeln des Polynoms 
        1.4.1 Konjugierte Wurzeln 
        1.4.2 Deutung der Wurzeln 
2. Bestimmung der Gesamtheit der irreduzibeln Polynome 
3. BCH-Codes 
    3.1 Primitive BCH-Codes 
    3.2 Nichtprimitive BCH-Codes 
4. Ein fiktiver BCH-Code 
5. Die wichtigen Eigenschaften der Polynome 
6. Anwendungsbeispiele 
7. Zusammenfassung 
8. Literatur

Um die Zusammenhänge vollständig zu verstehen und um den Code erfolgreich anwenden zu können sind jedoch die Grundkenntnisse der binären Algebra unentbehrlich. Es wird daher der mathematische Grundgedanke in kurzer aber anschaulicher Form, ohne jedoch einen Anspruch auf die mathematische Perfektion zu haben, zusammengefasst. Der Leser wird am Ende des Aufsatzes feststellen, dass er ein Polynom mit einer beliebig großen Hamming-Distanz relativ schnell und mit sehr wenig Aufwand bestimmen kann.

1. Mathematische Grundlagen

1.1 Galois-Felder GF(p)

Wenn ein Element eines Galois-Feldes q verschiedene Werte annehmen kann, so wird das Feld mit GF(q) bezeichnet und beinhaltet q Elemente. Für die Elemente des Feldes sind zwei Operationen, Addition und Multiplikation zu definieren. Bezüglich dieser Operationen müssen eine Reihe von Regeln, wie Assoziativ-, Kommutativ- bzw. Distributiv-Gesetze, eingehalten werden. Über diese und andere Regeln wird hier nicht näher eingegangen. Der interessierte Leser wird auf die Literatur verwiesen. [1], [2] Wesentlich ist, dass das Ergebnis der Operation selbst wieder zum Feld gehört. Ist q eine Primzahl p, so bilden die p Elemente {0, 1, 2, …, p-1} bezüglich der Addition und Multiplikation modulo p ein Galois-Feld GF(p). Für solche Felder kann die Existenz eines primitiven Elementes, dessen Potenzen die sämtlichen Elemente ungleich Null des Feldes generieren, nachgewiesen werden. [1] Für p = 7 gibt es zwei primitive Elemente 3 und 5 mit der folgenden Zuordnung:

50 = 1, 51 = 5, 52 = 4, 53 = 6, 54 = 2, 55 = 3, 56 = 1

Die Addition modulo p von zwei Elementen lässt sich relativ einfach durchführen. Die Multiplikation modulo p kann mit Hilfe der Potenzen des primitiven Elementes berechnet werden. Hier für wird die Potenz des Produktes modulo p – 1 eingesetzt. Z. B. 3 x 6 = 4.

3 * 6 = 55 x 53 = 58 modulo 6 = 52 = 4

Wenn für ein Element a ≠ 0 die kleinste Ganzzahl n die Beziehung (1) erfüllt, so heißt n die Ordnung des Elementes a.

an = 1 (1)

Regel 1: Primitive Elemente eines Galois-Feldes GF(p) haben die Ordnung p - 1.
Demnach kann das Element 2 nicht primitiv sein, da 23 = 1 (Ordnung = 3) ist.

Das binäre Galois-Feld GF(2) mit den Elementen 0 und 1 findet in der Praxis einen breiten Einsatz, da in der Technik die binäre Logik dominiert. In der Tabelle I und II sind die Regeln von modulo 2 Additionen bzw. modulo 2 Multiplikation definiert.

+01
001
110
Tabelle I modulo 2 Addition

*01
000
101
Tabelle II modulo 2 Multiplikation