1-Laboratoriya ishi Diskret xabar manbalari xarakteristikalarini tadqiq qilish. Ishdan maqsad

Endi entropiya xossalarini ko’rib chiqamiz.

1. 
   Har qanday habar manbaining entropiyasi musbat kattalik H (A) > 0 , chunki 0≤ p(a_k) ≤ 1, log p(a_k) ≤0, - p(a_k) log p(a_k) ≥0 . Agar manba faqat bitta habarni p(a_k)=1 ehtimollik bilan chiqarsa va qolganlari chiqish ehtimolligi nolga teng bo’lsa, u holda H(A) =0 bo’ladi.
   
2. 
   Agar xotirasiz xabar manbai chiqishida turli N-diskret xabarlar bir xil ehtimollik bilan paydo bo’lsa, u xolda bunday manba entropiyasi o’zining eng katta (maksimal) qiymatiga ega bo’ladi, ya'ni
   

(2)
Xususiy holda, agar xabar manbai faqat 2 ta xabar “ 1” va “0”ni chiqarsa, entropiya eng katta (maksimal) qiymati 1 bitga teng bo’ladi, ya'ni p(0)=P(1)=0,5.
Ushbu manba ikki xil diskret xabar ishlab chiqishidagi entropiyani aniqlaymiz. Bunda p(0)=P, p(1)=1-P deb belgilaymiz, u holda
(3)
(3) ifodadan ko’rinadiki p(0)=0 va p(1)=1 bo’lganda yoki p(0)=1 va p(1)=0 bo’lganda, entropiya H(A)=0 bo’ladi. Agar p(0)=p(1)=0,5 bo’lsa, entropiya o’zining eng katta (maksimal) qiymatiga erishadi, ya'ni
(4)
Ushbu xabar manbai entropiyasining p(0)=1-p(1) ga bog’liqligi 1 -rasmda keltirilgan.

1-rasm. Xotirasiz ikkilik xabar manbai entropiyasi.
Diskret axborot manbasining asosiy xarakteristikalari quyidagilardir:
- alifbo hajmi - m_a
– jo’natilayotgan xabarlarning turli belgilarining paydo bo'lishining apriori (eksperimentdan oldingi) ehtimoli – p (a_i ) ;
- bitta ixtiyoriy o'rtacha ma'lumot miqdori uchun manba belgisi – entropiya H (A) .
Shennona-Fano kodlovchi algoritmini axborot manbasidan kelgan xabarni teng bo'lmagan, mustaqil belgilar bilan kodlash misolida ko'rib chiqamiz. Manba alifbosi doirasi ma=8; yuzaga kelish ehtimoli belgilar quyidagicha: p(a1) = 0.12; p(a2) = 0.06; p(a3) = 0.21; p(a4) = 0.04; p(a5) =
0.32; p(a6) = 0.16; p(a7) = 0.01; p(a1) = 0.08.
Shennona-Fano kodlash algoritmi bir necha bosqichlarni o'z ichiga oladi:

1. 
   Habar manbasining barcha alifbo belgilari tartibda yoziladi ularning yuzaga kelish ehtimolining kamayishi (1.1-jadval) berilgan.
   
2. 
   Natijada tartiblangan ketma-ketlik belgilarning paydo bo'lish ehtimoli yig'indisi bo'lishi uchun ikki guruhga bo'linadi guruhlar taxminan bir xil bo’ladi.
   
3. 
   Birinchi guruhning elementlari birinchi belgi sifatida belgilanadi kod birikmasi "0", ikkinchi guruh elementlari - "1".
   
4. 
   Guruhlarning har biriga kiritilgan elementlar yana ikkiga bo'linadi taxminan bir xil ehtimollikdagi kichik guruhlarga. Birinchi kichik guruh sifatida kod kombinatsiyasining ikkinchi belgisi "0", ikkinchisi - "1" bilan belgilanadi.
   
5. 
   Bu jarayon har bir kichik guruhga ega bo'lgunga qadar davom etadi bir vaqtning o'zida bitta belgi ishlaydi.
   

Ushbu usul bo'yicha kodlashda kod birikmasining o'rtacha uzunligi
minimalga yaqin bo'lib, "0" va "1" ning paydo bo'lish ehtimoli mos keladi. Shu sababli, manbaning entropiyasi oshadi va maksimalga intiladi.
Shennona-Fano kodining muhim xususiyati uning qaytarilmasligidir.
Qaytarilmaslik qisqaroq kodning yo'qligidadir kombinatsiyada esa uzunroq kodning tarkibiy qismi emas.

1-jadval.

Masalan, 0110100011011100 xabarini qabul qilishda shifrni ochish
uchun quyidagicha amalga oshiriladi: a3 a1 a5 a3 a1 a2 (1-rasm).

1-rasm. Qabul qilingan xabarni dekodlash.
Algoritm yordamida taxminan bir xil natijaga erishish mumkin Haffmen tomonidan taklif qilingan. Xabarni Haffmen kodi bilan kodlashni kod daraxtini yaratish orqali amalga oshiriladi:

1. 
   Daraxtning ildizida alifbo belgilari kamayish tartibida joylashtirilgan bo’lib ehtimollar chapdan o'ngga qarab topiladi.
   
2. 
   Olingan tartiblangan qatordan eng past ehtimolga ega ikkita belgi tanlanadi va segmentlar (tarmoqlar) orqali bir-biriga bog'lanadi. Yuqorida ehtimollar yig'indisi yoziladi.
   
3. 
   Qolgan belgilar va oldingi bosqichda olingan summadan eng kichik qiymatlarga ega bo'lgan juftlik tanlanadi, u yana segmentlar bilan bog'lanadi, ularning birlashmasida yig'indisi qayd etiladi. Shuning uchun daraxtning "tepasi" ga yetguncha 11 ga qadar davom etadi. Eng yuqoridagi ehtimollar yig'indisi birga teng bo'lishi kerak.
   
4. 
   Kod kombinatsiyasini olish uchun siz daraxtning tepasidan borishingiz kerak uning shoxlari bo'ylab alifboning tegishli belgisiga ya’ni belgilangan yo'li bo’ylab o'tayotganda agar harakat o'ngdan chapga sodir bo'lsa, har bir birikmasidagi kod qabul qilinadi "1" va chapdan o'ngga bo’lsa "0" yoziladi.2-rasm
   

2-rasm. Haffmen kodlashi.