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 5

5. Die wichtigen Eigenschaften der Polynome

Ein Polynom m^ten Grades wird durch die Glg. (13) dargestellt. In der Praxis werden die Polynome durch die linear rückgekoppelten Schieberegister dargestellt. Die lineare Rückkoppelung bewirkt, dass die Koeffizienten a_m und a₀ stets ungleich Null sind.

P_m (x) = a_m* x^m + a_{m – 1}* x^{m - 1}... a₁* x¹ + a₀, mit a_m = a₀= 1 (13)

Nachfolgend werden die wichtigsten Eigenschaften der Polynome aufgelistet:

Alle Polynome mit einem geraden Gewicht (Gewicht = Anzahl der Koeffizienten a_i ≠ 0) haben eine Wurzel x = 1 in GF(2) und sind durch x + 1 teilbar.
Irreduzibele Polynome haben immer ein ungerades Gewicht und eine ungerade Zykluslänge.
Irreduzibele Polynome können über dem GF(2^m) definiert werden und besitzen Wurzeln in GF(2^m). Ist die Wurzel eines irreduzibeln Polynoms gleichzeitig ein primitives Element von GF(2^m), so ist das betreffende Polynom primitiv mit der Zykluslänge von 2^m – 1.
Irreduzibele Polynome m^ten Grades mit der Zykluslänge kleiner als 2^m – 1 sind nichtprimitiv. Ihre Zykluslänge ist ein Teiler von 2^m – 1.
Die Zykluslänge von irreduzibeln Polynomen m^ten Grades ist 2^m – 1 (primitiv) oder Teiler davon (nichtprimitiv).
Es existieren keine nichtprimitiven Polynome m^ten Grades, falls 2^m – 1 eine Primzahl ist.
Die Häufigkeit Hp(m) von primitiven Polynomen m^ten Grades ≤ (2^m – 2)/m. Das Produkt von sämtlichen irreduzibeln Polynomen m^ten Grades wird durch das Maximalpolynom (2^m – 2)^ten Grades dargestellt. Damit ist Hp(m) * m ≤ 2^m – 2. Die Gleichheit wird erreicht, wenn 2^m - 1 eine Primzahl darstellt.

6. Anwendungsbeispiele

Bei einem System Entwurf steht relativ früh, die Anzahl der Informationsbits, die verarbeitet werden müssen, fest. Die Sicherheitsanforderungen an das System sind ebenfalls schon am Anfang bekannt. Mit diesen zwei wichtigen Eckdaten kann dann rasch ermittelt werden, wie viele Bits an Redundanz (Anzahl des CRC-Bits) benötigt werden. Im Blatt 5 der Datei „BCH-Code.pdf“ sind sämtliche BCH-Codes bis zu einer Zykluslänge von 257 zusammengefasst. Im Blatt 6 dieser Datei sind sie nach aufsteigender Anzahl k der Informationsbits aufgelistet. Anhand von zwei Beispielen soll nun demonstriert werden, wie schnell und effektiv man ein passende Polynom finden kann.

Beispiel 1: Es sollen 12 Bytes, 96 Bits gesichert werden. Sicherheitstechnisch ist eine mindest Hamming-Distanz von 7 bis 9 erwünscht. Mit dieser Information öffnet man das Blatt 6 und stellt fest, dass für k = 96 es nur einen Eintrag mit einem Polynom 95^ten Grades (95-Bit Redundanz) und einer Hamming-Distanz von 7 in der Zeile 454 gibt. Dieser Aufwand ist natürlich sehr hoch. Durch aufwärts scrollen der Datei stellt man jedoch fest, dass noch weitere zwei Polynome mit 28^ten bzw. 21^ten Grades mit einer Hamming-Distanz von 9 bzw. 7 existieren. Beide Polynome können mindestens 99 Informationsbits verarbeiten und gehören zu den primitiven BCH-Codes. Beide Polynome können mit einem primitiven Polynom 7^ten Grades gemäß den Ausführungen im Abschnitt 4.1 generiert werden.

Beispiel 2: In einem zweiten Fall soll nur 1 Byte, also 8 Bits verarbeitet werden, jedoch wird dafür eine möglichst hohe Hamming-Distanz gefordert. Ab Zeile 77 im Blatt 6 der besagten Datei sind vier Einträge mit k = 8. Es ist möglich eine Hamming-Distanz von 45 mit einem Polynom 97^ten Grades zu realisieren. Dieser Aufwand ist verhältnismäßig hoch. Man findet jedoch in der Zeile 83 ein Polynom 42^ten Grades mit einer Hamming-Distanz von 19.Dieses BCH-Code kann mit einem nichtprimitiven Polynom 8^ten Grades und einer Zykluslänge von 51 generierte werden Dieses Polynom 5167036C6A1h fand bereits die Erwähnung im Blatt 4, Zeile 57. Das Polynom ist in der Lage bis zu 18 Bitfehlern zu erkennen bzw. 9-Bit Fehlerkorrektur durch zu führen.

Im Blatt 7 und 8 der Excel-Datei sind dann zum Schluss die BCH-Codes bis zu einer Zykluslänge von 1095 aufgelistet. Es wurden dabei praxisorientiert nur die Codes bis zu einem maximalen Polynomgrad von 64 und k > 1 berücksichtigt. Diese Daten können natürlich auch nach der Hamming-Distanz bzw. Polynomgrad sortiert werden und liefern demnach sehr aufschlussreiche Informationen und Entscheidungshilfen.