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). We will consider different values of Загвар:Mvar. 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 алдааны мессеж өгдөг.