BCH code

Чөлөөт нэвтэрхий толь — Википедиагаас
Jump to navigation Jump to search

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 код d ≤ qm – 1-д анхдагч чадал q болон эерэг бүхэл тоо болох m, d нь өгөгдсөн байдаг. Кодийн хэмжээ болох n = qm – 1 –д анхдагч narrow-sense BCH код нь хязгааргүй талбар болох GF(q), мөн зай /distance/ буюу d хамгийн багадаа доорх аргачлалаар бүтдэг. α –г GF(qm)-ын анхдагч элемент болгоно. Дурын эерэг тоо болох i нь αi-ын хамгийн бага олон гишүүнт байх ба over GF(q). BCH кодын генератор олон гишүүнт нь хамгийн бага энгийн хуваагдах g(x) = lcm(m1(x),…,md − 1(x)) байна. g(x) нь олон гишүүнт GF(q)-ын коеффициент ба xn – 1-д хуваагдана. Түүнчлэн, олон гишүүнт код нь g(x)-ээр давтагдах код гэж тодорхойлогддог.

Жишээ[засварлах | edit source]

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

its minimal polynomial over GF(2) is

The minimal polynomials of the first seven powers of are

The BCH code with has generator polynomial

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 has generator polynomial

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 and higher has generator polynomial

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.

Ерөнхий BCH[засварлах | edit source]

Ерөнхий BCH код нь primitive narrow-sense BCH кодоос 2 төрлийн ялгаатай. Эхнийх нь -ын анхдагч элемент болох а нь чөлөөтэй байх боломжтой. Үүнээс хамаарч кодын урт нь to -с өөрчлөгдөх буюу a элементийн дараалал нь өөрчлөгдөнө. 2 дугаарт, Генератор олон гишүүнтийн дараалсан эцэг элементүүд гэдгээс х хүртэл явах боломжтой.

Тодорхойлолт. q нь анхдагч чадал ба хязгааргүй талбарыг тодорхойлно. гэдгээс эерэг бүхэл тоонуудыг сонгох, мөн нь нэмэгдүүлсэн modulo -ын дараалал юм.

Үүнээс дээрх -г анхдагч -р нэгдэлийн эцэг болгож, -г бүх -ын хувьд хамгийн бага -ын -ын олон гишүүнт байна. BCH кодын генератор олон гишүүнт нь -ын хамгийн бага ерөнхий үржүүлэгч юм. Тэмдэглэл. Хэрвээ нь хялбаршуулсан тодорхойлолтоор, нь автоматаар 1 болох ба modulo -ын дараалал мөн автоматаар болно. Үүнээс хялбарчилсан тодорхойлолт нь ерөнхий байдлаас гадна онцгой нөхцөлд ашиглагдана.



Decoding

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

Calculate the syndromes[засварлах | edit source]

The received vector is the sum of the correct codeword and an unknown error vector The syndrome values are formed by considering as a polynomial and evaluating it at Thus the syndromes are[1]

for to Since are the zeros of of which is a multiple, Examining the syndrome values thus isolates the error vector so one can begin to solve for it.

If there is no error, for all If the syndromes are all zero, then the decoding is done.

Calculate the error location polynomial[засварлах | edit source]

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 where is the location of the error and is its magnitude. Then the first two syndromes are

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

If there are two or more errors,

It is not immediately obvious how to begin solving the resulting syndromes for the unknowns and First step is finding locator polynomial

compatible with computed syndromes and with minimal possible

Two popular algorithms for this task are:

  1. Peterson–Gorenstein–Zierler algorithm
  2. Berlekamp–Massey algorithm
    1. Lidl & Pilz 1999, p. 229