24
III BOB. KODLASH VA DEKODLASH
3.1. Kodlar, kodlash va dekodlash
Informatsiyani kodlash zaruriyati kompyuterlar paydo bo‘lmasdan
anchagina oldin vujudga kelgan. Texnikada kodlashga ehtiyoj telegraf
paydo bo‘lishi bilan vujudga kelgan bo‘lsada, kompyuter ixtiro
qilinganidan so‘ng bunday ehtiyoj yanada ortdi.
Kodlash nazariyasining ta’sir sohasi real (yoki xalalli) kanallar
bo‘yicha ma’lumotlarni qamrab olsa, predmeti uzatilgan infor-
matsiyaning korrektligini ta’minlash hisoblanadi. Boshqacha aytganda,
kodlash nazariyasi signal uzatilganidan so‘ng ma’lumotlardan ishonchli
va osongina foydali informatsiyani ajratib olishga imkon beruvchi
ma’lumotlarni qanday joylashtirish lozimligini o‘rganadi. Ba’zida
kodlash nazariyasini shifrlash bilan almashtirishadi, ammo bu noto‘g‘ri.
Chunki kriptografiya teskari masalani yechadi. Uning maqsadi –
ma’lumotlardan informatsiyani ajratib olishni qiyinlashtirish.
Kodlash – xabarni berilgan kanal bo‘yicha uzatish uchun qulay
holga keltirish. Oddiy misol tariqasida xabarni telegramma ko‘rinishida
uzatishni ko‘rsatish mumkin. Bunda barcha simvollar telegraf kodida
kodlanadi.
Dekodlash – qabul qilingan xabarni tiklash amali. Aloqa
sistemasida kodlash va dekodlash uchun qurilmalar ko‘zda tutilishi
lozim (3.1-rasm).
3.1-rasm. Xalalli aloqa kanalining informatsion modeli
Bunday sistemalarni nazariy asoslash K.Shennon tomonidan
amalga oshirilgan. U qator teoremalar orqali kodlash va dekodlash
qurilmalarining kiritilishi lozimligini asosladi. Kodlash va dekodlash
qurilmalarining vazifalari informatsiya manbai xususiyatlarini aloqa
kanallari xususiyatlari bilan muvofiqlashtirishdir. Ularning biri (kodlash
qurilmasi yoki koder) shunday kodlashni amalga oshirishi lozimki,
natijada informatsiya ortiqchaligini bartaraf etish yo‘li bilan xabar
birligida simvollarning o‘rtacha soni jiddiy kamaysin.
Manba
Kodlash
qurilmasi
Kodlash
koderi
Aloqa
kanali
Kanal
dekoderi
Dekodlash
qurilmasi
Qabul
qiluvchi
25
Bu esa, o‘z navbatida xalallar yo‘qligida uzatishning vaqti yoki
xotira qurilmasining hajmi bo‘yicha yutuqqa ega bo‘lishga imkon
beradi. Bunday kodlash samarali deb ataladi, chunki u sistema
samaradorligini oshiradi. Uzatish kanalida xalallar mavjudligida bunday
kodlash kirish yo‘li informatsiyasini uning keyinchalik ishlanishi
masalasiga maqbul javob beruvchi ketma-ketlikka o‘zgartirishga imkon
beradi. Boshqa kodlash qurilmasi (kanal koderi) qo‘shimcha
informatsiya ortiqchaligini kiritish yo‘li bilan informatsiyani uzatishda
yoki saqlashda berilgan haqiqiylikni ta’minlaydi. Bunday kodlash
ortiqchali yoki xalallarga bardosh kodlash deb yuritiladi.
Kodlar va kodlash nazariyasining asosiy tushunchalari. Kodlar
maxfiy yozuv vositasi sifatida qadimdan ma’lum. Yunon tarixchisi
Gerodot eramizdan avval
𝑉 − asrda faqat adresatga tushunarli xatlarga
misol keltirgan. Maxfiy alfavit Yuliy Sezar tomonidan ishlatilgan. Turli
maxfiy shifrlarni yaratish ustida o‘rta asr olimlari F.Bekon, D.Kardano
va boshqalar ishlashgan. Juda antiqa shifrlar va kodlar paydo bo‘ldi.
Ammo vaqt o‘tishi bilan ular rasshifrovka qilindi va ularning maxfiyligi
yo‘qoldi.
Aloqa kanallari bo‘yicha xabarlarni uzatishga mo‘ljallangan
birinchi kod S.Morze kodi hisoblanadi. Bu kodda harf va sonlarni
kodlashga mo‘ljallangan simvollarning turli soni mavjud. Keyin
telegrafiyada ishlatiluvchi N.Bodo kodi paydo bo‘ldiki, unda har bir harf
va son simvollarning bir xil soniga ega. Simvollar sifatida berilgan onda
elektr zanjiridagi impulsning borligi yoki yo‘qligini ko‘rsatish mumkin.
Ikkita turli elementar signallarni ishlatuvchi kodlar ikkilik kodlar
deb ataladi. Ushbu signallarni 0 va 1 simvollari yordamida belgilash
qulay hisoblanadi. Unda kod so‘zi nollar va birlar ketma-ketligidan
iborat bo‘ladi. Informatsiyani kodlash masalasiga raqamli ma’lumotlarni
qandaydir o‘zgartirish sifatida qarash mumkin. Xususiy holda ushbu
amal simvollarni guruhlash (triadalar yoki tetradalar ko‘rinishida
ifodalash) yoki pozitsion sanoq sistemasidagi simvollar (raqamlar)
ko‘rinishida ifodalashga keltirilishi mumkin. Har qanday pozitsion
sistemada
ortiqcha
informatsiya
bo‘lmaganligi
va
barcha
kombinatsiyalari ruxsat etilganligi sababli, bunday sistemalardan
nazoratlashda foydalanish mumkin emas.
Sistematik kod – informatsion xonalaridan tashqari nazorat
xonalariga ega bo‘lgan kod. Nazorat xonalariga dastlabki son xususida
qandaydir informatsiya yoziladi. Shu sababli sistematik kod
ortiqchalikka ega. Bunday absolyut ortiqchalik nazorat xonalari soni
𝑚
26
orqali, nisbiy ortiqchalik esa
𝑚/𝑛 nisbat orqali ifodalanadi. Bu yerda
𝑛 = 𝑚 + 𝑘 – kod so‘zidagi xonalarning umumiy soni, 𝑘 – informatsion
xonalar soni.
Kodning tuzatish (korrektlash) qobiliyati tushunchasini odatda
xatolarni aniqlash va tuzatish imkoniyati bilan bog‘lashadi. Miqdoran
kodning tuzatish qobiliyati xatolikni aniqlash va tuzatish ehtimolligi
orqali aniqlanadi. Ta’kidlash lozimki, asosiy e’tiborni yakka xatoliklarni
aniqlash va tuzatishga qaratilishi lozimligi isbot qilingan. Kodning
tuzatish qobiliyati kod masofasi tushunchasi bilan ham bog‘liq.
Kod kombinatsiyasining salmog‘i
𝑉(𝐴) – kod kombinatsiyasidagi
birlar soni.
𝐴 va 𝐵 kod kombinatsiyalari uchun kod masofasi
𝑑(𝐴, 𝐵) dastlabki kombinatsiyalarni 2ning moduli asosida xonalar
bo‘yicha jamlash orqali aniqlanuvchi uchinchi kombinatsiyaning
salmog‘i sifatida aniqlanadi. Ushbu masofa ba’zida Xemming masofasi
deb ham yuritiladi.
Misol:
𝐴 = 011011100 va 𝐵 = 100111001 kombinatsiyalari uchun
salmoq va kod masofasi aniqlansin.
Yechish:
𝑉(𝐴) = 5; 𝑉(𝐵) = 5.
Uchinchi kod kombinatsiyasi
𝐶 = 𝐴 ⊕ 𝐵 = 111100101.
Demak
𝑑(𝐴, 𝐵) = 6.
Kodlarni qandaydir geometrik shakllar sifatida ko‘rish mumkin.
Masalan, triadani ikkilik simvollarga mos keluvchi koordinata o‘qlariga
ega bo‘lgan quyidagi birlik kub ko‘rinishida ifodalash mumkin.
3.1-rasm. Triadaning ikkili simvollarga mos keluvchi koordinata
o‘qlariga ega bo‘lgan birlik kub ko‘rinishi
Bunda kod masofasi kubning mos uchlari orasidagi yoylar uzunligi
yig‘indisi orqali aniqlanadi (bitta yoy uzunligi 1 ga teng deb qabul
qilingan). Ma’lum bo‘lishicha, har qanday pozitsion sistemada minimal
001
011
111
100
101
110
010
000
27
kod masofasi 1 ga teng.
Kodlash nazariyasiga muvofiq sistematik kod xatoliklarni faqat
undagi minimal kod masofasi
2𝑡 dan katta yoki unga teng bo‘lgandagina
aniqlash imkoniyatiga ega, ya’ni:
𝑑
𝑚𝑖𝑛
≥ 2𝑡,
bu yerda
𝑡 – aniqlanuvchi xatolikning karraligi (yakka xatoliklar
holida
𝑡 = 1 va h). Demak, qo‘shni ruxsat etilgan kod so‘zlari orasida
bo‘lmaganida bitta kod so‘zi mavjud.
Nafaqat xatoliklarni aniqlash balki uni tuzatish (ya’ni xatolik joyini
ko‘rsatish) zaruriyati hollarida minimal kod oralig‘i
𝑑
𝑚𝑖𝑛
≥ 2𝑡 + 1 ga
teng bo‘lishi lozim.
|