BCH code

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

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

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[edit] 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[5]

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[edit] 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:

Peterson–Gorenstein–Zierler algorithm Berlekamp–Massey algorithm