25 – mavzu: Hosil bo‘luvchi turli polinom

25 – MAVZU: Hosil bo‘luvchi turli polinom ko‘rinishlari uchun siklik kod kombinatsiyalarini qurilish chizmasini qurishni, axboratni qayta kodlash ketma- ketligini tekshirishni bilish.
Siklik kodni tekshirish polinomi. Davriy kodlash jarayoni. Matritsa kodining ta'rifi
Siklik 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.
Siklik 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. Siklik kod tizimli blokga (l, &) tegishli - kodlar uchun birinchi raqamlar asosiy kodning kombinatsiyasi bo'lib, keyingi (l - To) raqamlari tekshiriladi.
Siklik 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 Siklik 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 Siklik siljishi - uning elementlari tartibini buzmasdan o'ngdan chapga siljish, eng chap elementning pozitsiyasini eng o'ng tomonga olish.
Siklik kodlarning asosiy xossalari va nomi uzatilayotgan xabardagi (kod so'zlari) barcha ruxsat etilgan bit birikmalarini har qanday manba kod so'zining Siklik siljishi orqali olish mumkinligi bilan bog'liq.
Aytaylik, asl kod birikmasi va tegishli polinom berilgan:
Repoduktsiya 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 ifodalanshi 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.
Sikik 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.Siklik kodlar nazariyasida ko'phadlar ko'phad yaratish rolini o'ynaydi.
Siklik kodning ta'rifiga qaytsak va kod birikmalarining Siklik 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. Siklik 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 Siklik 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 Siklik kodning uzunligi.
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 Siklik 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)
Siklik kod - bu uni tashkil etuvchi kod vektorlarining Siklik 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.