BCH-code (coderingstheorie)

In de coderingstheorie is een BCH-code een cyclische foutcorrigerende code die gegenereerd wordt door een polynoom over een eindig lichaam. BCH-codes zijn in 1959 bedacht door Hocquenghem en onafhankelijk van deze in 1960 door Bose en Ray-Chaudhuri. De afkorting BCH is opgebouwd uit hun initialen.

Een groot voordeel van BCH-codes is dat ze worden gedecodeerd door middel van een algebraïsche methode die bekendstaat als syndroom decoderen. Hierdoor kan de benodigde elektronische hardware eenvoudig zijn, en is het energieverbruik beperkt. Daarnaast zijn ze als een klasse codes flexibel, met instelbaarheid van bloklengte en inzetbaarheid bij in de praktijk voorkomende bitfoutkansen. Dus bij een specificatie kan een code worden ontworpen (vanzelfsprekend wel binnen de wiskundige grenzen).

Technisch uitgedrukt is een BCH-code een multiniveau, cyclische, fout-corrigerende, variabele lengte digitale code, die gebruikt wordt voor het corrigeren van foutpatronen met meer dan één bitfout per blok. BCH-codes kunnen ook worden gebruikt met multiniveau phase-shift keying, mits het aantal niveaus een priemgetal is, of een macht van een priemgetal. Een BCH-code met 11 niveaus is gebruikt voor het representeren van 10 decimale digits plus een teken.

Constructie

Een BCH-code wordt gegenereerd door een polynoom over een eindig lichaam ${\displaystyle \mathbb {GF} (q)}$, waarin ${\displaystyle q}$ een macht van een priemgetal is.

Een eenvoudige klasse BCH-codes

Definitie

Voor positieve gehele getallen ${\displaystyle q,\,m,\,n,}$ en ${\displaystyle d}$ met ${\displaystyle q}$ een priemgetal, ${\displaystyle n=q^{m}-1}$ en ${\displaystyle 2\leq d\leq n}$, wordt een polynoomcode met bloklengte ${\displaystyle n}$ en een minimum hammingafstand van minstens ${\displaystyle d}$ bepaald door de genererende polynoom die het kleinste gemeenschappelijke veelvoud ${\displaystyle g(x)={\rm {kgv}}(m_{1}(x),\ldots ,m_{d-1}(x))}$ is. Daarin is ${\displaystyle m_{i}(x)}$ de minimale polynoom van ${\displaystyle \alpha ^{i}}$ over ${\displaystyle \mathbb {GF} (q)}$, met ${\displaystyle \alpha }$ een primitief element in ${\displaystyle \mathbb {GF} (q^{m})}$.

Voorbeeld

In het voorbeeld is ${\displaystyle q=2}$ en ${\displaystyle m=4}$, dus ${\displaystyle n=15}$.

Volgens de theorie bestaat er een primitieve wortel ${\displaystyle \alpha \in \mathbb {GF} (16)}$ met een minimale polynoom van graad ${\displaystyle m}$ die voldoet aan:

${\displaystyle \alpha ^{4}+\alpha +1=0}$

De bijbehorende minimale polynoom over ${\displaystyle \mathbb {GF} (2)}$ is:

${\displaystyle m_{1}(x)=x^{4}+x+1}$

In ${\displaystyle \mathbb {GF} (2)}$ geldt ${\displaystyle (a+b)^{2}=a^{2}+2ab+b^{2}=a^{2}+b^{2}}$, zodat:

${\displaystyle m_{1}(\alpha ^{2})=\alpha ^{8}+\alpha ^{2}+1=(m_{1}(\alpha ))^{2}=0}$

Dus ${\displaystyle \alpha ^{2}}$ is een wortel van ${\displaystyle m_{1}(x)}$, en blijkbaar is:

${\displaystyle m_{2}(x)=m_{1}(x)=x^{4}+x+1}$

De minimale polynoom ${\displaystyle m_{3}(x)}$ van ${\displaystyle \alpha ^{3}}$ is ook van de graad 4:

Nu is:

${\displaystyle \alpha ^{4}+\alpha +1=0}$,

dus

${\displaystyle \alpha ^{4}=\alpha +1}$,

zodat

${\displaystyle \alpha ^{6}=\alpha ^{4}\alpha ^{2}=(\alpha +1)\alpha ^{2}=\alpha ^{3}+\alpha ^{2}}$

${\displaystyle \alpha ^{9}=(\alpha ^{4})^{2}\alpha =(\alpha ^{2}+1)\alpha =\alpha ^{3}+\alpha }$

${\displaystyle \alpha ^{12}=(\alpha ^{4})^{3}=(\alpha +1)^{3}=(\alpha ^{2}+1)(\alpha +1)=\alpha ^{3}+\alpha ^{2}+\alpha +1}$

Het blijkt dat

${\displaystyle (\alpha ^{3})^{4}+(\alpha ^{3})^{3}+(\alpha ^{3})^{2}+\alpha ^{3}+1=\alpha ^{12}+\alpha ^{9}+\alpha ^{6}+\alpha ^{3}+1=}$

${\displaystyle =\alpha ^{3}+\alpha ^{2}+\alpha +1+\alpha ^{3}+\alpha +\alpha ^{3}+\alpha ^{2}+\alpha ^{3}+1=0}$

De minimale polynoom van ${\displaystyle \alpha ^{3}}$ is de polynoom

${\displaystyle m_{3}(x)=x^{4}+x^{3}+x^{2}+x+1}$.

Op vergelijkbare wijze vindt men:

${\displaystyle m_{4}(x)=m_{2}(x)=x^{4}+x+1}$

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

${\displaystyle m_{6}(x)=m_{3}(x)=x^{4}+x^{3}+x^{2}+x+1}$

${\displaystyle m_{7}(x)=x^{4}+x^{3}+1}$

Deze polynomen zijn juist de vier irreducibele polynomen.

De BCH-code met ${\displaystyle d=1,\,2,\,3}$ heeft als genererende polynoom

${\displaystyle d(x)=m_{1}(x)=x^{4}+x+1}$

De minimale hammingafstand is minstens 3 en hij corrigeert 1 bitfout. Omdat de genererende polynoom van de graad 4 is, heeft deze code 11 data-bits en 4 checkbits.

De BCH-code met ${\displaystyle d=4,\,5}$ heeft als genererende polynoom

${\displaystyle {\begin{aligned}d(x)&{}={\rm {kgv}}(m_{1}(x),m_{3}(x))=(x^{4}+x+1)(1+x+x^{2}+x^{3}+x^{4})\\&{}=x^{8}+x^{7}+x^{6}+x^{4}+1\end{aligned}}}$

De minimale hammingafstand is minstens 5 en de code corrigeert 2 bitfouten. Omdat het genererende polynoom de graad 8 heeft, bevat deze code 7 data-bits en 8 checkbits.

De BCH-code met ${\displaystyle d=6,\,7}$ heeft als genererende polynoom

${\displaystyle {\begin{aligned}d(x)&{}={\rm {kgv}}(m_{1}(x),m_{3}(x),m_{5}(x))\\&{}=(x^{4}+x+1)(1+x+x^{2}+x^{3}+x^{4})(x^{2}+x+1)\\&{}=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1\end{aligned}}}$

De minimale hammingafstand is minstens 7 en de code corrigeert 3 bitfouten. Deze code heeft 5 data-bits en 10 checkbits.

De BCH-code met ${\displaystyle d=8}$ en hoger heeft als genererende polynoom

${\displaystyle {\begin{aligned}d(x)&{}={\rm {kgv}}(m_{1}(x),m_{3}(x),m_{5}(x),m_{7}(x))\\&{}=(x^{4}+x+1)(1+x+x^{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\end{aligned}}}$

Deze code heeft minstens hammingafstand 15 en corrigeert 7 bitfouten. De code heeft 1 data-bit en 14 checkbits. Feitelijk bestaat deze code uit de volgende twee codewoorden: 000000000000000 and 111111111111111.

Algemene BCH-codes

Algemene BCH-codes wijken op twee punten af van de hierboven behandelde eenvoudige BCH-codes. Ten eerste is de eis dat ${\displaystyle n=q^{m}-1}$ vervangen door een meer algemene eis. Ten tweede is het zo dat de opeenvolgende wortels van de generatorpolynoom niet bij ${\displaystyle \alpha ^{1}}$ hoeven te beginnen; voldoende is dus als de rij eruitziet als volgt: ${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}}$ (in plaats van ${\displaystyle \alpha ,\ldots ,\alpha ^{d-1}}$).

Definitie

Neem een eindig lichaam ${\displaystyle \mathbb {GF} (q)}$, waarbij ${\displaystyle q}$ een macht is van een priemgetal. Kies positieve gehele getallen ${\displaystyle m,n,d,c}$ zodat ${\displaystyle 2\leq d\leq n}$, ${\displaystyle {\rm {ggd}}(n,q)=1}$, en ${\displaystyle m}$ is de multiplicatieve orde van ${\displaystyle q}$ modulo ${\displaystyle n}$ (dat wil zeggen ${\displaystyle m}$ is de kleinste macht met de eigenschap dat ${\displaystyle q^{m}=1}$ modulo ${\displaystyle n}$).

Zoals hierboven is ${\displaystyle \alpha }$ een primitieve ${\displaystyle n}$-de machts eenheidswortel in ${\displaystyle \mathbb {GF} (q^{m})}$, en is (voor alle i) ${\displaystyle m_{i}(x)}$ de minimale polynoom over ${\displaystyle \mathbb {GF} (q)}$ van ${\displaystyle \alpha ^{i}}$. De generatorpolynoom van de BCH-code is nu gedefinieerd als het kleinste gemeenschappelijke veelvoud ${\displaystyle g(x)={\rm {kgv}}(m_{c}(x),\ldots ,m_{c+d-2}(x))}$.

NB

Als ${\displaystyle n=q^{m}-1}$, zoals in het eenvoudige geval, is ${\displaystyle {\rm {ggd}}(n,q)}$ gelijk aan 1, en is de orde van ${\displaystyle q\mod n}$ automatisch gelijk aan ${\displaystyle m}$. De 'eenvoudige' BCH-code is dus inderdaad een specifiek voorbeeld binnen de algemene BCH-codes.

Eigenschappen

1. De generatorpolynoom van een BCH-code heeft als graad ten hoogste ${\displaystyle (d-1)m}$. En als ${\displaystyle q=2}$ en ${\displaystyle c=1}$, dan is de graad van de generatorpolynoom ten hoogste ${\displaystyle dm/2}$.

Bewijs: elke minimale polynoom ${\displaystyle m_{i}(x)}$ heeft als graad ten hoogste ${\displaystyle m}$. Het kleinste gemeenschappelijke veelvoud van ${\displaystyle d-1}$ minimale polynomen heeft dus ten hoogste de graad ${\displaystyle (d-1)m}$. En als ${\displaystyle q=2}$, is ${\displaystyle m_{i}(x)=m_{2i}(x)}$ voor alle ${\displaystyle i}$. Dus ${\displaystyle g(x)}$ is het kleinste gemeenschappelijke veelvoud van ten hoogste ${\displaystyle d/2}$ minimale polynomen ${\displaystyle m_{i}(x)}$ voor oneven indices ${\displaystyle i}$, die elk ten hoogste de graad ${\displaystyle m}$ hebben.

2. Een BCH-code heeft als minimale hammingafstand ten minste ${\displaystyle d}$. Bewijs in het eenvoudige geval (het bewijs voor het algemene geval is vergelijkbaar). Neem aan dat ${\displaystyle p(x)}$ een codewoord is met minder dan ${\displaystyle d}$ digits ongelijk aan nul. Dan is

${\displaystyle p(x)=b_{1}x^{j_{1}}+\ldots +b_{d-1}x^{j_{d-1}},{\text{ waarbij }}j_{1}<j_{2}<\ldots <j_{d-1}}$

We wisten dat ${\displaystyle \alpha ^{1},\ldots ,\alpha ^{d-1}}$ wortels zijn van ${\displaystyle g(x)}$, en dus ook van ${\displaystyle p(x)}$. Hieruit volgt dat ${\displaystyle b_{1},\ldots ,b_{d-1}}$ aan de volgende vergelijkingen voldoen voor ${\displaystyle i=1,\ldots ,d-1}$:

${\displaystyle p(\alpha ^{i})=b_{1}\alpha ^{ij_{1}}+b_{2}\alpha ^{ij_{2}}+\ldots +b_{d-1}\alpha ^{ij_{d-1}}=0}$

Dit delen we nu door ${\displaystyle \alpha ^{ij_{1}}}$, en we definiëren ${\displaystyle k_{l}=j_{l}-j_{1}}$, om als resultaat te verkrijgen

${\displaystyle b_{1}+b_{2}\alpha ^{ik_{2}}+\ldots +b_{d-1}\alpha ^{ik_{d-1}}=0}$

voor alle ${\displaystyle i}$, hetgeen equivalent is met

${\displaystyle {\begin{bmatrix}1&\alpha ^{k_{2}}&\ldots &\alpha ^{k_{d-1}}\\1&\alpha ^{2k_{2}}&\ldots &\alpha ^{2k_{d-1}}\\\vdots &\vdots &&\vdots \\1&\alpha ^{(d-1)k_{2}}&\ldots &\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}}}$

Deze matrix is een vandermonde-matrix, en heeft als determinant

${\displaystyle \det(V)=\prod _{1\leq i<j\leq d-1}(\alpha ^{k_{j}}-\alpha ^{k_{i}})}$,

hetgeen ongelijk aan nul is. Hieruit volgt dat ${\displaystyle b_{1},\ldots ,b_{d-1}=0}$, en dus ${\displaystyle p(x)=0}$.

3. Een BCH-code is cyclisch.

Bewijs: een polynoomcode met bloklengte ${\displaystyle n}$ is dan en slechts dan cyclisch als zijn generatorpolynoom een deler is van ${\displaystyle x^{n}-1}$. Omdat ${\displaystyle g(x)}$ de minimale polynoom is met wortels ${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}}$, behoeft slechts te worden gecontroleerd dat alle ${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}}$ wortel zijn van ${\displaystyle x^{n}-1}$. Echter, dit volgt direct uit het feit dat ${\displaystyle \alpha }$ per definitie een ${\displaystyle n}$de machts eenheidswortel is.

Speciale gevallen

• Een BCH-code met ${\displaystyle c=1}$ wordt een BCH-code in engere zin genoemd.
• Een BCH-code met ${\displaystyle n=q^{m}-1}$ wordt primitief genoemd.

De hierboven beschouwde "eenvoudige" BCH-codes vormen precies de primitieve BCH-codes in engere zin.

• Een BCH-code in engere zin met ${\displaystyle n=q-1}$ wordt een Reed-Solomon code genoemd.