Axborot va kodlash nazariyasi asoslari

Kodning spektr og‘irligi. Ma’lumki kodning spektr og‘irligi – bu ko‘p sonli M(ω) ko‘pxadining, (ω =0,n) da kodli kombinatsiyalar og‘irligidagi qiymatidir. Ya’ni barcha kodli kombinatsiya tashkil etuvchilari nol bo‘lmagan yig‘indi orqali aniqlanadi. Kodli kombinatsiyalari ko‘p bo‘lmagan kodlar uchun (taqqoslaganda k- informatsion razryaddan ko‘p bo‘lmagan) spektr og‘irliklari uchun, ruxsat etilgan kerakli miqdordan ortiqcha 2^k kombinatsiyasi orqali aniqlashimiz mumkin. Uncha uzunlikka ega bo‘lmagan, odatda BChX kodlari kaskad kodning birinchi pog‘onasida past sifatli diskret kanalda kichkina xatoliklarni to‘g‘irlash uchun ishlatiladi. Siklik koddagi kodli kombinatsiyani qabul qilishda ikkita usuldan foydalanamiz:

1. 
   Q(x) kodli kombinatsiyani x^r bir xadiga ko‘paytirib, xosil bo‘lgan ko‘paytirish natijasiga R(x) polinomda Q(x)*x^r bo‘lish natijasida xosil bo‘lgan R(x) qoldiq qiymatni qo‘shish orqali:
   

F(x) =Q(x)*x^r+R(x) (1)

2. 
   Q(x) kodli kombinatsiyani oddiy kodli polinom xosil qiluvchiga ko‘paytirish orqali.
   

Birinchi usul tizim kodini xosil qiladi. Bunda informatsion belgilar, r- ning qolgan o‘rinlariga tekshirilgan, k-ning birinchi o‘rnida joylashadi. Ikkinchi usulda tizimlashmagan kod xosil bo‘ladi. Bunda tekshirilgan belgilar va ma’lumotlar aniq ko‘rinishda bo‘lmaydi. Shunga qaramasdan shovqinbardosh kodlarda tizimli va tizimlashmagan kodlar tengdir. Kodli ko‘plik o‘zgarmaydi, faqat xar bir so‘zli ma’lumot uchun kodli so‘zga mos xolda tartibi o‘zgaradi. Bunday tasdiqning to‘g‘riligini birinchi va ikkinchi usuldan foydalangan xolda tuzilgan 1 tasvir asosida ko‘rishimiz mumkin.

Ruxsat etilgan birinchi kodli kombinatsiya usulda avtomatizatsiyani qurishda u yoki bu dasturlash algoritmi usullaridan ma’lumotlarni siklik kodlash jarayonlarida foydalaniladi:

1. 
   Kodli xabarlarni qismlarga bo‘lish orqali;
   
2. 
   Kodli axborotni to‘g‘ridan -to‘g‘ri bo‘lish orqali;
   
3. 
   Matritsa usulida;
   

d) jadval usulida.

14.4-rasm. Turli xil usullarda olingan kodli kombinatsiyalarning o‘zaro bog‘liqligi.

Mavjud kodlash algoritmlariga asoslangan xolda dasturning murakkabligini baxolashni amalga oshiramiz. Buning uchun xotira xajmi va kodlash uchun talab qilinadigan vaqtli yuklamani xisoblashimiz zarur. Kodli kombinatsiyaga ishlov berish jarayonida operatsiyalar miqdori:

A₀=A_n+A_sK (2) shu formula orqali aniqlanadi.

Bu yerda:

A₀ – kodlash uchun zarur bo‘lgan umumiy jarayonlar miqdori;

A_n – bir marta bajariladigan operatsiyalar miqdori;

A_s – siklda bajariladigan operatsiyalar miqdori ;

K – kodlashning uslubiga bog‘liq bo‘lmagan xolda o‘zgaruvchi sikllar miqdori.

Kodlash usulini kodli kombinatsiyalarni qismlarga bo‘lish orqali amalga oshiramiz. ShKning yuklama o‘lchovi kodli kombinatsiyaning uzunligiga bog‘liq bo‘lgan xolda kodlash uchun zarur bo‘lgan vaqt va tekshiriladigan razryadlar soni 14.1-jadvalda keltirilgan.

14.1-jadval.

Kodli kombinatsiyani qismlarga bo‘lish usuli uchun asosiy ko‘rsatkichlar

Kod uzunligining ko‘rsatkichi	7,4	15,11	31,26	63,57	127,120	255,247
Yuklama (oper/bit)	15,25	14,45	14,19	14,08	14,04	14,02
Vaqt, Ms	0,061	0,159	0,369	0,803	1,685	3,46

 

Jadvaldan qo‘rinib turibdiki, bu usul katta uzunlikdagi kodlarni kodlash uchun qulay, u xotirada kodlash jadvaliga qo‘shimcha joyni talab qilmaydi.

14.2-jadval.

Asosiy parametrlarga bog‘liq bo‘lgan xolda kod uzunligini to‘g‘ridan to‘g‘ri bo‘lish

Kod parametri uzunligi	7,4	15,11	31,26	63,57	127,120	255,247
Yuklama (oper/bit)	8,7	7,38	7,26	7,17	7,15	7,05
Vakt, Ms	0,105	0,237	0,567	1,227	2,613	5,451

Jadvaldan ko‘rinib turibdiki, kod uzunligi oshgan sari yuklama kamayyapti, kodlash uchun sarflanadigan vaqt esa oshyapti. Kodni qismlarga bo‘lish usuli xotirada kod jadvali uchun qo‘shimcha xarajat talab etadi. Birinchi blok razryadining uzunligi qancha katta bo‘lsa, uning xajmi ya’nada oshadi. Matritsalardan foydalangan xolda kodlashda A_n,m matritsa xosil qilinadi. Uni qabul qilishda qo‘shimcha tekshirilgan matritsa elementlaridan foydalanish talab etiladi. Tekshiriluvchi elementlar ketma-ket bo‘linuv asosida polinom birligida o‘ng tomondagi nollarni va qo‘shimcha matritsa satrlarini saqlagan xolda qoldiq oralig‘ida aniqlaydi.

14.3-jadvalda ShKda kod kombinatsiyasining uzunligiga bog‘liq bo‘lgan xolda matritsa usulida tekshirilgan razryadlar uchun sarflangan yuklama va vaqt ifodalangan.

14.3-jadval.

Kod uzunligiga bog‘liq xoldagi Matritsa usulidagi asosiy parametrlar

Kod parametri uzunligi	7,4	15,11	31,26	63,57	127,120	255,247
Yuklama (oper/bit)	3,75	2,63	2,26	2,12	2,05	2,028
Vakt, Ms	0,075	0,089	0,099	0,121	0,247	0,601

 

Jadvalda keltirilgan ma’lumotlardan ko‘rinib turibdiki, matritsali usul mashina vaqtining katta sarfini talab qilmaydi. Lekin kodning uzunligi ortishi bilan jadval uchun kerakli xotira xam oshib boradi.

Jadval usulining a’malga oshirilishida ShK xotirasiga 0 dan 2^k gacha tekshiriluvchi razryadlarga tegishli natural sonlar o‘sib borish tartibida joylashadi va ma’lumotlar kombinatsiyalarining mumkin bo‘lgan qiymatlaridan tuzilgan matritsa yoziladi. Tekshirilayotgan razryadlar oldindan berilgan kodni kodlash qoidasi bo‘yicha xisoblanadi. Buning uchun kodli kombinatsiya qiymatini ko‘rsatuvchi jadval satrining tartibini bilish kifoya. Bundan maqsad kodlangan so‘zni aniqlashdir. Jadval usuli uchun xisoblangan xotira xajmi kodning uzunligiga bog‘liq va unga asosan vaqt va yuklama xaqida ma’lumot 14.4-jadvalda keltirilgan.

 14.4-jadval.

Jadvalli usulda kod uzunligiga bog‘liq bo‘lgan xolda asosiy parametrlar

Kod uzunligining parametrlari	7,4	15,11
Xotira xajmi (yacheykalar)	15	23
Yuklama (oper/bit)	1,25	0,45
Vaqt, ms	0,015	0,015

Jadvaldagi ma’lumotdan ko‘rinib turibdiki, kodlashning bu usuli xotira yuklamalari va kodning qisqa uzunlik xolatida mashina vaqtining kam sarfini talab qilar ekan. Kod uzunligi oshgan sari esa jadval uchun xotira xajmi xam oshib boradi.

Yuqoridagi jadvalni taxlil qilish natijasi shuni qo‘rsatadiki, katta bo‘lmagan uzunlikdagi kodlarda amalga oshirish qiyinligi tomondan eng qulay xisoblanadi. Chunki bu usul ShKdan kam yuklamani va ancha katta bo‘lmagan kodlash vaqtini talab qilar ekan. Shuningdek, kattalik o‘zgarish yo‘li bilan qismlarga bo‘lish usuli kam yuklama va vaqt tomondan yaxshi natijalarga ega. Biroq katta uzunlikdagi kodlarda ushbu ikkinchi usuldan foydalanish samarasiz bo‘lib qoladi. Chunki bunda ShKdan sezilarli xotira sarfini talab qilmaydigan to‘g‘ridan-to‘g‘ri bo‘lish usuli eng yaxshi xisoblanadi.

Ruxsat etilgan kodli ketma-ketlikni qurishni amalga oshirish qiyinligi tomondan qulayroq xisoblanadi. Uning qo‘llanilishi Q(x) ko‘pxad va P(x) ko‘pxadlarni qo‘llash orqali jarayonni soddalashtiradi.

Kodlashga asoslangan spektr og‘irligini aniqlash algoritmini ishlab chiqish asosi bo‘lib ruxsat etilgan kodlar ketma - ketligini olish qo‘yilgan. Algoritm o‘zgaruvchilarini va xotirani zaxiralashni e’lon qilish bilan boshlanadi (blok 2).

Bu blokda oraliq ma’lumotlarni, yakuniy natijani saqlash va yozish uchun qanday o‘zgaruvchilar va massivlar kerak bo‘lishini aniqlaymiz.

Keyin kerakli ma’lumotlarni yasovchi polinom P(x), ma’lumot polinomi uzunligi k lar kiritilishi kerak (blok 3).

Axborot qismi uzunligi kodli so‘zning mumkin bo‘lgan barcha ketma-ketliklarini qidirish sonini aniqlash uchun kerak (blok 4). 5 blokda r kodli ketma-ketlikning tekshirilayotgan razryadlarini xisoblash amalga oshiriladi. Keyin x^r ko‘pxad xisoblanadi (blok 6). 7 blokda x^r va Q_i(x) ko‘pxadlar ko‘paytiriladi. Bu oraliq natija xotiraga saqlanadi va axborot ketma-ketligining mumkin bo‘lgan qiymatlarini xisoblanganlik sharti tekshiriladi (blok 8). Keyingi qadamda olingan natijani yasovchi polinom P(x) ga bo‘lish bajariladi (blok 9). Bu 10 blokdagi qoldiq R(x) aniqlash uchun zarur. R(x) qoldiq xar bir ketma- ketlik uchun topiladi va shuning uchun yana kodli ketma-ketlik yana bir bor yoki yo‘qligi sharti teshiriladi (11blok). 12 blokda F(x) kodli ketma-ketlik shakllantiriladi. Kodli ketma ketlikni olgandan so‘ng og‘irlikni xisoblashga kirishish mumkin (13blok ). Endi og‘irlik qiymatini ifodalab chiqamiz(14 blok). Algoritmning tuzilish sxemasi 14.5-rasmda keltirilgan.

2 rasm .

14.5-rasm. Og‘irlikni xisoblovchi algoritm sxemasining tuzilishi

 

Polinomlarni ko‘paytirishga asoslangan spektr og‘irlikni aniqlash algoritmiga siklik kodning kodli ketma-ketligini olish ikkita ko‘pxad yasovchi axborot yordamida amalga oshirish asos bo‘lgan.

Algoritm o‘zgaruvchilarni va xotirani zaxiralash e’lon qilinadi (2 blok). Bu blokda oraliq ma’lumotlar va yakuniy natija yozish va saqlash uchun (s1, s2, s3) kerak bo‘lgan massivlar va o‘zgaruvchilar aniqlanadi.

Keyin chiquvchi ma’lumotlarni kiritish zarur bo‘ladi: (50) shaklida polinom va polinom ma’lumotlar uzunligi (№1) (blok3).

Ma’lumotning uzunlik qismi, kerakli miqdordagi kodli so‘zning barcha imkoniyatlarini aniqlash uchun kerak. Bundan tashqari boshlang‘ich s1 i s2 (4 blok ) qiymatini aniqlash uchun kerak.

Bu qiymatlar oraliq natijani yozish uchun qo‘llaniladi. 5 blokda ikkita ko‘pxad ko‘paytiriladi va xosil bo‘lgan siklik kodli kombinatsiyani olgan xolda og‘irlikni xisoblashga o‘tishimiz mumkin (blok 6). Xisoblash amalini yakunlashdan oldin xabar kombinatsiyasining ketma-ketlik imkoniyatlarini (blok 7) ko‘ramiz. Siklik kombinatsiyaning chapga surilishi operatsiyasi kerakli miqdor prinsipi xisoblanadi. Agar to‘liq to‘lib qolish kuzatilsa, og‘irlik qiymatlarini chiqaramiz. (blok 9). Agar yo‘q bo‘lsa, keyingi 1 qiymatni aniqlaymiz (blok 8), va kodli og‘irliqni xisoblash jarayonini takrorlaymiz. Shu bilan xisoblash jarayonini (blok 10).