Цикл код

Цикл код - Кодын онолд алдаа илрүүлэх болон засахад тохирсон алгебрийн бүтэцтэй Цикл код нь “шугаман блок алдаа засах код”-ын бүлэгт хамаардаг.

Тодорхойлолт

Төгсгөлөг талбар дээрхи n урттай блокод хуваасан шугаман код C-г цикл код гэнэ. Хэрэв С кодын үг (codeword)-ийн c=(c₁,...,c_n) утга бүрийг баруун тийш шилжүүлбэл төгсгөлөг талбар дээр хүлээж авсан үг (c_n,c₁,...,c_n-1)нь дахин кодын үг байна. Зүүн тийш шилжүүлэхэд ижилхэн кодын үг (c₂,c₃,...,c_n,c_n-1) үүснэ. Иймээс шугаман код С нь тогтмол бүх тойрог шилжүүлэлтийн үед Цикл код байна.

Цикл кодийг зарим нэмэлт бүтцийн хязгаарлалттайгаар кодонд хэрэгжүүлдэг. Энэ Галуагийн талбарт суурилсан ба бүтцийн онцлогоос хамаарч алдааны удирдлагад хэрэглэхэд тохиромжтой байдаг. Цикл кодонд зориулсан кодлох болон тайлах аргууд нь өндөр үр дүнтэй байдаг учраас түүний бүтэц нь Галуагийн талбартай нягт холбоотой байдаг.

Алгебрийн бүтэц

Цикл кодыг цагирагаар төсөөлж болно. $R=A[x]/(x^{n}-1)$ нь төгсгөлөг талбар $A=GF(q)$-д дүрслэгдсэн олон гишүүнтийн цагираг юм. С цикл кодын элементүүдийг R-ийн олон гишүүнттэй адилтгаж болно. Энэ нь (c₀,...,c_n-1)-ийг олон гишүүнт рүү буулгасан буулгалт нь $c_{0}+c_{1}x+\cdots +c_{n-1}x^{n-1}$ болно. Энэд х-ээр үржсэн үржвэр нь тойргоор шилжүүлсэнтэй таарна. С-гийн хамгийн бага зэргийн элементээр үүсгэгч олон гишүүнт g-г үүсгэнэ. Энэ нь $x^{n}-1$-ийн хуваагч байх ёстой. Үүнээс бүх цикл код нь олон гишүүнт код гэж мөрдөнө. Хэрэв үүсгэгч олон гишүүнтийн зэрэг $d$ бол код С-ийн зэрэг $n-d$ болно.

Үүсгэгч олон гишүүнт нь дахин хуваагддаггүй байна.

Цикл кодыг ганц алдаа засахад ашиглах

Цикл кодыг Хэммингийн кодтой адилхан ганц алдаа, давхар алдаа, үргэлжилсэн алдааг засахад хэрэглэдэг. Бүх алдаа засах төрлүүдийг дэд хэсэг болгон авч үздэг. (7,4) Хэммингийн кодонд үүсгэгч олон гишүүнт нь $g(x)=x^{3}+x+1$ байна. Энэ олон гишүүнт нь Галуагийн өргөтгсөн талбар $GF(8)$ дээрхи үндсэн элемент $\alpha$ ба бүх кодын үг дотроос ${\mathcal {C}}(\alpha )=0$ нөхцлийг хангах олон гишүүнт байна. Цикл кодийг Галуагийн $GF(2)$ талбар дээрхи давхар алдааг засахад бас ашигладаг. "2" ширхэг алдааг засахын тулд нэг алдааг засах дараах хоёр нөхцлийг хоёуланг авч үзэх ёстой.

Нэгт. Блокын урт n нь $2^{m}-1$-тэй тэнцүү байх

Хоёрт. Үндсэн элемент $\alpha$ ба $\alpha ^{3}$ нь Галуагийн $GF(2^{m})$ талбар дээр тэг байх

Хүлээж авсан үг нь хэлбэртэй зэрэгтэй олон гишүүнт байна. Үүнд: e(x)-д "2" алдааг засахын тулд хамгийн их хоёр тэгээс ялгаатай коеффициент агуулагдаж байх ёстой.

“Синдром олон гишүүнт” -ийг тодорхойлох ёстой. $S(x)$ нь $v(x)$ олон гишүүнтийг $g(x)$ үүсгэгч олон гишүүнтэд хуваагаад гарсан үлдэгдэл юм.

Хоёр алдаа засахад ашиглах

$X_{1}$ ба $X_{2}$ элементийн алдааны байрлалыг олье. Хэрэв ганц алдаа илэрвэл $X_{2}$ тэгтэй тэнцүү байна. Хэрэв алдаа илрээгүй бол хоёулаа тэг байна.

$S_{1}={v}(\alpha )$ ба $S_{3}={v}(\alpha ^{3})$-ийг ольё.

Эдгээрийг “Синдром” гэж нэрлэнэ. $g(x)$ нь тэг гэдгээс үндсэн элемент $\alpha$ ба $\alpha ^{3}$-ийг тодорхойлбол $S_{1}=e(\alpha )$ ба $S_{3}=e(\alpha ^{3})$ болно. Хэрэв хоёр алдаа илэрвэл $S_{1}=\alpha ^{i}+\alpha ^{i'}$ ба $S_{3}=\alpha ^{3i}+\alpha ^{3i'}$ болно. Эдгээр хоёр тэнцэтгэл нь Галуагийн талбар $GF(2^{m})$-т харьялагдах бөгөөд үл мэдэгдэх гишүүнтэй бол дараах байдлаар бичиж болно.

$S_{1}=X_{1}+X_{2}$ ба $S_{3}=(X_{1})^{3}+(X_{2})^{3}$.

Энэ хоёр хос нь шугаман тэнцэтгэлийг шийдэж чадах ба хоёр алдааг засч чадна.

Хэммингийн код

Хэммингийн (7,4) код нь $1+x+x^{3}$ үүсгэгч олон гишүүнтээр Галугаийн GF(2) талбар дээр үүсгэгдсэн цикл код юм. Хоёртын Хэммингийн Ham(2,q) хэлбэртэй код нь цикл кодтой адилхан бөгөөд q нь тэгш тоо юм. Хэммингийн кодын Ham(r,2) хэлбэр нь $r\geq 3$ үед бас цикл код байна. Эдгээр нь $[2^{r}-1,2^{r}-r-2,4]$ кодууд юм.

Үргэлжилсэн алдаа засах Цикл код

Үргэлжилсэн алдаа

“Хэммингийн зай” ойлголтоос үүдэн хамгийн бага зай нь $2t+1$ байвал $t$ хэмжээний алдааг засч чадна. Гэвч ихэнхи сувгийн алдаанууд нь санаандгүй үүсдэггүй ба мэдээллийн асар бага хэсэгт илэрдэг. Эдгээр алдааг үргэлжилсэн алдаа гэж нэрлэдэг. Тиймээс эдгээр алдааг засахын тулд илүү үр дүнтэй арай өндөр гүйцэтгэлтэй, нэмэлт бүтэц багатай код ашиглах хэрэгтэй. Үргэлжилсэн алдааг засахад цикл кодыг ашигладаг. Цикл код нь бас цикл үргэлжилсэн алдааг засч чаддаг. $t$ урттай цикл үргэлжилсэн алдаа нь вектор хэмжигдэхүүн бөгөөд $t$ урттай дараалсан тэгээс ялгаатай элементүдийг агуулна. Эхний бөгөөд сүүлчийн бит тэг биш байна.

$t$ урттай үргэлжилсэн цикл алдааг $t-1$ зэрэгтэй тэгээс ялгаатай коэффициенттэй дараах олон гишүүнтээр илэрхийлж болно. Алдааны урт $b(x)+1$-аар тодорхойлогдоно.

Синдром олон гишүүнт нь төлөв бүрийн хувьд цор ганц байхыг дараах томьёоноос харж болно.

$s(x)=e(x)\mod g(x)$

Шугаман блок код нь хамгийн багадаа $t$-ээс $2t$ хүртэлх үргэлжилсэн алдааг засч чадна.