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 langeren Nutzer-Datenwort.

Definition [ Bearbeiten | Quelltext bearbeiten ]

Sei ${\displaystyle \beta }$ eine primitive ${\displaystyle n}$-te Einheitswurzel in einem Erweiterungskorper des endlichen Korpers ${\displaystyle \mathbb {F} _{q}}$. Seien ${\displaystyle l,\delta \in \mathbb {N} }$, ${\displaystyle \delta \geq 2}$, und C der zyklische Code, dessen Generatorpolynom das Produkt der verschiedenen Minimalpolynome von ${\displaystyle \beta ^{l},\dots ,\beta ^{l+\delta -2}}$ ist. (Dann besteht C also aus allen ${\displaystyle f\in \mathbb {F} _{q}[x]/(x^{n}-1)}$ mit ${\displaystyle f(\beta ^{l})=\dots =f(\beta ^{l+\delta -2})=0}$), dann nennt man C einen BCH-Code mit geplantem Minimalabstand ${\displaystyle \delta }$, wobei C den Minimalabstand ${\displaystyle d\geq \delta }$ hat.

Fur den Fall ${\displaystyle l=1}$ spricht man von einem BCH-Code im gewohnlichen Sinn .

Falls ein m existiert mit ${\displaystyle n=q^{m}-1}$ (d. h. ${\displaystyle \beta }$ ist ein Erzeuger der multiplikativen Gruppe eines Korpers ${\displaystyle \mathbb {F} _{q^{m}}}$), so spricht man von einem primitiven BCH-Code.

Ein Reed-Solomon-Code ist ein primitiver BCH-Code im gewohnlichen Sinn, fur den ${\displaystyle n=q-1}$ gilt. Hier sind die Minimalpolynome also von der Form ${\displaystyle x-\beta ^{i}\in \mathbb {F} _{q}[x],i=1,\ldots ,\delta -1}$.

Einsatzbereiche [ Bearbeiten | Quelltext 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 zunachst BCH-, dann LDPC-kodiert. Der BCH korrigiert hierbei die Restfehlerbits, die nach der LDPC-Korrektur verbleiben konnen.
• Die Funkruf-Protokolle POCSAG und FLEX verwenden den BCH(31,21)-Code

BCH(15, 7, 5) [ Bearbeiten | Quelltext bearbeiten ]

Als Beispiel sei ein ${\displaystyle (n=15,k=7,d_{\text{min}}=5)}$ BCH-Code gegeben. Die Parameter ${\displaystyle n,k,d_{\text{min}}}$ sind dabei wie folgt zu interpretieren. Der Code erzeugt Codeworter mit einer Lange von ${\displaystyle n=15}$ Bits , wovon ${\displaystyle k=7}$ Bits die kodierte Information enthalten und ${\displaystyle n-k}$ Bits Redundanz zur Korrektur von Ubertragungsfehlern dienen. Der Parameter ${\displaystyle d_{min}}$ gibt die minimale Hammingsdistanz des Codes an.

Es gilt: Es konnen Ubertragungsfehler von bis zu ${\displaystyle d_{\mathrm {min} }-1}$ Einzelbitfehlern erkannt werden, es konnen Ubertragungsfehler von bis zu ${\displaystyle (d_{\mathrm {min} }-1)/2}$ Einzelbitfehlern korrigiert werden. Bundelfehler von bis zu ${\displaystyle f_{\mathrm {b} }\leq k}$ Bits werden erkannt.

Ein BCH-Code wird in der Regel durch sein Generatorpolynom beschrieben. Im gegebenen Beispiel lautet das Generatorpolynom ${\displaystyle g(x)=x^{8}+x^{7}+x^{6}+x^{4}+1}$. Die Anzahl der Prufbits ${\displaystyle n-k}$ lasst sich ubrigens immer aus dem Generatorpolynom ablesen. Es gilt ${\displaystyle n-k=\operatorname {Grad} (g)}$.

Fur die Dimension des Codes gilt: ${\displaystyle \dim C=n-\operatorname {Grad} (g)=15-8=7=k}$.

Kodieren [ Bearbeiten | Quelltext bearbeiten ]

Zum Kodieren mit BCH-Kodes konnen das Multiplikations- oder das Divisionsverfahren verwendet werden.

Multiplikationsverfahren [ Bearbeiten | Quelltext bearbeiten ]

Beim Multiplikationsverfahren wird das zu kodierende Quellkodewort aus ${\displaystyle l=7}$ Bits einfach mit dem Generatorpolynom des BCH-Codes multipliziert. Es gilt: ${\displaystyle a(x)=a^{*}(x)\cdot g(x)}$. Dabei steht ${\displaystyle a(x)}$ fur das kodierte Kanalkodewort, ${\displaystyle a^{*}(x)}$ steht fur das unkodierte Quellkodewort. Die Multiplikation kann sowohl mit Polynomen als auch mit einer binaren Darstellung der Polynome durchgefuhrt werden.

Hier wollen wir ein Beispiel in binarer Darstellung durchrechnen:

Das gegebene Generatorpolynom ${\displaystyle g(x)=x^{8}+x^{7}+x^{6}+x^{4}+1}$ lasst sich binar als die Folge ${\displaystyle g=111010001}$ darstellen (die Folge ist dabei zu interpretieren als ${\displaystyle 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 ${\displaystyle a^{*}=1001011}$ bzw. ${\displaystyle 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, mussen wir jetzt also einfach ${\displaystyle a^{*}}$ mit ${\displaystyle g}$ multiplizieren:

${\displaystyle a=a^{*}\cdot g=1001011\cdot 111010001=111100010111011}$

Divisionsverfahren [ Bearbeiten | Quelltext bearbeiten ]

Das Divisionsverfahren ermoglicht es zu einem gegebenen Quellkodewort genau jenes Kanalkodewort zu ermitteln, welches das gegebene Quellkodewort als Prafix hat, weswegen man sagt, das Verfahren liefert einen systematischen Kode. Fur ein gegebenes Generatorpolynom ${\displaystyle g}$ und ein Quellkodewort ${\displaystyle a^{*}}$ errechnet man das zugehorige Kanalkodewort ${\displaystyle a}$ nach Divisionsverfahren wie folgt:

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

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

${\displaystyle {\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 ${\displaystyle a=100101100000000-01010111=\underbrace {1001011} _{a^{*}}01010111}$.

Dekodieren [ Bearbeiten | Quelltext bearbeiten ]

Die Dekodierung kann mittels verschiedener Verfahren nach folgendem Muster erfolgen:

1. Bestimmung des Syndromwertes (Divisionsrest), indem das empfangene Kanalkodewort ${\displaystyle a(x)}$ durch das Generatorpolynom ${\displaystyle g(x)}$ 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

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

Beispiel [ Bearbeiten | Quelltext bearbeiten ]

Wenn das Codewort vom obigen Beispiel ohne Fehler ubertragen wird, bleibt als Rest der Division ${\displaystyle a:g}$ Null. Die Division in Koeffizienten-Schreibweise lautet dann:

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

Wurde das Codewort wahrend der Ubertragung verfalscht, beispielsweise zu 10 1 101 01 1010111 (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 | Quelltext 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 .