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 3

2. Bestimmung der Gesamtheit der irreduzibeln Polynome

Die bisherigen Überlegungen zeigen, zur Bestimmung aller irreduzibeln Polynome m^ten Grades benötigt man lediglich:

ein primitives Polynom zur Generierung des Feldes GF(2^m)
h niedrigsten Wurzeln des irreduzibeln Polynoms, jeweils ein pro Polynom

Unter niedrigster Wurzel ist natürlich die Wurzel mit der niedrigsten Potenz der Wurzel gemeint. h stellt hier die Häufigkeit bzw. die Anzahl der irreduzibeln Polynome m^ten Grades dar. Zur vollständigen Bestimmung des Minimalpolynoms müssen alle konjugierten Wurzeln bekannt sein. Die konjugierten Wurzeln können wie bereits erwähnt aus Potenzen von niedrigster Wurzel aⁱ gewonnen werden. Schematisch werden sie mit der Darstellung (11) erfasst. Für l = 0 ergibt die niedrigste Wurzel aⁱ. Ab l = 1 bekommt man die konjugierten Wurzeln. l wird in Schritten von 1 inkrementiert bis (i * 2^l) modulo n ≠ i bleibt. n stellt die Zykluslänge des Generator-Polynoms dar.

a^{(i * 2^l) modulo n}, l = 0,1, 2… (11)

Für die Polynome 4^ten Grades gibt es 4 irreduzibeln Polynome. a stellt die niedrigste Wurzel des Generator-Polynoms dar. Mit der Darstellung gemäß (11) werden nun die konjugierten Wurzeln von a bestimmt. Die Gesamtheit der konjugierten Wurzel des Generator-Polynoms sind dann a, a², a⁴, a⁸. Die nächste unverbrauchte niedrigste Wurzel ist a³ und dient zur Bestimmung des nächsten Minimalpolynoms. Die konjugierten Wurzeln dieses Polynoms sind a³, a⁶, a¹², a⁹. Dieses Schema wird fortgeführt bis alle 4 Minimalpolynome ermittelt werden. Mit der Bestimmung des letzten Polynoms finden dann alle 14 (2^m – 2) Wurzeln a¹ bis a¹⁴ genau einmal den Einsatz, wie es auch aus der Tabelle IV erkannt wird.

3. BCH-Codes

3.1 Primitive BCH-Codes

Die Art und Weise wie die irreduzibeln Polynome entstehen ist ideal zur Bildung von BCH-Codes. Der BCH-Code hat die Eigenschaft, dass dieser d – 1 Wurzeln in Folge besitzt und seine Hamming-Distanz HD mindestens d beträgt.^[4] Wenn man die 4 Minimalpolynome m₁, m₃, m₅undm₇ aus der Tabelle IV sukzessiv miteinander multipliziert so entstehen 4 Polynome mit den Eigenschaften eines BCH-Codes. Der Code heißt primitiver BCH-Code, wenn zur Bildung des Codes, Minimalpolynome, abgeleitet mit einem primitiven Generator-Polynom wie z. B. 19h, den Einsatz finden. In der Tabelle V sind die primitiven BCH-Codes zusammengestellt. Das erste Polynom ist identisch mit dem Minimalpolynom m₁ 19h und besitzt zwei Wurzeln a¹ und a² in Folge mit einer Hamming-Distanz von 3. Das Produkt von m₁ und m₃ hat 4 aufeinander folgenden Wurzeln a¹, a², a³ und a⁴mit einer HD = 5. Der dritte Code ist das Produkt von m₁, m₃ und m₅ mit 6 Wurzeln, die in einer Reihe folgen. Die Hamming-Distanz beträgt somit 7. Letztendlich beinhaltet das Produkt von allen 4 Minimalpolynomen sämtliche 14 Wurzeln und hat eine HD von 15. Dieses Polynom stellt gemäß Glg. (5) ein Maximalpolynom dar. Alle diese Polynome haben eine Zykluslänge von 15. Durch die sukzessive Produktbildung wächst jedoch der Grad rb des BCH-Codes rasch an, wie es aus der Tabelle V deutlich wird. Somit nimmt natürlich mit den wachsenden Grad die Anzahl der Informationsbits k, die übertragen werden können, schnell ab. Für den ersten BCH-Code sind es 11 Bits und für das Maximalpolynom kann nur ein einziges Bit übertragen werden. Interessant ist zu merken, dass die Hamming-Distanz von BCH-Code b_i identisch ist mit der Potenz der niedrigsten Wurzel des nächsten Minimalpolynoms m_x in aufsteigender Folge.

Polynom		r_m	Wurzeln	BCH-Code b_i	r_b		HD	k I-Bits
m₁	19h	4	a¹, a², a⁴, a⁸	b₁ = m₁	19h	4	3	11
m₃	1Fh	4	a³, a⁶, a¹², a⁹	b₂ = m₁*m₃	117h	8	5	7
m₅	7h	2	a⁵, a¹⁰	b₃ = m₁m₃m₅	765h	10	7	5
m₇	13h	4	a⁷, a¹⁴, a¹³, a¹¹	b₄ = m₁m₃m₅*m₇	7FFFh	14	15	1
Tabelle V Die Primitiven BCH-Codes generiert mit dem Polynom 19h

3.2 Nichtprimitive BCH-Codes

Im Gegensatz zu primitiven BCH-Codes werden zur Generierung eines nichtprimitiven BCH-Codes die Minimalpolynome, abgeleitet mit einem nichtprimitiven Polynom, die selbst verständlich irreduzibel sein müssen, herangezogen. Die Zykluslänge n eines nichtprimitiven Polynoms m^ten Grades ist kleiner als 2^m – 1 und für ein beliebiges Element a des Feldes GF(n + 1) muss die Glg. (1), aⁿ = 1, erfüllt werden (siehe hierzu auch 2.4). Andererseits bildet das Feld GF(n + 1) eine Untermenge von GF(2^m). Für das Galois-Feld GF(2^m) muss jedoch die Glg. (2), a^(2^m – 1) = 1, erfüllt werden. Diese beiden Forderungen, dargestellt durch die Glg. (12), lassen sich nur dann in Einklang bringen, wenn n ein Teiler von 2^m - 1 ist.

aⁿ = a^(2^m – 1) = 1 (12)

Kurz gesagt heißt das, die Zykluslänge von nichtprimitiven Polynomen (irreduzibel aber nichtprimitiv) m^ten Grades muss ein Teiler von 2^m – 1 sein. Ist 2^m – 1 eine Primzahl, so gibt es keine nichtprimitiven Polynome m^ten Grades. Die Zykluslänge von 15 (m = 4) hat zwei Teiler 3 und 5. Nur die Zykluslänge 5 kann mit einem Polynom 4^ten Grades realisiert werden. Die Tabelle IV zeigt, dass ein nichtprimitives Polynom 1Fh eine Zykluslänge von 5 hat. Für das Polynom 1Fh gibt es nur einen BCH-Code, da das Polynom 1Fh bereits ein Maximalpolynom (n – 1)^ten Grades ist. Ein weiteres interessantes Beispiel stellt die Zykluslänge 23 dar. 23 ist Teiler von 2047 = 23 * 89. Ein Polynom 11^ten Grades mit einer Zykluslänge von 23 kann gemäß der Glg. (10) mit einem Minimalpolynom mit der Wurzel a⁸⁹ gebildet werden. Um das Polynom zu bestimmen benötigt man ein primitives Polynom 11^ten Grades mit dem zunächst das Galois-Feld GF(2¹¹) generiert wird. Das Minimalpolynom der Wurzel a⁸⁹ dieses Feldes kann dann als C75h bestimmt werden, wenn zur Generierung des Feldes das primitive Polynom A01h genommen wird. Die 11 konjugierten Wurzeln des Polynoms C75 sind:

a, a², a⁴, a⁸, a¹⁶, a⁹, a¹⁸, a¹³, a³, a⁶, a¹²

Das Polynom besitzt somit 4 Wurzeln a¹ bis a⁴ in der Folge. Die Hamming-Distanz dieses Polynoms muss demnach mindestens 5 betragen. Das Polynom C75h ist in der Literatur als Golay-Code mit einer Zykluslänge von 23 und mit einer Hamming-Distanz von 7 bekannt und findet große Beachtung.