BCH-Code zum Anfassen

7. Zusammenfassung

Bisher wurde gezeigt, dass sich ein geeigneter BCH-Code in vier Schritten problemlos bestimmen lässt.

1. Ausgehend von einer Zykluslänge n (Wahl einer geeigneten Zykluslänge aus der Datei BCH-Code.pdf) wird zunächst ein fiktiver Code, bestehend aus Produkt von l Minimalpolynomen, erzeugt.
2. Zur Bestimmung von Minimalpolynomen muss dann nur ein einziges irreduzibeles Polynom mit der Zykluslänge n bekannt sein. Der Grad dieses Polynoms ist identisch mit dem ersten Minimalpolynom aus der Liste der fiktiven Polynome des vorigen Schrittes.
3. Berechnung von ersten l Minimalpolynomen mit Hilfe der bekannten Wurzeln dieser Polynome aus der Liste von fiktiven Polynomen.
4. Die Bildung des Produkts von l Minimalpolynomen.

Für diesen Zweck wurden drei Programme entwickelt. Das Programm „Ber_wur“ erzeugt aus einer Eingabe n, die sämtlich möglichen fiktiven BCH-Codes der Länge n. Als Beispiele dienen die ersten 3 Blätter der Datei „BCH-Code.pdf“. Das Programm benötigt 10 Sekunden zur Berechnung von 4114 fiktiven Polynomen (n = 65535). Das zweite Programm „Ber_minpol_wur“ berechnet das Minimalpolynom der Wurzel aⁱ und benötigt als Eingabe ein Minimalpolynom und die Potenz der Wurzel des Minamalpolynoms, das berechnet werden soll. Dieses Programm bildet eigentlich den Kern dieses Verfahrens und ist relativ komplex. Das Programm ist extrem Arbeitsspeicherintensiv und benötigt zur Bildung von einem Galois-Feld GF(2²¹) für die Polynome 21^ten Grades 150 Sekunden (Arbeitsspeicherbedarf 3,2 GB). Danach können beliebig viele Minimalpolynome blitzschnell berechnet werden. Das Programm ist kurzfristig entstanden und hat noch Optimierungspotentiale. Als Ziel ist die Bearbeitung von 32-Bit Polynomen angestrebt. Die Rechenzeit Angaben sind für eine 3,6 GHz CPU. Das dritte Programm ist relativ einfach und bildet das Produkt von l Minimalpolynomen.

Das hier vorgestellte Verfahren ist sehr effizient und erlaubt eine extrem schnelle Suche mit anschließender Bestimmung eines geeigneten Polynoms mit den gewünschten Eigenschaften. Das Ergebnis erscheint im ersten Augenblick etwas enttäuschend, da das gefundene Polynom einen überdurchschnittlich hohen Grad aufweist. Sicherlich findet man gleichwertige Polynome mit einem geringeren Grad als eines BCH-Codes. Dies erfordert jedoch eine intensive Nachforschung von mehreren Monaten wenn nicht sogar Jahren. ^[5] Dennoch bietet das vorgestellte Verfahren zwei entscheidende Vorteile, die nicht außer Acht gelassen werden sollten.

1. Der Systemingenieur bekommt das für seine Bedürfnisse passende Polynom zum Nulltarif. So kann er seine Wertvolle Zeit zur optimalen Gestaltung des Gesamtprojektes sinnvoll einbringen. Natürlich kostet die Hardware ein Paar Cents mehr aber dafür kann die rechtszeitige Einführung des Produktes auf den Markt beschleunigt werden. Der Faktor „Time to Market“ holt die betätigte Investition mehrfach zurück.
2. Das Verfahren ist sehr transparent und leicht nachvollziehbar. Die Prüfung des Produktes durch die Zertifizierungsbehörde wird dadurch wesentlich erleichtert. Das Produkt findet so schnell die breite Akzeptanz.

Zum Schluss soll noch bemerkt werden, dass der technologische Fortschritt zunehmend höhere Integrationsdichte ermöglicht. Der Einsatz von 64-Bit CRC gehört schon lange zur gängigen Praxis. Somit dürfte die Realisierung von 100 oder Mehr-Bit CRC kein Problem darstellen. Viel mehr ist es eine Herausforderung an Asic-Designer. Das Verfahren eignet sich besonders gut für die sicherheitsrelevanten Applikationen, wo wenige Bytes zum Einsatz kommen. Für diese Daten wird jedoch der Nachweis einer extrem geringen Restfehlerwahrscheinlichkeit gefordert. Es kann nämlich mit einem Polynom 98^ten bzw. 105^ten Grades 29 bzw. 22 Informationsbits mit einer Hamming-Distanz von 43 bzw. 47 gesichert werden. Die exakte Berechnung der Restfehlerwahrscheinlichkeit mit so hoher Hamming-Distanz ist nicht mehr trivial und erfordert große mathematische Sorgfalt.

1. BCH-Code zum Anfassen
2. 1.2 Erweiterung des binären Galois-Feldes zum GF(2m)
3. 4. Ein fiktiver BCH-Code
4. 2. Bestimmung der Gesamtheit der irreduzibeln Polynome
5. 1.4 Wurzeln des Polynoms
6. 5. Die wichtigen Eigenschaften der Polynome
7. 7. Zusammenfassung

Das könnte Sie auch interessieren

Analyseverfahren spart Rechenzeit

Polynome schneller auf Primitivität prüfen