Axborot va kodlash nazariyasi asoslari

12-ma’ruza uchun nazorat savollari

1. 
   Fayra kodiga tushuncha bering?
   
2. 
   Fayra kodini qurish qanday amalga oshiriladi?
   
3. 
   Fayra kodida yasovchi polinomlarga tushuncha bering?
   
4. 
   Axborotlarni Fayra kodida kodlashtirish usullari qanday amalga oshiriladi?
   
5. 
   Fayra kodi parametrlari.
   
6. 
   Axborotlarni Fayra kodida kodlashtirish usullariga misol keltiring?
   
7. 
   Fayra kodida kodlashtirish algoritmini tushuntiring?
   

13-ma’ruza. Kaskadli kodlar.

Reja:

1. 
   Kaskadli kodlar.
   
2. 
   Kodlashni kaskadli prinsipini amalga oshirish.
   
3. 
   Kaskad kodning afzalligi.
   
4. 
   RS kodi xossalari.
   

Kaskad kodlar. Real aloqa kanallari, ayniqsa ovoz chastotasidagi standart kanal asosidagi aloqa kanallari xatolarni guruxlash aloqa kanallari hisoblanadi, xatolar paketlari uzunligi o‘nlab ikkilik belgilaridan yuzlab ikkilik belgilarigacha chegarada bo‘lishi mumkin. Bundan tashqari paketlar orasidagi himoya intervallarida tasodifiy xatolar mavjud. Bu strukturadagi xatolarni korreksiya qilish uchun shovqinbardosh kodlar talab qilinadi, bu esa juda katta uzunlikdagi kodlar ketma-ketligi va yuqori ortiqchalikdagi shovqinbardosh kodlardan foydalanish demakdir. Bunday kodlar dekodlash jarayonida yuqori murakkablikdagi amalga oshirish va katta axborot kechikishiga ega.

Bu strukturadagi xatolarni korreksiya qilish uchun talab etilayotgan axborot uzatilishi ishonchliligini dekodlashda kodekni kam murakkablikda amalga oshirish va kechikishni ta’minlaydigan axborotni kodlash usuli yaratilgan.

Bunday axborotni kodlash usulining mohiyati ikki va undan ortiq kodlarni kaskadlashdan iborat. Bunda har bir kodlash darajasida bir xil turdagi va korrektlash xususiyatidagi yoki har xil kodlardan foydalansa bo‘ladi.

Eng keng tarqalgan kaskad kodlar tuzilishi sxemasi ikki kaskadli yoki ikki pog‘onali sxema hisoblanadi:

Tashqi kod sifatida ko‘pincha paket xatoliklarini korrektlovchi Rid-Solomon kodlaridan foydalaniladi, ichki kodlar esa tasodifiy xatolarni korrektlovchi siklik xamda o‘rama kodlar bo‘lishi mumkin. Real aloqa sistemalarida ichki kod sifatida Viterbi dekodlash algoritmiga ega o‘rama kodlardan foydalaniladi.

Axborotni kodlash va dekodlash quyidagi ko‘rinishda amalga oshadi:

Tashqi koderda uzatilayotgan axborot paketli xatolarni korreksiyalashga mo‘ljallangan kod bilan kodlanadi. Asosan Rid-Solomonning ikkilik bo‘lmagan kodlaridan foydalaniladi. Keyin tashqi kodning kodli ketma-ketliklari ichki kod bilan kodlanadi.

Ichki koderning chiqishida kaskad kodning kodli belgilari modulyatorning kirishiga tushadi va keyin aloqa kanaliga uzatiladi.

Qabul qilish qismida avval ichki dekoderda, keyin esa tashqi dekoderda qayta ishlanadi.

Ichki kodni korrektlash xususiyatini oshirish maqsadida ichki koderning chiqishiga kodli belgilarni joyi o‘zgartiriladi.

Kodlar joyini o‘zgartirishning mohiyati kodlarni xar hil kodli so‘zlar bilan paketga kiruvchi, tasodifiy xatolarni to‘g‘irlovchi xatolarni bo‘lib-bo‘lib joylashtirishdan iborat.

Simsiz aloqa kanallarida bunday aniqlikni shovqinbardosh kodlashni qo‘llamay turib olish qiyin. Kodlash va dekodlash usulini tanlash 3 ta asosiy guruxga bo‘lingan, o‘zaro bog‘liqligi rasmda ko‘rsatilgan ko‘plab faktorlarga amal qilinadi.

Amalga oshish murakkabligi deganda:

• 
  apparat, hamda dastur harajatlari;
  
• 
  mikrosxema va mikroprotsessor narxi;
  
• 
  ma’lumotlar saqlash uchun xotira narxi va boshqalar tushuniladi.
  

O‘tkazish xususiyati deganda, bu kontekstda, faqatgina foydali axborot xajmi va ortiqchaligidan tashqari xizmat axboroti xajmi ham tushuniladi. Bunday xabarlar uzatish qabul qilishda sinxronizatsiyani o‘rnatish va qo‘llash uchun, ma’lumotlarni uzatishda elementlarni boshqarish uchun kerak bo‘ladi.

Amalda asosan tarkibli va kaskad kodlardan foydalaniladi. Kaskad koddan foydalanilgan axborot kanali 13.2-rasmda keltirilgan.

1 3.2-rasm. Kaskad koddan foydalanilgan axborot kanali
Kodlashni kaskadli prinsipini a’malga oshirish. Kodlashni kaskadli prinsipini amalga oshiruvchi xar xil variantlari mavjud. Avval axborotlarni ikkilik belgilar ketma-ketligi blok osti xar biriga belgidan bo‘linadi. Bu blok osti Galua ikkilik maydoni daraja kengaytmasi k₁ osti tashqi kodning axborot guruxini tashkil etgan xolda ko‘riladi. Ko‘p bunday belgilar dan aniqlanadi.

Tashqi kod k₂ asosida tekshirish belgilarini hosil qiladi. Agar tashqi kod sifatida Rid-Solomon kodidan foydalanilsa, unda u kodning korrektlash xususiyatlari ifodasi orqali aniqlanadi. Bu kodning tekshirish belgilari maydoni elementlari xisoblanadi.

Kodning (n₂, k₂) kombinatsiyalari barcha q-lik belgilari (n₁, k₁) ichki kod bilan kodlanadi. Natijada n₁ n₂ uzunliudagi k₁ k₂ ikkilik axborot umumiy minimal d₁ d₂ masofaga ega belgilardan iborat ikkilik blok kodi olinadi. Bu yerda d₁ ichki kodning minimal masofasi.

Quyida kaskad kodi so‘zi tuzilish sxemasi keltirilgan.

13.1-rasm. Kaskad kodi so‘zi tuzilish sxemasi

Kaskad kodning afzalligi ular (n₁, n₂, k₁, k₂) uzun kodni dekodlashni ikki sezilarli ichki ikkilik (n₁, k₁)  kod va tashqi (n₂, k₂) kod bilan dekodlashni almashtirishdan iborat. Kaskad kodlar  yetarlicha katta qiymatga ega   amalga oshirish imkonini beradi, shuning uchun ularning xatolarni guruxlanuvchi xatolar kanallarida qo‘llanilishi ma’noga ega.

Kaskad kodlarining boshqa afzalligi shundan iboratki, xatolarni ichki kod orqali to‘g‘rilashda erkin xatolarni faqatgina konstruktiv usul bilan emas, agar (n₁, k₁) kam quvvatli kod bo‘lsa, balki optimal saralash usullardan foydalanish mumkin. Uning xususiyatidan blokli kodlarni dekodlashda, klaster taxlili usuli orqali foydalanish mumkin. Qachonki klaster ehtimolligi ko‘proq xato namunalari kirsa bu dekodlash algoritmi ro‘yhat bo‘yicha dekodlashga o‘xshaydi.

Dekoderning murakkabligi kaskadli kodlash bilan sistemada xatolarni kod bilan to‘g‘irlash soni, funksiya kabi chiziqli o‘sadi, vaholanki oddiy kodlardan foydalanilsa, bu bog‘liqlik eksponensial xarakterga ega. Bunday effektning asosiy sababi shundan iboratki, ichki kodlar kombinatsiyasini dekodlashda u xatolarni to‘g‘irlamaydi, balki xatolarni aniqlaganda o‘chirib yuboradi.

O‘chirilgan pozitsiyalar RS kod bilan qayta tiklanadi, madomiki o‘chirish xato pozitsiyalarni yetarlicha ko‘rsatib bera olarkan, kodning korrektlash xususiyatlari xatoni topish uchun emas, balki o‘chirilgan pozitsiyalarni to‘g‘irlashga ishlatiladi.

RS kodlari so‘nggi maydon ustida quriladi. Aytib o‘tilganidek, bunday maydon har qanday r uchun hosil qilinishi mumkin va GF(p) kabi belgilanadi. GF(p) tushunchasi pm elementlaridan iborat GF(p) maydon kengaytmasi bilan nomlangan, kengaytirish darajasi GF (pm) bo‘lgan maydonda umumiylashtiriladi. GF (pm) maydoni   sifatida GF(p) ning barcha elementlariga ega. GF (2m) maydon kengaytmasida belgilar RS kodlarini qurishda ishlatiladi.

RS kodninig umumqabul qilingan ko‘rinishi  parametri va qandaydir   hisoblanadi, bu yerda    – xatolarni kod bilan to‘g‘irlash soni,   da. RS kod uchun umumlovchi polinom ushbu ko‘rinishga ega:

.

  RS kodining informatsion belgilar umumiy soni ikkilik maydonda GF (2m) ushbu ifoda orqali baxolanadi:

.

Tasvvur qilamiz  , m = 3, unda K = 64. Bunda informatsion RS kodning razryadlari orasida xuddi o‘sha GF (2m) maydonidagi a’zo 0 dan  gacha birinchi o‘rinda  gurux kombinatsiyasida shakllanadi. Sezilarliki, barcha kodli kombinatsiyalarning X5 razryadi (jadval RS kodni n2 = 7, k2 = 2 bilan tasvirlaydi) klaster deb ataladigan , konkret gurux kombinatsiyasini aniqlaydi. Klaster sonini X5 razryadi o‘rnidagi baza maydoni primitiv elementi darajasi kabi aniqlaymiz. Hosil bo‘ladigan kod polinomi quyidagicha aniqlanadi:

Bu yerda qo‘shish va ayrish operatsiyalari ikkilik maydonda tengligi xisobga olingan. RS kodning mashxur xususiyatlaridan tashqari keyingi muxokamalar nuqtai nazaridan muxim bo‘lgan xususiyatlarini ko‘rsatib o‘tamiz.

1-xossa. Istalgan sistematik RS kod o‘zini tarkibida n₂ bir xil q-lik elementlardan iborat  kombinatsiyalarga ega. Ikkilik gurux kodi toza yagona elementga (yagona kombinatsiya) ega ekan, q-lik kod GF (2m) maydonidagi bir xil elementlardan iborat kombinatsiyalardan tashkil topishi kerak, misol uchun,  .

Ko‘rilayotgan kodning parametrlari chegarasida 5ta birinchi belgilar tekshirish, oxirgi ikkitasi esa axborot belgilaridir. Ko‘rib o‘tilgan xossa ma’lumotlarni sinxron qo‘llash usuli va kodli kombinatsiyalarni majoritar usul bilan dekodlashda xam qo‘llanilishi mumkin. Bunday kodlarni qo‘llash umumlashtirilgan kaskad kodlarni qo‘llash protsedurasida majburiy talabdir.