Samarali kodlash algoritmlarining kamchiliklari:
tashqi shovqinlarga ta‘sirchanligi – shovqin ta‘sirida bitta elementda sodir bo‗lgan xato bir kod kombinatsiyasini vaqt birligi bo‗yicha boshqa qiymatga ega ikkinchisiga o‗tib ketishiga sabab bo‗lishi mumkin;
bir kod simvoli boshqa vaqt birligidagi simvolga aylanishi mumkin, buning oqibatida joriy, keyingi simvollar noto‗g‗ri dekodlanadi va birlamchi ma‘lumot boshqa ma‘lumotga o‗zgarib ketadi;
keyingi kamchilik bu texnik jihatdan ularni yaratish murakkabligi hisoblanadi: qurilma bufer va simvollarni yig‗ish uskunalariga ega bo‗lishi kerak. Chunki, aloqa kanallari bir xil uzunlikdagi kod kombinatsiyalarini uzatishda samarali ishlaydi, yuqoridagi algoritmlardagi kod kombinatsiyalarining uzunligi har xil, ularni yig‗ib bir tugallangan ma‘lumot shakliga keltirish uchun oldin qabul qilingan simvollarni saqlash kerak bo‗ladi.
Amaliy, bir o‗tishli, kodlar jadvallarini uzatilishini talab qilmaydigan algoritm hisoblanadi. Uning ma‘nosi adaptiv algoritmdan foydalanishdan iborat, ya‘ni simvolni kodga har bir taqqoslashda, bundan tashqari, hisoblashlarning ichki borishi shunday o‗zgartiriladiki, keyingi marta bu simvolga boshqa kod taqqoslanishi mumkin, ya‘ni algoritmni kodlash
uchun keladigan simvollarga moslashishi bo‗lib o‗tadi. Dekodlashda esa o‗xshash jarayon bo‗lib o‗tadi.
Algoritm ishlashining boshlanishida kodlash daraxti doimo 0 chastotaga ega bo‗ladigan bitta maxsus simvolga ega bo‗ladi. U daraxtga yangi simvollarni kiritilishi uchun zarur bo‗ladi. Undan keyin simvolning kodi to‗g‗ridan to‗g‗ri uzatiladi. Bunday simvol escape-simvol (ESC) deyiladi. Kengaytirilgan ASCII har bir simvolni 8-bitli son, ya‘ni 0 dan
255 gacha son bilan kodlaydi. Kodlash daraxtini qurishda to‗g‗ri dekodlash uchun daraxtning tuzilmasini qandaydir tartiblashtirish zarur bo‗ladi. Daraxtning barglarini chastotalarning ortishi tartibida va keyin simvollarning standart kodlarning ortishi tartibida joylashtiramiz. Tugunlar chapdan o‗ngga tashlamasdan yig‗iladi. Chapdagi tarmoqlar 0 bilan, o‗ngdagi tarmoqlar 1 bilan belgilanadi.
Xaffman adaptiv bo‗lmagan kodini qurishga misolda X diskret tasodifiy qiymat (DTQ) 10-talik qiymatlarni tanlashga mos keladigan ACCBCAAABC xabar uchun Xaffman adaptiv algoritmi bo‗yicha kodlarni qurish jarayonini ko‗rib chiqamiz:
|
Kirish
ma‘lumotlari
|
Kod
|
Kod uzunligi
|
Daraxt №
| |
A
|
‗A‘
|
8
|
1
| |
S
|
0‘S‘
|
9
|
2
| |
S
|
1
|
1
|
3
| |
V
|
00‘V‘
|
10
|
4
| |
S
|
1
|
1
|
5
| |
A
|
001
|
3
|
6
| |
A
|
01
|
2
|
7
| |
A
|
01
|
2
|
8
| |
V
|
001
|
3
|
9
| |
S
|
01
|
2
|
|
Bu yerda Li (ACCBCAAABC) = 4.1 bit/simvol. Agar siqish ishlatilmasa, u holda Li (ACCBCAAABC) = 8 bit/simvol bo‗ladi. Ko‗rib chiqilayotgan DTQ uchun oldin MLi(X) = 1,6 bit/simvol va HX ≈ 1,523 bit/simvol qiymatlar olingan edi. Lekin xabarning uzunligi ortishi bilan xabar simvoliga o‗rtacha bitlar soni adaptiv kodlash algoritmida Xaffman yoki Shennon-Fano adaptiv bo‗lmagan usuli ishlatilganida olingan qiymatdan kam farqlanadi, chunki simvollar alifbosi cheklangan va har bir simvolning to‗liq kodini faqat bir marta uzatish kerak.
Endi ‘A‘0‘C‘100 ‘B‘1001010100101 xabarni dekodlash jarayonini ko‗rib chiqamiz. Bu yerda va keyinchalik ajratish belgisidagi simvol ASCII+ jadvalidagi ikkilik son, simvollar raqami hisoblanadigan sakkizta bitni bildiradi. Dekodlashning boshlanishida Xaffman daraxti faqat 0 chastotali escape-simvolga ega bo‗ladi. Har bir yangi simvol koddan chiqarilishi bilan daraxt yana qayta sozlanadi.
|
Kirish
ma‘lumotlari
|
Kod
|
Daraxt №
| |
‗A‘
|
A
|
1
| |
0‘S‘
|
S
|
2
| |
1
|
S
|
3
| |
00‘V‘
|
V
|
4
| |
1
|
S
|
5
| |
001
|
A
|
6
| |
01
|
A
|
7
| |
01
|
A
|
8
| |
001
|
V
|
9
| |
01
|
S
|
|
Algoritmning tanlangan moslashish usuli juda samarasiz, chunki har bir simvolga ishlov berilganidan keyin butun kodlash daraxtini qayta qurish kerak bo‗ladi. Butun daraxtni qayta qurish emas, balki faqat sezilarsiz o‗zgartirish kerak bo‗ladigan ancha kam mehnatli usullar mavjud.
Binar daraxt, agar uning tugunlari vaznning kamaymasligi tartibida sanab o‗tilgan va bu ro‗yhatda umumiy ota-onaga ega bo‗lgan bitta qavatda yonma-yon turishi mumkin bo‗lsa, tartiblashgan hisoblanadi. Binobarin, sanab o‗tish qavatlar bo‗ylab pastdan-yuqoriga va chapdan- o‗ngga har bir qavatda borishi kerak. 2.1-rasmda tartiblashtirilgan Xaffman daraxtiga misol keltirilgan.
2.1-rasm. Tartiblashtirilgan Xaffman daraxtiga misol
Agar kodlash daraxti tartiblashtirilgan bo‗lsa, u holda mavjud tugunning vaznini o‗zgartirishda daraxtni butunlay qayta qurish kerak emas, unda faqat ikkita tugunlar – vaznli tartiblashtirishni buzgan tugun va undan keyin keladigan tugunlardan kam vaznli oxirgi tugun joylarini almashtirish yetarli bo‗ladi. Tugunlar joylari o‗zgartirilganidan keyin ularning barcha avlodlar-tugunlarining vaznlarini qayta hisoblash zarur bo‗ladi.
Masalan, agar 2.1-rasmdagi daraxtga yana ikkita A harflari qo‗shilsa, u holda A va D tugunlar joylarini almashtirish kerak bo‗ladi (2.2-rasmga qarang).
2.2-rasm. Tartiblashtirilgan Xaffman daraxtiga 2-chi misol
Agar yana ikkita A harflari qo‗shilsa, u holda dastlab A tugun va D hamda B tugunlar uchun ota-onalar, keyin esa E tugun va E aka-tugun (2.3-rasm) joylarini almashtirish zarur bo‗ladi.
Daraxtni faqat unda yangi barg-tugun paydo bo‗lganida qayta sozlash kerak bo‗ladi. To‗liq qayta qurish o‗rniga (ESC) bargdan o‗ngda yangi barg qo‗shish va agar bunday tarzda olingan daraxt zarur bo‗lsa tartiblashtirish mumkin.
2.3-rasm. Tartiblashtirilgan Xaffman daraxtiga 3-chi misol
Tartiblashtirilgan daraxtli Xaffman adaptiv algoritmining ishlash jarayonini quyidagi sxema orqali tasvirlash mumkin:
|
Kirish
ma‘lumotlari
|
Kod
|
Kod
uzunligi
|
Daraxt
№
|
Qabul qilish
usuli
| |
A
|
‗A‘
|
8
|
1
|
Tugun qo‗shish
| |
S
|
0‘S‘
|
9
|
2
|
Tugun qo‗shish
| |
S
|
01
|
2
|
3
|
Tartibga solish
| |
V
|
00‘V‘
|
10
|
4
|
Tugun qo‗shish
| |
S
|
1
|
1
|
5
|
O‗zgarmaydi
| |
A
|
01
|
2
|
6
|
O‗zgarmaydi
| |
A
|
01
|
2
|
7
|
Tartibga solish
| |
A
|
11
|
2
|
8
|
Tartibga solish
| |
V
|
101
|
3
|
9
|
O‗zgarmaydi
| |
S
|
11
|
2
|
|
|
Bu yerda L1 (ACCBCAAABC) = 4.1 bit/simvol olinadi.
| 