Цикл кодуудыг нэг буюу хэд хэдэн кодын хослолыг циклээр солих замаар зарим буюу бүх кодын хослолыг олж авч болох тул ийм нэрлэсэн. Циклийн шилжилт нь баруунаас зүүн тийш хийгдэх бөгөөд хамгийн зүүн талын тэмдэг нь хослолын төгсгөлд шилжинэ. Бараг бүх цикл кодууд нь системчилсэн кодуудад хамаардаг бөгөөд хяналтын болон мэдээллийн битүүд нь хатуу тодорхойлогдсон газруудад байрладаг. Үүнээс гадна кодуудыг блок код гэж ангилдаг. Блок бүр (нэг үсэг нь блокийн онцгой тохиолдол) тус тусад нь кодлогдсон байдаг.

Цикл кодыг бүтээх санаа нь хоёртын тоонуудын талбарт бууруулж болохгүй олон гишүүнтүүдийг ашиглахад суурилдаг. Бууруулах боломжгүйАнхны тоог бусад тоонуудын үржвэрээр дүрслэх боломжгүйтэй адил ижил талбарын коэффициент бүхий доод зэргийн олон гишүүнтүүдийн үржвэрээр дүрслэх боломжгүй олон гишүүнт гэж нэрлэдэг. Өөрөөр хэлбэл, бууруулж болохгүй олон гишүүнтүүд үлдэгдэлгүйгээр зөвхөн өөртөө эсвэл нэгээр хуваагддаг.

Циклийн кодын онол дахь бууруулж болохгүй олон гишүүнт олон гишүүнт үүсгэх үүрэг гүйцэтгэдэг. Хэрэв өгөгдсөн кодын хослолыг сонгогдсон бууруулж болохгүй олон гишүүнтээр үржүүлбэл бид залруулах чадвар нь бууруулж болохгүй олон гишүүнт тодорхойлогддог цикл кодыг олж авна.

Та дөрвөн оронтой хоёртын кодын аль нэгийг кодлох хэрэгтэй гэж бодъё. Энэ хослолыг бас авч үзье G(x) = x 3 + x 2 + 1 ® 1011. Сонголтоо зөвтгөхгүйгээр бид бууруулж болохгүй олон гишүүнтүүдийн хүснэгтээс үүсгэгч олон гишүүнтийг авдаг. P(x) = x 3 + x + 1 ® 1011. Дараа нь үржүүлнэ G(x)үүсгэгч олон гишүүнтэй ижил зэрэгтэй мономиалаар. Олон гишүүнтийг зэрэгтэй мономиалаар үржүүлэхээс nолон гишүүнт гишүүн бүрийн зэрэг нь нэмэгдэнэ n, энэ нь оноохтой тэнцэнэ nолон гишүүнтийн доод эрэмбийн тал дээрх тэг. Сонгосон бууруулж болохгүй олон гишүүнтийн зэрэг нь гурван тул анхны мэдээллийн хослолыг гурван градусын мономиалаар үржүүлнэ.

G(x) x n =(x 3 + x 2 + 1) x 3 =x 6 + x 5 + x 3 = 1101000.

Дараа нь эдгээр тэгүүдийн оронд залруулах цифрүүдийг бичихийн тулд үүнийг хийдэг.

Залруулсан цифрүүдийн утгыг хуваах үр дүнгээс олно G(x)xnдээр P(x):

x 6 +x 5 +0+x 3 +0+0+0 ½x 3 +x+1

x 6 +0+x 4 +x 3

x 5 +x 4 +0+0 x 3 +x 2 +x+1+ x 5 +0+x 3 +x 2

x 4 + x 3 +x 2 +0

x 4 + 0 +x 2 +x

x 3 +0+x+0

x 3 +0+x+1

Тиймээс,

эсвэл ерөнхийдөө

Хаана Q(x)¾ хэсэг, ба R(x)¾ хуваалтын үлдэгдэл G(x)×x nдээр P(x).

Хоёртын арифметикт 1 Å 1 = 0, тиймээс -1 = 1 тул хоёртын тоог нэмэхдээ тэмдгийг өөрчлөхгүйгээр (тохиромжтой бол) нэг хэсгээс нөгөөд шилжүүлэх боломжтой тул хэлбэрийн тэгш байдал. a Å b = 0 гэж бас бичиж болно a = b, яаж a - b = 0. Энэ тохиолдолд бүх гурван тэгш байдал нь аль нэгийг илэрхийлнэ аТэгээд б 0-тэй тэнцүү эсвэл аТэгээд б 1-тэй тэнцүү байна, өөрөөр хэлбэл. ижил тэнцүү байна.

Иймд (5.1) илэрхийллийг дараах байдлаар бичиж болно

F(x)=Q(x) P(x)= G(x) x n +R(x),

Энэ нь бидний жишээн дээр өгөх болно

F(x)=(x 3 + x 2 + x + 1) (x 3 + x + 1)= (x 3 + x 2 + 1)x 3 + 1,

F(x)= 1111 1011 = 1101000 + 001 = 1101001.

1101001 олон гишүүнт нь хүссэн хослол бөгөөд 1101 нь мэдээллийн хэсэг, 001 нь хяналтын тэмдэгт юм. Бүрэн дөрвөн оронтой хоёртын кодын хослолуудын аль нэгийг (энэ тохиолдолд 1111) үүсгэгч олон гишүүнээр үржүүлсний үр дүнд, мөн өгөгдсөн хослолыг ижил зэрэгтэй мономиалаар үржүүлснээр бид хүссэн хослолыг олж авна гэдгийг анхаарна уу. сонгогдсон үүсгэгч олон гишүүнт байдлаар (бидний тохиолдолд 1101000 хослолыг ийм аргаар олж авсан бөгөөд дараа нь энэ бүтээгдэхүүнийг үүсгэгч олон гишүүнт хуваасан үлдэгдлийг гарсан бүтээгдэхүүнд нэмсэн (бидний жишээнд үлдсэн хэсэг нь 001 хэлбэртэй байна).

Энд үүсгэгч олон гишүүнтийн шинж чанарууд шийдвэрлэх үүрэг гүйцэтгэдэг P(x). Цикл кодыг бүтээх арга нь генераторын олон гишүүнт кодын хослол бүрийг бүрдүүлэхэд оролцдог тул цикл кодын аль ч олон гишүүнт үлдэгдэлгүй генераторт хуваагддаг. Гэхдээ зөвхөн тухайн кодонд хамаарах олон гишүүнтүүдийг үлдэгдэлгүйгээр хуваадаг, өөрөөр хэлбэл үүсгэгч олон гишүүнт нь бүх боломжит хослолуудаас зөвшөөрөгдсөн хослолуудыг сонгох боломжийг олгодог. Хэрэв цикл кодыг үүсгэгч олон гишүүнт хуваах үед үлдэгдэл гарвал кодонд алдаа гарсан эсвэл бусад кодын хослол (хориотой хослол) байна. Үлдсэн хэсэг нь хориотой хослол байгааг харуулж байна, өөрөөр хэлбэл алдаа илэрсэн байна. Олон гишүүнт хуваагдсан үлдэгдэл нь мөчлөгийн кодын алдаа илрүүлэгч юм.

Нөгөө талаас нэгийг тэгтэй хуваах олон гишүүнтийн үлдэгдлийг цикл кодыг бүтээхэд ашигладаг.

Тэгтэй нэгжийг үүсгэгч олон гишүүнтээр хуваахдаа үлдэгдлийн урт нь шалгах цифрүүдийн тооноос багагүй байх ёстой гэдгийг санах хэрэгтэй, тиймээс хэрэв үлдсэн хэсэгт хангалттай цифр байхгүй бол шаардлагатай тооны тэгийг нэмнэ. үлдсэн хэсгийн баруун талд.

01100 11111+

наймаас эхлэн үлдэгдэл нь давтагдана.

Хуваалтын үлдэгдлийг үүсгэгч матрицыг бүтээхэд ашигладаг бөгөөд тэдгээр нь тодорхой бөгөөд дериватив хослолыг авахад хялбар байдаг тул цикл кодыг бүтээхэд өргөн хэрэглэгддэг. Үүсгэх матрицыг бий болгох нь нэгийг үүсгэгч олон гишүүнтээр тэгээр хуваахад элементүүд нь үлдэгдэл болох нэгжийн шилжүүлсэн болон нэмэлт матрицыг эмхэтгэх явдал юм. P(x). Нэгж шилжүүлсэн матриц нь дөрвөлжин матриц бөгөөд баруунаас зүүн тийш дээрээс доош диагональ байрлалтай элементүүдээс бусад бүх элементүүд нь тэгтэй тэнцүү байдаг (шилжүүлээгүй матрицад нэгж элементүүдтэй диагональ нь дараахаас байрлана) зүүнээс баруун тийш дээрээс доош). Нэмэлт матрицын элементүүдийг таних тэмдэг шилжүүлсэн матрицын баруун талд хуваарилдаг. Зөвхөн жинтэй үлдэгдэл W ³ d 0- 1, хаана d 0- хамгийн бага кодын зай. Үлдэгдэлийн урт нь хяналтын битийн тооноос багагүй байх ёстой бөгөөд үлдэгдэл нь мэдээллийн битийн тоотой тэнцүү байх ёстой.

Үүсгэх матрицын мөрүүд нь эхний хослолуудыг илэрхийлнэ эх код. Үлдсэн кодын хослолыг модуль 2-ыг үүсгэгч матрицын мөрүүдийн бүх боломжит хослолыг нэгтгэн гаргаж авна.

Жишээ.

10 битийн хоёртын хослолыг дамжуулахад дан болон давхар алдааг илрүүлдэг цикл кодын бүрэн үүсгэгч матрицыг байгуул.

Шийдэл.

Хүснэгт 5.12-ын дагуу хамгийн ойрын утгыг сонгоно k ³ 10.

Хүснэгт 5.12 – 16 бит хүртэл урттай кодын мэдээлэл ба шалгах тэмдэгтүүдийн хоорондын хамаарал

n	к	ρ	n	к	ρ

Хүснэгтийн дагуу энэ утга нь байх болно k = 11, байхад r = 4, А

n= 15. Бид мөн үүсгэгч олон гишүүнийг сонгодог x 4 + x 3 +1.

Бид каноник хэлбэрт шилжүүлсэн нэгж матрицаас бүрэн үүсгэгч матриц болон шалгах битүүдэд тохирох нэмэлт матрицыг бүтээдэг.

Шилжүүлсэн матриц k = 11 дараах байдалтай байна.

Сонгосон үүсгэгч олон гишүүнт тэгээр (нэгж шилжүүлсэн матрицын сүүлчийн эгнээ) нэг хэлбэрийн хослолыг хуваах үлдэгдэлээс нэмэлт матриц байгуулж болно.

Бүрэн үүсгэх матриц нь дараах байдлаар харагдах болно.

Матриц үүсгэх дээр дурдсан арга нь цорын ганц биш юм. үүсгэгч матрицыг үүсгэгч олон гишүүнтээр таних матрицын элементүүдийг шууд үржүүлэх замаар байгуулж болно. Энэ нь хуваалтаас үлдэгдлийг олохоос илүү тохиромжтой байдаг. Үүссэн кодууд нь үүсгэгч матрицыг ашиглан бүтээгдсэн кодуудаас ялгаагүй бөгөөд нэмэлт матриц нь үүсгэгч олон гишүүнт нэгийг тэгээр хуваахад үлдэгдлээс бүрддэг.

Үүсгэх матрицыг мөн зэрэглэлийн таних матрицын мөрийг үржүүлэх замаар олж авсан хослолыг мөчлөгөөр шилжүүлэх замаар байгуулж болно. күүсгэгч олон гишүүнт рүү.

Циклийн кодын алдаа нь үүссэн хослолыг үүсгэгч олон гишүүнт хуваах үлдэгдлийг ашиглан илрүүлдэг. Хуваалтын үлдэгдэл нь алдаа тодорхойлогч боловч мөчлөгийн код дахь алдааны байршлыг шууд заадаггүй.

Алдаа засах санаа нь тодорхой тооны мөчлөгийн шилжилтийн дараа алдаатай хослолыг үлдсэн хэсэгтэй нь хамт залруулсан кодын хослолыг өгөх байдлаар "тохируулсан" явдал юм. Энэ тохиолдолд үлдсэн хэсэг нь гажуудсан ба зөв тэмдэгтүүдийн хоорондох ялгаанаас өөр зүйл биш юм. Үлдсэн нэгжийн тоо нь кодын алдааны тоотой тэнцэх хүртэл гажуудсан хослолыг тохируулна. Энэ тохиолдолд мэдээжийн хэрэг нэгжийн тоо нь алдааны тоотой тэнцүү байж болно с,энэ кодоор зассан (код нь гажуудсан хослолын 3 алдаа, 3 алдааг засдаг) эсвэл түүнээс бага с(код нь 3 алдааг засч, хүлээн зөвшөөрсөн хослолд 1 алдаа байна).

Кодын хослол дахь алдааны байршил хамаагүй. Хэрэв к³(n/2), дараа нь тодорхой тооны ээлжийн дараа бүх алдаа нь үүсгэгч олон гишүүнт "нэг удаагийн" үйл ажиллагааны бүсэд байх болно, өөрөөр хэлбэл жин нь нэг үлдэгдлийг авахад хангалттай. W £ с, мөн энэ нь гажуудсан хослолыг засахад аль хэдийн хангалттай байх болно.

Алдаа засах үйл явцыг тусгай кодыг бүтээх жишээнүүдийг ашиглан доор дэлгэрэнгүй авч үзнэ.

Хамгийн энгийн цикл код нь ганц алдаа, сондгой олон тооны алдааг илрүүлэх боломжийг олгодог. Энэ кодын үүсгэгч олон гишүүнт хэлбэрт орсон байна. Өргөтгөлд багтсан бууршгүй олон гишүүнтийн дотроос энэ олон гишүүнт нь хамгийн бага зэрэгтэй олон гишүүнт тул ямар ч тооны мэдээллийн битийн хувьд зөвхөн нэг шалгах бит хэрэгтэй. Энэ битийн тэмдгийн утга нь зөвшөөрөгдсөн кодын хослол дахь нэгийн тооны жигд байдлыг баталгаажуулдаг. Үүссэн мөчлөгийн паритын код нь зөвхөн бие даасан битийн алдааг төдийгүй сондгой тооны битийн алдааг илрүүлэх чадвартай.

Жишээ. Цикл кодыг үүсгэгч олон гишүүнт 1-р зэргийн олон гишүүнт тул шалгах цифрүүдийн тоо Иймд цикл кодыг бүтээхийн тулд үүсгэгч матрицыг байгуулна.

Нэмэлт матрицыг бий болгохын тулд бид тэгээр дүүргэсэн нэгжийн шилжүүлсэн матрицын сүүлчийн эгнээг сонгосон олон гишүүнт хуваахад үлдэгдлийг олно.

Тиймээс нэмэлт C,k матриц нь хэлбэртэй байна

Одоо бид үүсгэгч матрицыг барьж байна

Энэ матрицын мөрүүд нь эхний гурван кодын хослол юм. Үлдсэн зөвшөөрөгдсөн хослолыг хоёр матрицын эгнээний бүх боломжит хослолыг нэгтгэн олж авах боломжтой. 39.

Хүснэгт 39 (скан харна уу)

Хоёрдахь зэрэглэлийн бууруулж болохгүй олон гишүүнтийг ашиглан үүсгэсэн дараах хамгийн энгийн кодыг авч үзэх нь хүмүүсийн сонирхлыг татдаг.

Ерөнхий үзэл бодолОлон гишүүнтээс үүссэн цикл кодын үүсгэгч матриц нь хоёр баганатай нэмэлт матрицын бүтцээрээ ялгаатай.

Өгөгдсөн үүсгэгч олон гишүүнт хуваахдаа мөрүүдийг илэрхийлдэг мономиалуудыг шалгахад хялбар байдаг.

таних матриц (нэмэлт матрицыг олохын тулд гурван төрлийн үлдэгдэл үүсдэг: 11, 01 ба 10. Иймээс үүссэн -кодын хослол бүрийн жин хамгийн багадаа хоёр байх болно. Аливаа хоёр хослолын хоорондох кодын хамгийн бага зай нь мөн хоёр. Гэхдээ хамгийн энгийн нь мөн адил утгуудаар тодорхойлогддог бөгөөд эхний зэрэглэлийн хоёр кодыг засах чадвар нь ижил биш юм Энэ нь зөвхөн сондгой үржвэрийн аливаа алдааг төдийгүй хосолсон зэргэлдээх алдаа, түүнчлэн нэг эвдрэлгүй элементээр тусгаарлагдсан бүх алдааг илрүүлэх боломжтой.

гэж нэрлэгддэг шугаман кодын ангилал Шайк кодууд. Нэр нь эдгээр кодын үндсэн шинж чанараас гаралтай: хэрэв тодорхой кодын хослол нь мөчлөгийн кодонд хамаарах бол анхны хослолыг циклээр солих замаар олж авсан хослол (циклик шилжилт) мөн энэ кодонд хамаарна.

Циклийн кодын зөвшөөрөгдсөн бүх хослолын хоёр дахь шинж чанар нь үүсгэгч гэж нэрлэгддэг сонгосон олон гишүүнт үлдэгдэлгүйгээр хуваагдах чадвар юм.

Эдгээр шинж чанаруудыг кодлох, тайлах төхөөрөмжүүдийн кодыг бүтээх, түүнчлэн алдааг илрүүлэх, засахад ашигладаг.

Циклийн кодууд нь алдаанаас хамгаалах кодуудын бүхэл бүтэн гэр бүл (тэдгээрийн нэг төрөл нь Хаммингийн кодууд) бөгөөд кодын хослолыг дамжуулах үед гарч буй алдааг илрүүлэх, засах шаардлагатай чадвартай кодуудыг хэрэгжүүлэх чадварын хувьд илүү уян хатан байдлыг хангадаг. харилцааны суваг. Цикл код нь системчилсэн блок (l, &) кодуудыг хэлнэ рууэхний цифрүүд нь үндсэн код болон дараагийнхуудын хослолыг илэрхийлнэ (l - Хэнд)цифрүүд нь баталгаажуулалт юм.

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

Хүлээн авсан n-бит кодын хослолыг тайлахдаа хуваалтыг үүсгэгч (үүсгэх, үүсгэх) олон гишүүнт дахин гүйцэтгэдэг.

Эдгээр кодын алдааны синдром нь хүлээн авсан кодын хослолыг үүсгэгч олон гишүүнт хуваах үед үлдэгдэл байх явдал юм. Хэрэв синдром тэг байвал алдаа байхгүй гэж үзнэ. Үгүй бол үүссэн синдромыг ашиглан алдаа гарсан хүлээн авсан кодын хослолын оронтой тоог тодорхойлж, засах боломжтой.

Гэсэн хэдий ч кодын хослолд олон тооны алдаа гарах магадлалыг үгүйсгэх аргагүй бөгөөд энэ нь нэг зөвшөөрөгдсөн хослолыг нөгөө болгон хувиргах үед хуурамч залруулга хийх, (эсвэл) алдааг илрүүлэхэд хүргэж болзошгүй юм.

Блок дахь нийт битийн тоог i-тэй тэнцүү гэж үзье хэрэгтэй мэдээлэлдотроо авч явах Тбит, дараа нь алдаа гарсан тохиолдолд j битийг засах боломжтой. 5-аас хамаарал nТэгээд Ткодыг хүснэгтээс тодорхойлж болно. 2.6.

Хүснэгт 2.6

Нийт битийн хослолын тоо мэдээлэл ба зассан битийн тооноос хамаарах байдал

Ялгааг нэмэгдүүлэх (p - t),та зөвхөн зассан битийн тоог нэмэгдүүлэх боломжгүй с,гэхдээ бас олон алдааг илрүүлэх. Илэрсэн олон алдааны хувийг Хүснэгтэнд үзүүлэв. 2.7.

Хүснэгт 2.7

Илэрсэн олон алдааны хувь

Циклийн кодуудыг тайлбарлаж, олон гишүүнт (эсвэл олон гишүүнт) ашиглан бүтээх нь тохиромжтой. Олон гишүүнт хэлбэрээр хослол бичих нь анхны кодын хослолын мөчлөгийн шилжилтийн үйлдлийг албан ёсны байдлаар харуулахад хэрэглэгддэг. Тиймээс “-элементийн кодын хослолыг олон гишүүнтээр дүрсэлж болно (х- 1) зэрэг:

Хаанаa„_j =(0, 1), баa„_, =0 нь хослолын тэг элементтэй тохирч байна, d„_, = 1 - тэг биш;би- кодын хослолын оронтой тоо.

Тодорхой 4 элементийн хослолын олон гишүүнтийг төсөөлье:

Нэмэх, хасах үйлдлүүд нь эквивалент ба ассоциатив бөгөөд модуль 2-ыг гүйцэтгэнэ:

Үйлдлүүдийг гүйцэтгэх жишээ:

Хуваах үйлдэл нь олон гишүүнтийг хуваах ердийн үйлдэл боловч хасахын оронд нэмэх модуль 2-г ашигладаг.

Кодын хослолын мөчлөгийн шилжилт - түүний элементүүдийг дарааллыг нь зөрчихгүйгээр баруунаас зүүн тийш шилжүүлэх, ингэснээр хамгийн зүүн талын элемент нь хамгийн баруун талын элементийг эзэлнэ.

Циклийн кодын үндсэн шинж чанар ба нэр нь дамжуулж буй мессеж дэх битүүдийн зөвшөөрөгдсөн бүх хослолыг (код үг) тодорхой эх кодыг циклээр шилжүүлэх замаар олж авах боломжтой байдагтай холбоотой юм.

Анхны кодын хослол болон харгалзах олон гишүүнт өгөгдсөн гэж үзье.

Үржүүлье Өө)дээр X:

Хамгийн дээд зэрэглэлээс хойш Xуртын кодын хослолоор n(l - 1) -ээс хэтрэхгүй бол үүссэн илэрхийллийн баруун талаас анхны олон гишүүнтийг авахын тулд хасах шаардлагатай. Өө"- 1). Хасах Өө"- 1) Үлдэгдэл модулийг авах гэж нэрлэдэг (x n - 1).

Анхны хослолын шилжилтийг / хэмжигдэхүүнээр дараах байдлаар илэрхийлж болно. a(x)? U - Өө"- 1), өөрөөр хэлбэл. үржүүлэх Өө) x" ба үлдсэн модулийг (x" - 1) авна. -аас их буюу тэнцүү олон гишүүнт авах үед үлдэгдлийг авах шаардлагатай х.

Циклийн кодыг бий болгох санаа нь ашиглалт дээр суурилдаг бууруулж болохгүй олон гишүүнт.Бууруулах боломжгүй олон гишүүнт гэдэг нь доод зэрэглэлийн олон гишүүнтүүдийн үржвэрээр дүрслэгдэх боломжгүй олон гишүүнт юм. нь өөр олон гишүүнт хуваагдахгүй зөвхөн өөртөө эсвэл нэгд хуваагдана. Хоёр гишүүн (x" + 1) ийм олон гишүүнт үлдэгдэлгүй хуваагдана.Циклийн кодын онол дахь бууруулж болохгүй олон гишүүнт олон гишүүнт үүсгэх үүрэг гүйцэтгэдэг.

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

ХаанаP(x)- бусад бүх кодыг гаргаж авсан анхны кодын хослол(Т- 1) үндсэн хослолууд;

C, = 0 эсвэлCj =1 (“O” бол олон гишүүнтийн үр дүнгийн зэрэгR(x)-x‘(l - 1) -ээс хэтрэхгүй, эсвэл хэтэрсэн бол "1").

Хослол P(x)үүсгэгч (үүсгүүр) хослол гэж нэрлэдэг. Цикл кодыг бүтээхийн тулд зөв сонгоход л хангалттай P(x).Дараа нь бусад бүх кодын хослолууд нь бүлгийн кодтой ижил байна.

Олон гишүүнт үүсгэгч нь дараах шаардлагыг хангасан байх ёстой.

• P(x)тэг биш байх ёстой;
• жин P(x) хамгийн бага кодын зайнаас бага байж болохгүй: V(P(x)) > d мм ;
• P(x)дээд зэрэгтэй байх ёстой k (k -кодын илүүдэл элементүүдийн тоо);
• P(x)олон гишүүнт хуваагч байх ёстой (x" - 1).

Сүүлчийн нөхцлийг биелүүлэх нь цикл кодын бүх ажлын кодын хослолууд нь хуваагдах шинж чанарыг олж авахад хүргэдэг. P(x)ул мөргүй. Үүнийг харгалзан бид мөчлөгийн кодын өөр нэг тодорхойлолтыг өгч болно: цикл код нь бүх ажлын хослолууд нь үүсгэгч олон гишүүнт үлдэгдэлгүйгээр хуваагддаг код юм.

Үүсгэх олон гишүүнтийн зэргийг тодорхойлохын тулд r > log 2 (ба + 1), хаана n- нэг удаад дамжуулагдсан багцын хэмжээ, i.e. бүтээж буй мөчлөгийн кодын урт.

Олон гишүүнт үүсгэх жишээг Хүснэгтэнд үзүүлэв. 2.8.

Хүснэгт 2.8

Олон гишүүнт үүсгэх жишээ

Энгийн кодын хослолоос зөвшөөрөгдөх циклийн кодын хослолыг олж авах алгоритм нь дараах байдалтай байна.

Олон гишүүнтийг өгье P(x) = a g _ ( x g + a g _ 2 x g ~ 1 + ... + 1 бөгөөд энэ нь кодын залруулах чадвар болон шалгах битийн тоог тодорхойлдог. руу,түүнчлэн энгийн элементийн код болон олон гишүүнт хэлбэрийн мэдээллийн битүүдийн анхны хослол A t(x).

Зөвшөөрөгдсөн мөчлөгийн кодын хослолыг тодорхойлох шаардлагатай (ба, руу).

• 1. Бид анхны кодын хослолыг олон гишүүнт хэлбэрээр илэрхийлдэг A t(x).Анхны кодын хослолын олон гишүүнтийг үржүүлнэ x g: A t (x) x g.Үүсгэх олон гишүүнтийн зэрэг Ганхны кодын хослолын хамгийн чухал битийн утгатай тэнцүү байна.
• 2. Өмнөх догол мөрөнд олж авсан бүтээгдэхүүнийг үүсгэгчд хуваах үлдэгдэл гэж бид анхны мэдээллийн нэгдлийг зөвшөөрөгдсөнтэй нөхөх шалгах битүүдийг тодорхойлно.

олон гишүүнт:

Бид хуваалтын үлдсэн хэсгийг гэж тэмдэглэнэ R(x).

3. Эцэст нь шийдэгдсэн мөчлөгийн кодын хослол

кодыг = гэж тодорхойлно Тэгээд t(x)? x r + R(x).

Хүлээн авсан кодын хослолын алдааг тодорхойлохын тулд түүнийг үүсгэгч олон гишүүнт хуваахад хангалттай. Хэрэв хүлээн зөвшөөрөгдсөн хослол нь хууль ёсны бол хуваагдлын үлдсэн хэсэг нь тэг болно. Тэг бус үлдэгдэл нь хүлээн зөвшөөрөгдсөн хослолд алдаа байгааг илтгэнэ. Үлдэгдэл (синдром) төрлөөс хамааран зарим тохиолдолд алдааны шинж чанар, түүний байршлын талаар дүгнэлт хийж, алдааг засах боломжтой байдаг.

Алдаа илрүүлэх алгоритм нь дараах байдалтай байна.

"-элементийн хослолууд ( n = k + t).

• 1. Бид алдаа байгаа эсэхийг тогтооно. Бид хүлээн зөвшөөрөгдсөн хослолын үлдсэн хэсгийг авна A n -(x)үүсгэгч олон гишүүнт рүү P(x): А(X)
• --- = Rq(x). Тэнцвэрийн бэлэн байдал R0(x)үед (L 0 (x) f 0) заана P(x)

алдааны талаар.

2. Үүссэн олон гишүүнтийг #(x) хуваа. = L„_,(X) 0 Rq (x) генератор руу R g (x): W-1 = R(x),Хаана R(x)- одоогийн үлдэгдэл.

3. LDx) ба харьцуул R(x).Хэрэв тэдгээр нь тэнцүү бол алдаа нь хамгийн чухал битэд гарсан. Хэрэв үгүй ​​бол хүлээн зөвшөөрөгдсөн олон гишүүнтийн зэргийг х-ээр нэмэгдүүлж дахин хуваана.

4. Үр дүнгийн үлдэгдлийг харьцуул Rq(x). Хэрэв тэдгээр нь тэнцүү бол хоёр дахь оронтой тоонд алдаа гарсан байна. Хэрэв тэд тэнцүү биш бол үржүүлнэ Чшш) x 2 ба бид авах хүртэл эдгээр үйлдлийг давтана

R(x) =там.

Алдаа нь зэрэг нэмэгдсэн тоонд харгалзах оронтой байх болно шш),нэмэх 1. Жишээлбэл, тэгш эрхтэй тохиолдолд R(x)болон LDx)

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

Харилцаа холбооны системийн дуу чимээнд тэсвэртэй олон чухал кодууд байдаг

ялангуяа төгсгөлтэй арифметикийн бүтцэд тулгуурласан цикл

Галуагийн талбайнууд. Талбайнь хязгаарлагдмал талбартай элементүүдийн багц юм

Үргэлж энгийн арифметик үйлдлүүд байдаггүй тул үйлдлүүдийн нэрийг хашилтанд оруулсан болно. Талбар нь үргэлж null элементтэй (0), эсвэл тэг, ба нэг элемент(1), эсвэл нэг. Хэрэв тоо qталбайн элементүүд хязгаарлагдмал, дараа нь талбар гэж нэрлэдэг хязгаарлагдмал талбар, эсвэл хязгаарлагдмал Галуагийн талбар, болон тэмдэглэгдсэн байна GF(q)yХаана q-талбайн захиалга. Галуагийн хамгийн жижиг талбар нь хоёр элементийн талбар юм GF( 2), зөвхөн 1 ба 0 гэсэн хоёр элементээс бүрдэх. тулд

1 Эваристе Галуа (1811 - 1832) - Францын математикч, орчин үеийн алгебрийн үндэс суурийг тавьсан.

элементүүд дээр үйлдэл хийх GF( 2) энэ талбарын хязгаараас хэтрээгүй, тэдгээрийг модуль 2-оор гүйцэтгэдэг (ерөнхийдөө энэ нь талбайн дарааллаар тодорхойлогддог. энгийн Галуагийн талбайнууд).

Талбар нь хэд хэдэн тодорхой математик шинж чанартай байдаг. Талбайн элементүүдийн хувьд нэмэх, үржүүлэх үйлдлүүд тодорхойлогддог бөгөөд эдгээр үйлдлүүдийн үр дүн нь нэг багцад хамаарах ёстой.

Нэмэх, үржүүлэх үйлдлүүдийн хувьд ердийн математикийн нэгдлийн дүрмийг дагаж мөрддөг. А + (б + в) = (а + б)+ в, шилжих чадвар - a + b = b + aТэгээд А b = b Аба хуваарилалт - А (б+ в) = А б + А -тай.

Талбайн элемент бүрийн хувьд Анэмэхэд урвуу элемент байх ёстой (-A)мөн хэрэв Атэгтэй тэнцүү биш, үржүүлгийн урвуу элемент (th').

Талбар нь заавал байх ёстой нэмэлт нэгж - 0 элемент ийм байна А + 0 = Ааливаа талбарын элементийн хувьд А.

Талбар нь заавал байх ёстой үржүүлэх нэгж - 1-р элемент, ийм aL = aаливаа талбарын элементийн хувьд А.

Жишээлбэл, бодит тоо, рационал тоо, комплекс тоонуудын талбарууд байдаг. Эдгээр талбарууд нь хязгааргүй тооны элементүүдийг агуулдаг.

Үнэн хэрэгтээ код үгийн мөчлөгийн солигдох замаар үүссэн бүх багцууд нь бас код үг юм. Жишээлбэл, 1000101 хослолын мөчлөгийн өөрчлөлтүүд нь 0001011, 0010110, 0101100 гэх мэт кодын хослолууд байх болно. Энэ шинж чанар нь алдааг илрүүлэх, нэг алдааг засах үед кодлох, тайлах төхөөрөмжийг ихээхэн хялбаршуулах боломжийг олгодог. Цикл кодуудад анхаарал хандуулах нь тэдний төрөлхийн өндөр засварлах шинж чанарууд нь харьцангуй энгийн үндсэн дээр хэрэгждэгтэй холбоотой юм. алгебрийн аргууд. Үүний зэрэгцээ дурын шугаман блокийн кодыг тайлахын тулд хүснэгтийн аргуудыг ихэвчлэн ашигладаг бөгөөд энэ нь их хэмжээний декодчилогч санах ой шаарддаг.

Цикл код нь шугаман блок код юм. (n, k) -мөчлөгийн шинж чанараар тодорхойлогддог код, өөрөөр хэлбэл. Зөвшөөрөгдсөн аливаа код үгийг зүүн тийш нэг алхамаар шилжүүлэх нь ижил кодонд хамаарах зөвшөөрөгдсөн кодыг өгөх бөгөөд код үгийн багцыг градусын олон гишүүнтийн багцаар төлөөлдөг. (х- 1) буюу түүнээс бага, үүсгэгч олон гишүүнт хуваагддаг g(x)градус r=n-k yэнэ нь биномийн хүчин зүйл юм X n+

Цикл кодонд код үгсийг олон гишүүнт (олон гишүүн) -ээр төлөөлдөг.

Хаана p -кодын урт; би -Галуагийн талбайн коэффициентүүд (кодын хослолын утгууд).

Жишээлбэл, 101101 кодын хослолын хувьд олон гишүүнт тэмдэглэгээ нь хэлбэртэй байна

Цикл кодуудын жишээ бол тэгш шалгах код, давталтын код, Хэммингийн код, компьютерийн код, турбо кодууд юм.

Хаммингийн код. Хаммингийн кодын алдааг засах чадвар нь кодын хамгийн бага зайтай холбоотой d0.Бүх олон тооны алдааг зассан q= cnt (d 0- l)/2 (энд cnt нь “бүхэл тоо” гэсэн үг) ба олон тооны алдаа илэрсэн. d 0 - 1. Тэгэхээр сондгой тэнцлийг шалгахдаа d Q = 2 ба ганц алдаа илэрсэн. Хаммингийн код дээр d 0 = 3. Мэдээллийн ангиллуудаас гадна танилцуулсан L=бүртгэлийн илүүдэл хяналтын битийн 2 Q, хаана Q-мэдээллийн битийн тоо. Параметр Лхамгийн ойрын өндөр бүхэл тоо хүртэл дугуйрсан. L-битийн хяналтын код нь утгууд нь нэгтэй тэнцүү байгаа мэдээллийн битүүдийн тоог битээр нэмэх (нэмэх модуль 2)-ын урвуу үр дүн юм.

Жишээ 7.7

100110 гэсэн үндсэн кодтой болцгооё. Q = 6. Тодорхойлъё нэмэлт код.

Шийдэл

Бид үүнийг олдог Л= 3 ба нэмэлт код нь байна

Энд P нь битээр нэмэх үйлдлийн тэмдэг бөгөөд инверсицийн дараа бид 000 байна. Одоо нэмэлт кодыг үндсэн кодын хамт дамжуулах болно. Хүлээн авагч дээр нэмэлт кодыг дахин тооцоолж, дамжуулсан кодтой харьцуулна. Харьцуулах кодыг бүртгэх бөгөөд хэрэв энэ нь тэгээс ялгаатай бол түүний утга нь үндсэн кодын алдаатай хүлээн авсан битийн тоо юм. Тиймээс, 100010 кодыг хүлээн зөвшөөрсөн тохиолдолд тооцоолсон нэмэлт код нь 010Ш10 = 100-ийн урвуутай тэнцүү байна, өөрөөр хэлбэл. 011, энэ нь 3-р оронтой алдаа гэсэн үг.

Хаммингийн кодын ерөнхий ойлголт нь мөчлөгийн BCH кодууд бөгөөд энэ нь батлагдсан кодын хослол дахь олон алдааг засах боломжтой болгодог.

Рид-Соломон кодуудГалуагийн талбарууд буюу хязгаарлагдмал тэг дээр суурилдаг. Арифметик үйлдлүүд нэмэх, хасах, үржүүлэх, хуваах гэх мэт. Төгсгөлийн тэгийн элементүүд дээр үр дүн гарна, энэ нь мөн тэгийн элемент болно. Reed-Solomon кодлогч эсвэл декодлогч эдгээр үйлдлийг заавал гүйцэтгэх ёстой. Кодыг хэрэгжүүлэх бүх үйлдлүүд шаардлагатай тусгай тоног төхөөрөмжэсвэл тусгай програм хангамж.

Турбо кодууд.Илүүдэл кодыг бие даан эсвэл хэд хэдэн кодын хослол хэлбэрээр ашиглаж болно, хэрэв нэг илүүдэл кодын тэмдэгтүүдийг өөр нэг нэмэлт кодын энгийн мэдээллийн тэмдэг гэж үздэг. Энэ холбоог дуудах болсон шаталсанкод. Холбогдсон кодын асар том давуу тал нь тэдгээрийн хэрэглээ нь ижил урттай, давхардсан кодтой ижил төстэй төхөөрөмжтэй харьцуулахад кодлогч, ялангуяа декодчилогчийг хялбаршуулах боломжийг олгодог. Каскадын кодчилол нь турбо кодуудыг бий болгоход хүргэсэн. Турбо кодхоёроос бүрдсэн зэрэгцээ дохионы бүтэц гэж нэрлэдэг илүүсистемчилсэн кодууд. Тэдгээрийн барилгын үндсэн зарчим нь хэд хэдэн зэрэгцээ ажиллаж буй бүрэлдэхүүн хэсгийн кодлогчийг ашиглах явдал юм. Бүрэлдэхүүн хэсгүүдийн кодуудын хувьд та блок болон эргэлтийн код, Хаммингийн код, PC код, BCH гэх мэтийг хоёуланг нь ашиглаж болно. Цооролт (цооролт) ашиглах нь турбо кодын харьцангуй хурдыг нэмэгдүүлэх, түүний залруулах чадварыг тохируулах боломжийг олгодог. статистик шинж чанаруудхарилцааны суваг. Турбо код үүсгэх зарчим нь дараах байдалтай байна: оролтын дохио X,-аас бүрдэнэ TOбит, зэрэгцээ хооллож байна Нхолбогч. Сүүлийнх бүр нь блок дахь элементүүдийг дахин цэгцлэх төхөөрөмж юм TOбитүүд псевдо санамсаргүй дарааллаар. Завсрын гаралтын дохио - өөрчлөгдсөн дараалал бүхий тэмдэгтүүдийг харгалзах анхан шатны кодлогч руу илгээдэг. Хоёртын дараалал x p i= 1,2,..., JV, кодлогчийн гаралт дээр мэдээллийн битүүдийн хамт нэг кодын үгийг бүрдүүлдэг шалгах тэмдэгтүүд байдаг. Холбогчийг ашиглах нь турбо кодыг тайлахдаа харилцан хамааралтай алдааны дараалал гарахаас урьдчилан сэргийлэх боломжийг олгодог бөгөөд энэ нь боловсруулахад уламжлалт давтагдах код тайлах аргыг ашиглахад чухал юм. Бүрэлдэхүүн хэсгүүдийн кодын сонголтоос хамааран турбо кодыг эргэлтийн турбо код болон блок бүтээгдэхүүний код гэж хуваана.

Энэ үгтэй харгалзах, албан ёсны хувьсагчаас x. Энэ захидал харилцаа нь зөвхөн нэгийг харьцах биш, мөн изоморф шинж чанартай болохыг харж болно. "Үг" нь талбарын үсгүүдээс бүрддэг тул тэдгээрийг нэмж, үржүүлж (элементээр) хийх боломжтой бөгөөд үр дүн нь ижил талбарт байх болно. Хос үгийн шугаман хослолд тохирох олон гишүүнт бөгөөд эдгээр үгсийн олон гишүүнтийн шугаман хослолтой тэнцүү байна.

Энэ нь хязгаарлагдмал талбар дээрх n урттай үгсийн багцыг талбар дээрх хамгийн ихдээ n-1 зэрэгтэй олон гишүүнтийн шугаман орон зай гэж үзэх боломжийг бидэнд олгодог.

Алгебрийн тайлбар

Хэрэв код үг нь тухайн үгнээс нэг бит баруун тийш мөчлөгт шилжих замаар олж авсан бол түүнд харгалзах олон гишүүнт байна. в 1 (x) нь өмнөхөөсөө x-ээр үржүүлж гарна.

Үүнийг далимдуулан

Баруун болон зүүн тийш шилжинэ үү jзэрэглэл:

Хэрэв м(x) - талбар дээрх дурын олон гишүүнт ГФ(q) Мөн в(x) - мөчлөгийн код үг ( n,к) код, дараа нь м(x)в(x)мог(x n − 1) мөн энэ кодын код үг.

Олон гишүүнт үүсгэх

ТодорхойлолтЦиклийн үүсгэгч олон гишүүнт ( n,к) код Cтэгээс өөр олон гишүүнтийг нэрлэдэг -аас C, түүний зэрэг нь хамгийн бага, хамгийн дээд зэргийн коэффициент юм g r = 1 .

Теорем 1

Хэрэв C- мөчлөг ( n,к) код болон g(x) нь түүний үүсгэгч олон гишүүнт, дараа нь зэрэг юм g(x) тэнцүү байна r = n − к мөн код үг бүрийг хэлбэрээр өвөрмөц байдлаар илэрхийлж болно

в(x) = м(x)g(x) ,

зэрэг хаана байна м(x) түүнээс бага буюу тэнцүү к − 1 .

Теорем 2

g(x) - циклийн олон гишүүнт үүсгэх ( n,к) код нь хоёр гишүүний хуваагч юм x n − 1

Үр дагавар:Иймээс аливаа олон гишүүнт хуваагчийг үүсгэгч олон гишүүнт болгон сонгож болно x n− 1. Сонгосон олон гишүүнтийн зэрэг нь тестийн тэмдгийн тоог тодорхойлно r, тоо мэдээллийн тэмдэг к = n − r .

Генератор матриц

Олон гишүүнт нь шугаман хамааралгүй, өөрөөр хэлбэл м(x)g(x) = 0 тэг биш хувьд м(x) энэ нь боломжгүй юм.

Энэ нь шугаман кодын хувьд кодын үгсийг дараах байдлаар бичиж болно гэсэн үг юм.

, Хаана Гбайна матриц үүсгэх, м(x) - мэдээллийн чанартайолон гишүүнт.

Матриц Гбэлгэдлийн хэлбэрээр бичиж болно:

Матрицыг шалгах

Цикл кодын код үг бүрийн хувьд, . Тийм ч учраас шалгах матрицдараах байдлаар бичиж болно.

Кодлох

Системийн бус

Системийн бус кодчилолоор код үгийг мэдээллийн олон гишүүнт ба үүсгэгч олон гишүүнтийн үржвэр хэлбэрээр олж авдаг.

в(x) = м(x)g(x) .

Үүнийг олон гишүүнт үржүүлэгч ашиглан хэрэгжүүлж болно.

Системчилсэн

Системчилсэн кодчилолоор код үг нь мэдээллийн дэд блок, баталгаажуулалт хэлбэрээр үүсдэг

Мэдээллийн үг нь кодын үгийн дээд хүчийг бий болгоё

в(x) = x r м(x) + с(x),r = n − к

Дараа нь дараах нөхцлөөс

Энэ тэгшитгэл нь системчилсэн кодлох дүрмийг тогтоодог. Үүнийг олон мөчлөгт шугаман шүүлтүүр (MLFs) ашиглан хэрэгжүүлж болно.

Жишээ

Хоёртын (7,4,3) код

Хуваагч байдлаар x 7 − 1 бид гуравдугаар зэргийн үүсгэгч олон гишүүнийг сонгоно g(x) = x 3 + x + 1 , дараа нь гарсан код нь урттай байх болно n= 7, туршилтын тэмдгийн тоо (олон гишүүн үүсгэх зэрэг) r= 3, мэдээллийн тэмдгийн тоо к= 4, хамгийн бага зай г = 3 .

Генератор матрицкод:

,

Энд эхний мөр нь олон гишүүнт тэмдэглэгээ юм g(x) нэмэгдүүлэх дарааллаар коэффициент. Үлдсэн мөрүүд нь эхний эгнээний мөчлөгийн шилжилтүүд юм.

Шалгах матриц:

,

Энд 0-ээс эхлэн i-р багана нь хуваагдлын үлдэгдлийг илэрхийлнэ x биолон гишүүнт рүү g(x) дээрээс эхлэн өсөх дарааллаар бичнэ.

Жишээлбэл, 3-р баганыг эсвэл вектор тэмдэглэгээгээр авна.

Үүнийг шалгах нь амархан ГХ Т = 0 .

Хоёртын (15,7,5) BCH код

үүсгэгч олон гишүүнт байдлаар g(x) хоёр хуваагчийн үржвэрийг сонгож болно x 15 − 1 ^

g(x) = g 1 (x)g 2 (x) = (x 4 + x + 1)(x 4 + x 3 + x 2 + x + 1) = x 8 + x 7 + x 6 + x 4 + 1 .

Дараа нь мэдээллийн олон гишүүнтийн үржвэрийг ашиглан код үг бүрийг авч болно м(x) зэрэгтэй к− 1 ингэж:

в(x) = м(x)g(x) .

Жишээлбэл, мэдээллийн үг олон гишүүнттэй тохирч байна м(x) = x 6 + x 5 + x 4 + 1 , дараа нь код үг в(x) = (x 6 + x 5 + x 4 + 1)(x 8 + x 7 + x 6 + x 4 + 1) = x 14 + x 12 + x 9 + x 7 + x 5 + 1 , эсвэл вектор хэлбэрээр

Мөн үзнэ үү

Холбоосууд

Викимедиа сан.

• 2010 он.
• Хөгжим дэх мөчлөгийн хэлбэрүүд

Бусад толь бичгүүдэд "Циклийн кодууд" гэж юу болохыг харна уу.

богиносгосон мөчлөгийн кодууд- - [Л.Г.Суменко. Мэдээллийн технологийн англи-орос толь бичиг. М.: ЦНИС-ийн улсын үйлдвэр, 2003.] Сэдвүүд мэдээллийн технологиерөнхийдөө EN богиносгосон мөчлөгийн кодууд ...

Рид-Соломон кодууд- өгөгдлийн блок дахь алдааг засах боломжийг олгодог хоёртын бус цикл кодууд. Кодын векторын элементүүд нь бит биш, харин битүүдийн бүлгүүд (блокууд) юм. Байттай (октет) ажилладаг Рид Соломоны кодууд нь маш түгээмэл байдаг. Рид Соломоны код нь... Википедиа

Голай кодууд- Алдаа засах төгс шугаман блок кодын гэр бүл. Хамгийн ашигтай нь хоёртын кодГолай. Гурвалсан Голай кодыг бас мэддэг. Голай кодыг мөчлөгийн код гэж үзэж болно. …… Техникийн орчуулагчийн гарын авлага

Кодуудыг засах алдаа

Алдаа засах кодууд- Харилцаа холбооны технологийн алдааг илрүүлэх, мэдээллийг бүртгэх / хуулбарлах эсвэл холбооны шугамаар дамжуулах үед мэдээллийн бүрэн бүтэн байдлыг хянахад чиглэсэн үйлдэл. Алдаа засах (алдаа засах) процедурын дараа мэдээллийг сэргээх ... ... Википедиа

Кодуудыг засах алдаа- Харилцаа холбооны технологийн алдааг илрүүлэх, мэдээллийг бүртгэх / хуулбарлах эсвэл холбооны шугамаар дамжуулах үед мэдээллийн бүрэн бүтэн байдлыг хянахад чиглэсэн үйлдэл. Алдаа засах (алдаа засах) процедурын дараа мэдээллийг сэргээх ... ... Википедиа

Эхлэх