imported>Wdwd: rev, Änderung bitte kommentieren

2026-02-27T18:09:10Z

rev, Änderung bitte kommentieren

Neue Seite

'''BCH-Codes''' (Bose-Chaudhuri-Hocquenghem-Codes) sind [[Zyklischer Code|zyklische]] [[Vorwärtsfehlerkorrektur|fehlerkorrigierende]] [[Kanalkodierung|Codes]], welche in der [[Digitale Signalverarbeitung|digitalen Signalverarbeitung]] und [[Datenspeicher]]ung eingesetzt werden. Der Name BCH ergibt sich aus den Anfangsbuchstaben der drei Wissenschaftler, die diesen Code entwickelt haben: [[Raj Chandra Bose|R. C. Bose]], [[D. K. Ray-Chaudhuri]] und [[Alexis Hocquenghem|A. Hocquenghem]] (1908–1990). BCH-Codes korrigieren mehrere 1-Bit-Fehler in einem längeren Nutzer-Datenwort.

== Definition ==
Sei <math>\beta</math> eine primitive <math>n</math>-te [[Einheitswurzel]] in einem [[Körpererweiterung|Erweiterungskörper]] des [[Endlicher Körper|endlichen Körpers]] <math>\mathbb F_q</math>. Seien <math> l,\delta \in \mathbb{N}</math>, <math>\delta \ge 2</math>, und C der zyklische Code, dessen [[Generatorpolynom]] das Produkt der verschiedenen [[Minimalpolynom]]e von <math>\beta^l, \dots, \beta^{l+\delta-2}</math> ist. (Dann besteht C also aus allen <math>f \in \mathbb F_q[x]/(x^n-1)</math> mit <math>f(\beta^l) = \dots = f(\beta^{l+\delta-2})=0</math>), dann nennt man C einen '''BCH-Code''' mit '''geplantem Minimalabstand''' <math>\delta</math>, wobei C den Minimalabstand <math>d \ge \delta</math> hat.

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

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

Ein [[Reed-Solomon-Code]] ist ein primitiver BCH-Code im gewöhnlichen Sinn, für den <math>n = q - 1</math> gilt. Hier sind die Minimalpolynome also von der Form <math>x-\beta^i \in \mathbb F_q[x], i=1, \ldots, \delta-1</math>.

== Einsatzbereiche ==
* Die sogenannten [[Reed-Solomon-Code]]s sind spezielle BCH-Codes und werden z. B. zur Fehlerkorrektur auf [[Compact Disk|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 (Protokoll)|FLEX]] verwenden den BCH(31,21)-Code

== BCH(15, 7, 5) ==
Als Beispiel sei ein <math>(n = 15, k = 7, d_\text{min} = 5)</math> BCH-Code gegeben. Die Parameter <math>n, k, d_\text{min}</math> sind dabei wie folgt zu interpretieren. Der Code erzeugt Codewörter mit einer Länge von <math>n = 15</math> [[Bit]]s, wovon <math>k = 7</math> Bits die kodierte Information enthalten und <math>n -k</math> Bits Redundanz zur Korrektur von Übertragungsfehlern dienen. Der Parameter <math>d_{min}</math> gibt die minimale Hammingsdistanz des Codes an.

Es gilt: Es können Übertragungsfehler von bis zu <math>d_\mathrm{min} - 1</math> Einzelbitfehlern erkannt werden, es können Übertragungsfehler von bis zu <math>(d_\mathrm{min} - 1) / 2</math> Einzelbitfehlern korrigiert werden. Bündelfehler von bis zu <math>f_\mathrm{b} \le k</math> [[Bit]]s werden erkannt.

Ein BCH-Code wird in der Regel durch sein Generatorpolynom beschrieben. Im gegebenen Beispiel lautet das Generatorpolynom <math>g(x) = x^8 + x^7 + x^6 + x^4 + 1</math>. Die Anzahl der Prüfbits <math>n-k</math> lässt sich übrigens immer aus dem Generatorpolynom ablesen. Es gilt <math>n-k = \operatorname{Grad}(g)</math>.

Für die Dimension des Codes gilt: <math>\dim C = n-\operatorname{Grad}(g) = 15-8 = 7 = k</math>.

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

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

Als zu kodierendes Quellkodewort dient in unserem Beispiel <math>a^* = 1001011</math> bzw. <math>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</math>.

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

<math>a = a^* \cdot g = 1001011 \cdot 111010001 = 111100010111011</math>

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

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

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

<math> \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} </math>

Die Division in Koeffizienten-Schreibweise lautet dann:

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

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

=== Dekodieren ===
Die Dekodierung kann mittels verschiedener Verfahren nach folgendem Muster erfolgen:

# Bestimmung des Syndromwertes (Divisionsrest), indem das empfangene Kanalkodewort <math>a(x)</math> durch das Generatorpolynom <math>g(x)</math> dividiert wird. Ist der Rest ungleich 0 liegen ein oder mehrere Fehler vor.
# Bestimmen des Fehlerpolynoms.
# Bestimmung der Nullstellen des Fehlerpolynoms zur Ermittlung der Fehlerpositionen im Codewort.
# Bestimmung der Fehlerwerte

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

=== Beispiel ===
Wenn das Codewort vom obigen Beispiel ohne Fehler übertragen wird, bleibt als Rest der Division <math> a : g</math> Null. Die Division in Koeffizienten-Schreibweise lautet dann:

<pre>
100101101010111 : 111010001 = 1100111
111010001
001010011
010100110
111010001
100111001
111010001
--------
'''00000000'''
</pre>

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

<pre>
101101011010111 : 111010001 = 1111100
101110100
101001011
100110100
111001011
000110101
001101011
--------
'''01101001'''
</pre>

== Literatur ==
*{{Literatur
|Autor = Shu Lin, Daniel J. Costello
|Titel = Error Control Coding. Fundamentals and applications
|Verlag = Prentice Hall |Ort=Upper Saddle River NJ | Auflage = 2. | Jahr = 2004 | ISBN = 0-13-042672-5 }}
*{{Literatur
|Autor = Robert H. Morelos-Zaragoza
|Titel = The Art of Error Correcting Coding
|Verlag = Wiley | Ort=New York NY |Auflage = 2. | Jahr = 2006 | ISBN = 0-470-01558-6 }}

{{DEFAULTSORT:Bch-Code}}
[[Kategorie:Theoretische Informatik]]
[[Kategorie:Kodierungstheorie]]

BCH-Code - Versionsgeschichte

imported>Wdwd: rev, Änderung bitte kommentieren