Axborot va kodlash nazariyasi asoslari

misol: Quyidagi ko‘rinishda axborot berilgan:

BBCBBBCDDEDAAADDFFGGHHEE.

Ushbu axborotda umumiy belgilar soni 24 ta. Dastlab ushbu axborot uchun entropiya ko‘rsatkichining qiymatini hisoblaymiz.

N(x) = ∑ R(x) * Log ₂ R(x) = 2,89 bit ga teng bo‘ladi.

Ushbu algoritm bo‘yicha hisoblash natijalari jadvalda keltirilgan.

Shennon- Fano algoritmi bo‘yicha hisoblash natijalari.

Belgilar	Paydo bo‘lish chastotasi	Yordamchi jadval		Kodi
B	5	5(1) 5(1)	5(1)	11
D	5	3(1)	5(0) 3(0)	101
A	3	3(0)	3(1)	100
E	3	2(0)	2(1)	011
C	2	2(0)	2(0)	010
F	2	2(0)	2(0)		001
G	2	2 (0)	2(0)		0001
H	2				0000

Misol. Quyidagi ko’rinishda axborot bеrilgan:

ВВСВВВСDDEDAAADDFFGGHHEE ushbu axborotda umumiy bеlgilar soni 24 ta. Dastlab ushbu axborot uchun entropiya ko’rsatkichining qiymatini xisoblaymiz.

bitga tеng bo’ladi.
Ushbu algoritm bo’yicha xisoblash natijalari jadvalda kеltirilgan.

Shеnnon-Fano algoritmi bo’yicha xisoblash natijalari.

Kodlashtirilgan axborotdagi xar bir belgiga mos kelgan kodli kombinatsiyaning o‘rtacha uzunligi quyidagicha hisoblanadi:

n _o‘rt = ∑ n _i * R(x) = 2,96 bitga teng.
Hozirgi kunda eng keng tarqalgan, amaliyotda ko‘p ishlatiladigan entropiyali kodlash usuliga asoslangan algoritmlardan biri bu – Xaffmen algoritmi hisoblanadi.

Xaffmen algoritmi asosida matnli axborotlar kodlashtiriladi.

Ushbu algoritm yordamida axborotni kodlashtirish quyidagicha amalga oshiriladi:

• 
  axborotdagi barcha belgilar soni, ya’ni N hisoblanadi;
  
• 
  jami N ta belgidan iborat bo‘lgan axborotdagi har bir belgining paydo bo‘lish chastotasi hisoblanadi;
  
• 
  har bir belgining paydo bo‘lish chastotasi kamayib borish tartibida jadvalga joylashtiriladi;
  
• 
  jadvaldagi oxirgi ikkita chastota yig‘indisi hisoblanib, bitta umumiy bo‘lgan yig‘indi chastotaga birlashtiriladi;
  
• 
  hisoblangan yangi yig‘indi chastotadan va hisoblashda qatnashmagan boshqa chastotalardan jadvalning yangi ustuni hosil qilinadi (bunda ham chastotalar kamayib borish tartibida joylashtiriladi);
  
• 
  shu tarzda to bitta umumiy N ga teng bo‘lgan yig‘indi hosil bo‘lguncha jarayon davom etaveradi;
  
• 
  jadval to‘ldirilgandan so‘ng, undagi hisoblashlarga muvofiq daraxt quriladi;
  
• 
  daraxtning tepa qismida N joylashgan bo‘ladi va uni teng ikkiga bo‘lish kerak, hosil bo‘lgan natijalarni yana teng ikkiga bo‘lish lozim;
  
• 
  shu tarzda axborotdagi har bir belgining paydo bo‘lish chastotasi topilguncha, bo‘lish davom ettiriladi.