Цикл код нь шугаман код бөгөөд түүнийг бүрдүүлж буй кодын векторуудын мөчлөгийн шилжилтийн үйл ажиллагааны хувьд хаалттай хязгаарлагдмал олонлог юм. Өгчихье n- хэмжээст вектор v = а 0 а 1 …a n-1 хүрэх газрын координаттай Ф. Түүний мөчлөгийн шилжилтийг вектор гэж нэрлэдэг v"= a n-1-ээс 0-ээс 1... a n -2 .

Санаж үз n-Галуагийн талбар дээрх хэмжээст арифметик орон зай Г.Ф(2). Вектор бүр а 0 а 1 …a n-1-ийн Г.Ф(2) нэгээс нэг олон гишүүнтийг холбож болно а 0 +а 1 x+…+a n -1 x n-1-ээс коэффициенттэй Г.Ф(2). Хоёр векторын нийлбэр а 0 а 1 …a n-1 ба б 0 б 1 …б н-1 нь тэдгээрт харгалзах олон гишүүнтүүдийн нийлбэр, талбарын элементүүдийн векторын үржвэрт - энэ векторт харгалзах олон гишүүнт элементийн үржвэрт тохирно.

Зарим олон гишүүнтийг авч үзье g(x) тодорхойлсон шугаман орон зайнаас. Энэ дэд орон зайн үлдэгдэлгүйгээр хуваагдах бүх олон гишүүнтүүдийн олонлог g(x) шугаман дэд орон зайг үүсгэдэг. Шугаман дэд орон зай нь зарим шугаман кодыг тодорхойлдог.

Олон гишүүнтийн ангиллаар үүссэн шугаман код C(g(x)), зарим олон гишүүнтийн үржвэрүүд g(x), үүсгэгч олон гишүүнт гэж нэрлэгддэг олон гишүүнт гэж нэрлэдэг.

Олон гишүүнт кодууд хэрхэн хамааралтай болохыг харуулъя C(g(x)) болон мөчлөгийн кодууд. Болъё а = а 0 …a n-1 нь зарим код үг бөгөөд түүнд харгалзах олон гишүүнт код юм а(x) = а 0 +...+a n -1 x n-нэг. мөчлөгийн шилжилт а" кодын олон гишүүнттэй тохирч байна а"(x) = a n -1 +а 0 x+…+a n -2 x n -1 , үүнийг эх хувилбараар илэрхийлж болно:

Олон гишүүнт код нь хуваагдах ёстой тул g(x), дараа нь цикл байхын тулд олон гишүүнт а"(x) -д хуваагдах ёстой g(x). Энэ үүднээс авч үзвэл бид дараах теоремыг томъёолж болно. Олон гишүүнт код нь зөвхөн олон гишүүнт байвал мөчлөгтэй болно g(x) нь олон гишүүнт хуваагч юм x n-нэг. Энэ тохиолдолд олон гишүүнт g(x) нь мөчлөгийн кодын үүсгэгч олон гишүүнт гэж нэрлэгддэг.

Кодлох онолд дараах теорем батлагдсан: хэрэв олон гишүүнт g(x) зэрэгтэй n–кба хуваагч юм x n-1 тэгвэл C(g(x)) нь шугаман мөчлөгт ( n, к)-код.

Олон гишүүнт x n-1 хүчин зүйлчлэл x n–1 = (x–1)(x n -1 +x n-1 +…+1). Тиймээс цикл кодууд нь аль ч тохиолдолд байдаг n. Циклийн тоо n-битийн код нь олон гишүүнт хуваагдагчийн тоотой тэнцүү байна x n-нэг. Циклийн кодыг бий болгохын тулд олон гишүүнтийн задралын хүснэгтүүдийг боловсруулсан x n-1 бууруулж болохгүй олон гишүүнт, өөрөөр хэлбэл зөвхөн 1 болон өөртөө хуваагддаг олон гишүүнтүүдийн хувьд.

Жишээлбэл, олон гишүүнт дээр үндэслэн ямар кодуудыг барьж болохыг авч үзье xТалбай дээр 7-1 Г.Ф(2). Олон гишүүнтийг бууруулж болохгүй хүчин зүйл болгон задлах нь хэлбэртэй байна

Олон гишүүнт зургаан хуваагч үүсгэх боломжтой тул x 7-1, бууруулж болохгүй хуваагчдыг нэгтгэснээр зургаан хоёртын цикл код байдаг. ( n, к)-код нь нэгдүгээрт, утгаараа тодорхойлогддог n, хоёрдугаарт, үнэ цэнэ к = n – с, снь хуваагч олон гишүүнтийн зэрэг юм x n-1 кодыг тодорхойлох. Дараах нь олон гишүүнт хуваагч ба тэдгээрийн харгалзах утгууд юм к:

x – 1, с=1, к=6;

x 3 +x 2 +1, с=3, к=4;

x 3 +x+1, с=3, к=4;

(x–1)(x 3 +x 2 +1)=x 4+x 2+x+1, с=4, к=3;

(x–1)(x 3 +x+1)=x 4+x3+x2+1, с=4, к=3;

(x 3 +x 2 +1)(x 3 +x+1)=x 6 +x 5 +x 4 +x 3 +x 2 +x, с=6, к=1.

(7, 6)-код нь зөвхөн нэг шалгах тэмдэгтэй, (7, 1)-код нь зөвхөн нэг мэдээллийн тэмдэгтэй. Эдгээр нь тус тусын паритет шалгах код ба давталтын код юм.

Энгийн шугаман кодын нэгэн адил цикл кодыг үүсгэгч матрицаар өгч болно. Тиймээс даалгавар бол ийм матрицыг олох, өөрөөр хэлбэл олох явдал юм ктүүнийг бүрдүүлдэг шугаман бие даасан кодын хослолууд. Үүний тулд бид мөчлөгийн шилжилтийн үйл ажиллагааны хувьд мөчлөгийн кодыг хаах шинж чанарыг ашигладаг. Циклээрээ баруун тийш нэг оронтой шилжих нь олон гишүүнтийг үржүүлэхтэй тэнцүү гэдгийг анхаарна уу. g(x) дээр x. Дараа нь үүсгэгч олон гишүүнтийг эгнээ болгон авч үүсгэгч матрицыг байгуулж болно ктүүний мөчлөгийн өөрчлөлтүүд:

Одоо үүсгэгч олон гишүүнтийг хэрхэн ашиглах талаар авч үзье g(x) = 1+x+x 3 нь (7, 4)-кодоор кодлогдсон. Жишээлбэл, олон гишүүнттэй тохирох 4 битийн үгийг (0101) ав е(x) = x + x 3 . Эдгээр хоёр олон гишүүнтийг үржүүлэх

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

Энд x нь тооллын системийн суурь, хоёртын тооллын системийн хувьд олонлогт хамаарах коэффициентүүд.

Жишээ. Хоёртын векторыг олон гишүүнт байдлаар дараах байдлаар илэрхийлж болно.

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

олон гишүүнт нэмэх нь хувьсагчийн тэнцүү зэрэгтэй үед коэффициентүүдийн нийлбэр модуль 2 хүртэл буурдаг

үржүүлэх нь чадлын функцийг үржүүлэх ердийн дүрмийн дагуу хийгддэг боловч өгөгдсөн зэрэгт олж авсан коэффициентүүдийг модуль 2 нэмнэ;

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

Жишээ. Олон гишүүнтийн нийлбэрийг ол

Олон гишүүнтийн үржвэрийг ол

Олон гишүүнт хуваагдлыг гүйцэтгэнэ

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

Циклийн кодыг бүтээх санаа нь бууруулж болохгүй олон гишүүнтийн тухай ойлголт дээр суурилдаг. Олон гишүүнт зөвхөн өөртөө болон 1-д хуваагдаж, өөр олон гишүүнт хуваагдахгүй бол түүнийг бууруулж болохгүй гэж нэрлэдэг. Өөрөөр хэлбэл, бууруулж болохгүй олон гишүүнтийг доод зэрэглэлийн олон гишүүнтийн үржвэр болгон төлөөлөх боломжгүй. Бууруулах боломжгүй олон гишүүнт олон гишүүнтийг үлдэгдэлгүйгээр хуваана. Цикл кодын онолд олон гишүүнт үүсгэх үүргийг бууруулж болохгүй олон гишүүнт гүйцэтгэдэг. Төрөл бүрийн зэрэгтэй, бууруулж болохгүй олон гишүүнтүүдийн төрлийг энд үзүүлэв

Буурагдах боломжгүй олон гишүүнтүүдийн жишээ:

Цикл кодын векторуудыг дараах дүрмийн дагуу байгуулна. Зарим байгалийн кодын дурын хоёртын вектор байг; - зэрэгтэй мономиаль буурахгүй зэрэгтэй олон гишүүн Дараа нь хамаарлыг ашиглан цикл кодын дурын вектор үүсдэг.

хэсгийн үлдсэн хэсэг хаана байна

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

Жишээ. Байгалийн хоёртын кодын вектор нь хэлбэртэй байна

Векторыг олон гишүүнт хэлбэрээр илэрхийлье

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

Цикл кодыг аливаа системчилсэн кодын нэгэн адил матриц хэлбэрээр матриц үүсгэгч хэлбэрээр хялбархан зааж өгч болно.

форматын шилжүүлсэн нэгж ятриц хаана байна - хуваагдлын үлдэгдэлээс үүссэн паритын битүүдийн матриц

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

Мэдээжийн хэрэг үүсгэгч матрицын хоосон зай нь хэлбэртэй байна

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

Тиймээс цикл кодын векторын урт нь байна

(скан харах)

Үүний үр дүнд бид үүсгэгч С матрицыг олж авна.

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

Хүснэгт 13.5

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

Кодыг хүснэгтэд үзүүлэв. 13.5.

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

Жишээ нь, цикл кодыг үүсгэгч матрицаар нь өгдөг

Зүүн талаас сүүлийн зургаан мөр, эхний зургаан баганыг хөндлөн зуръя. Бид үүсгэгч матрицыг авдаг

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

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

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

1. Циклийн кодын хүчийг өгсөн тул түүний мэдээллийн битийн тоог томъёоны дагуу тодорхойлно.

2. Циклийн кодын шалгах цифрүүдийн оновчтой тоог тусгай хүснэгтээр тодорхойлно.

3. Лавлахуудын дагуу градусын бууруулж болохгүй олон гишүүнт бүгд олддог

4. Дамжуулагч бус олон гишүүнтийн аль нэгнийх нь хувьд (хамгийн их гишүүний тоотой олон гишүүнийг сонгох хэрэгтэй) мөчлөгийн кодын үүсгэгч матрицыг байгуулна. Кодын вектор бүрийг томъёогоор тооцоолно

үүсгэгч матрицын мэдээллийн векторын олон гишүүнт хаана байна; - зэрэг мономиал - хуваагдлын үлдэгдэл

5. Баригдсан үүсгэгч матрицыг дараах нөхцлөөр шалгана.

a) үүсгэгч матрицын аль нэг векторын Хэммингийн утгаараа жин нь авч үзэж буй цикл кодын Хаммингийн утгаараа хамгийн бага зай байх харьцааг хангасан байх ёстой;

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

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

16 хүчин чадалтай цикл код, багтаамжтай залруулах кодыг бүтээцгээе

утгыг тодорхойлохын тулд

3 "Лавлах номноос бид бүх бууруулж болохгүй олон гишүүнтүүдийг олдог. Ийм хоёр олон гишүүнт байдаг.

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

Матрицын мэдээллийн вектор бүрийг олон гишүүнтээр төлөөлдөг

Бид үүсгэгч матрицын бүх векторуудыг томъёог ашиглан бүрэн тодорхойлдог

Циклийн кодын векторын уртаас хойш (үүсгэх матрицын форматыг үзнэ үү, дараа нь

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

Хүснэгт 13.6

Үр дүн нь үүсгэгч матриц С үү? мөчлөгийн код

5. Үүссэн үүсгэгч матриц нь шаардлагатай бүх нөхцлийг хангана. Тиймээс бид мөчлөгийн кодыг бүрэн бүтээдэг (Хүснэгт 13.6). Хүснэгтээс харахад код нь даалгаврын шаардлагыг хангасан байна.

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

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

1. Хүлээн авсан кодын векторыг үүсгэгч олон гишүүнт хуваа.

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

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

Цикл кодыг үүсгэгч С матриц ба үүсгэгч олон гишүүнтээр өгье.

Код нь 3-тай, өөрөөр хэлбэл, олон тооны алдааг засдаг. 0001101 векторын оронд 0011101 векторыг авъя. Алдааг засахын тулд бид дараах үйлдлүүдийг хийнэ. Бид хүлээн авсан векторыг олон гишүүнт гэж бичнэ: дараа нь бид хуваана

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

Бид хуваана

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

Бид хуваана

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

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

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

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

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

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

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

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

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

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

Хүснэгт 2.6

Мэдээллийн тоо, засч залруулж болох цифрүүдийн хослолын нийт цифрээс хамаарах байдал

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

Хүснэгт 2.7

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

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

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

Тодорхой 4 элементийн хослолын олон гишүүнтүүдийг танилцуулъя:

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

Үйлдлийн жишээ:

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

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

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

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

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

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

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

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

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

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

C, = 0 эсвэлCj =1 ("O" бол олон гишүүнтийн үр дүнгийн зэрэгP(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), хаана П- нэг удаад дамжуулагдсан багцын хэмжээ, i.e. бүтээж буй циклийн кодын урт.

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

Хүснэгт 2.8

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

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

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

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

• 1. Бид анхны кодын хослолыг олон гишүүнт байдлаар төлөөлдөг A t (x).Бид анхны кодын хослолын олон гишүүнтийг үржүүлдэг x z: 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) хуваа. \u003d L„_,(X) 0 Rq (x) generatrix дээр R g(h): W-1 = R(x),хаана R(x)- одоогийн үлдэгдэл.

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

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

R(x) =там.

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

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

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

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

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

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

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

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

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

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

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

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

6. Циклийн код бүхий алдааг засах

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

Циклийн кодууд нь шугаман байдаг тул алдаа илрүүлэх, засах үйл явц нь хүлээн авсан векторын синдромыг олохтой холбоотой юм. Вектор синдром гэдгийг санаарай укодын вектор ба шилжүүлсэн шалгах матрицын үржвэрээр тооцогдоно, i.e. s u= ӨХ Т. Цикл кодын хувьд синдром нь шалгах матрицыг тодорхой аргаар барьсан бол харгалзах олон гишүүнт кодын үүсгэгч олон гишүүнт хуваагдсантай тэнцүү байна. Өөрөөр хэлбэл, хэрэв g(x) нь үүсгэгч кодын олон гишүүнт, дараа нь векторын хам шинж юм ухуваагдлын үлдсэн хэсэгтэй тэнцүү байна у(x) дээр g(x). Хэрэв алдаа гараагүй бол үлдэгдэл, улмаар хүлээн авсан вектор синдром нь 0 байна.

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

1. Хүлээн авсан үгийн хувьд бид хүлээн авсан үгтэй тохирох олон гишүүнт хам шинжийг олно.

2. Хэрэв хам шинж нь 0-тэй тэнцүү биш бол олж авсан хам шинжийн дагуу (хуваалтын үлдэгдэл) бид хүснэгтээс харгалзах алдааны векторыг олно.

3. Тооцоолсон алдааны вектортой модуль 2-ыг нэмж хүлээн авсан үгийг бид залруулна.

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

Жишээ:Олон гишүүнтийн үүсгэсэн циклийн (7,1) кодыг авч үзье g(x) = x 6 + x 5 + x 4 + x 3 + x 2 + x+1. Код нь 0000000 ба 1111111 гэсэн хоёр үгнээс бүрдэх ба 3 ба түүнээс бага алдааны бүх хослолыг засдаг. Генераторууд нь 0, 1, 2, 3 жинтэй 7 урттай Булийн векторууд юм. Шалгах матрицыг quotient () ашиглан бүтээдэг. x+1) хуваалтаас x 7 +1 дээр x 6 + x 5 + x 4 + x 3 + x 2 + x+1 бөгөөд иймэрхүү харагдаж байна

Олон гишүүнт тохирох 11101101 үгийг хүлээн зөвшөөр x 6 + x 5 + x 4 + x 2 + 1. Энэ олон гишүүнтийг үүсгэгч кодын олон гишүүнт хуваасны дараах үлдэгдэл нь x 3 + x. Шууд баталгаажуулалтаар векторыг үржүүлэхдээ үүнийг баталгаажуулж болно у= 1110101 шилжүүлсэн матриц тутамд ХТ, түүнчлэн 0001010 векторыг үржүүлэх үед ХТ 0001010 векторыг авсан бөгөөд энэ нь олон гишүүнттэй тохирч байна x 3 + x. Олон гишүүнт харгалзах вектор x 3 + x, 2 жинтэй, өөрөөр хэлбэл, косетийн генератор юм. Хүлээн авсан вектор 11101101-ийг 0001010 генератортой нэмснээр бид 1111111 кодын үгийг авах болно, өөрөөр хэлбэл алдаа засах болно.

Шугаман кодын хувьд янз бүрийн хам шинжийн тоо 2 байна n - к, хаана n-к- шалгах тэмдэгтүүдийн тоо. Тиймээс код үгийн урт нь том кодуудын хувьд, өөрөөр хэлбэл хангалттай их тоотэмдэгтүүдийг шалгавал синдромын хүснэгт нь маш том болж, алдааны векторыг олоход маш их цаг хугацаа шаардагдана. Циклийн кодын хувьд энэ хүснэгтийн мөрийн тоог багасгахын тулд та ийм кодын хатуу математик бүтцийг ашиглаж болно. Гол теорем нь кодын үүсгэгч олон гишүүнт хуваагдсаны дараа векторын мөчлөгийн шилжилт ба тэдгээрийн үлдэгдлийн хоорондох холбоог тогтоодог Мегитийн теорем юм.

Теорем 6.1. (Меггит). Болъё с- вектор синдром уурт n. Цикл вектор шилжих синдром уолон гишүүнт харгалзах векторын синдромтой давхцдаг xs(x).

Жишээ:Олон гишүүнтийн үүсгэсэн цикл код болох (7,4) Хэммингийн кодыг авч үзье. g(x) = x 3 + x+ 1. 1011000 хоёртын вектор нь код үг, учир нь харгалзах олон гишүүнт байдаг. x 6 + x 4 + x 3 нь хуваагдана g(x). Энэ код үгийг дамжуулах явцад тохирох битэд нэг алдаа гарсан гэж үзье x 4, мөн үгийг хүлээн зөвшөөрсөн у= 1001000. Хам шинж схүлээн авсан векторын 110 нь олон гишүүнттэй тохирч байна x 2 + x.

Векторын 0010001 мөчлөгийн шилжилтийг авч үзье у. Энэ нь олон гишүүнттэй тохирч байна x 4 + 1. Шууд баталгаажуулалтаар олон гишүүнт хуваагдсан үлдэгдлийг шалгаж болно. xОлон гишүүнт бүрт 4 + 1 x 3 + x+ 1 тэнцүү x 2 + x+ 1, өөрөөр хэлбэл 0010001 векторын синдром нь 111. Олон гишүүнт хуваагдлын үлдэгдэл xs(x) = x 3 + x 2 дээр x 3 + x+ 1 бас тэнцүү байна x 2 + x + 1.

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

1. Бид харгалзах олон гишүүнийг үүсгэгч кодын олон гишүүнт хуваах замаар хүлээн авсан векторын синдромыг олно. Хэрэв бүртгэлд байгаа хуваагдлын үлдэгдэл 0 байвал алдаа гараагүй бөгөөд хуваах хэсэг нь шаардлагатай мэдээллийн үг юм. Үгүй бол бид хэлтсийн үлдсэн хэсгийг хүснэгтэд байгаа бүх синдромтой харьцуулна.

2. Хэрэв үлдсэн хэсэг нь хүснэгтийн хам шинжийн аль нэгтэй давхцаж байвал бид хүлээн авсан үгэнд харгалзах алдааны векторыг нэмж, үүссэн үгийг кодын үүсгэгч олон гишүүнт хуваана; хуваалтын коэффициент нь хүссэн мэдээллийн үг юм. Хэрэв үлдсэн бол xs(x) хүснэгтэд байгаа аль ч синдромтой таарахгүй, үржүүлнэ с(x) дээр xолон гишүүнт хуваагдана xs(x) кодын үүсгэгч олон гишүүнт рүү.

3. 2-р алхамыг дараа нь хүртэл гүйцэтгэнэ хҮлдсэн алхмууд нь хүснэгтэд байгаа синдромуудын аль нэгэнд тохирохгүй байна. Үүний дараа бид харгалзах алдааны векторыг мөчлөгөөр шилжүүлдэг худаа, үр дүнгийн векторыг хүлээн авсан үгэнд нэмж, үүссэн үгийг кодын үүсгэгч олон гишүүнт хуваах; хуваалтын коэффициент нь хүссэн мэдээллийн үг юм.

Жишээ:Олон гишүүнтийн үүсгэсэн циклийн (7,4) Хэммингийн кодыг авч үзье g(x) = x 3 + x+ 1. Синдромтой харгалзах декодчилох хүснэгт дараах байдалтай байна.

дамжуулсан 0001011 кодын үгэнд нэг алдаа гарсан, жишээлбэл, олон гишүүнт тохирох 0101011 үгийг хүлээн авсан гэж бодъё. x 5 + x 3 + x+ 1. Олон гишүүнтийн хуваагдлын үлдэгдэл x 5 + x 3 + x+ 1 олон гишүүнт кодын үүсгэгч бүрт g(x) = x 3 + x+ 1 тэнцүү x 2 + x+ 1, өөрөөр хэлбэл, хүлээн авсан векторын синдром нь 0-ээс ялгаатай бөгөөд 111-тэй тэнцүү байна. Хүснэгтэнд ийм синдром байхгүй тул хамгийн чухал битийн алдаа байхгүй байна. Олон гишүүнтийг үржүүлэх x 2 + x+ 1, хам шинж 111-д харгалзах, дээр xгарсан олон гишүүнтийг хуваана x 3 + x 2 + xдээр g(x). Олон гишүүнт хуваагдах үлдэгдэл x 3 + x 2 + xдээр x 3 + x+ 1 тэнцүү x 2 + 1, өөрөөр хэлбэл үлдэгдэлтэй харгалзах 101-р хам шинж нь код тайлах хүснэгтийн синдромтой таарч байна. Үүний дагуу зэргэлдээх ангийн 100000 генераторыг нэг бит зүүн тийш шилжүүлж, хүлээн авсан вектор 0100000 нь хүлээн авсан вектор 0101011 дээр нэмэгддэг. Үүний үр дүнд 0001011 гэсэн үг гарч ирдэг бөгөөд энэ нь дамжуулагдсан код үг, өөрөөр хэлбэл алдаа юм. засч залруулах болно.

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