WikiDer > BCH-Code (Codierungstheorie)

EIN BCH-Code ist innerhalb der Codierungstheorie ein fehlerkorrigierender Code, der in den letzten 50 Jahren unter Wissenschaftlern viel Aufmerksamkeit auf sich gezogen hat. BCH-Codes wurden 1959 von . erfunden Hocquenghem, und unabhängig im Jahr 1960 von Bose und Ray Chaudhuric. Die Abkürzung BCH besteht aus den Initialen der Erfinder.

Ein großer Vorteil von BCH-Codes besteht darin, dass sie mit a . decodiert werden algebraisch Methode bekannt als dekodiersyndrom. Dadurch kann die erforderliche elektronische Hardware einfach sein und der Energieverbrauch ist begrenzt. Außerdem sind sie als eine Klasse von Codes flexibel, mit Blocklängeneinstellbarkeit und Einsatzfähigkeit bei in der Praxis üblichen Bitfehlerraten. Mit einer Spezifikation kann also ein Code entworfen werden (natürlich innerhalb der mathematischen Grenzen).

Technisch gesehen ist ein BCH-Code ein mehrstufiger, zyklischein fehlerkorrigierender digitaler Code variabler Länge, der verwendet wird, um Fehlermuster mit mehr als einem Bitfehler pro Block zu korrigieren. BCH-Codes können auch mit Multilevel verwendet werden Phasenumtastung, vorausgesetzt, die Anzahl der Ebenen ist a Primzahl ist, oder a Leistung einer Primzahl. Ein 11-stufiger BCH-Code wurde verwendet, um 10 Dezimalstellen plus ein Zeichen darzustellen.

Konstruktion

Ein BCH-Code ist a Polynomcode über einen endlicher Körper mit einem bestimmten erzeugenden Polynom. Es ist auch ein zyklischer Code.

Eine einfache Klasse von BCH-Codes

Um das Konzept anschaulich zu vermitteln, wird zunächst eine spezielle Klasse von BCH-Codes diskutiert.

Definition. Nehmen Sie ein endlicher Körper${displaystyle GF(q)}$, bei welchem ${Anzeigestil q}$ ist die Potenz einer Primzahl. Nimm positive ganze Zahlen ${displaystyle m}$, ${displaystyle n}$, und ${displaystyle d}$ so dass ${Anzeigestil n=q^{m}-1}$ und ${displaystyle 2leq dleq n}$. Wir konstruieren einen Polynomcode über ${displaystyle GF(q)}$ mit Blocklänge ${displaystyle n}$, und ein Minimum Hamming-Abstand von mindestens ${displaystyle d}$. Was noch anzugeben ist, ist das erzeugende Polynom dieses Codes.

Sie ${displaystyle alpha }$ eine primitive n-te Potenzwurzel der Einheit ${displaystyle GF(q^{m})}$. Für alle ${Anzeigestil i}$, bezeichnen wir als ${displaystyle m_{i}(x)}$ zum Minimalpolynom von ${displaystyle alpha ^{i}}$ mit Koeffizienten in ${displaystyle GF(q)}$. Das erzeugende Polynom des BCH-Codes ist definiert als kleinstes gemeinsames Vielfaches${displaystyle g(x)={m {kgf}}(m_{1}(x),ldots,m_{d-1}(x))}$.

Beispiel

Annehmen ${Anzeigestil q=2}$ und ${Anzeigestil m=4}$ (hieraus folgt das ${Anzeigestil n=15}$). Wir nehmen mehrere Werte von ${displaystyle d}$ behandeln. Es gibt eine primitive Wurzel ${Anzeigestil Alpha in GF(16)}$ was befriedigt

${Anzeigestil Alpha ^{4} Alpha 1=0}$ (1);

das entsprechende minimale Polynom über ${displaystyle GF(2)}$ ist: ${displaystyle m_{1}(x)=x^{4} x 1}$. Beachten Sie, dass in ${displaystyle GF(2)}$, Die gleichung ${displaystyle (a b)^{2}=a^{2} 2ab b^{2}=a^{2} b^{2}}$ gilt, was bedeutet, dass${displaystyle m_{1}(alpha ^{2})=m_{1}(alpha)^{2}=0}$.So ${displaystyle alpha ^{2}}$ ist eine Wurzel von ${displaystyle m_{1}(x)}$, und so gilt das

${Anzeigestil m_{2}(x)=m_{1}(x)=x^{4} x 1}$.

Zu ${displaystyle m_{3}(x)}$ Zur Berechnung ist zu beachten, dass durch wiederholtes Anwenden von Gleichung (1) die folgenden linearen Gleichungen erhalten werden können:

• ${Displaystil 1=0alpha ^{3} 0alpha ^{2} 0alpha 1}$
• ${displaystyle alpha ^{3}=1alpha ^{3} 0alpha ^{2} 0alpha 0}$
• ${displaystyle alpha ^{6}=1alpha ^{3} 1alpha ^{2} 0alpha 0}$
• ${displaystyle alpha ^{9}=1alpha ^{3} 0alpha ^{2} 1alpha 0}$
• ${displaystyle alpha ^{12}=1alpha ^{3} 1alpha ^{2} 1alpha 1}$

Die fünf rechten Seiten müssen abhängig sein, und das finden wir tatsächlich ${displaystyle alpha ^{12} alpha ^{9} alpha ^{6} alpha ^{3} 1=0}$.Da es keine Abhängigkeit geringeren Grades gibt, ist das Minimalpolynom von is ${Anzeigestil Alpha ^{3}}$ das Polynom ${displaystyle m_{3}(x)=x^{4} x^{3} x^{2} x 1}$.

Ähnlich finden wir das

${Anzeigestil m_{4}(x)=m_{2}(x)=x^{4} x 1,,}$

${displaystyle m_{5}(x)=x^{2} x 1,,}$

${Anzeigestil m_{6}(x)=m_{3}(x)=x^{4} x^{3} x^{2} x 1,,}$

${Anzeigestil m_{7}(x)=x^{4} x^{3} 1.,}$

• Der BCH-Code mit ${Displaystil d=1,,2,,3}$ hat als erzeugendes Polynom

${Anzeigestil d(x)=m_{1}(x)=x^{4} x 1.,}$

Die minimale Hamming-Distanz beträgt mindestens 3 und korrigiert 1-Bit-Fehler. Da das erzeugende Polynom Grad 4 hat, hat dieser Code 11 Datenbits und 4 Prüfbits.

• Der BCH-Code mit ${Anzeigestil d=4,5}$ hat als erzeugendes Polynom

${displaystyle { egin{aligned}d(x)&{}={m {kgf}}(m_{1}(x),m_{3}(x))=(x^{4} x 1)(1 xx^{2} x^{3} x^{4})/&{}=x^{8} x^{7} x^{6} x^{4} 1.Ende{ausgerichtet}}}$

Die minimale Hamming-Distanz beträgt mindestens 5 und der Code korrigiert 2 Bitfehler. Da das erzeugende Polynom den Grad 8 hat, enthält dieser Code 7 Datenbits und 8 Prüfbits.

• Der BCH-Code mit ${Anzeigestil d=6,,7}$ hat als erzeugendes Polynom

${displaystyle { egin{aligned}d(x)&{}={m {kgf}}(m_{1}(x),m_{3}(x),m_{5}(x)))/&{ } =(x^{4} x 1)(1 xx^{2} x^{3} x^{4})(x^{2} x 1)/&{}=x^{10} x^ { 8} x^{5} x^{4} x^{2} x 1.Ende{ausgerichtet}}}$

Die minimale Hamming-Distanz beträgt mindestens 7 und der Code korrigiert 3-Bit-Fehler. Dieser Code hat 5 Datenbits und 10 Prüfbits.

• Der BCH-Code mit ${Anzeigestil d=8,}$ und oben hat als erzeugendes Polynom

${displaystyle { egin{aligned}d(x)&{}={m {kgf}}(m_{1}(x),m_{3}(x),m_{5}(x),m_{7} (x))/&{}=(x^{4} x 1)(1 xx^{2} x^{3} x^{4})(x^{2} x 1)(x^{4 } x^{3} 1)/&{}=x^{14} x^{13} x^{12} cdots x^{2} x 1.Ende{ausgerichtet}}}$

Dieser Code hat eine Hamming-Distanz von mindestens 15 und korrigiert 7-Bit-Fehler. Der Code hat 1 Datenbit und 14 Prüfbits. Tatsächlich besteht dieser Code aus den folgenden zwei Codewörtern: 000000000000000 und 11111111111111111.

Allgemeine BCH-Codes

Allgemeine BCH-Codes unterscheiden sich von den oben diskutierten einfachen BCH-Codes in zweierlei Hinsicht. Voraussetzung ist zunächst, dass ${Anzeigestil n=q^{m}-1}$ durch eine allgemeinere Anforderung ersetzt. Zweitens stimmen die aufeinanderfolgenden Nullstellen des Generatorpolynoms nicht überein ${Displaystil-Alpha ^{1}}$ beginnen müssen; es reicht also, wenn die Reihenfolge so aussieht: ${displaystyle alpha ^{c},ldots ,alpha ^{c d-2}}$ (Anstatt von ${displaystyle alpha ,ldots ,alpha ^{d-1}}$).

Definition. Nehmen Sie ein endlicher Körper${displaystyle GF(q)}$, bei welchem ${Anzeigestil q}$ ist eine Potenz einer Primzahl. Wähle positive ganze Zahlen ${Anzeigestil m,n,d,c}$ so dass ${displaystyle 2leq dleq n}$, ${displaystyle {m {ggd}}(n,q)=1}$, und ${displaystyle m}$ ist die multiplikative Ordnung von ${Anzeigestil q}$ modular ${displaystyle n}$ (was bedeutet ${displaystyle m}$ ist der kleinste Macht mit der Eigenschaft, dass ${displaystyle q^{m}=1}$ modular ${displaystyle n}$).

Wie oben ${displaystyle alpha }$ eine primitive n-te Wurzel der Macht in eenheid ${displaystyle GF(q^{m})}$, und ist (für alle i) ${displaystyle m_{i}(x)}$ das minimale Polynom über ${displaystyle GF(q)}$ von ${displaystyle alpha ^{i}}$. Das Generatorpolynom des BCH-Codes ist nun definiert als kleinstes gemeinsames Vielfaches${Anzeigestil g(x)={m {kgf}}(m_{c}(x),ldots,m_{c d-2}(x))}$.

Hinweis: wenn ${Anzeigestil n=q^{m}-1}$ wie im einfachen Fall dann ${displaystyle {m {ggd}}(n,q)}$ gleich 1 und ist die Ordnung von ${Anzeigestil q}$ modular ${displaystyle n}$ automatisch gleich ${displaystyle m}$. Der "einfache" BCH-Code ist also tatsächlich ein spezifisches Beispiel innerhalb der allgemeinen BCH-Codes.

Eigenschaften

1. Das Generatorpolynom eines BCH-Codes hat höchstens Grad ${Anzeigestil (d-1)m}$. Und wenn ${Anzeigestil q=2}$ und ${Anzeigestil c=1}$, dann ist der Grad des Generatorpolynoms höchstens ${displaystyle dm/2}$.

Beweis: beliebiges minimales Polynom ${displaystyle m_{i}(x)}$ hat höchstens einen Abschluss ${displaystyle m}$. Das kleinste gemeinsame Vielfache von ${Anzeigestil d-1}$ minimale Polynome haben also höchstens den Grad ${Anzeigestil (d-1)m}$. Und wenn ${Anzeigestil q=2}$, dann ist ${Anzeigestil m_{i}(x)=m_{2i}(x)}$ für alle ${Anzeigestil i}$. So ${Anzeigestil g(x)}$ ist das kleinste gemeinsame Vielfache von höchstens ${Anzeigestil d/2}$ minimale Polynome ${displaystyle m_{i}(x)}$ für ungerade Indizes ${Anzeigestil i}$, die jeweils den Grad nicht überschreiten ${displaystyle m}$ haben.

2. Ein BCH-Code hat das Minimum Hamming-Abstand mindestens ${displaystyle d}$. Beweis im einfachen Fall (der Beweis für den allgemeinen Fall ist ähnlich): Angenommen, ${Anzeigestil p(x)}$ ist ein Codewort mit weniger als ${displaystyle d}$ Ziffern ungleich Null. Dann ist

${displaystyle p(x)=b_{1}x^{j_{1}} cdots b_{d-1}x^{j_{d-1}},{ ext{ wobei }}j_{1}$

Das wussten wir ${displaystyle alpha ^{1},ldots ,alpha ^{d-1}}$ Wurzeln sind von ${Anzeigestil g(x)}$, und damit auch von ${Anzeigestil p(x)}$. Es folgt dem ${displaystyle b_{1},ldots ,b_{d-1}}$ erfüllen die folgenden Gleichungen für ${displaystyle i=1,ldots,d-1}$:

${displaystyle p(alpha ^{i})=b_{1}alpha ^{ij_{1}} b_{2}alpha ^{ij_{2}} cdots b_{d-1}alpha ^{ij_{d-1 }}=0}$.

Das teilen wir jetzt ${displaystyle alpha ^{ij_{1}}}$, und wir definieren ${displaystyle k_{l}=j_{l}-j_{1}}$, als Ergebnis zu erhalten

${displaystyle b_{1} b_{2}alpha ^{ik_{2}} cdots b_{d-1}alpha ^{ik_{d-1}}=0}$

für alle ${Anzeigestil i}$, was äquivalent zu ist

${displaystyle { egin{bmatrix}1&alpha ^{k_{2}}&cdots &alpha ^{k_{d-1}}/1&alpha ^{2k_{2}}&cdots &alpha ^{2k_{d-1}}/vdots &vdots &&vdots /1&alpha ^{(d-1)k_{2}}&cdots &alpha ^{(d-1)k_{d-1}}/end{bmatrix}}{ egin{bmatrix}b_{1}/b_{2} /vdots /b_{d-1}end{bmatrix}}={ egin{bmatrix}0/0/vdots /0end{bmatrix}}}$

Diese Matrix ist ein Vandermonde-Matrix, und hat as bestimmend

${displaystyle det(V)=prod_{1leq i$,

was nicht null ist. Es folgt dem ${displaystyle b_{1},ldots ,b_{d-1}=0}$, und somit ${Anzeigestil p(x)=0}$.

3. Ein BCH-Code ist zyklisch.

Beweis: ein Polynomcode mit Blocklänge ${displaystyle n}$ ist genau dann zyklisch, wenn sein Generatorpolynom ein Teiler von ist ${Displaystil x^{n}-1}$. weil ${Anzeigestil g(x)}$ ist das minimale Polynom mit Wurzeln ${displaystyle alpha ^{c},ldots ,alpha ^{c d-2}}$, es muss nur überprüft werden, ob alle ${displaystyle alpha ^{c},ldots ,alpha ^{c d-2}}$ Wurzel sein von ${Displaystil x^{n}-1}$. Dies folgt jedoch direkt aus der Tatsache, dass ${displaystyle alpha }$ per definitionem a ${displaystyle n}$ist die Wurzel der Macht.

Sonderfälle

• Ein BCH-Code mit ${Anzeigestil c=1}$ wird ein BCH-Code im engeren Sinne erwähnt.
• Ein BCH-Code mit ${Anzeigestil n=q^{m}-1}$ wird Primitive erwähnt.

Die oben betrachteten "einfachen" BCH-Codes bilden genau die primitiven BCH-Codes im engeren Sinne.

• Ein BCH-Code im engeren Sinne mit ${Anzeigestil n=q-1}$ wird ein Reed-Solomon-Code erwähnt.