BCH code

BCH код нь хязгаарлагдмал талбаруудаас бүтсэн, давтагддаг алда засах кодын төрөл юм. 1959 онд Францын математикч Alexis Hocquenghem нь BCH кодыг нээсэн. BCH кодын дизайнын онцлог нь кодоор олон тооны тэмдэгтүүдийг удирдах нарийн удирдлагаар адлааг засдаг. Ихэнхдээ олон битийн алдааг засах боломжтой 2-тын BCH кодыг зохиох боломжтой байдаг. BCH кодын өөр нэг давуу тал нь syndrome decoding буюу алгебрийн аргаар хялбар тайлагдах боломжтой байдаг. Энэ нь уг кодын decoder-ийн зохиомжын хялбарчилдаг буюу жижиг хэмжээний бага хүчдэлийн электрон техник хангамж ашиглах боломжтой юм.

BCH код нь хиймэл дагуулын холбоо, Уян диск тоглуулагч, DVD, disk drives, solid-state drives, 2 хэмжээст bar code зэрэгт ашигладаг.

Анхдагч narrow-sense /нарийвчилсан утга/ BCH код Загвар:Mvar and Загвар:Mvar with d ≤ q^m − 1,-д анхдагч чадал q болон эерэг бүхэл тоо болох m, d нь өгөгдсөн байдаг. Кодийн хэмжээ болох n = q^m − 1 –д анхдагч narrow-sense BCH код нь хязгааргүй талбар болох GF(q), мөн зай /distance/ буюу d хамгийн багадаа доорх аргачлалаар бүтдэг. α –г {{math|GF(q^m)}-ын анхдагч элемент болгоно. Дурын эерэг тоо болох i нь αi-ын хамгийн бага олон гишүүнт байх ба over GF(q). BCH кодын генератор олон гишүүнт нь хамгийн бага энгийн хуваагдах g(x) = lcm(m1(x),…,md − 1(x)) байна. g(x) нь олон гишүүнт GF(q)-ын коеффициент ба xn – 1-д хуваагдана. Түүнчлэн, олон гишүүнт код нь g(x)-ээр давтагдах код гэж тодорхойлогддог. General BCH codes Ерөнхий BCH код нь primitive narrow-sense BCH кодоос 2 төрлийн ялгаатай. Эхнийх нь -ын анхдагч элемент болох а нь чөлөөтэй байх боломжтой. Үүнээс хамаарч кодын урт нь to -с өөрчлөгдөх буюу a элементийн дараалал нь өөрчлөгдөнө. 2 дугаарт, Генератор олон гишүүнтийн дараалсан эцэг элементүүд гэдгээс х хүртэл явах боломжтой.

Example

Let q=2 and m=4 (therefore n=15). Бид d гээс ялгаатай утгуудыг авч үзнэ. There is a primitive root α in GF(16) satisfying

Загвар:NumBlk

its minimal polynomial over GF(2) is

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

The minimal polynomials of the first seven powers of α are

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

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

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

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

The BCH code with $d=2,3$ has generator polynomial

$g(x)=m_{1}(x)=x^{4}+x+1.\,$

It has minimal Hamming distance at least 3 and corrects up to one error. Since the generator polynomial is of degree 4, this code has 11 data bits and 4 checksum bits.

The BCH code with $d=4,5$ has generator polynomial

$g(x)={\rm {lcm}}(m_{1}(x),m_{3}(x))=(x^{4}+x+1)(x^{4}+x^{3}+x^{2}+x+1)=x^{8}+x^{7}+x^{6}+x^{4}+1.\,$

It has minimal Hamming distance at least 5 and corrects up to two errors. Since the generator polynomial is of degree 8, this code has 7 data bits and 8 checksum bits.

The BCH code with $d=8$ and higher has generator polynomial

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

This code has minimal Hamming distance 15 and corrects 7 errors. It has 1 data bit and 14 checksum bits. In fact, this code has only two codewords: 000000000000000 and 111111111111111.

Decoding

BCH кодыг тайлах олон decoding алгоримтууд байдаг. Өргөн хэрэглэдэг доорх аргууд байдаг. 1. Хүлээн авсан векторд sj шинжийг тооцоолох 2. Алдааны тоо t болон алдааны байрлал тодорхойлогч олон гишүүнтийг Λ(x) тодорхойлох мөн 3. Алдааны байрлалын олон гишүүнтийн язгуурыг тооцоолж алдааны байрлал олох Xi 4. Алдааны байрлалууд дээрх алдааны утгыг Yi тодорхойлох 5. Алдааг засах Дээрх алхамуудын үед тайлах алгоритм засагдахааргүй олон тооны алдааг хүлээн авсан вектороос илрүүлэх магадлалтай. Жишээ нь Тухайн хувьсагчийн утга нь олдоогүй тохиолдолд алдаа засах боломжгүй. Товчилсон кодод алдааны байрлал нь хязгаараас хэтрэх магадлалтай. Хүлээн авсан вектор код засаж чадахаас олон тооны алдаа илэрвэл decoder алдааны мессеж өгдөг.

Calculate the syndromes

The received vector $R$ is the sum of the correct codeword $C$ and an unknown error vector $E.$ The syndrome values are formed by considering $R$ as a polynomial and evaluating it at $\alpha ^{c},\ldots ,\alpha ^{c+d-2}.$ Thus the syndromes are

$s_{j}=R(\alpha ^{j})=C(\alpha ^{j})+E(\alpha ^{j})$

for $j=c$ to $c+d-2.$ Since $\alpha ^{j}$ are the zeros of $g(x),$ of which $C(x)$ is a multiple, $C(\alpha ^{j})=0.$ Examining the syndrome values thus isolates the error vector so one can begin to solve for it.

If there is no error, $s_{j}=0$ for all $j.$ If the syndromes are all zero, then the decoding is done.

Calculate the error location polynomial

If there are nonzero syndromes, then there are errors. The decoder needs to figure out how many errors and the location of those errors.

If there is a single error, write this as $E(x)=e\,x^{i},$ where $i$ is the location of the error and $e$ is its magnitude. Then the first two syndromes are

$s_{c}=e\,\alpha ^{c\,i}$

$s_{c+1}=e\,\alpha ^{(c+1)\,i}=\alpha ^{i}s_{c}$

so together they allow us to calculate $e$ and provide some information about $i$ (completely determining it in the case of Reed–Solomon codes).

If there are two or more errors,

$E(x)=e_{1}x^{i_{1}}+e_{2}x^{i_{2}}+\cdots \,$

It is not immediately obvious how to begin solving the resulting syndromes for the unknowns $e_{k}$ and $i_{k}.$ First step is finding locator polynomial

$\Lambda (x)=\prod _{j=1}^{t}(x\alpha ^{i_{j}}-1)$ compatible with computed syndromes and with minimal possible $t.$

Two popular algorithms for this task are:

1. Peterson–Gorenstein–Zierler algorithm
2. Berlekamp–Massey algorithm

Peterson–Gorenstein–Zierler algorithm

Peterson's algorithm is the step 2 of the generalized BCH decoding procedure. Peterson's algorithm is used to calculate the error locator polynomial coefficients $\lambda _{1},\lambda _{2},\dots ,\lambda _{v}$ of a polynomial

$\Lambda (x)=1+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{v}x^{v}.$

Now the procedure of the Peterson–Gorenstein–Zierler algorithm. Expect we have at least 2t syndromes s_c,...,s_c+2t−1. Let v = t.

• Start by generating the $S_{v\times v}$ matrix with elements that are syndrome values

$S_{v\times v}={\begin{bmatrix}s_{c}&s_{c+1}&\dots &s_{c+v-1}\\s_{c+1}&s_{c+2}&\dots &s_{c+v}\\\vdots &\vdots &\ddots &\vdots \\s_{c+v-1}&s_{c+v}&\dots &s_{c+2v-2}\end{bmatrix}}.$

• Generate a $c_{v\times 1}$ vector with elements

$C_{v\times 1}={\begin{bmatrix}s_{c+v}\\s_{c+v+1}\\\vdots \\s_{c+2v-1}\end{bmatrix}}.$

• Let $\Lambda$ denote the unknown polynomial coefficients, which are given by

$\Lambda _{v\times 1}={\begin{bmatrix}\lambda _{v}\\\lambda _{v-1}\\\vdots \\\lambda _{1}\end{bmatrix}}.$

• Form the matrix equation

$S_{v\times v}\Lambda _{v\times 1}=-C_{v\times 1\,}.$

• If the determinant of matrix $S_{v\times v}$ is nonzero, then we can actually find an inverse of this matrix and solve for the values of unknown $\Lambda$ values.
• If $\det(S_{v\times v})=0,$ then follow

       if $v=0$
       then
             declare an empty error locator polynomial
             stop Peterson procedure.
       end
       set $v\leftarrow v-1$
       continue from the beginning of Peterson's decoding by making smaller $S_{v\times v}$

• After you have values of $\Lambda$, you have with you the error locator polynomial.
• Stop Peterson procedure.