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

Engil qaror bilan kodlarni ochish

Blokli kodlarni ochish qattiq yoki engil qaror qabul qilish yordamida amalga oshirilishi mumkin, kodni ochuvchidan chiqishda esa qattiq yoki engil echimli ma’lumotlarga ega bo‘lamiz. Qattiq qaror qabul qilish orqali kodni ochishda har bir qabul qilinayotgan bitga qabul qilinayotgan ma’lumotlardagi halaqitlarning me’yordan ko‘p yoki kamligiga bog‘liq ravishda 0 yoki 1 belgisi yoziladi. Kod ochgichda kodlagichda xato borligini aniqlash, imkon bo‘lganda xatoni to‘g‘irlash uchun qo‘shilgan ortiqcha ma’lumot qo‘llaniladi. Kod ochgichdan chiqayotgan ma’lumotlar – bu to‘g‘irlangan kodli so‘zlar xisoblanadi.

Engil echimli qaror bilan qabul qilingan kod ochuvchi faqatgina 1 yoki 0 binar kattalikni qabul qilib qolmasdan, balki, berilgan bit bilan bog‘liq ishonchli kattalikni ham qabul qiladi. Agar modulyator bitga 1 belgisi biriktirilishini aniqlasa, u holda ishonchlilik darajasi unda yuqori bo‘ladi. Agar u kamroq aniqlansa, bu xolda u pastroq ishonchli kattalikka joylashtiriladi. Engil echimga kiradigan kod ochuvchi qattiq qarorli yoki engil echimga ega qarorli ma’lumotlar chiqarishi mumkin. Masalan, Viterbi kodni ochish qurilmasi engil echimli axborotni qabul qiladi va qattiq qarorli ma’lumotlarni chiqaradi. Kod ochuvchi engil echimli ma’lumotni berilgan 0 yoki 1 bitning qattiq tengligini aniqlash uchun ishlatishi mumkin. Bunda biz chiqayotgan bitdan shunday qattiq qarorga ega bo‘lamiz.
Engil echimga kiruvchi va engil chiquvchi (SISO) kod ochuvchi engil qarorli ma’lumotlarni qabul qiladi va engil qarorli ma’lumotlarni chiqaradi. Kodli so‘zning har bir biti uchun SISO kod ochuvchisi kodning ortiqcha ma’lumotidan foydalangan holda kodli so‘zdagi boshqa bitlarning ishonchlilik darajasini baxolaydi, berilgan bit uchun mukammallashtirilgan engil ma’lumotlarni ishlab chiqadi.
Xatolarni tahrirlovchi RS – kodlar (FEC) xatolar tahririni ogohlantirish uchun standart algoritm hisoblanadi.
RS – kodlar – bu blokli kodlar bo‘lib, dasturiy hamda uskunaviy ta’minotni qo‘llash jarayonida xatolarni to‘g‘irlash bo‘yicha juda yaxshi qobiliyatga ega.
RS – kodlar – bu qattiq qaror qabul qiluvchi kodlar hisoblanadi. RS – kodlardan keyingi o‘rinda Viterbi (RSV) kaskad kodlari turadi, ular xato bitlarning paydo bo‘lish tezligi bo‘yicha avtonom RS – kodlardan ustun turadi.
SISO kod ochgichlari konsepsiyasi turbo-kodlarda qo‘llangan. Turbo-kod SISO kod ochgichiga engil echimga ega qarorli ma’lumotlarni etkazadi. Mazkur kod ochgichning chiquvchi ma’lumotlari keyin aynan shu yoki boshqa SISO kod ochgichiga uzatiladi. Keyin jarayon qayta takrorlanadi. Bu iterasiya jarayoni qat’iy qaror qabul qilingunga qadar davom etadi. Chiqayotgan ma’lumotlarni orqaga kirish qismiga qaytarilish konsepsiyasi dvigatelning turbopurkagichiga o‘xshash bo‘lganligi sababli ham turbo-kod aynan shunday nomlangan.
Turbo-kodni qo‘llash samaradorligini oshirish uchun, ma’lumotlarni ikki yoki ko‘proq turli xil kodlar bilan kodlash lozim. Shundan so‘ng kodni ochish jarayonida kodlarning har biri har bitta bitga nisbatan o‘z ishonchlilik darajasini o‘zgartiradi. Har bir iterasiyada barcha kodlar ma’lumotlarga bo‘lgan ishonchlilik darajasini o‘zgartiradi, shunday ekan, har bir kod har bir iterasiya uchun birmuncha farq qiluvchi ma’lumotlarni kuzatadi. Har bir kod berilgan bitga nisbatan ishonchlilik darajasini oshiradi yoki pasaytiradi, va natijada xato bitlarga nisbatan qarorning qattiqlik darajasini o‘zgatiradi. Oxir oqibatda, ma’lumotlar shunday ko‘rinishga keladiki, bunda barcha kodlar barcha bitlarga nisbatan ishonchlilik darajasini faqatgina oshiradi. Bu bosqichda qattiq qaror kattaligi uzatilayotgan ma’lumotlarga yaqinlashadi.
Tahrirli kodlarni qo‘llash jarayonida ikkilamchi signallarning kanal bo‘ylab shovqinli uzatilishini ko‘rib chiqamiz.
Halaqitga qarshi kodlarni ochishning ikkita usuli mavjud bo‘lib, ular amaldagi sonlarni ketma-ketlikda demodulyasiya qilinishidan keyin olinishga asoslanadi.
“Qattiq” qaror orqali kodni ochish (hard decision decoding). Bu holatda amaldagi songa 0 yoki 1 taqqoslanadi, ya’ni kanaldan qabul qilingan birliklarga nisbatan qattiq qarorlarni qo‘llash jarayonida qabul qilinayotgan belgilarning inversiyasi ko‘rinishidagi xato paydo bo‘ladi. Bunday holatda maksimal ishonchlilik tamoyili asosida kodni ochish uchun Xemming masofasidan foydalaniladi.
“Engil” echimli qaror orqali kodni ochish (soft-decision decoding). Kanaldan qabul qilingan birliklar darajalarning berilgan sonida kvantlanadi va darajalar bir nechta intervalda sonlar bilan kodlanadi, masalan, sakkizinchi darajali kvantlanishda -4, -3, -2, -1, 0, 1, 2, 3 birliklari vositasida kodlanadi. Bunday holatda maksimal ishonchlilik tamoyili asosida kodni ochish uchun odatiy evklid masofasidan foydalaniladi.
Umuman olganda, u yoki bu qarorni tanlashdan oldin aloqa kanalidagi shovqin statistikasini bilish maqsadga muvofiq. Bundan tashqari, shuni yodda tutish kerakki, “Qattiq” qaror orqali kodni ochish berilgan kodni ma’qul darajada tahrirlashni kafolatlovchi boy nazariy bazaga ega.
“Engil” echimli qaror uchun esa bunday nazariy baza deyarli mavjud emas. Boshqa tomondan olganda, “Engil” echimli qarorda kod ochgich tomonidan aniqlangan xatolar miqdori ( darajalar sonining ko‘pligi hisobiga) “Qattiq” qarordagiga nisbatan kamroq bo‘lishini kutish mumkin, va mos ravishda aynan bitta kod ko‘p miqdordagi xatolarni to‘g‘irlashi mumkin, masalan, (ABGSH) additiv oq gauss kanalida. “Engil” echimli qaror orqali kod ochish qo‘llanilishining maqsadga muvofiqligi ma’lumotlarni tiklash yoki signal qabul qilishdagi shovqin komponenti o‘z tabiatiga ko‘ra diskret emas, balki uzluksiz bo‘lganligi bilan ham asoslanadi. Bu esa qabul qilingan belgilar GF(2m) yakuniy maydonning ikkilamchi belgilari bilan emas, balki, (kuchlanishga mos keluvchi) amaldagi sonlar bilan birmuncha tabiiyroq kvantlanishini bildiradi.
“Engil” echimli qaror uchun Viterbi algoritmi “Qattiq” echimli qaror uchun bo‘lgan algoritmdan farq qilmaydi, faqatgina masofalar Xemming bo‘yicha emas, balki evklid masofasi bo‘yicha hisoblanishi bundan istisno. Ishlarda ko‘rsatilishicha, “Engil” echimli qarordan foydalanish signal 8-16 darajalarda kvantlanganda optimal hisoblanadi.
Maksimum ishonchlilik asosida kodni ochish kodlash nazariyasida birmuncha muhim va murakkab algoritmik muammo hisoblanadi. Ma’lumki, aloqaning ikkilamchi simmetrik kanali va erkin chiziqli kodlar uchun bu muammo NP-to‘liq hisoblanadi. Bundan tashqari, u kodning uzoq qayta ishlanish vaqtida ham shundayligicha qoladi.
Binobarin, mazkur masalani hal etish uchun bugungi kunda ko‘plab umumiy nazariyalar o‘rganilgan va ishlab chiqilgan. Bu barcha algoritmlar kod uzunligiga eksponensial ravishda qotib qolish kabi murakkabliklarga ega. Bundan tashqari ular o‘rtacha uzunlikdagi (blokda 200 belgigacha) kodlarni bog‘lashda oddiy qo‘llanilishi bilan yaroqli hisoblanadi.
Ular jumlasiga, masalan, axborot jamlanmalari deb nomlanuvchi kod ochish algoritmlari kiradi. Masalani hal etuvchi boshqa bir misol, Levitin va Xartman tomonidan taklif etilgan “nol qo‘shnisi” (ingl. zeroneighbors) algoritmi nomini olgan ML-kod ochish hisoblanadi. Ta’kidlangan oilalarga mansub ML-kod ochish algoritmi o‘rganilgan ishda minimal so‘zlar uslubi hisoblanadi.