Belgilar
|
Paydo bo„lish chastotasi
| | | |
Yordamchi jadval
| | | |
B
|
5
|
5
|
5
|
6
|
8
|
10
|
14
|
24
| |
D
|
5
|
5
|
5
|
5
|
6
|
8
|
10
|
| |
A
|
3
|
4
|
4
|
5
|
5
|
6
|
|
| |
E
|
3
|
3
|
4
|
4
|
5
|
|
|
| |
C
|
2
|
3
|
3
|
4
|
|
|
|
| |
F
|
2
|
2
|
3
|
|
|
|
|
| |
G
|
2
|
2
|
|
|
|
|
|
| |
H
|
2
|
|
|
|
|
|
|
|
1 2 0
1
1 1 5 B
1 0 0
8 6 0 5
0 D
1 1 3
4 1 3 Е A
0
4 0
1
2 2 C
2 2 F
H G
Belgilar
|
B
|
D
|
A
|
E
|
C
|
F
|
G
|
H
|
kodi
|
01
|
00
|
100
|
101
|
1101
|
1100
|
1111
|
1110
|
Kodlashtirilgan axborotdagi har bir belgiga mos kelgan kodli kombinatsiyaning o‗rtacha uzunligini hisoblaymiz:
no'rtacha ni P(x) 2,92
bitga teng.
Yuqoridagi ko‗rib chiqilgan 1 va 2 misollarda kodlashtirilayotgan axborot qo‗yidagicha, ya‘ni BBCBBBCDDEDAAADDFFGGHHEE.
Biroq, hisoblash natijalariga ko‗ra, kodlashtirilgan axborotdagi har bir belgiga mos kelgan kodli kombinatsiyaning o‗rtacha uzunligi Shennon
- Fano usuli uchun n o‗rtacha =2,96 bitga, Xaffman usuli uchun esa n o‗rtacha
=2,92 bitga teng chiqdi.
Bundan xulosa qilinadiki, yuqoridagi axborotni Xaffan usuli bilan kodlashtirilsa maqsadga muvofiq bo‗ladi, chunki ushbu algoritm bilan axborot kodlashtirilganda axborotdagi har bir belgiga mos keluvchi kodli kombinatsiyaning o‗rtacha uzunligi kichkina, ya‘ni axborotni uzatish uchun kam bit sarflanadi. Bu esa o‗z navbatida axborotni uzatish tezligini oshirishga olib keladi.
misol: Quyidagi ko‗rinishda axborot berilgan bo‗lsin:
Simvol
|
A
|
B
|
V
|
G
|
D
|
Chastota
|
15
|
7
|
6
|
6
|
5
|
Bu misolni yechish uchun daraxtsimon usulni qurishdan foydalanamiz:
39
Bu berilgan usul uchun Xaffman kodi jadvali quyidagi ko‗rinishda bo‗ladi:
Simvol
|
A
|
B
|
V
|
G
|
D
|
Kod
|
0
|
100
|
101
|
110
|
111
|
Teng ehtimolli bo„lgan belgili xabarni samarali kodlash. Samarali kodlash shovqinsiz kanallarda va xalaqitlar yo‗q kanallarda yoki ulardan himoyalanish mumkin bo‗lgan kanallarda ishlatiladi. Bunday kanallarda kodlashning asosiy vazifasi uzatish kanalining o‗tkazuvchanlik qobiliyatiga yaqin holda, xabarni maksimal tezlikda uzatishdir.
Agar, hamma kodlanayotgan xabarning alfavit belgilari mustaqil va ularning kelib chiqishi bir xil bo‗lsa samarali optimal kodni qurish qiyinchilik tug‗dirmaydi. Xaqiqatan, H(x)ni olaylik – yuborilayotgan xabarning entropiyasi. Xabarning belgilari (xi) teng ehtimolli va dastlabki xabar manbaining alfavit hajmi m ga teng deb faraz qilaylik. Binobarin,
har qanday i belgisini xabarda paydo bo‗lish ehtimoli (P(xi)) bir xil bo‗ladi, ya‘ni:
P(x ) = 1 , i=1,.., m,
i m
Xabarning entropiyasi esa (N(x)) ga teng:
m
H (x) P(x) log 2 P(x) log 2 m
i1
Agar kodlash uchun k (kodli belgilarning element alfavit xajmi k ga teng) asosi bo‗yicha sonli kod ishlatilayotgan bo‗lsa, u holda, kod belgi elementlari paydo bo‗lishi teng ehtimolli va o‗zaro mustaqil bo‗lganda kodli belgilar elementi entropiyasi (H1), mos ravishda aniqlanadi:
H1 = log2k .
Unda, samarali yagona kod uzunligi, ya‘ni, kodli belgidagi elementlar soni (lsamarali.) quyidagicha topilishi mumkin:
Hx log 2 m
log 2 k n ,
bu yerda m = k n.
lsamarali =
H
1
= =
log 2 k
log 2 k
Teng ehtimolli bo„lmagan belgili xabarni samarali kodlash. Agar kodlanayotgan xabarning belgilari teng ehtimolli bo‗lmasa, umumiy ko‗rinishda optimal samarali kodni olish qoidasi noma‘lum. Shu bilan birga, umumiy mulohazalardan uning qurilish prinsiplarini tasavvur qilish mumkin.
Ko‗rinib turibdiki, qachonki agar, aniq bir yo‗l yordamida xabar manbasining alfavit belgilari paydo bo‗lish ehtimolligining tengsiz taqsimlanishini kod belgisi elementlarining mustaqil paydo bo‗lish ehtimolligining teng ehtimolligiga o‗tkazilsa samarali kodlash optimal bo‗ladi.
Bunday holatda, bitta kod belgisi elementi boshiga to‗g‗ri keladigan o‗rta hisobdagi axborot maksimal bo‗ladi. Bu talabga javob bera oladigan kod turini aniqlash uchun, ―qiymat funksiyasini‖ (xabar belgilarini uzatish narxi) quyidagicha ko‗rib chiqish mumkin:
m
Q = P(xi ) Wi ,
i=1
bu yerda: P(xi) - i belgisini dastlabki kodlanayogan xabarda paydo bo‗lish ehtimoli;
m – alfavit xajmi;
Wi – kod so‗zning proportsional uzunlikdagi i belgini uzatish qiymati.
Samarali kod Q funksiyasini kamaytirishi kerak. Agar, kod belgisining barcha elementlarini uzatish qiymatlari bir xil bo‗lsa, kod belgisining qiymati kod belgisiga mos holda proportsional uzunlikda bo‗ladi. Shuning uchun, umumiy (dastlabki xabarning belgilari teng ehtimolli bo‗lmasa) kod notekis bo‗lishi kerak, shu sababli samarali kod qurilishi quyidagi prinsiplarga asoslanishi kerak:
kod belgisining uzunligi (ni) mos keladigan dastlabki kodlangan xabar belgisining paydo bo‗lish ehtimoliga (xi) teskari proportsional bo‗lishi kerak;
boshidagi uzun kod belgisi boshidagi kalta kod belgisi bilan mos kelmasligi kerak (ajratuvchi belgilarni ishlatmagan holda kod belgisini ajratish imkoniyati uchun);
uzun ketma-ketlikdagi kod belgisi elementlari mustaqil va teng ehtimolli bo‗lishi kerak.
Kanal bo‗yicha uzatiladigan xabarni samarali kodlash imkoniyatini
K. Shennon tomonidan isbotlangan. Shennonning birinchi teoremasi nomini olgan teorema yoki shovqinsiz kanallar uchun kodlash haqidagi Shennonning asosiy teoremasi ta‘minlaydi. Bu teoremada, agar xabar manbasini entropiyasi bo‗lsa H [bit/belgi], kanal o‗tkazuvchanlik qobiliyatiga C [bit/sek] (o‗tkazuvchanlik qobiliyati axborotni imkoni boricha maksimum tezlikda uzatishni xarakterlaydi) ega, demak har doim kanal bo‗yicha o‗rta tezlikda xabar belgilarini uzatishni ta‘minlaydigan kodlash imkonini topish mumkin:
Vo' rtacha
= C
H
[belgi/sek],
bu yerda: ε – asossiz kichiq miqdor.
Teskari aytganda, xabar belgilarini kanal bo‗yicha o‗rta tezlikda
Vo‗rtacha.> H uzatish imkonsiz, sababi:
V C
[belgi/sek].
Bu teorema ko‗p hollarda boshqacha ko‗rinishda keladi: xabarni har doim entropiyali xabarlar N manbaini alfavit xajmi k bilan kod belgisi elementlarining ketma-ketligida kodlash mumkin, shu sababli xabarning kodlanayotgan belgisi (lo‗rtacha) kod belgisinig o‗rtacha elementlar sonidan H/ log2 k, qiymatiga asossiz tarzda yaqin bo‗ladi, lekin undan kam emas.
Bu teoremani isbotini ko‗rmasdan turiboq, teng ehtimolli va mustaqil kelib tushadigan kod belgisi elementlarini ta‘minlaydigan eng yaxshi samarali kodlash ekanligini ko‗rish mumkin va shu sababli har bir o‗tkazilgan axborotning maksimal soni log2 k (bit/element) ga teng. Afsuski, teorema aniq bir samarali kodlash usulini ko‗rsatmayapti, u faqat har bir kod belgisi elementini tanlashda maksimum axborotni tashishi kerakligi aytilgan, sababi, barcha kod belgisi elementlari teng ehtimollik va mustaqil paydo bo‗lishlari kerak.
Keltirilgan prinsiplardan kelib chiqqan holda xabarning mustaqil belgilari va o‗zaro bog‗liqligi uchun samarali kodlashning qator algoritmlari ishlab chiqilgan. Ularning mohiyati shundaki, tez-tez uchraydigan minimal uzunlikdagi dastlabki xabarning va kodning belgilarini belgilash orqali o‗rtacha uzunlikdagi kod belgilarini qisqartiradi.
|
