27 – 28 –mavzu: Axborotli teskari aloqali tizimni, qanday xatolar aniqlanmasligini

27 – 28 –MAVZU: Axborotli teskari aloqali tizimni, qanday xatolar aniqlanmasligini, yolg‘on ishga tushish holati qachon ro‘y berishni, yechimli teskari aloqali tizimni, xatolar bilan qabul qilingan axborotni qayta uzatish qanday amalga oshirilishini o‘rganish

-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 Siklik kesishuvi asl nusxa bilan ifodalanishi mumkin:

Ko'phadning kodi g (x) ga bo'linishi kerakligi sababli, u Siklik 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. Siklik 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, Siklik 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 Siklik 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 Siklik 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.

Siklik kodlar shunday nomlanadi, chunki ular bir yoki bir nechta kod birikmalarining Siklik siljishi natijasida olinadigan kod birikmalarining bir qismini yoki barchasini o'z ichiga oladi. Siklik siljish o'ngdan chapga amalga oshiriladi va eng chapdagi belgi har safar kombinatsiyaning oxiriga o'tkaziladi. Siklik 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.

Siklik 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 Siklik 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.