BCH-Code

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. BCH-Codes korrigieren mehrere 1-Bit-Fehler in einem längeren Nutzer-Datenwort.

Inhaltsverzeichnis

Definition

Sei β eine primitive n-te Einheitswurzel in einem Erweiterungskörper des endlichen Körpers \mathbb F_q. Seien  l,\delta \in \mathbb{N}, \delta \ge 2, und C der zyklische Code dessen Generatorpolynom das Produkt der verschiedenen Minimalpolynome \beta^l, \dots \beta^{l+\delta-2} ist. (Dann besteht C also aus allen f \in \mathbb F_q[x]/(x^n-1) mit f(\beta^l) = \dots = f(\beta^{l+\delta-2})=0 ), dann nennt man C einen BCH-Code mit geplantem Minimalabstand δ. Beachte, dass C Minimalabstand d \ge \delta hat.

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

Falls ein m existiert mit n = qm − 1 (d.h. β ist ein Erzeuger der multiplikativen Gruppe eines Körpers \mathbb F_{q^m}), so spricht man von einem primitiven BCH-Code.

Ein Reed-Solomon-Code ist ein primitiver BCH-Code im gewöhnlichen Sinn, für den n = q − 1 gilt.

Einsatzbereiche

  • 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.

Beispiel BCH(15, 7, 5)

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

Es gilt: Es können Übertragungsfehler von bis zu dmin − 1 Einzelbitfehlern erkannt werden, es können Übertragungsfehler von bis zu (dmin − 1) / 2 Einzelbitfehlern korrigiert werden. Bündelfehler von bis zu f_\mathrm{b} \le k Bits werden erkannt.

Ein BCH-Code wird in der Regel durch sein Generatorpolynom beschrieben. Im gegebenen Beispiel lautet das Generatorpolynom g(x) = x8 + x7 + x6 + x4 + 1. Die Anzahl der Prüfbits k lässt sich übrigens immer aus dem Generatorpolynom ablesen. Es gilt k = \operatorname{Grad}(g).

Kodieren

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

Multiplikationsverfahren

Beim Multiplikationsverfahren wird das zu kodierende Quellkodewort aus l = 7 Bits einfach mit dem Generatorpolynom des BCH-Codes multipliziert. Es gilt: a(x) = a^*(x) \cdot g(x). Dabei steht a(x) für das kodierte Kanalkodewort, a*(x) 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 g(x) = x8 + x7 + x6 + x4 + 1 lässt sich binär als die Folge g = 111010001 darstellen (die Folge ist dabei zu interpretieren als g(x) = 1 \cdot x^8 + 1 \cdot x^7 + 1 \cdot x^6 + 0 \cdot x^5 + 1 \cdot x^4 + 0 \cdot x^3 + 0 \cdot x^2 + 0 \cdot x^1 + 1 \cdot x^0).

Als zu kodierendes Quellkodewort dient in unserem Beispiel a * = 1001011 bzw. a^*(x) = 1 \cdot x^6 + 0 \cdot x^5 + 0 \cdot x^4 + 1 \cdot x^3 + 0 \cdot x^2 + 1 \cdot x^1 + 1 \cdot x^0.

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

a = a^* \cdot g = 1001011 \cdot 111010001 = 111100010111011

Divisionsverfahren

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 g und ein Quellkodewort a * errechnet man das zugehörige Kanalkodewort a nach Divisionsverfahren wie folgt:

 a := a^* \cdot x^k - \left( a^* \cdot x^k \right) \bmod g

Das heißt, man muss den Rest der Polynom-Division  \left( a^* \cdot x^k \right) : g ermitteln und diesen von  a^* \cdot x^k subtrahieren. Am Beispiel von oben:

 \begin{array}{ccccc} g & = & x^8 + x^7 + x^6 + x^4 + 1 & \mathrel{\widehat{=}} & 111010001 \\ a^* & = & x^6 + x^3 + x + 1 & \mathrel{\widehat{=}} & 1001011 \\ a^* \cdot x^k & = & x^{14} + x^{11} + x^9 + x^8 & \mathrel{\widehat{=}} & 100101100000000 \end{array}


Die Division in Koeffizienten-Schreibweise lautet dann:

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

Damit gilt  a = 100101100000000 - 01010111 = \underbrace{1001011}_{a^*}01010111 .

Dekodieren

Die Dekodierung kann mittels verschiedener Verfahren nach folgenden Muster erfolgen:

  1. Bestimmung der Syndromwertes (Divisionsrest) indem das empfangene Kanalkodewort a(x) durch das Generatorpolynom g(x) dividiert wird. Ist der Rest ungleich 0 liegen ein oder mehrere Fehler vor.
  2. Bestimmen des Fehlerpolynoms.
  3. Bestimmung der Wurzeln 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.

Literatur

  • 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.

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • BCH code — In coding theory the BCH codes form a class of parameterised error correcting codes which have been the subject of much academic attention in the last fifty years. BCH codes were invented in 1959 by Hocquenghem, and independently in 1960 by Bose… …   Wikipedia

  • BCH — and BCh may refer to: * BCH code, in coding theory, a code by Bose, Chaudhuri, and Hocquenghem * Bachelor of Surgery, a component of an undergraduate medical degree in some countries * Baker Campbell Hausdorff formula, in mathematics and Lie… …   Wikipedia

  • BCH — ist die Abkürzung für: Bose Chaudhuri Hocquenghem Codes (BCH Code), eine Gruppe zyklischer fehlerkorrigierender Blockcodes in der Kodierungstheorie Bulletin de Correspondance Hellénique, eine Fachzeitschrift der Altertumswissenschaften Flughafen… …   Deutsch Wikipedia

  • Code Cyclique — En mathématiques et en informatique, un code cyclique est un code correcteur linéaire. Ce type de code possède non seulement la capacité de détecter les erreurs, mais aussi de les corriger sous reserve d altérations modérée. Les mathématiques… …   Wikipédia en Français

  • Code De Hamming — Un code de Hamming est un code correcteur linéaire. Il permet la détection et la correction automatique d une erreur si elle ne porte que sur une lettre du message. Un code de Hamming est parfait, ce qui signifie que pour une longueur de code… …   Wikipédia en Français

  • Code de hamming — Un code de Hamming est un code correcteur linéaire. Il permet la détection et la correction automatique d une erreur si elle ne porte que sur une lettre du message. Un code de Hamming est parfait, ce qui signifie que pour une longueur de code… …   Wikipédia en Français

  • Bch — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. {{{image}}}   Sigles d une seule lettre   Sigles de deux lettres > Sigles de trois lettres …   Wikipédia en Français

  • Code Correcteur — Un code correcteur est une technique de codage basée sur la redondance. Elle est destinée à corriger les erreurs de transmission d une information (plus souvent appelée message) sur une voie de communication peu fiable. La théorie des codes… …   Wikipédia en Français

  • Code MDS — Code parfait et code MDS Un code parfait (ou code MDS, pour maximum distance séparable) est un concept de la théorie des codes et qui traite plus spécifiquement des codes correcteurs. Un code correcteur est un code permettant au récepteur de… …   Wikipédia en Français

  • Code Parfait Et Code MDS — Un code parfait (ou code MDS, pour maximum distance séparable) est un concept de la théorie des codes et qui traite plus spécifiquement des codes correcteurs. Un code correcteur est un code permettant au récepteur de détecter ou de corriger des… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”