Axborot va kodlash nazariyasi asoslari

Fayra kodini qurish asoslari. Bir karralik va ko‘p karralik tasodifiy xatolarni to‘g‘irlovchi kodlarni ishlatish, xar doim ham o‘zini oqlayvermaydi. Bunga sabab, aloqa kanallariga guruxli shovqinlarning ta’sir qilishidir. Guruxli shovqinlar esa kodli kombinatsiyadagi element (razryad)larni xatolarga uchrashini keltirib chiqaradi. Bu esa xatolar paketi deyiladi.

Uzatilgan kodli kombinatsiya 10100010001 ko‘rinishida bo‘lsin. Qabul qilish tomonida bu kodli kombinatsiya 10001010101 ko‘rinishda olindi. Bu kombinatsiyalarning razryadlarini o‘zaro modul 2 (mod 2) bo‘yicha yig‘indisini olsak, natija quyidagi ko‘rinishda bo‘ladi: 00101000100. Bundan ko‘rinadiki, qabul qilingan kodli kombinatsiyadagi xatolar soni natijaviy kombinatsiyadagi birlar soni (vazni) uchga teng bo‘lar ekan.

Xatolar paketining uzunligi v deb – qabul kilingan kodli kombinatsiyadagi eng yuqori xato razryad bilan eng kichik xato razryad orasidagi farqli bir birlikka oshirilganiga aytiladi.

Bizning yuqoridagi misolimizda xatolar paketining uzunligi

v = (9 – 3) + 1 = 7 ga teng. Xatolar paketini aniqlash va to‘g‘irlash uchun ancha effektiv xisoblangan Fayra kodi xozirda qo‘llanilmokda.

Fayra kodi siklik kodlar turkumiga kirib, xamma siklik kodlar kabi u ham ikkita muxim xususiyatga ega: birinchidan, berilgan kodning ixtiyoriy ikkita ruxsat etilgan kombinatsiyasining mod 2 bo‘yicha yig‘indisi, yana ruxsat etilgan kodli kombinatsiyani beradi. Bundan esa ko‘rinadiki, siklik koddagi eng kichik kod masofasi uning kombinatsiyalari ichidan eng kichik vaznlisi orqali aniqlanadi.

Odatda, eng kichik kod masofasini topish uchun, kodli kombinatsiyalarning xamma juftlarini o‘zaro mod 2 bo‘yicha yig‘indisini aniqlaymiz. Yig‘indilar ichidan eng kichik vaznlisi eng kichik kod masofasini bildiradi.

Ikkinchi muxim xususiyati, agar ruxsat etilgan kodli kombinatsiyani bitta elementga siklik siljitsak, ya’ni oxirgi pozitsiyadagi elementni birinchi qo‘yib, qolganlarini undan keyin joylashtirsak, natijada shu kodga tegishli bo‘lgan boshqa ruxsat etilgan kodli kombinatsiya xosil bo‘ladi. Masalan: agar kodli kombinatsiya 110101 dan iborat bo‘lsa, bitta qadamga siklik siljitish orqali 111010 dan iborat bo‘lgan boshqa ruxsat etilgan kombinatsiyani olamiz. Keyingi siljish esa 011101 ni beradi va xokazo.

Xamma siklik kodlar kabi Fayra kodidagi kodli kombinatsiyalarda ham birinchi tekshiruv bitlari, keyin informatsion bitlar joylashgan bo‘ladi. Ya’ni aloqa kanaliga birinchi k informatsion bitlar, keyin esa r tekshiruv – bitlari uzatiladi.

Fayra kodini qurishda, kodli kombinatsiyalarni x argumentdan iborat bo‘lgan ko‘pxad ko‘rinishiga keltirish ancha qulayliklarni yuzaga keltiradi. Bu ifodadagi x – sanoq sistema asosini bildiradi.

Ixtiyoriy sanoq sistemasidagi N sonini quyidagicha yozish mumkin:
N = Kn b ^n-1 + K _n-1 b ^n-2 + … K _i b^i-1 + . . . K_{2 b}¹ + K_{1 b} ⁰

b- sanoq sistema asosi;

n – sondagi razryadlar miqdori;

K_i- razryaddagi raqam.

Yuqoridagi ifodaga asosan ixtiyoriy sonni x o‘zgaruvchili polinom ko‘rinishda yozish mumkin.

Masalan ikkilik sanoq sistemasidagi 101001101 sonni, x o‘zgaruvchili polinom ko‘rinishda yozamiz.

G(X) = 1•X ⁸ + 0 • X ⁷ + 0 • X ⁶ + 0 • X ⁵ + 0 • X ⁴ + 0 • X ³ + 0 • X ² + 0 • X ¹ +0 • X ⁰
yoki G(X) = X ⁸ + X ⁶ + X ³ + X ² + 1
So‘nggi ikkita ifodani solishtirib, koeffitsienti nol bo‘lgan xadlar yozilmasligini ko‘ramiz. Undan tashqari ko‘pxad darajasi har doim kombinatsiyadagi razryadlar sonidan bittaga kichik bo‘ladi.

Kodli kombinatsiyalarni tasvirlovchi ko‘pxadlarni ko‘paytirish va bo‘lish oddiy algebraik qoida asosida bajarilsa, qo‘shish esa mod 2 bo‘yicha amalga oshiriladi:

Masalan:

Siklik kodlar yasovchi (xosil qiluvchi) polinom bilan xarakatlanadi. Kodlashtirish bevosita yasovchi polinom orqali xosil qilinadi. Shu sababli ushbu polinom xosil qiluvchi, yasovchi polinom deyiladi. Yasovchi polinom darajasi r = n - k ga teng bo‘ladi. Yasovchi polinomning ko‘rinishi va uning darajasi siklik kodning korrektorlash qobiliyatini ifodalaydi.

Yasovchi polinom sifatida keltirilmaydigan ko‘pxadlar olinadi. Keltirilmaydigan ko‘pxad deb – faqat o‘ziga va birga qoldiqsiz bo‘linadigan polinomlarga aytiladi. Ya’ni bunday polinomlarni ko‘paytuvchilarga ajratib bo‘lmaydi. Quyida beshinchi darajagacha bo‘lgan keltirilmaydigan polinomlar ko‘rsatilgan:

P(x¹) = x+1;

P(x²) = x² + x+1;

P(x³) = x³ + x+1;

P(x³) = x³ + x² +1;

P(x⁴) = x⁴ + x +1;

P(x⁴) = x⁴ + x³ + x² + x +1;

P(x⁵) = x⁵ + x² +1;

P(x⁵) = x⁵ + x³ +1;

P(x⁵) = x⁵ + x³ + x² + x +1;

P(x⁵) = x⁵ + x⁴ + x³ + x +1;

P(x⁵) = x⁵ + x⁴ + x³ + x ²+1;
Siklik kodning aloxida jixatlaridan biri, uning xamma kodli kombinatsiyalarini yasovchi polinomga qoldiqsiz bo‘linishidir. Xatoga uchragan kodli konbinatsiyani yasovchi polinomga bo‘lganda, albatta qoldiq xosil bo‘ladi. Demak, yasovchi polinomga bo‘lish natijasida qoldiq xosil bo‘lmaydigan kodli kombinatsiyaga, siklik kodning ruxsat etilgan kodli kombinatsiyasi deb ataladi. Aks xolda esa ta’kidlangan yoki man qilingan kodli kombinatsiya deyiladi.

Siklik kodining bunday xususiyatidan xatolarni aniqlash va to‘g‘irlashda foydalaniladi. Ma’lumki, uzatiladigan kodli kombinatsiyaga shovqin ta’sir etishi natijasida u man qilingan kombinatsiyaga aylanadi. Bunday kombinatsiyani yasovchi polinomga bo‘lganda qoldiq xosil bo‘ladi. Bu esa xato yuz berganligini bildiradi. Demak yasovchi polinomga bo‘lishdan xosil bo‘lgan qoldiq orqali xatolar aniqlanadi.