BCH-code (coderingstheorie)

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een BCH-code is binnen de coderingstheorie een foutcorrigerende code die de laatste 50 jaar bij wetenschappers veel onder de aandacht gestaan heeft. BCH-codes werden in 1959 uitgevonden door Hocquenghem, en onafhankelijk daarvan in 1960 door Bose and Ray-Chaudhuri. De afkorting BCH is opgebouwd uit de initialen van de uitvinders.

Een groot voordeel van BCH-codes is dat ze worden gedecodeerd middels 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 bit error rates. 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[bewerken]

Een BCH-code is een polynoomcode over een eindig lichaam met een bepaald genererend polynoom. Het is tevens een cyclische code.

Een eenvoudige klasse BCH-codes[bewerken]

Om het begrip helder over te brengen, wordt als eerste een speciale klasse BCH-codes behandeld.

Definitie. Neem een eindig lichaam GF(q), waarbij q de macht van een priemgetal is. Neem positieve gehele getallen m, n, en d zodanig dat n=q^m-1 en 2 \leq d \leq n. We construeren een polynoomcode over GF(q) met bloklengte n, en een minimum Hammingafstand van minstens d. Wat nu nog dient te worden gespecificeerd is het genererend polynoom van deze code.

Zij \alpha een primitieve n-de machts eenheidswortel GF(q^m). Voor alle i, duiden we als m_i(x) aan het minimale polynoom van \alpha^i met coëfficiënten in GF(q). Het genererend polynoom van de BCH-code is gedefinieerd als het kleinste gemeenschappelijke veelvoud g(x) = {\rm kgv}(m_1(x),\ldots,m_{d-1}(x)).

Voorbeeld[bewerken]

Stel dat q=2 en m=4 (hieruit volgt dat n=15). We zullen meerdere waarden van d behandelen. Er bestaat een primitieve wortel \alpha\in GF(16) die voldoet aan

\alpha^4+\alpha+1=0 (1);

het bijbehordende minimale polynoom over GF(2) is: m_1(x) = x^4+x+1. Merk op dat in GF(2), de vergelijking (a+b)^2 = a^2 + 2ab + b^2 = a^2 + b^2 van toepassing is, waardoor geldt dat m_1(\alpha^2) = m_1(\alpha)^2 = 0. Dus \alpha^2 is een wortel van m_1(x), en er geldt dus dat

m_2(x) = m_1(x) = x^4+x+1.

Om m_3(x) te berekenen dienen we op te merken dat, door herhaald toepassen van vergelijking (1), de volgende lineaire vergelijkingen kunnen worden verkregen:

  • 1 = 0\alpha^3 + 0\alpha^2 + 0\alpha + 1
  • \alpha^3 = 1\alpha^3 + 0\alpha^2 + 0\alpha + 0
  • \alpha^6 = 1\alpha^3 + 1\alpha^2 + 0\alpha + 0
  • \alpha^9 = 1\alpha^3 + 0\alpha^2 + 1\alpha + 0
  • \alpha^{12} = 1\alpha^3 + 1\alpha^2 + 1\alpha + 1

De vijf rechterzijden moeten afhankelijk zijn, en inderdaad vinden we dat \alpha^{12}+\alpha^9+\alpha^6+\alpha^3+1=0. Omdat er geen afhankelijkheid van kleinere graad bestaat, is het minimale polynoom van \alpha^3 het polynoom m_3(x) = x^4+x^3+x^2+x+1.

Op vergelijkbare wijze vinden we dat

m_4(x) = m_2(x) = x^4+x+1,\,
m_5(x) = x^2+x+1,\,
m_6(x) = m_3(x) = x^4+x^3+x^2+x+1,\,
m_7(x) = x^4+x^3+1.\,
  • De BCH-code met d=1, \, 2, \, 3 heeft als genererend polynoom
d(x) = m_1(x) = x^4+x+1.\,

De minimale Hamming-afstand is minstens 3 en hij corrigeert 1 bitfout. Omdat het genererend polynoom de graad 4 heeft, heeft deze code 11 data-bits en 4 checkbits.

  • De BCH code met d=4, \, 5 heeft als genererend polynoom
 
\begin{align}
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{align}

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

  • De BCH-code met d=6, \, 7 heeft als genererend polynoom

\begin{align}
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{align}

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

  • De BCH-code met d=8 \, en hoger heeft als genererend polynoom

\begin{align}
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{align}

Deze code heeft minstens Hamming-afstand 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[bewerken]

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

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

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

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

Eigenschappen[bewerken]

1. Het generatorpolynoom van een BCH-code heeft als graad ten hoogste (d-1)m. En als q=2 en c=1, dan is de graad van het generatorpolynoom ten hoogste dm/2.

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

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

p(x) = b_1x^{j_1} + \cdots + b_{d-1}x^{j_{d-1}},\text{ waarbij }j_1<j_2<\cdots<j_{d-1}.

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

p(\alpha^i) = b_1\alpha^{ij_1} + b_2\alpha^{ij_2} + \cdots + b_{d-1}\alpha^{ij_{d-1}} = 0.

Dit delen we nu door \alpha^{ij_1}, en we definiëren k_l = j_l - j_1, om als resultaat te verkrijgen

b_1 + b_2\alpha^{ik_2} + \cdots + b_{d-1}\alpha^{ik_{d-1}} = 0

voor alle i, hetgeen equivalent is met

\begin{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}
\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

\det(V) = \prod_{1\le i<j\le d-1} (\alpha^{k_j}-\alpha^{k_i}),

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

3. Een BCH-code is cyclisch.

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

Speciale gevallen[bewerken]

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

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