www.wikidata.de-de.nina.az

BCH Code s Bose Chaudhuri Hocquenghem Codes sind zyklische fehlerkorrigierende Codes welche in der digitalen Signalverar

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 (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.
  • 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
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 Inhaltsverzeichnis 1 Definition 2 Einsatzbereiche 3 BCH 15 7 5 3 1 Kodieren 3 2 Multiplikationsverfahren 3 3 Divisionsverfahren 3 4 Dekodieren 3 5 Beispiel 4 LiteraturDefinition BearbeitenSei b displaystyle beta nbsp eine primitive n displaystyle n nbsp te Einheitswurzel in einem Erweiterungskorper des endlichen Korpers F q displaystyle mathbb F q nbsp Seien l d N displaystyle l delta in mathbb N nbsp d 2 displaystyle delta geq 2 nbsp und C der zyklische Code dessen Generatorpolynom das Produkt der verschiedenen Minimalpolynome von b l b l d 2 displaystyle beta l dots beta l delta 2 nbsp ist Dann besteht C also aus allen f F q x x n 1 displaystyle f in mathbb F q x x n 1 nbsp mit f b l f b l d 2 0 displaystyle f beta l dots f beta l delta 2 0 nbsp dann nennt man C einen BCH Code mit geplantem Minimalabstand d displaystyle delta nbsp wobei C den Minimalabstand d d displaystyle d geq delta nbsp hat Fur den Fall l 1 displaystyle l 1 nbsp spricht man von einem BCH Code im gewohnlichen Sinn Falls ein m existiert mit n q m 1 displaystyle n q m 1 nbsp d h b displaystyle beta nbsp ist ein Erzeuger der multiplikativen Gruppe eines Korpers F q m displaystyle mathbb F q m nbsp so spricht man von einem primitiven BCH Code Ein Reed Solomon Code ist ein primitiver BCH Code im gewohnlichen Sinn fur den n q 1 displaystyle n q 1 nbsp gilt Hier sind die Minimalpolynome also von der Form x b i F q x i 1 d 1 displaystyle x beta i in mathbb F q x i 1 ldots delta 1 nbsp Einsatzbereiche BearbeitenDie 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 Die Funkruf Protokolle POCSAG und FLEX verwenden den BCH 31 21 CodeBCH 15 7 5 BearbeitenAls Beispiel sei ein n 15 k 7 d min 5 displaystyle n 15 k 7 d text min 5 nbsp BCH Code gegeben Die Parameter n k d min displaystyle n k d text min nbsp sind dabei wie folgt zu interpretieren Der Code erzeugt Codeworter mit einer Lange von n 15 displaystyle n 15 nbsp Bits wovon k 7 displaystyle k 7 nbsp Bits die kodierte Information enthalten und n k displaystyle n k nbsp Bits Redundanz zur Korrektur von Ubertragungsfehlern dienen Der Parameter d m i n displaystyle d min nbsp gibt die minimale Hammingsdistanz des Codes an Es gilt Es konnen Ubertragungsfehler von bis zu d m i n 1 displaystyle d mathrm min 1 nbsp Einzelbitfehlern erkannt werden es konnen Ubertragungsfehler von bis zu d m i n 1 2 displaystyle d mathrm min 1 2 nbsp Einzelbitfehlern korrigiert werden Bundelfehler von bis zu f b k displaystyle f mathrm b leq k nbsp Bits werden erkannt Ein BCH Code wird in der Regel durch sein Generatorpolynom beschrieben Im gegebenen Beispiel lautet das Generatorpolynom g x x 8 x 7 x 6 x 4 1 displaystyle g x x 8 x 7 x 6 x 4 1 nbsp Die Anzahl der Prufbits n k displaystyle n k nbsp lasst sich ubrigens immer aus dem Generatorpolynom ablesen Es gilt n k Grad g displaystyle n k operatorname Grad g nbsp Fur die Dimension des Codes gilt dim C n Grad g 15 8 7 k displaystyle dim C n operatorname Grad g 15 8 7 k nbsp Kodieren Bearbeiten Zum Kodieren mit BCH Kodes konnen das Multiplikations oder das Divisionsverfahren verwendet werden Multiplikationsverfahren Bearbeiten Beim Multiplikationsverfahren wird das zu kodierende Quellkodewort aus l 7 displaystyle l 7 nbsp Bits einfach mit dem Generatorpolynom des BCH Codes multipliziert Es gilt a x a x g x displaystyle a x a x cdot g x nbsp Dabei steht a x displaystyle a x nbsp fur das kodierte Kanalkodewort a x displaystyle a x nbsp 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 g x x 8 x 7 x 6 x 4 1 displaystyle g x x 8 x 7 x 6 x 4 1 nbsp lasst sich binar als die Folge g 111010001 displaystyle g 111010001 nbsp darstellen die Folge ist dabei zu interpretieren als g x 1 x 8 1 x 7 1 x 6 0 x 5 1 x 4 0 x 3 0 x 2 0 x 1 1 x 0 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 nbsp Als zu kodierendes Quellkodewort dient in unserem Beispiel a 1001011 displaystyle a 1001011 nbsp bzw a x 1 x 6 0 x 5 0 x 4 1 x 3 0 x 2 1 x 1 1 x 0 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 nbsp Um das kodierte Kanalkodewort zu erhalten mussen wir jetzt also einfach a displaystyle a nbsp mit g displaystyle g nbsp multiplizieren a a g 1001011 111010001 111100010111011 displaystyle a a cdot g 1001011 cdot 111010001 111100010111011 nbsp Divisionsverfahren 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 g displaystyle g nbsp und ein Quellkodewort a displaystyle a nbsp errechnet man das zugehorige Kanalkodewort a displaystyle a nbsp nach Divisionsverfahren wie folgt a a x k a x k mod g displaystyle a a cdot x k left a cdot x k right bmod g nbsp Das heisst man muss den Rest der Polynom Division a x k g displaystyle left a cdot x k right g nbsp ermitteln und diesen von a x k displaystyle a cdot x k nbsp subtrahieren Am Beispiel von oben g x 8 x 7 x 6 x 4 1 111010001 a x 6 x 3 x 1 1001011 a x k x 14 x 11 x 9 x 8 100101100000000 displaystyle begin array ccccc g amp amp x 8 x 7 x 6 x 4 1 amp mathrel widehat amp 111010001 a amp amp x 6 x 3 x 1 amp mathrel widehat amp 1001011 a cdot x k amp amp x 14 x 11 x 9 x 8 amp mathrel widehat amp 100101100000000 end array nbsp Die Division in Koeffizienten Schreibweise lautet dann 100101100000000 111010001 1100111 111111010 001010110 010101100 101011000 100010010 110000110 01010111 Damit gilt a 100101100000000 01010111 1001011 a 01010111 displaystyle a 100101100000000 01010111 underbrace 1001011 a 01010111 nbsp Dekodieren Bearbeiten Die Dekodierung kann mittels verschiedener Verfahren nach folgendem Muster erfolgen Bestimmung des Syndromwertes Divisionsrest indem das empfangene Kanalkodewort a x displaystyle a x nbsp durch das Generatorpolynom g x displaystyle g x nbsp 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 FehlerwerteUbliche 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 ubertragen wird bleibt als Rest der Division a g displaystyle a g nbsp Null Die Division in Koeffizienten Schreibweise lautet dann lt Berechnungen konnen hier nachgerechnet werden http www flechtmann net crc index php gt 100101101010111 111010001 1100111 111010001 001010011 010100110 111010001 100111001 111010001 00000000 Wurde das Codewort wahrend der Ubertragung verfalscht 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 BearbeitenShu 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 Abgerufen von https de wikipedia org w index php title BCH Code amp oldid 227373885