Axborot va kodlash nazariyasi asoslari

Halaqitga qarshi kodlarni ochish. 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 demodulyatsiya 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.

“Yengil” yechimli 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, 4 birliklari vositasida kodlanadi. Bunday holatda maksimal ishonchlilik tamoyili asosida kodni ochish uchun odatiy yevklid masofasidan foydalaniladi.

“Yengil” yechimli qaror. 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.

“Yengil” yechimli qaror uchun esa bunday nazariy baza deyarli mavjud emas. Boshqa tomondan olganda, “Yengil” yechimli 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. “Yengil” yechimli 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.

“Yengil” yechimli qaror uchun Viterbi algoritmi “Qattiq” yechimli qaror uchun bo‘lgan algoritmdan farq qilmaydi, faqatgina masofalar Xemming bo‘yicha emas, balki Yevklid masofasi bo‘yicha hisoblanishi bundan istisno.

Ishlarda ko‘rsatilishicha, “Yengil” yechimli 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.