|
Texnologiyalari universiteti qarshi
|
| Sana | 23.05.2024 | | Hajmi | 2,01 Mb. | | #250730 |
Bog'liq AVK 2 A I UMIDJON
O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALAR VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI FILIALI TELEKOMMUNIKATSIYA TEXNOLOGIYALARI” FAKULTETI TELEKOMMUNIKATSIYA TEXNOLOGIYALARI YO’NALISHI 3-BOSQICH “TT”-13-21(S)-GURUH TALABASINING AXBOROT VA KODLASH NAZARIYASI FANIDAN TAYYORLAGAN
2-AMALIY ISHI
TOPSHIRDI: JABBOROV.U
QABUL QILDI: KUCHABOYEV.R
Qarshi-2024
2-amaliy mashg’ulot
Mavzu: Shennon-Fano, Xaffman, LZ77 va LZ78 lug’atli siqish algoritmlari, audio va video ma’lumotlarini siqish algoritmlari samaradorligini baholash
Samarali kodlarni qurishning SHennon-Fano algoritmi
1. O‘zaro statistik bog‘lanmagan xabarlar alfaviti xarflari uchun samarali kodlarni qurish usullari ilk bor amerika olimlari SHennon va Fano tomonidan taklif etilgan. Ularning usullari, jiddiy farqlanmaganligi tufayli, mos kod SHennon-Fano kodi nomini olgan.
SHennon-Fano algoritmiga binoan samarali kodni qurish quyidagicha amalga oshiriladi:
xabar alfavitining xariflari ehtimolliklarining pasayishi tartibida joylashtiriladi;
barcha kodlanuvchi xabar xarflari ikkita guruhga shunday ajratiladiki, ikkala guruhdagi xarflar ehtimolliklarining yig‘indilari iloji boricha teng bo‘lsin. Agar tenglikka erishib bo‘lmasa, yig‘indi orasidagi tafovut minimal bo‘lsin;
Yuqori guruhga “0” simvoli, pastki guruhga “1” simvoli beriladi;
Hosil bo‘lgan qismguruhlar o‘z navbatida ikki qismga shunday ajratiladiki, yangida hosil bo‘lgan qismguruhlardagi xarflar extimolliklarining yig‘indilari iloji borpicha teng bo‘lsin va h.;
Jarayon har bir qismguruhda bitta xarf qolguncha takrorlanadi.
Ushbu (yoki shunga o‘xshash) algoritm bo‘yicha qurilgan xarflari notekis taqsimlangan va kod so‘zining minimal o‘rtacha uzunligiga ega kodlar samarali notekis kodlar deb ataladi.
Bunday kodlar quyidagi shartni qanoatlantirsa maksimal samarali hisoblanadi. Nўрт.=H,
Ikkili kodlar uchun
2. Alfavitdagi xarflarning paydo bo‘lish ehtimolliklari:
А1=0,25;
|
А2=0,25;
|
А3=0,125;
|
А4=0,125;
|
А5=0,0625;
|
А6=0,0625;
|
А7=0,0625;
|
А8=0,0625
|
bo‘lgan xabarning samarali notekis kodi qurilsin.
Yechish. Kod qurilishining tatijasi quyidagi jadvalda aks ettirilgan.
Xarflar
|
Extimol-liklar
|
Xarflarni guruhlarga
ketma-ket ajratish
|
Kod so‘zlar
|
Pi(Ai)▪n
|
1
|
2
|
3
|
4
|
|
|
А1
|
0,25
|
|
|
|
|
00
|
0,5
|
А2
|
0,25
|
|
|
|
01
|
0,5
|
А3
|
0,125
|
|
|
|
|
100
|
0,375
|
А4
|
0,125
|
|
|
101
|
0,375
|
А5
|
0,0625
|
|
|
|
1100
|
0,25
|
А6
|
0,0625
|
|
1101
|
0,25
|
А7
|
0,0625
|
|
|
1110
|
0,25
|
А8
|
0,0625
|
|
1111
|
0,25
|
Shunday qilib, quyidagi kodlar hosil qilindi:
А1=00;
|
А2=01;
|
А3=100;
|
А4=101;
|
А5=1100;
|
А6=1101;
|
А7=1110;
|
А8=1111
|
Xarflar ehtimolliklari ikkining butun sonli manfiy darajasi bo‘lganligi sababli kodlashda ortiqchalik to‘laligicha bartaraf etiladi. Undan tashqari ushbu kodlar maksimal samarali notekis kodlardir. Bunga ishonch hosil qilish uchun entropiyani va kod kombinatsiyalarining o‘rtacha uzunligini hisoblaymiz.
Sakkizta simvollarni uzunligi o‘zgarmas kod orqali kodlashda uchta ikkili xona kerakligi hisobga olinsa, bitta simvolga o‘rtacha 0,25 ikkili xona tejalganligini ko‘rish mumkin.
Samarali kodlarni qurishning Xaffmen algoritmi
1. SHennon Fano usuli doimo bir ma’noli kod qurishga imkon bermaydi, chunki qismguruxlarga ajratishda extimolligi bo‘yicha yuqoridagi yoki pastki qismguruxni katta deb xisoblash mumkin. Bunday kamchlik Xaffmenusulida yo‘q.
Xaffmen algoritmi bo‘yicha samarali notekis kodni qurish quyidagicha amalga oshiriladi:
xabarlar alfavitining harflari asosiy ustunga ehtimolliklarining pasayishi tartibida joylashtiriladi;
ikkita oxirgi harf bitta yordamchi harfga birlashtirilib, unga yig‘indi ehtimollik yoziladi;
birlashtirishda ishtirok etmagan harflar ehtimolliklari hosil qilingan yig‘indi ehtimolligi bilan birga ehtimolliklarining pasayishi tartibida yordamchi ustunga yoziladi va ohirgi ikkitasi birlashtiriladi va h;
jarayon yig‘indi ehtimolligi 1 ga teng bo‘lgan yagona yordamchi harf hosil qilinmaguncha davom etadi.
2. Alfavitdagi harflarning paydo bo‘lish ehtimolliklari А1=0,25; А2=0,25; А3=0,125; А4=0,125; А5=0,0625; А6=0,0625; А7=0,0625; А8=0,0625 bo‘lgan xabarning samarali notekis kodi qurilsin.
Yechish. Kodlash jarayonini quyidagi jadval yordamida tushuntirish mumkin.
Harflar
|
Ehtimolliklar
|
Yordamchi ustunlar
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
А1
А2
А3
А4
А5
А6
А7
А8
|
0,25
0,25
0,125
0,125
0,0625
0,0625
0,0625
0,0625
|
0,25
0,25
0,125
0,125
0,125
0,0625
0,0625
|
0,25
0,25
0,125
0,125
0,125
0,125
|
0,25
0,25
0,25
0,125
0,125
|
0,25
0,25
0,25
0,25
|
0,5
0,25
0,25
|
0,5
0,5
|
1
|
Berilgan xabarga mos kod kombinatsiyasini aniqlash uchun xarfning jadval qatori va ustuni bo‘yicha o‘tish yo‘lini kuzatish zarur.
Ko‘zga tashlanuvchanlikni ta’minlash maqsadida kod daraxti quriladi. Ehtimolligi birga mos nuqtadan ikkita shox yo‘naltirilib, ehtimolligi katta shoxga “1” simvoli, ehtimolligi kichik shoxga “0” simvoli beriladi. Bunday ketma – ket shoxlash har bir harf ehtimolligiga yetguncha davom ettiriladi.
Kod daraxti bo‘yicha yuqoridan pastga qarab harakatlanib, har bir harf uchun unga mos kod kombinatsiyasini yozish mumkin.
А1
|
А2
|
А3
|
А4
|
А5
|
А6
|
А7
|
А8
|
00
|
01
|
100
|
101
|
1100
|
1101
|
1110
|
1111
|
Hosil qilingan kodlardan ko‘rinib turibdiki, ular SHennon-Fano usuli bo‘yicha shakllangan kodlarga mos. Demak, SHennon-Fano va Xaffmen usullari bil xil samaradorlikka ega.
|
| |
