Im Codieren der Theorie bilden die BCH-Codes eine Klasse von zyklischen Fehlerkorrekturcodes, die mit begrenzten Feldern gebaut werden. BCH Codes wurden 1959 von Hocquenghem, und unabhängig 1960 von Bose und Ray-Chaudhuri erfunden. Die Abkürzung BCH umfasst die Initialen der Namen dieser Erfinder.

Eines der Hauptmerkmale von BCH-Codes ist, dass während des Codedesigns es eine genaue Kontrolle über die Zahl von durch den Code korrigierbaren Symbol-Fehlern gibt. Insbesondere es ist möglich, binäre BCH-Codes zu entwerfen, die vielfache Bit-Fehler korrigieren können. Ein anderer Vorteil von BCH-Codes ist die Bequemlichkeit, mit der sie nämlich über eine algebraische als Syndrom-Entzifferung bekannte Methode decodiert werden können. Das vereinfacht das Design des Decoders für diese Codes, mit der kleinen niedrigen Macht elektronische Hardware.

BCH Codes werden in Anwendungen wie Satellitenverkehr, CD-Spieler, DVDs, Laufwerke, Halbleiterlaufwerke und zweidimensionale Strichcodes verwendet.

Aufbau

Primitiver engerer Sinn BCH Codes

Für eine gegebene Blüte und positive ganze Zahlen und mit ein primitiver engerer Sinn wird der BCH Code über das begrenzte Feld mit der Codelänge und minimalen Entfernung mindestens durch die folgende Methode gebaut.

Lassen Sie, ein primitives Element dessen zu sein. Für jede positive ganze Zahl, lassen Sie, das minimale Polynom dessen zu sein. Das Generator-Polynom des BCH-Codes wird als kleinstes Gemeinsames Vielfaches definiert. Es kann gesehen werden, dass das ein Polynom mit Koeffizienten darin ist und sich teilt. Deshalb ist der polynomische Code, der dadurch definiert ist, ein zyklischer Code.

Beispiel

Lassen Sie und (deshalb). Wir werden verschiedene Werte dessen denken. Es gibt eine primitive Wurzel, die befriedigt

:

sein minimales Polynom ist:.

Bemerken Sie, dass in die Gleichung, und deshalb hält

.

So ist eine Wurzel, und deshalb

:.

Um zu rechnen, bemerken Sie, dass, durch die wiederholte Anwendung , wir die folgenden geradlinigen Beziehungen haben:

Fünf rechte Seiten der Länge vier müssen linear abhängig sein, und tatsächlich finden wir eine geradlinige Abhängigkeit.

Da es keine kleinere Grad-Abhängigkeit gibt, ist das minimale Polynom dessen:.

Auf eine ähnliche Weise weitermachend, finden wir

::::

Der BCH-Code damit hat Generator-Polynom

:

Es hat minimale Entfernung von Hamming mindestens 3 und korrigiert bis zu 1 Fehler. Da das Generator-Polynom des Grads 4 ist, hat dieser Code 11 Datenbit und 4 Kontrollsumme-Bit.

Der BCH-Code damit hat Generator-Polynom:

Es hat minimale Entfernung von Hamming mindestens 5 und korrigiert bis zu 2 Fehler. Da das Generator-Polynom des Grads 8 ist, hat dieser Code 7 Datenbit und 8 Kontrollsumme-Bit.

Der BCH-Code damit hat Generator-Polynom:

\begin {richten }\aus

g (x) & {} = {\\rm lcm} (m_1 (x), m_3 (x), m_5 (x)) \\

& {} = (X^4+x+1) (x^4+x^3+x^2+x+1) (x^2+x+1) \\

& {} = x^ {10} +x^8+x^5+x^4+x^2+x+1.

\end {richten }\aus

</Mathematik>

Es hat minimale Entfernung von Hamming mindestens 7 und korrigiert bis zu 3 Fehler. Dieser Code hat 5 Datenbit und 10 Kontrollsumme-Bit.

Der BCH-Code damit und hat höher Generator-Polynom

:\begin {richten }\aus

g (x) & {} = {\\rm lcm} (m_1 (x), m_3 (x), m_5 (x), m_7 (x)) \\

& {} = (X^4+x+1) (x^4+x^3+x^2+x+1) (X^2+x+1) (x^4+x^3+1) \\

& {} = x^ {14} +x^ {13} +x^ {12} + \cdots+x^2+x+1.

\end {richten }\aus</Mathematik>

Dieser Code hat minimale Entfernung von Hamming 15 und korrigiert 7 Fehler. Es hat 1 Datenbit und 14 Kontrollsumme-Bit. Tatsächlich hat dieser Code nur zwei Kennwörter: 000000000000000 und 111111111111111.

Allgemeine BCH-Codes

Allgemeine BCH-Codes unterscheiden sich vom primitiven engeren Sinn BCH Codes in zwei Hinsicht.

Erstens kann die Voraussetzung, die man ein primitives Element dessen ist, entspannt werden. Durch das Entspannen dieser Voraussetzung ändert sich die Codelänge von zu, die Ordnung des Elements.

Zweitens können die Konsekutivwurzeln des Generator-Polynoms von statt laufen.

Definition. Befestigen Sie ein begrenztes Feld, wo eine Hauptmacht ist. Wählen Sie positive solche ganze Zahlen, dass, und die multiplicative Ordnung von modulo ist.

Lassen Sie wie zuvor, eine primitive th Wurzel der Einheit zu sein in und zu lassen, das minimale Polynom zu sein, das für alle zu Ende ist. Das Generator-Polynom des BCH-Codes wird als kleinstes Gemeinsames Vielfaches definiert.

Zeichen: Wenn als in der vereinfachten Definition, dann automatisch 1 ist, und die Ordnung von modulo automatisch ist. Deshalb ist die vereinfachte Definition tatsächlich ein spezieller Fall des allgemeinen.

Eigenschaften

1. Das Generator-Polynom eines BCH-Codes hat Grad höchstens. Außerdem, wenn und, das Generator-Polynom Grad höchstens hat.

:Proof: Jedes minimale Polynom hat Grad höchstens. Deshalb hat kleinstes Gemeinsames Vielfaches ihrer Grad höchstens. Außerdem, wenn, dann für alle. Deshalb, ist kleinstes Gemeinsames Vielfaches an den meisten minimalen Polynomen für sonderbare Indizes, jeden des Grads höchstens.

2. Ein BCH-Code hat minimale Entfernung von Hamming mindestens. Beweis: Wir geben nur den Beweis im vereinfachten Fall; der allgemeine Fall ist ähnlich. Nehmen Sie an, dass das ein Codewort mit weniger ist als Nichtnullbegriffe. Dann

:

Rufen Sie zurück, dass Wurzeln, folglich dessen sind. Das deutet an, dass die folgenden Gleichungen befriedigen, für:

:.

In der Matrixform haben wir

:

\alpha^ {k_1} & \alpha^ {k_2} & \cdots & \alpha^ {k_ {d-1}} \\

\alpha^ {2k_1} & \alpha^ {2k_2} & \cdots & \alpha^ {2k_ {d-1}} \\

\vdots & \vdots && \vdots \\

\alpha^ {(d-1) k_1} & \alpha^ {(d-1) k_2} & \cdots & \alpha^ {(d-1) k_ {d-1}} \\

\end {bmatrix }\\begin {bmatrix }\

b_1 \\b_2 \\\vdots \\b_ {d-1 }\

\end {bmatrix }\\begin {bmatrix }\

0 \\0 \\\vdots \\0

\end {bmatrix }\</Mathematik>

Die Determinante dieser Matrix kommt gleich

:

1 & 1 & \cdots & 1 \\

\alpha^ {k_1} & \alpha^ {k_2} & \cdots & \alpha^ {k_ {d-1}} \\\vdots & \vdots && \vdots \\

\alpha^ {(d-2) k_1} & \alpha^ {(d-2) k_2} & \cdots & \alpha^ {(d-2) k_ {d-1}} \\

\end {pmatrix} = \left (\prod_ {i=1} ^ {d-1 }\\alpha^ {k_i }\\Recht) \det (V) </Mathematik>

Wie man

sieht, ist die Matrix eine Matrix von Vandermonde, und seine Determinante ist

:

der Nichtnull ist. Es folgt deshalb dem folglich.

3. Ein BCH-Code ist zyklisch.

Beweis: Ein polynomischer Code der Länge ist zyklisch, wenn, und nur wenn sich sein Generator-Polynom teilt. Seitdem ist das minimale Polynom mit Wurzeln, es genügt, um zu überprüfen, dass jeder dessen eine Wurzel dessen ist. Das folgt sofort von der Tatsache d. h. definitionsgemäß, einer th Wurzel der Einheit.

Spezielle Fälle

• Ein BCH-Code damit wird einen engeren Sinn BCH Code genannt.
• Ein BCH-Code damit wird primitiv genannt.

Das Generator-Polynom eines BCH-Codes hat Koeffizienten davon. Das Polynom gehört auch dem polynomischen Ring über so lange. Im Allgemeinen wird ein zyklischer Code mit als das Generator-Polynom ein BCH-Code verlesen. Der BCH-Code mit als das Generator-Polynom wird einen Code des Rohres-Solomon genannt. Mit anderen Worten ist ein Code des Rohres-Solomon ein BCH-Code, wo das Decoder-Alphabet dasselbe als das Kanalalphabet ist.

Entzifferung

Es gibt viele Algorithmen, um BCH-Codes zu decodieren. Die allgemeinsten folgen diesem allgemeinen Umriss:

1. Berechnen Sie die Syndrome s für den erhaltenen Vektoren
2. Bestimmen Sie die Zahl von Fehlern t und dem Fehler locator Polynom &Lambda; (x) von den Syndromen
3. Berechnen Sie die Wurzeln des Fehlerpositionspolynoms, um die Fehlerpositionen X zu finden
4. Rechnen Sie der Fehler schätzt Y auf jene Fehlerpositionen

Berechnen Sie die Syndrome

Der erhaltene Vektor ist die Summe des richtigen Kennwortes und eines unbekannten Fehlervektoren.

Die Syndrom-Werte werden durch das Betrachten als ein Polynom und das Auswerten davon daran gebildet.

So sind die Syndrome

:

weil dazu. Seitdem sind die Nullen, der

ist ein Vielfache. Das Überprüfen des Syndroms schätzt

so isoliert den Fehlervektoren, so können wir beginnen, dafür zu lösen.

Wenn es keinen Fehler, für alle gibt. Wenn die Syndrome die ganze Null sind, dann wird die Entzifferung getan.

Berechnen Sie das Fehlerpositionspolynom

Wenn es Nichtnullsyndrome gibt, dann gibt es Fehler. Der Decoder muss sich wie viel Fehler und die Position jener Fehler belaufen.

Wenn es einen einzelnen Fehler gibt, schreiben Sie das als,

wo die Position des Fehlers ist und sein Umfang ist. Dann sind die ersten zwei Syndrome

::

so zusammen erlauben sie uns, eine Auskunft über (völlig Bestimmung davon im Fall von Codes des Rohres-Solomon) zu berechnen und zu geben.

Wenn es zwei oder mehr Fehler, gibt

:

Es ist nicht sofort offensichtlich, wie man beginnt, die resultierenden Syndrome für den unknowns zu lösen, und.

Zwei populäre Algorithmen für diese Aufgabe sind:

1. Peterson-Gorenstein-Zierler-Algorithmus
2. Berlekamp-Massey Algorithmus

Peterson-Gorenstein-Zierler-Algorithmus

Der Algorithmus von Peterson ist der Schritt 2 des verallgemeinerten BCH Entzifferung des Verfahrens. Wir verwenden den Algorithmus von Peterson, um den Fehler locator polynomische Koeffizienten eines Polynoms zu berechnen

:

Jetzt ist das Verfahren des Peterson-Gorenstein-Zierler Algorithmus für einen gegebenen BCH-Code, der entworfen ist, um Fehler zu korrigieren

• Erzeugen Sie zuerst die Matrix 2t Syndrome
• Erzeugen Sie als nächstes die Matrix mit Elementen, die Syndrom-Werte sind

::

s_2&s_3&s_4& \dots&s_ {t+1 }\\\

s_3&s_4&s_5& \dots&s_ {t+2 }\\\

\vdots&\vdots&\vdots&\ddots&\vdots \\

s_t&s_ {t+1} &s_ {t+2} &\\dots&s_ {2t-1 }\\Ende {bmatrix} </Mathematik>

• Erzeugen Sie einen Vektoren mit Elementen

::

s_ {t+2 }\\\

\vdots \\

\vdots \\

s_ {2t }\\Ende {bmatrix }\

</Mathematik>

• Lassen Sie zeigen die unbekannten polynomischen Koeffizienten an, die durch gegeben werden

::

\lambda_ {t-1 }\\\

\vdots \\

\lambda_ {2 }\\\

\lambda_ {1 }\\Ende {bmatrix }\

</Mathematik>

• Bilden Sie die Matrixgleichung

::

• Wenn die Determinante der Matrix besteht, dann können wir wirklich ein Gegenteil dieser Matrix finden und für die Werte unbekannter Werte lösen.
• Wenn, dann folgen Sie

wenn

dann

erklären Sie einen leeren Fehler locator Polynom

hören Sie Verfahren von Peterson auf.

Ende

Satz

machen Sie vom Anfang der Entzifferung von Peterson weiter

• Nachdem Sie Werte von Ihnen haben, haben mit Ihnen den Fehler locator Polynom.
• Hören Sie Verfahren von Peterson auf.

Faktor-Fehler locator Polynom

Jetzt wo Sie das Polynom haben, können Sie seine Wurzeln in der Form mit dem Suchalgorithmus von Chien finden. Der Exponential-

Mächte des primitiven Elements werden die Positionen nachgeben, wo Fehler im erhaltenen vorkommen

Wort; folglich der Name 'Fehler locator' Polynom.

Die Nullen &Lambda; (x) sind X..., X. Die Nullen sind die Gegenstücke der Fehlerpositionen.

Berechnen Sie Fehlerwerte

Sobald die Fehlerpositionen bekannt sind, soll der nächste Schritt die Fehlerwerte an jenen Positionen bestimmen. Die Fehlerwerte werden dann verwendet, um die erhaltenen Werte an jenen Positionen zu korrigieren, um das ursprüngliche Kennwort wieder zu erlangen.

Für den Fall von binärem BCH ist das trivial; schnipsen Sie gerade die Bit für das erhaltene Wort

an diesen Positionen, und haben wir das korrigierte Codewort. Im allgemeineren Fall, dem

Fehlergewichte können durch das Lösen des geradlinigen Systems bestimmt werden

::

:...

Jedoch gibt es eine effizientere Methode, die als der Algorithmus von Forney bekannt ist, der auf der Interpolation von Lagrange basiert. Berechnen Sie zuerst das Fehlerschätzer-Polynom

:

Dann bewerten Sie die Fehlerwerte:

:

Für den engeren Sinn BCH Codes, c = 1, so vereinfacht der Ausdruck zu:

:

&Lambda;' (x) ist die formelle Ableitung des Fehlers locator polynomical &Lambda; (x):

:::

Entzifferung des Beispiels

Betrachten Sie den Code als definiert oben, mit in GF (2). (Dieser Generator wird im QR-Code verwendet.) Lassen die Nachricht, die zu übersenden ist, oder in der polynomischen Notation sein. Die "Kontrollsumme"-Symbole werden durch das Teilen durch und die Einnahme des Rests berechnet, hinauslaufend oder. Diese werden an der Nachricht angehangen, so ist das übersandte Kennwort.

Stellen Sie sich jetzt vor, dass es zwei Bit-Fehler in der Übertragung gibt, so ist das erhaltene Kennwort [1 0 1 1 1 0 0 0 1 0 1 0 0]. In der polynomischen Notation:

:

Um die Fehler zu korrigieren, berechnen Sie zuerst die Syndrome. Einnahme, wir, haben s = 1001, s = 1011, s = 1101, s = 0001 und s = 1001. Dann wenden Sie das Verfahren von Peterson durch das Reihe-Reduzieren die folgende vermehrte Matrix an.

:

\begin {bmatrix} s_1&s_2&s_3&s_4 \\

s_2&s_3&s_4&s_5 \\

s_3&s_4&s_5&s_6 \end {bmatrix} =

\begin {bmatrix} 1011&1001&1011&1101 \\

1001&1011&1101&0001 \\

1011&1101&0001&1001 \end {bmatrix} \Rightarrow

\begin {bmatrix} 0001&0000&1000&0111 \\

0000&0001&1011&0001 \\

0000&0000&0000&0000 \end {bmatrix} </Mathematik>

Wegen der Nullreihe, ist einzigartig, der keine Überraschung ist, seitdem nur zwei Fehler ins Kennwort eingeführt wurden. Jedoch ist die ober verlassene Ecke der Matrix dazu identisch, der die Lösung verursacht. Der resultierende Fehler locator Polynom ist, der Nullen an hat und. Die Hochzahlen dessen entsprechen den Fehlerpositionen. Es gibt kein Bedürfnis, die Fehlerwerte in diesem Beispiel zu berechnen, wie der einzige mögliche Wert 1 ist.

Zitate

Primäre Quellen

Sekundäre Quellen