Telekommunikatsiya texnologiyalari

tải về 1.75 Mb.

Chuyển đổi dữ liệu	13.04.2024
Kích	1.75 Mb.
	#57184

2-amaliy mashg\'ulot axborot

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 Xaffmen algoritmi

O’ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALARI VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI QARSHI FILIALI
“TELEKOMMUNIKATSIYA TEXNOLOGIYALARI” FAKULTETI
TT 14-21s guruh 3-bosqich talabasining
“Axborot va kodlash nazariyasi” fanidan tayyorlagan
Amaliy mashg’ulot-2

Bajardi: Turobova Sh

Qabul qildi: KUCHABOYEV R. T.

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:

А₁=0,25;	А₂=0,25;	А₃=0,125;	А₄=0,125;
А₅=0,0625;	А₆=0,0625;	А₇=0,0625;	А₈=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	P_i(A_i)▪n
Xarflar	Extimol-liklar	1	2	3	4
А₁	0,25					00	0,5
А₂	0,25					01	0,5
А₃	0,125					100	0,375
А₄	0,125					101	0,375
А₅	0,0625					1100	0,25
А₆	0,0625					1101	0,25
А₇	0,0625					1110	0,25
А₈	0,0625					1111	0,25

Shunday qilib, quyidagi kodlar hosil qilindi:

А₁=00;	А₂=01;	А₃=100;	А₄=101;
А₅=1100;	А₆=1101;	А₇=1110;	А₈=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 А₁=0,25; А₂=0,25; А₃=0,125; А₄=0,125; А₅=0,0625; А₆=0,0625; А₇=0,0625; А₈=0,0625 bo‘lgan xabarning samarali notekis kodi qurilsin.
Yechish. Kodlash jarayonini quyidagi jadval yordamida tushuntirish mumkin.

Harflar	Ehtimolliklar	Yordamchi ustunlar
Harflar	Ehtimolliklar	1	2	3	4	5	6	7
А₁ А₂ А₃ А₄ А₅ А₆ А₇ А₈	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.

tải về 1.75 Mb.

Chia sẻ với bạn bè của bạn: