Constructie
Een BCH-code wordt gegenereerd door een polynoom over een eindig lichaam
, waarin
een macht van een priemgetal is.
Een eenvoudige klasse BCH-codes
- Definitie
Voor positieve gehele getallen
en
met
een priemgetal,
en
, wordt een polynoomcode met bloklengte
en een minimum hammingafstand van minstens
bepaald door de genererende polynoom die het kleinste gemeenschappelijke veelvoud
is. Daarin is
de minimale polynoom van
over
, met
een primitief element in
.
Voorbeeld
In het voorbeeld is
en
, dus
.
Volgens de theorie bestaat er een primitieve wortel
met een minimale polynoom van graad
die voldoet aan:
![{\displaystyle \alpha ^{4}+\alpha +1=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86a5e40e15897843ac7639a532ad23a78401d5c1)
De bijbehorende minimale polynoom over
is:
![{\displaystyle m_{1}(x)=x^{4}+x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/67a3e90397f55d1db87dc310e7fef5fb2ac4bda7)
In
geldt
, zodat:
![{\displaystyle m_{1}(\alpha ^{2})=\alpha ^{8}+\alpha ^{2}+1=(m_{1}(\alpha ))^{2}=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c395873fa6ab4834fe71fb146ffb5c641662aaa)
Dus
is een wortel van
, en blijkbaar is:
![{\displaystyle m_{2}(x)=m_{1}(x)=x^{4}+x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/77223fd45b6611416eae5b232d86e9796267e633)
De minimale polynoom
van
is ook van de graad 4:
Nu is:
,
dus
,
zodat
![{\displaystyle \alpha ^{6}=\alpha ^{4}\alpha ^{2}=(\alpha +1)\alpha ^{2}=\alpha ^{3}+\alpha ^{2))](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad7acb145f7666087dc27d9960b0103d397354ae)
![{\displaystyle \alpha ^{9}=(\alpha ^{4})^{2}\alpha =(\alpha ^{2}+1)\alpha =\alpha ^{3}+\alpha }](https://wikimedia.org/api/rest_v1/media/math/render/svg/ba7af366dac688a4f1350c38170c073bf8086927)
![{\displaystyle \alpha ^{12}=(\alpha ^{4})^{3}=(\alpha +1)^{3}=(\alpha ^{2}+1)(\alpha +1)=\alpha ^{3}+\alpha ^{2}+\alpha +1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2688e3306705b53c629cafe9ce6ba65fd86c3572)
Het blijkt dat
![{\displaystyle =\alpha ^{3}+\alpha ^{2}+\alpha +1+\alpha ^{3}+\alpha +\alpha ^{3}+\alpha ^{2}+\alpha ^{3}+1=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d6e27b0a5b7293581938e39fa9ab688fbe1339d6)
De minimale polynoom van
is de polynoom
.
Op vergelijkbare wijze vindt men:
![{\displaystyle m_{4}(x)=m_{2}(x)=x^{4}+x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d886645ecfe881a4bb597527536b0cb0bcaadaa0)
![{\displaystyle m_{5}(x)=x^{2}+x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2c05d4a062c0861a30c5421b8baadd1d69a3349c)
![{\displaystyle m_{6}(x)=m_{3}(x)=x^{4}+x^{3}+x^{2}+x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/770a1c9bdb966bc0ee0e00e82bd16bca79b4dd1f)
![{\displaystyle m_{7}(x)=x^{4}+x^{3}+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/456a2327bc19ab7514041d0fea9b3279175cbc6b)
Deze polynomen zijn juist de vier irreducibele polynomen.
De BCH-code met
heeft als genererende polynoom
![{\displaystyle d(x)=m_{1}(x)=x^{4}+x+1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb56aa6638a56fe11f6246ea72aa2086d78e7cb9)
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
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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4324621395d0bc1f2a29150eadd8aca7ae5e8932)
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
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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33f5fae4d80d620939a2093305865b91207c8209)
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
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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5d91db74c21067201069f0dd46ebed05ebf08a02)
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
vervangen door een meer algemene eis. Ten tweede is het zo dat de opeenvolgende wortels van de generatorpolynoom niet bij
hoeven te beginnen; voldoende is dus als de rij eruitziet als volgt:
(in plaats van
).
- Definitie
Neem een eindig lichaam
, waarbij
een macht is van een priemgetal. Kies positieve gehele getallen
zodat
,
, en
is de multiplicatieve orde van
modulo
(dat wil zeggen
is de kleinste macht met de eigenschap dat
modulo
).
Zoals hierboven is
een primitieve
-de machts eenheidswortel in
, en is (voor alle i)
de minimale polynoom over
van
. De generatorpolynoom van de BCH-code is nu gedefinieerd als het kleinste gemeenschappelijke veelvoud
.
- NB
Als
, zoals in het eenvoudige geval, is
gelijk aan 1, en is de orde van
automatisch gelijk aan
. 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
. En als
en
, dan is de graad van de generatorpolynoom ten hoogste
.
- Bewijs: elke minimale polynoom
heeft als graad ten hoogste
. Het kleinste gemeenschappelijke veelvoud van
minimale polynomen heeft dus ten hoogste de graad
. En als
, is
voor alle
. Dus
is het kleinste gemeenschappelijke veelvoud van ten hoogste
minimale polynomen
voor oneven indices
, die elk ten hoogste de graad
hebben.
2. Een BCH-code heeft als minimale hammingafstand ten minste
. Bewijs in het eenvoudige geval (het bewijs voor het algemene geval is vergelijkbaar). Neem aan dat
een codewoord is met minder dan
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))](https://wikimedia.org/api/rest_v1/media/math/render/svg/7674fe9db2bd48884a66aa479180dda9c6ea34d3)
We wisten dat
wortels zijn van
, en dus ook van
. Hieruit volgt dat
aan de volgende vergelijkingen voldoen voor
:
![{\displaystyle p(\alpha ^{i})=b_{1}\alpha ^{ij_{1))+b_{2}\alpha ^{ij_{2))+\ldots +b_{d-1}\alpha ^{ij_{d-1))=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc539cbd1069a487338d7884f32ee7c8a7e1dfa8)
Dit delen we nu door
, en we definiëren
, om als resultaat te verkrijgen
![{\displaystyle b_{1}+b_{2}\alpha ^{ik_{2))+\ldots +b_{d-1}\alpha ^{ik_{d-1))=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/339f4f00f18bf2ecf20c15df8346032a631297e9)
voor alle
, 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))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3fee37dd9b0cf3f436d497f8cac2321e4308f4ff)
Deze matrix is een vandermonde-matrix, en heeft als determinant
,
hetgeen ongelijk aan nul is. Hieruit volgt dat
, en dus
.
3. Een BCH-code is cyclisch.
Bewijs: een polynoomcode met bloklengte
is dan en slechts dan cyclisch als zijn generatorpolynoom een deler is van
. Omdat
de minimale polynoom is met wortels
, behoeft slechts te worden gecontroleerd dat alle
wortel zijn van
. Echter, dit volgt direct uit het feit dat
per definitie een
de machts eenheidswortel is.
Speciale gevallen
- Een BCH-code met
wordt een BCH-code in engere zin genoemd.
- Een BCH-code met
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
wordt een Reed-Solomon code genoemd.