BCH-Code

fehlerkorrigierende Codes in der digitalen Signalverarbeitung

BCH-Codes (Bose-Chaudhuri-Hocquenghem-Codes) sind zyklische fehlerkorrigierende Codes, welche in der digitalen Signalverarbeitung und Datenspeicherung eingesetzt werden. Der Name BCH ergibt sich aus den Anfangsbuchstaben der drei Wissenschaftler, die diesen Code entwickelt haben: R. C. Bose, D. K. Ray-Chaudhuri und A. Hocquenghem (1908–1990). BCH-Codes korrigieren mehrere 1-Bit-Fehler in einem längeren Nutzer-Datenwort.

Definition

Bearbeiten

Sei   eine primitive  -te Einheitswurzel in einem Erweiterungskörper des endlichen Körpers  . Seien  ,  , und C der zyklische Code, dessen Generatorpolynom das Produkt der verschiedenen Minimalpolynome von   ist. (Dann besteht C also aus allen   mit  ), dann nennt man C einen BCH-Code mit geplantem Minimalabstand  , wobei C den Minimalabstand   hat.

Für den Fall   spricht man von einem BCH-Code im gewöhnlichen Sinn.

Falls ein m existiert mit   (d. h.   ist ein Erzeuger der multiplikativen Gruppe eines Körpers  ), so spricht man von einem primitiven BCH-Code.

Ein Reed-Solomon-Code ist ein primitiver BCH-Code im gewöhnlichen Sinn, für den   gilt. Hier sind die Minimalpolynome also von der Form  .

Einsatzbereiche

Bearbeiten
  • Die sogenannten Reed-Solomon-Codes sind spezielle BCH-Codes und werden z. B. zur Fehlerkorrektur auf Audio-CDs eingesetzt.
  • Der BCH-Code wird auch bei der Sicherung der TPS-Daten im DVB-T-Standard genutzt.
  • Der BCH-Code wird zur Sicherung der Nutzdaten in den DVB-S-Standards genutzt. Die Daten werden zunächst BCH-, dann LDPC-kodiert. Der BCH korrigiert hierbei die Restfehlerbits, die nach der LDPC-Korrektur verbleiben können.
  • Die Funkruf-Protokolle POCSAG und FLEX verwenden den BCH(31,21)-Code

BCH(15, 7, 5)

Bearbeiten

Als Beispiel sei ein   BCH-Code gegeben. Die Parameter   sind dabei wie folgt zu interpretieren. Der Code erzeugt Codewörter mit einer Länge von   Bits, wovon   Bits die kodierte Information enthalten und   Bits Redundanz zur Korrektur von Übertragungsfehlern dienen. Der Parameter   gibt die minimale Hammingsdistanz des Codes an.

Es gilt: Es können Übertragungsfehler von bis zu   Einzelbitfehlern erkannt werden, es können Übertragungsfehler von bis zu   Einzelbitfehlern korrigiert werden. Bündelfehler von bis zu   Bits werden erkannt.

Ein BCH-Code wird in der Regel durch sein Generatorpolynom beschrieben. Im gegebenen Beispiel lautet das Generatorpolynom  . Die Anzahl der Prüfbits   lässt sich übrigens immer aus dem Generatorpolynom ablesen. Es gilt  .

Für die Dimension des Codes gilt:  .

Kodieren

Bearbeiten

Zum Kodieren mit BCH-Kodes können das Multiplikations- oder das Divisionsverfahren verwendet werden.

Multiplikationsverfahren

Bearbeiten

Beim Multiplikationsverfahren wird das zu kodierende Quellkodewort aus   Bits einfach mit dem Generatorpolynom des BCH-Codes multipliziert. Es gilt:  . Dabei steht   für das kodierte Kanalkodewort,   steht für das unkodierte Quellkodewort. Die Multiplikation kann sowohl mit Polynomen als auch mit einer binären Darstellung der Polynome durchgeführt werden.

Hier wollen wir ein Beispiel in binärer Darstellung durchrechnen:

Das gegebene Generatorpolynom   lässt sich binär als die Folge   darstellen (die Folge ist dabei zu interpretieren als  ).

Als zu kodierendes Quellkodewort dient in unserem Beispiel   bzw.  .

Um das kodierte Kanalkodewort zu erhalten, müssen wir jetzt also einfach   mit   multiplizieren:

 

Divisionsverfahren

Bearbeiten

Das Divisionsverfahren ermöglicht es zu einem gegebenen Quellkodewort genau jenes Kanalkodewort zu ermitteln, welches das gegebene Quellkodewort als Präfix hat, weswegen man sagt, das Verfahren liefert einen systematischen Kode. Für ein gegebenes Generatorpolynom   und ein Quellkodewort   errechnet man das zugehörige Kanalkodewort   nach Divisionsverfahren wie folgt:

 

Das heißt, man muss den Rest der Polynom-Division   ermitteln und diesen von   subtrahieren. Am Beispiel von oben:

 

Die Division in Koeffizienten-Schreibweise lautet dann:

 100101100000000 : 111010001 = 1100111
  111111010
   001010110
    010101100
     101011000
      100010010
       110000110
        --------
        01010111


Damit gilt  .

Dekodieren

Bearbeiten

Die Dekodierung kann mittels verschiedener Verfahren nach folgendem Muster erfolgen:

  1. Bestimmung des Syndromwertes (Divisionsrest), indem das empfangene Kanalkodewort   durch das Generatorpolynom   dividiert wird. Ist der Rest ungleich 0 liegen ein oder mehrere Fehler vor.
  2. Bestimmen des Fehlerpolynoms.
  3. Bestimmung der Nullstellen des Fehlerpolynoms zur Ermittlung der Fehlerpositionen im Codewort.
  4. Bestimmung der Fehlerwerte

Übliche Algorithmen zur Dekodierung von BCH-Codes sind der Berlekamp-Massey-Algorithmus oder der Peterson-Gorenstein-Zierler-Algorithmus.

Beispiel

Bearbeiten

Wenn das Codewort vom obigen Beispiel ohne Fehler übertragen wird, bleibt als Rest der Division   Null. Die Division in Koeffizienten-Schreibweise lautet dann:

<!-- Berechnungen können hier nachgerechnet werden: http://www.flechtmann.net/crc/index.php -->
  100101101010111 : 111010001 = 1100111
   111010001
    001010011
     010100110
      111010001
       100111001
        111010001
         --------
         '''00000000'''

Würde das Codewort während der Übertragung verfälscht, beispielsweise zu 101101011010111 (Stellen 3, 7 und 8), ergibt sich nach der Polynomdivision ein von 0 verschiedenes Fehlersyndrom:

  101101011010111 : 111010001 = 1111100
   101110100
    101001011
     100110100
      111001011
       000110101
        001101011
         --------
         '''01101001'''

Literatur

Bearbeiten
  • Shu Lin, Daniel J. Costello: Error Control Coding. Fundamentals and applications. 2. Auflage. Prentice Hall, Upper Saddle River NJ 2004, ISBN 0-13-042672-5.
  • Robert H. Morelos-Zaragoza: The Art of Error Correcting Coding. 2. Auflage. Wiley, New York NY 2006, ISBN 0-470-01558-6.