13-ma’ruza. O‘rama, ldpc va Turbo kodlar

Kodning spektr og‘irligi


Ma’lumki kodning spektr og‘irligi – bu ko‘p sonli M(ω) ko‘pxadining, (ω =0,n) da kodli kombinasiyalar og‘irligidagi qiymatidir. Ya’ni barcha kodli kombinasiya tashkil etuvchilari nol bo‘lmagan yig‘indi orqali aniqlanadi. Kodli kombinasiyalari ko‘p bo‘lmagan kodlar uchun (taqqoslaganda k- informasion razryaddan ko‘p bo‘lmagan) spektr og‘irliklari uchun, ruxsat etilgan kerakli miqdordan ortiqcha 2^k kombinasiyasi 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 kombinasiyani qabul qilishda ikkita usuldan foydalanamiz:

1. 
   Q(x) kodli kombinasiyani 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‘shib:
   

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

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

Birinchi usul tizim kodini xosil qiladi. Bunda informasion 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 kombinasiya usulda avtomatizasiyani 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.



1-rasm. Turli xil usullarda olingan kodli kombinasiyalarning o‘zaro bog‘liqligi.

Mavjud kodlash algoritmlariga asoslangan xolda dasturning murakkabligini baxolashni a’malga oshiramiz. Buning uchun xotira xajmi va kodlash uchun talab qilinadigan vaqtni yuklamani xisoblashimiz zarur. Kodli kombinasiyaga ishlov berish jarayonida operasiyalar miqdori:

A₀=A_n+A_sK (3)
shu formula orqali aniqlanadi.
Bu erda:
A₀ – kodlash uchun zarur bo‘lgan umumiy jarayonlar miqdori;
A_n – bir marta bajariladigan operasiyalar miqdori;
A_s – siklda bajariladigan operasiyalar miqdori ;
K – kodlashning uslubiga bog‘liq bo‘lmagan xolda o‘zgaruvchi sikllar miqdori.

Kodlash usulini kodli kombinasiyalarni qismlarga bo‘lish orqali amalga oshiramiz. PKning yuklama o‘lchovi kodli kombinasiyaning uzunligiga bog‘liq bo‘lgan xolda kodlash uchun zarur bo‘lgan vaqt va tekshiriladigan razryadlar soni 1 jadvalda keltirilgan.

1 jadval.

Kodli kombinasiyani 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.

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.
3 jadvalda PKda kod kombinasiyasining uzunligiga bog‘liq bo‘lgan xolda matritsa usulida tekshirilgan razryadlar uchun sarflangan yuklama va vaqt ifodalangan.
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 PK xotirasiga 0 dan 2^k gacha tekshiriluvchi razryadlarga tegishli natural sonlar o‘sib borish tartibida joylashadi va ma’lumotlar kombinasiyalarining mumkin bo‘lgan qiymatlaridan tuzilgan matritsa yoziladi. Tekshirilayotgan razryadlar oldindan berilgan kodni kodlash qoidasi bo‘yicha xisoblanadi. Buning uchun kodli kombinasiya qiymatini ko‘rsatuvchi jadval satrining tartibini bilish kifoya. Bundan maqsad kodlangan so‘zni aniqlashdir. Jadval usuli uchun xioblangan xotira xajmi kodning uzunligiga bog‘liq va unga asosan vaqt va yuklama xaqida ma’lumot 4 jadvalda keltirilgan.

3.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 PKdan 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 PKdan 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 2 rasmda keltirilgan.

2-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 a’malga 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 kombinasiyani olgan xolda og‘irlikni xisoblashga o‘tishimiz mumkin (blok 6). Xisoblash amalini yakunlashdan oldin xabar kombinasiyasining ketma-ketlik imkoniyatlarini (blok 7) ko‘ramiz. Siklik kombinasiyaning chapga surilishi operasiyasi kerakli miqdor prinsipi xisoblanadi. Agar to‘liq to‘lib qolish kuzatilsa, og‘irlik qiymatlarini chiqaramiz. (blok 9).agar yo‘q bo‘lsa, keyingis 1 qiymatni aniqlaymiz (blok 8), va kodli og‘irliqni xisoblash jarayonini takrorlaymiz. shu bilan xisoblash jarayonini (blok 10).