Mavzu: Siklik kodlar va ularni ko’p elementlarni ko’paytirish usuli bilan hosil qilish va ularni kodlash va dekodlash sxemalari

TOSHKENT DAVLAT TRANSPORT UNIVERSITETI
Avtomatika va Telemexanika
Kafedrasi

MUSTAQIL ISH

MAVZU: Siklik kodlar va ularni ko’p elementlarni ko’paytirish usuli bilan hosil qilish va ularni kodlash va dekodlash sxemalari

Tekshirdi: AB 224 guruh talabasi
Annageldiyev Erkaboy
Qabul qildi : Zakirov V
TOSHKENT 2021
REJA :

1.Siklik kodlar va ularni ko’p elementlarni ko’paytirish usuli

2.Siklik kodlarni dekodlash
3. Siklik kodlar va ularni ko’p elementlarni ko’paytirish usuli bilan kodlash

Tsiklik kodni tekshirish polinomi. Davriy kodlash jarayoni. Matritsa kodining ta'rifi

Tsiklik kodlarning barcha ruxsat etilgan kombinatsiyalarining ikkinchi xususiyati shundaki, ular generator deb ataladigan tanlangan polinom tomonidan muammosiz bo'linishi mumkin. Bu xususiyatlar kodlash va dekodlash qurilmalari uchun kodlarni qurishda, shuningdek xatolarni aniqlash va tuzatishda qo'llaniladi.

Tsiklik kodlar - bu xatolarni tuzatish kodlarining butun oilasi (turlardan biri Hamming kodlari) bo'lib, kod birikmalarini uzatish jarayonida yuzaga keladigan xatolarni aniqlash va tuzatish uchun zarur bo'lgan kodlarni qo'llash qobiliyati nuqtai nazaridan katta moslashuvchanlikni ta'minlaydi. aloqa kanali orqali. Tsiklik kod tizimli blokga (l, &) tegishli - kodlar uchun birinchi raqamlar asosiy kodning kombinatsiyasi bo'lib, keyingi (l - To) raqamlari tekshiriladi.
Tsiklik kodlarni qurish uzatilgan kod so'zini qaytarilmas darajali ko'phadlarga bo'lish operatsiyasiga asoslanadi. G. Birlikning qolgan qismi tekshirish raqamlarini yaratish uchun ishlatiladi. Bunday holda, ko'paytirish operatsiyasi ^ -bitli axborot kodlari kombinatsiyasining chap tomoniga siljishni amalga oshiradigan bo'lim operatsiyasidan oldin amalga oshiriladi. G razryadlari.
Qabul qilingan n-bit kodli so'zni dekodlashda qayta yaratuvchi (yaratish, yaratish) ko'phadli bo'lim bajariladi.
Ushbu kodlardagi xato sindromi hosil bo'lgan kod so'zining avlod polinomlariga bo'lingan qolgan qismining mavjudligi. Agar sindrom nolga teng bo'lsa, unda xatolar yo'q. Aks holda, paydo bo'lgan sindromdan foydalanib, siz xatolik yuzaga kelgan qabul qilingan kod so'zining bit raqamini aniqlashingiz va uni tuzatishingiz mumkin.
Shu bilan birga, bir ruxsat etilgan kombinatsiyani boshqasiga o'tkazishda noto'g'ri tuzatishlar va (yoki) xatolarga olib keladigan kod birikmalarida bir qator xatolar bo'lishi mumkinligi istisno qilinmaydi.
Blokdagi bitlarning umumiy soni foydali ma'lumotlarni tashuvchi i ga teng bo'lsin. 5 NS va Tochun kodlaridan bog'liqlikni jadvaldan aniqlash mumkin.

Kombinatsiyalar raqamlarining umumiy sonining ma'lumotlar va tuzatilgan raqamlar soniga bog'liqligi

Farqni oshirish (n - t) nafaqat tuzatilishi mumkin bo'lgan bitlar sonini oshiradi, s, balki ko'plab xatolarni ham ochib beradi. Aniqlangan ko'plab xatolarning foizlari jadvalda ko'rsatilgan. 2.7.

Aniqlangan ko'plab xatolar ulushi

Ko'phadlar (yoki ko'phadlar) yordamida siklik kodlarni va ularning qurilishini tasvirlash qulay. Asl kod so'zining tsiklik siljishi ishini ko'rsatish uchun birikma ko'phad shaklida yoziladi. Shunday qilib, "-elementli kod birikmasi polinom (NS-1) darajalari bilan tavsiflanishi mumkin:

Bu yerda „_j = (0, 1) va„ _, = 0 kombinatsiyaning nol elementlariga mos keladi, q „_, = 1 - noldan farq qiladi; i kod kombinatsiyasining bitlari soni.

Maxsus 4 elementli birikmalar uchun ko‘phadlarni ifodalaymiz:

Qo‘shish va ayirish amallari ekvivalent va assotsiativ bo‘lib, 2-modul bajariladi:

Operatsiyalarga misollar:

Bo'lish operatsiyasi ko'phadlarni oddiy bo'linishdir, lekin ayirish o'rniga qo'shimcha modul 2 ishlatiladi:
Kod kombinatsiyasining tsiklik siljishi - uning elementlari tartibini buzmasdan o'ngdan chapga siljish, eng chap elementning pozitsiyasini eng o'ng tomonga olish.

Tsiklik kodlarning asosiy xossalari va nomi uzatilayotgan xabardagi (kod so'zlari) barcha ruxsat etilgan bit birikmalarini har qanday manba kod so'zining tsiklik siljishi orqali olish mumkinligi bilan bog'liq.

Aytaylik, asl kod birikmasi va tegishli polinom berilgan:

Reproduktsiya Oh) NS haqida:

G, [24.11.21 11:51]

Maksimal daraja NS uzunlik kodi NS (n - 1) so'zidan oshmaganligi sababli, boshlang'ich ko'phadni olish uchun olingan ifodani o'ngdan olib tashlash kerak. oh "- 1). Ayirma oh" - 1) qoldiq modulning (x n - 1) olinishi deyiladi.

Asl kombinatsiya / o'lchamlarning o'zgarishi quyidagicha ifodalanishi mumkin: a (x)? Y - oh "- 1), ya'ni. Ko'paytirish Oh) nah" va biz qolgan modulni olamiz (x "- 1). dan katta yoki teng ko'phadni olishda.

Tsiklik kodlarni yaratish g'oyasi kamaymaydigan polinomlardan foydalanishga asoslangan. Qaytarib bo'lmaydigan ko'phad - bu past tartibli polinomlarning mahsuloti sifatida taqdim etilmaydigan ko'phad, ya'ni. faqat o'ziga yoki bittaga bo'linadi va boshqa ko'phadga bo'linmaydi. Binomlar (x "+ 1) shunday ko'phadga qoldiqsiz bo'linadi.Tsiklik kodlar nazariyasida ko'phadlar ko'phad yaratish rolini o'ynaydi.

Tsiklik kodning ta'rifiga qaytsak va kod birikmalarining tsiklik o'zgartirish operatsiyalarini hisobga olgan holda, siklik kodni yaratuvchi matritsani quyidagi ko'rinishda yozishimiz mumkin:

bu erdaP (x) - boshqa barcha (T-1) asosiy kombinatsiyalarga asoslangan original kod birikmasi;

S, = 0 yokiCj = 1 (agar "O" ko'phadning natijasi P (x) -x '(l - 1) bo'lsa yoki "1" dan ko'p bo'lmasa).

P (x) birikmasi generator deb ataladi. Tsiklik kodni o'rnatish uchun to'g'ri P (x) ni tanlash kifoya. Keyin boshqa barcha kod birikmalari guruh kodidagi bilan bir xil bo'ladi.

Generator polinomi quyidagi talablarga javob berishi kerak:
P (x) noldan farq qilishi kerak;
og'irligi P (x) minimal kod masofasidan kam bo'lmasligi kerak: V (P (x))> d mm;
P (x) k maksimal quvvatga ega bo'lishi kerak (k - koddagi keraksiz elementlarning soni);
P (x) ko'phad bo'luvchi bo'lishi kerak (x "- 1).
Oxirgi shartning bajarilishi tsiklik kodning barcha ishchi kod birikmalari bo'linish xususiyatiga ega bo'lishiga olib keladi. P (x) qoldiqsiz. Buni hisobga olsak, biz siklik kodning yana bir ta'rifini berishimiz mumkin: siklik kod - barcha ishchi kombinatsiyalar generatorning ko'phadiga bo'linadigan kod.
Yaratuvchi polinomning darajasini aniqlash uchun r> log 2 (va + 1) ifodasidan foydalanishimiz mumkin, bu erda NS bir vaqtning o'zida uzatiladigan paketning o'lchamidir, ya'ni. o'rnatilgan tsiklik kodning uzunligi.

Ko'phadlarga misollar jadvalda keltirilgan. 2.8.

Generator polinomlariga misollar

Oddiy kodlar birikmasidan siklik kodning ruxsat etilgan kod birikmasini olish algoritmi quyidagicha.

P (x) = az _ (xz + az _ 2 xr ~ 1 + ... + 1) polinomini bering, kodning tahrirlanishini va boshqaruv bitlari sonini, shuningdek, oddiy kod va kodning asl birikmasini aniqlang. A m (x) polinom shaklidagi elementdan axborot bitlari. Ruxsat etilgan kod birikmalarini (va kimga) belgilash uchun tsiklik kod talab qilinadi.

1. Biz A m (x) polinom ko'rinishidagi dastlabki kod birikmasini keltiramiz. Asl x g kod so'zining ko'phadini ko'paytiramiz: A t (x) x d. G ijodiy polinomining darajasi asl kod so'zining eng muhim bitining qiymatiga teng.

2. Oldingi xatboshida, ishlab chiqaruvchi tomonidan mahsulot taqsimotining qolgan qismi sifatida ruxsat etilgan asl ma'lumotlar kombinatsiyasini qo'shadigan tekshirish raqamlarini aniqlang.

polinom:

Birlikning qolgan qismi R (x) bilan belgilanadi.

3. Nihoyat hal qilingan siklik model

kod quyidagicha aniqlanadi = Va t (x)? x r + R (x).

Qabul qilingan kodli so'zdagi xatolarni aniqlash uchun uni yaratgan ko'phadga bo'lish kifoya. Agar qabul qilingan kombinatsiya qonuniy bo'lsa, unda qolgan birlik nolga teng bo'ladi. Nolga teng bo'lmagan balans qabul qilingan kombinatsiyada xatolar mavjudligini ko'rsatadi. Qoldiq (sindrom) turiga qarab, ba'zi hollarda xatoning tabiati va joylashuvi haqida xulosa chiqarish va xatoni tuzatish mumkin.

Xatoni aniqlash algoritmi quyidagicha.

"-element birikmalari (n = k + t) bo'lsin.

1. Biz xato faktini aniqlaymiz. Qabul qilingan A n - (x) birikmaning P (x) hosil qiluvchi ko'phadga bo'linishining qolgan qismini olamiz: A (NS)

G, [24.11.21 11:51]

--- = Rq (x). Qolganlarning mavjudligi R 0 (x) (A 0 (x) f 0) P (x) uchun R (0) ni bildiradi.

xato haqida.

2. Olingan ko'phadni # (x) bo'linadi. = L „_, (NS) 0 Rq (x) R g (x) har bir generator uchun: W-1 = R (x), bu erda R (x) - joriy balans.

3. LDx) va R (x) ni solishtiring.Agar ular teng bo'lsa, xato eng muhim bitda sodir bo'lgan. Agar bunday bo'lmasa, biz qabul qilingan x ko'phadning darajasini oshiramiz va qayta taqsimlaymiz:

4. Olingan balansni Rq (x) bilan solishtiring. Agar ular teng bo'lsa, ikkinchi bitda xatolik yuz berdi. Agar ular teng bo'lmasa, biz Shx) x 2 ni ko'paytiramiz va olingangacha bu amallarni takrorlaymiz

R (x) = do'zax.

Shx), plyus 1. Masalan, R (x) va LDx tengligida)

Tsiklik kod - bu uni tashkil etuvchi kod vektorlarining tsiklik siljish operatsiyasi bilan bog'langan chekli to'plamga ega chiziqli kod. N-o‘lchovli vektor v = a 0 a 1… a n-1 bo‘lsin, koordinatalari F maqsadli sohadan ... Uning siklik siljishi 0 ... a n -2 bo‘lgan v “= a n-1 vektordir.

n-Galua maydoni ustidagi Gf (2) o'lchovli arifmetik fazoni ko'rib chiqaylik. a 0 a 1… a n-1 dan Gf (2) gacha boʻlgan har bir vektor a 0 + a 1 x +… + a n -1 x n-1 Gf (2) koeffitsientli polinom bilan bogʻlanishi mumkin. a 0 a 1… a n-1 va b 0 b 1… b n-1 ikkita vektor yig‘indisi mos ko‘phadlar yig‘indisiga, vektor bilan maydon elementlarining ko‘paytmasi esa ko‘paytmaga bog‘liq. bu vektorga mos keladigan ko'phadning.

g (x) bilan tasvirlangan chiziqli fazodan ba'zi polinomlarni ko'rib chiqing. G (x) qoldiqsiz shu pastki fazoga boʻlinadigan barcha koʻphadlar toʻplami chiziqli pastki fazoni hosil qiladi. Chiziqli pastki bo'shliq ba'zi chiziqli kodlarni belgilaydi.

Ko'phadlar sinfi tomonidan yaratilgan chiziqli kod C (g (x)), ba'zi ko'phadlarning qatlamlari g (x), uni hosil qiluvchi ko'phad esa ko'phad deyiladi.

Keling, polinom kodlari C (g (x)) va siklik kodlar bilan qanday bog'liqligini ko'rsatamiz. a = a 0… A n-1 - ba'zi kodli so'zlar va tegishli kodli polinom a (x) = a 0 + ... + a n -1 x n-1 bo'lsin. "a" polinom kodiga to'g'ri keladi" (x) = a n -1 + a 0 x +… + a n -2 x n -1 tsiklik kesishuvi asl nusxa bilan ifodalanishi mumkin:

Ko'phadning kodi g (x) ga bo'linishi kerakligi sababli, u tsiklik bo'lishi uchun ko'phad "(x) g (x) ga bo'linishi kerak. Shu fikrdan kelib chiqib, quyidagi teorema hosil bo'lishi mumkin. n-1. Bunda g (x) ko‘phad siklik kodni hosil qiluvchi ko‘phad deyiladi.

Kodlash nazariyasida quyidagi teorema isbotlangan: agar g (x) koʻphad boʻlsa, n – k daraja va boʻluvchi x n-1 boʻlsa, C (g (x)) chiziq siklik (n, k) boʻladi. ) -shifr.

Polinom x n-1 omil x n – 1 = (x – 1) (x n -1 + x n-1 + ... + 1). Shuning uchun har bir n uchun siklik kodlar mavjud ... Davriy n-bit kodlari x n-1 polinomining bo'luvchilari soniga teng. Tsiklik kodlarni qurish uchun x n – 1 ko'phadlarning parchalanish jadvallari kamaytirilmagan ko'phadlarga, ya'ni faqat bir va bo'luvchilarga keltiriladi.

Masalan, x kvadrat 7 -1 Gf (2) polinomi asosida qanday kodlar tuzilishi mumkinligini ko'rib chiqing. U ko'phadni kamaymaydigan omillarga bo'lish shakliga ega

Ko'phad kamaymaydigan bo'luvchilarni birlashtirgan oltita x 7 -1 bo'luvchiga ega bo'lishi mumkinligi sababli, oltita ikkilik siklik kodlari mavjud. (N, k) -kod, birinchi navbatda, n qiymati bilan aniqlanadi, ikkinchidan, qiymat k = n - s, s kodning bo'linadigan ko'phadning x n – 1 ta'rifi darajasi. Ko'phadning bo'luvchilari va ularning mos qiymatlari quyida keltirilgan:

x - 1, s = 1, k = 6;

x 3 + x 2 +1, s = 3, k = 4;

x 3 + x + 1, s = 3, k = 4;

(x – 1) (x 3 + x 2 +1) = x 4 + x 2 + x + 1, s = 4, k = 3;

(x – 1) (x 3 + x + 1) = x 4 + x 3 + x 2 +1, s = 4, k = 3;

(x 3 + x 2 +1) (x 3 + x + 1) = x 6 + x 5 + x 4 + x 3 + x 2 + x, s = 6, k = 1.

Kod (7, 6) faqat bitta tasdiqlash belgisini o'z ichiga oladi va kod (7, 1) faqat bitta ma'lumot belgisini o'z ichiga oladi. Ular mos ravishda paritet va takroriy kodlardir.

G, [24.11.21 11:51]

Oddiy chiziqli kod singari, tsiklik kod ham generator matritsasi orqali aniqlanishi mumkin. Shuning uchun vazifa shunday matritsani topish, ya'ni uni tashkil etuvchi chiziqli mustaqil kod birikmalarini k topishdir. Buning uchun biz siklik sirpanish operatsiyasi bilan bog'liq bo'lgan siklik kodni yopish xususiyatidan foydalanamiz. E'tibor bering, bir bit bilan o'ngga tsiklik siljish g (x) ko'phadni x ga ko'paytirishga teng ... Keyin biz chiziqlarni va hosil bo'lgan k matritsasini uning siklik o'zgarishlarini olib, hosil qiluvchi ko'phadni qurishimiz mumkin:

Endi g (x) = 1 + x + x 3 (7, 4) kodi bilan kodlangan hosil qilingan ko'phaddan qanday foydalanishni ko'rib chiqamiz. Masalan, f (x) = x + x 3 ko'phadiga mos keladigan 4 bitli so'zni (0101) oling. Bu ikki ko'phadni ko'paytirish.

Eng oddiy siklik kod bitta xatoliklarni va bitta to'plamdagi xatolarni aniqlash imkonini beradi. U kodni yaratadigan polinomli shaklga ega. Bu ko'phad kengaytmaga kiritilgan kamaytirilmaydigan ko'phadlar ichida eng kichik darajali ko'phaddir.Shunday qilib, har qanday miqdordagi axborot bitlari uchun faqat bitta boshqaruv biti talab qilinadi. Ushbu bitning belgi qiymati har qanday ruxsat etilgan kod birikmasidagi belgilar sonining paritetini ta'minlaydi. Olingan tsiklik paritetni tekshirish kodi nafaqat alohida bitlardagi individual xatolarni, balki har qanday toq sonli bitlardagi xatolarni ham aniqlashga qodir.

Masalan. uchun siklik kod yarating Generator polinom 1-darajali ko'phad bo'lgani uchun boshqaruv bitlari soni Natijada, siklik kodni qurish uchun biz generator matritsani quramiz.

Qo'shimcha matritsani qurish uchun nol bilan to'ldirilgan bitta o'tkazilgan matritsaning oxirgi qatorini tanlangan polinomga bo'lishning qolgan qismini topamiz:

Shunday qilib, qo'shimcha matritsasi C, k shaklga ega

Endi biz avlod matritsasi qurmoqdamiz

Ushbu matritsadagi chiziqlar dastlabki uchta kodning birikmasidir. Ruxsat etilgan kombinatsiyalarning qolgan qismini modulning ikkita mumkin bo'lgan chiziqli kombinatsiyasini yig'ish orqali olish mumkin. Natijada yo'q qilingan kod birikmalari jadvalda keltirilgan. 39.

39-jadval (skanerga qarang)

Ikkilamchi kamaytirmaydigan ko'phaddan quyidagi oddiy kodni ko'rib chiqish ma'lum qiziqish uyg'otadi

Polinom tomonidan hosil qilingan siklik kodni yaratuvchi matritsaning umumiy ko'rinishi ikki ustunli qo'shimcha matritsaning tuzilishida farqlanadi.

Berilgan generator tomonidan bo'linganda, satrlarni ifodalovchi ko'phadlar mavjudligini tekshirish oson

identifikatsiya matritsasi (qo'shimcha matritsani topish uchun uch turdagi qoldiqlar hosil bo'ladi: 11, 01 va 10. Natijada olingan -kodning har bir kombinatsiyasining og'irligi kamida ikkita bo'ladi. Har qanday ikkita kombinatsiya orasidagi minimal kod masofasi Shuningdek, ikkita. Paritetni tekshirish uchun eng oddiy kod Biroq, ikkala kodni ham tuzatish qobiliyati bir xil emas, balki har qanday juftlashgan qo'shni xatolar, shuningdek, buzilmagan element bilan ajratilgan barcha xatolar.

Tsiklik kodlar shunday nomlanadi, chunki ular bir yoki bir nechta kod birikmalarining tsiklik siljishi natijasida olinadigan kod birikmalarining bir qismini yoki barchasini o'z ichiga oladi. Tsiklik siljish o'ngdan chapga amalga oshiriladi va eng chapdagi belgi har safar kombinatsiyaning oxiriga o'tkaziladi. Tsiklik kodlar, aslida, barchasi tizimli kodlarga tegishli bo'lib, ularda boshqaruv va ma'lumotlar raqamlari qat'iy belgilangan joylarda joylashgan. Bundan tashqari, kodlar blok kodlari sifatida tasniflanadi. Har bir blok (harf blokning alohida holati) mustaqil ravishda kodlanadi.

Tsiklik kodlarni yaratish g'oyasi ikkilik sonlar sohasida qaytarilmas polinomlardan foydalanishga asoslangan. Qaytarib bo'lmaydigan tub sonlarni boshqa sonlarning ko'paytmasi sifatida ifodalab bo'lmagani kabi, koeffitsientlari bir xil maydonga ega bo'lgan kichik tartibli ko'phadlarning ko'paytmasi sifatida ifodalab bo'lmaydigan ko'phadlar ko'phadlar deyiladi.

G, [24.11.21 11:51]

Boshqacha qilib aytganda, kamaytirilmagan ko'phadlar faqat o'ziga yoki qoldiqsiz birlashmaga bo'linadi.

Davriy kodlash nazariyasida ko'phadlar ko'phadlarning generatorlari rolini o'ynaydi. Agar berilgan kod birikmasi tanlangan kamaytirilmaydigan ko'phadga ko'paytirilsa, u holda biz tsiklik kodni olamiz, uning tuzatishi kamaytirilmaydigan polinom bilan aniqlanadi.

Aytaylik, siz to'rt xonali ikkilik kod birikmalaridan birini kodlashni xohlaysiz. Faraz qilaylik, bu birikma G (x) = x 3 + x 2 + 1 ® 1011. Tanlovimizni oqlamasak ham, uni qisqartirilmagan ko'phadlar jadvalidan hosil qilingan ko'phad sifatida qabul qilamiz. P (x) = x 3 + x + 1 ® 1011. Keyin G (x) ni hosil qiluvchi ko'phadga monomial ekvivalentiga ko'paytiramiz. Ko'phadni monohamiya darajasiga ko'paytirish orqali ko'phaddagi har bir a'zoning darajasi n ni oshiradi, bu polinomning eng kichik ahamiyatli bitlari tomonidagi n nolning aniqlanishiga teng. Tanlangan kamaytirmaydigan polinomning darajasi uchta bo'lganligi sababli, dastlabki ma'lumotlar kombinatsiyasi uch darajali monomial bilan ko'paytiriladi.

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

Keyin bu nollar o'rniga tuzatish raqamlarini yozish uchun amalga oshiriladi.

Tuzatilgan raqamlarning qiymati G (x) x n birligining P (x) haqida natijalaridan topiladi:

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

Shunday qilib,

yoki umuman

Bu erda Q (x) ¾ xususiy va R (x) ¾ P (x) birlikning qolgan qismiga nisbatan G (x) × x n.

Ikkilik arifmetikada -1 = 1 degan ma'noni anglatuvchi 1 Å 1 = 0 bo'lgani uchun, ikkilik sonlarni qo'shganda belgisini o'zgartirmasdan hadlarni bir qismdan ikkinchi qismga o'tkazish mumkin, shuning uchun tenglik olinadi. a Å b = 0 shaklini a = b va qanday qilib a - b = 0 deb yozish mumkin. Bu holda, barcha uchta tenglama a va b 0 ga teng yoki a va b 1 ga teng ekanligini anglatadi, ya'ni. . bir xil paritetga ega.

Shunday qilib, uni (5.1) shaklida yozish mumkin.

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

buni bizning misolimizda keltiramiz

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.

Polinom 1101001 - kerakli kombinatsiya, bu erda 1101 - axborot qismi va 001 - nazorat belgisi. E'tibor bering, biz to'liq to'rt xonali ikkilik kodning kombinatsiyalaridan birini (bu holda 1111) generatorning polinomiga ko'paytirish, shuningdek, berilgan kombinatsiyani bir xil darajadagi mono sovg'aga ko'paytirish natijasini olamiz. tanlangan generator ko'phad sifatida (bizning holimizda shunday qilib 1101000 birikmasi olingan) bu ko'paytmani hosil bo'lgan ko'phadga bo'linishning qolgan qismini hosil bo'lgan mahsulotga qo'shish orqali (bizning misolimizda qolgan 001 ko'rinishga ega).

Va bu erda hal qiluvchi rol o'ynaydigan ko'phadning xususiyatlari P (x) ... Tsikl kodni qurish usuli shundayki, generator ko'phad har bir kod birikmasini shakllantirishda ishtirok etadi, shuning uchun siklik kodning har qanday ko'phad generator tomonidan qoldiqsiz bo'linadi. Biroq, faqat berilgan kodga tegishli bo'lgan ko'phadlar qoldiqsiz bo'linadi, ya'ni hosil qiluvchi ko'phad barcha mumkin bo'lganlardan ruxsat etilgan birikmalarni tanlash imkonini beradi. Agar tsiklik kodni hosil qiluvchi polinomga bo'lishda qoldiq olinsa, bu koddagi xato yoki boshqa kodning kombinatsiyasi (taqiqlangan kombinatsiya). Qolganlari uchun taqiqlangan birikmaning mavjudligi aniqlanadi, ya'ni xatolik aniqlanadi. Polinomlarning bo'linishining qolgan qismi tsiklik kodlarning noto'g'ri identifikatorlari hisoblanadi.

Boshqa tomondan, birni nolga bo'lishning qolgan qismi tsiklik kodlarni yaratish uchun ishlatiladi.

Birni nolga xos bo'lgan ko'phadga bo'lishda shuni esda tutish kerakki, qolgan qismning uzunligi hech bo'lmaganda nazorat raqamlari soniga teng bo'lishi kerak, shunda qolgan nollar raqamlar yo'qligida tayinlanadi. qal'aning o'ng tomonida.

01100 11111+

G, [24.11.21 11:51]

sakkizinchidan boshlab balanslar takrorlanadi.

Kesim qoldiqlari hosilaviy matritsalarni qurish uchun ishlatiladi, ular siklik kodlarni qurishda keng qo'llaniladi, chunki ular hosila birikmalarini olishda aniq va qulaydir. Kreativ matritsani qurish elementlari birlikning qolgan qismi bo'lgan birlikni hosil qiluvchi polinom bilan nolga ko'chirish va qo'shimcha matritsani kompilyatsiya qilish uchun qisqartiriladi. P (x) ... Eslatib o'tamiz, uzatilgan identifikatsiya matritsasi barcha elementlari nolga teng bo'lgan kvadrat matritsadir, yuqoridan pastga diagonal ravishda o'ngdan chapga diagonal joylashtirilgan elementlardan tashqari (o'zgartirilmagan matritsada identifikatsiya elementlari bilan diagonal chapdan o'ngga). yuqoridan pastga). Qo'shimcha matritsaning elementlari aniqlangan matritsaning o'ng tomoniga tayinlanadi. Faqat og'irligi bo'lgan qoldiqlar W ³ d 0- 1, bu erda d 0 - minimal kod masofasi. Balanslar uzunligi kamida nazorat bitlari soniga teng bo'lishi kerak va balanslar soni ma'lumotlar bitlari soniga teng bo'lishi kerak.

Generator matritsasining satrlari manba kodining birinchi birikmalaridir. Qolgan kod kombinatsiyalari 2-modulni tashkil etuvchi matritsa satrlarining barcha mumkin bo'lgan kombinatsiyalarini yig'ish yo'li bilan olinadi.

Masalan.

10-bitli ikkilik birikmalarni uzatishda barcha bitta va qoʻsh xatolarni aniqlaydigan siklik kodning toʻliq matritsasini tuzing.

Yechim.

5.12-jadvalga muvofiq, eng yaqin qiymatni tanlang k³ 10.

5.12-jadval - 16 bitgacha bo'lgan kod uchun ma'lumotlar va tekshirish belgilari o'rtasidagi munosabatlar

nkrankr

Jadvalga ko'ra, bu qiymat k = 11, va r = 4, a bo'ladi

n = 15. X 4 + x 3 +1 generator ko'phadini ham tanlaymiz.

To'liq ishlab chiqaruvchi matritsa bitta transpozitsiya matritsasidan va nazorat raqamlariga mos keladigan qo'shimcha matritsadan kanonik shaklda tuzilgan.

k = 11 uchun matritsadan nusxa oling:

Qo'shimcha matritsa tanlangan generator bilan bo'linish bo'limining qolgan qismidan bitta va keyingi nollar (identifikatsiya o'tkaziladigan matritsaning oxirgi qatori) shaklida tuzilishi mumkin.

To'liq generator matritsasi quyidagicha ko'rinadi:

Yuqoridagi usul generatsiya qiluvchi matritsalarni qurish uchun yagona emas. Generator matritsasi identifikatsiya matritsasining elementlarini bevosita generator polinomiga koʻpaytirish yoʻli bilan tuzilishi mumkin. Bu ko'pincha birlikning qolgan qismini topishdan ko'ra qulayroqdir. Olingan kodlar avlod matritsalaridan tuzilgan kodlardan hech qanday farq qilmaydi, bu erda qo'shimcha matritsa hosil qiluvchi polinomga bo'linishning qolgan qismidan iborat.

Ijodiy matritsani darajaning tenglik matritsasi qatorini ko'paytirish natijasida olingan birikmaning tsiklik siljishi bilan ham xuddi shunday qurish mumkin. k generator polinomi.

Tsiklik kodlardagi xatolar hosil bo'lgan birikmani hosil qiluvchi polinomga bo'linishning qolgan qismidan foydalangan holda aniqlanadi. Bo'limning qolgan qismi xato identifikatorlaridir, lekin tsiklik koddagi xatoning o'rnini bevosita ko'rsatmaydi.

Xatolarni tuzatish g'oyasi ma'lum miqdordagi tsiklik siljishlardan so'ng, noto'g'ri kombinatsiya qolganlarga "moslashtirilgan" bo'lib, u tuzatilgan kodning so'zini qolganlari bilan birga berishiga asoslanadi. Bunday holda, qoldiq buzilgan va to'g'ri belgilar o'rtasidagi farqdan boshqa narsa emas va qolgan qismlardagi birliklar tsiklik siljishlar bilan tartibga solinadigan kombinatsiyadagi buzilgan bitlar o'rnida to'liq turadi. Buzilgan kombinatsiya qoldiqlar soni koddagi xatolar soniga teng bo'lguncha o'rnatiladi. Bu holda, albatta, ularning soni ushbu kod bilan tuzatilgan xatolar soniga teng bo'lishi mumkin s (kod buzilgan kombinatsiyadagi 3 ta xato va 3 ta xatoni tuzatadi) yoki kamroq s (kod 3 ta xatoni tuzatadi va Qabul qilingan kombinatsiyadagi 1 xato).

G, [24.11.21 11:51]

Kod kombinatsiyasidagi xatoning joylashuvi muhim emas. Agar k ³ (n / 2) bo'lsa, unda ma'lum miqdordagi burilishlardan so'ng barcha xatolar polinomning "bir martalik" harakati zonasida bo'ladi, ya'ni og'irlik bilan qoldiqni olish kifoya. W £ s va bu allaqachon buzilgan ulanishni tuzatish uchun etarli bo'ladi.

Xatolarni tuzatish jarayoni maxsus kod ishlab chiqarish misollari yordamida quyida batafsil muhokama qilinadi.

Yagona, bir nechta xatolar va xato portlashlarini aniqlaydigan samarali kodlar tsiklik kodlarni (CRC - Cyclic Redundance Code) o'z ichiga oladi. Ular juda ishonchli va bloklarni sinxronlashtirish uchun ishlatilishi mumkin, bu erda, masalan, bitta bitni nusxalash qiyin bo'ladi.

Tsiklik kodlash variantlaridan biri manba kodini g (x) polinomiga ko'paytirish, dekodlash esa g (x) ga bo'lishdir. Agar birlikning qolgan qismi nolga teng bo'lmasa, xatolik yuz berdi. Transmitterga xato signali yuboriladi, bu esa uni qayta uzatishga olib keladi.

Yaratuvchi ko'phad X n -1 soni bo'linadigan asosiy omillardan birining ikkilik ko'rinishi bo'lib, bu erda X n n-raqamdagi bittani ifodalaydi, n kod guruhidagi raqamlar soniga teng. Shunday qilib, agar n = 10 va X = 2 bo'lsa, X n -1 = 1023 = 11 * 93 va g (X) = 11 yoki ikkilik kodda 1011 bo'lsa, A i * g (X) siklik kodlari misollari. polinom kodlari guruhidagi A i raqamlarini quyidagi jadvalda ko'rish mumkin. 3.1.

Asosiy variant Amalda keng qo‘llaniladigan siklik kod avvalgisidan farq qiladi, chunki hosil qiluvchi ko‘phad bilan bo‘lish amali quyidagi algoritm bilan almashtiriladi: 1) K nollar o‘ng tarafdagi dastlabki kodlangan A raqamiga beriladi, bu yerda K – avlod polinomidagi qisqartirilgan bitlar soni; 2) O operatsiya olingan A * (2 K) raqami bo'yicha bajariladi, bu bo'limdan farq qiladi, chunki operatsiyaning har bir bosqichida chiqish o'rniga bitda eksklyuziv OR operatsiyasi bajariladi: 3) natijada B. qolgan qismi CRC. - keraksiz K-bit kodi kodlangan C raqamida o'ng K ga tayinlangan nollarni almashtiradi, ya'ni.

C = A * (2 K) + B.

Qabul qiluvchi tomonda O operatsiyasi C kodida amalga oshiriladi.Agar balans nolga teng bo'lmasa, u holda uzatish paytida xatolik yuz berdi va A kodini qayta uzatish kerak.

O'RNAK A = 1001 1101 ko'phad 11001 bo'lsin.

K = 4 bo'lgani uchun A * (2 K) = 100111010000. Tsiklik kodni hisoblash uchun O operatsiyasining bajarilishi rasmda ko'rsatilgan.

NumberCyclic codeNumerCyclic code00000000000.1300100011111000000101114001001101020000010110150010100101300001000011600110001105000011011118001100011060001000010190011010001 ...........................

Tsiklik kodlarning ijobiy xossalari xatoliklarni aniqlashning past ehtimoli va keraksiz bitlarning nisbatan kamligidir.