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

Primitive narrow-sense BCH codes

Given a prime power q and positive integers m and d with d ≤ q^m − 1, a primitive narrow-sense BCH code over the finite field GF(q) with code length n = q^m − 1 and distance at least Загвар:Mvar is constructed by the following method.

Let Загвар:Mvar be a primitive element of GF(q^m). For any positive integer Загвар:Mvar, let m_i(x) be the minimal polynomial of αⁱ over GF(q). The generator polynomial of the BCH code is defined as the least common multiple g(x) = lcm(m₁(x),…,m_{d − 1}(x)). It can be seen that g(x) is a polynomial with coefficients in GF(q) and divides xⁿ − 1. Therefore, the polynomial code defined by g(x) is a cyclic 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.

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

General BCH codes

General BCH codes differ from primitive narrow-sense BCH codes in two respects.

First, the requirement that $\alpha$ be a primitive element of $\mathrm {GF} (q^{m})$ can be relaxed. By relaxing this requirement, the code length changes from $q^{m}-1$ to $\mathrm {ord} (\alpha ),$ the order of the element $\alpha .$

Second, the consecutive roots of the generator polynomial may run from $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$ instead of $\alpha ,\ldots ,\alpha ^{d-1}.$

Definition. Fix a finite field $GF(q),$ where $q$ is a prime power. Choose positive integers $m,n,d,c$ such that $2\leq d\leq n,$ ${\rm {gcd}}(n,q)=1,$ and $m$ is the multiplicative order of $q$ modulo $n.$

As before, let $\alpha$ be a primitive $n$th root of unity in $GF(q^{m}),$ and let $m_{i}(x)$ be the minimal polynomial over $GF(q)$ of $\alpha ^{i}$ for all $i.$ The generator polynomial of the BCH code is defined as the least common multiple $g(x)={\rm {lcm}}(m_{c}(x),\ldots ,m_{c+d-2}(x)).$

Note: if $n=q^{m}-1$ as in the simplified definition, then ${\rm {gcd}}(n,q)$ is automatically 1, and the order of $q$ modulo $n$ is automatically $m.$ Therefore, the simplified definition is indeed a special case of the general one.

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