Ma'lumotlarni uzatish tizimlarini qurilish prinsiplari

Entropiyaning asosiy xossalari
O'ylab ko'ring, da nima sharoitlar entropiya qabul qiladi kamida va eng buyuk qiymatlar. Faraz qilaylik, ikkita x ₁ , x ₂ elementdan tashkil topgan X ikkilik xabari p (x ₁ ) va p yuzaga kelish ehtimoli bilan uzatilishi kerak. (x ₂ ).
₁ ) =1, p (x ₂ ) =0 bo'lgan holatni ko'rib chiqaylik .

H ( X )   p ( x ₁ ) log p ( x ₁ )  p ( x ₂ ) log p ( x ₂ ) 

^{ } lim
p ( x2 _{_} )  0
p ( x ₂ ) log p ( x ₂ ) 

^ lim
jurnal
bitta


p ( x2 ) _{_
 lim} jurnal  _{_}

p ( x
)  0 ¹
  ^

2
p ( x2 ) _{_}

¹ log e

1
^ lim ^
 

 0.

Bu yerda  =1/p(x ₂ ) belgisi kiritiladi va noaniqlik Lapital qoidasiga muvofiq ochiladi. Agar elementlardan birining paydo bo'lish ehtimoli 1 ga teng bo'lsa, entropiya minimal va 0 ga teng.

2

₁ ) = p (x ₂ ) = 0,5 bo'lgan holatni ko'rib chiqing .
H ( X  _  _{ 0,5} funt 0,5 _  1 bit
i = 1
Entropiya maksimal va 1 ga teng.

Ikkilik belgilar uchun H _max = 1bit/dv.symbol.

Olingan natijalar n - elementlarning x ₁ , x ₂ ,..., x _n-1 , x _{n ning X xabariga umumlashtiriladi} . p(x _i ) = 1, p(x _j ) = 0, i  j uchun H _min (X) =0 .
n

Hmax _{_} ( X )   _ p ( x _i ) jurnal p ( x _i )
i = 1
p(x ₁ )= uchun p(x ₂ )= =p(x _n-1 )= p ( _xn ).
 log n ,

Shuning uchun optimal kodlash uchun elementlarning paydo bo'lish ehtimolini tenglashtirish kerak.

3-ma'ruza

O'rtasida statistik aloqalar mavjudligida diskret xabarlarning entropiyasi
elementlar

Elementlar orasidagi statistik munosabatlar, agar x i elementining paydo bo'lish ehtimoli undan oldin qaysi element x i-1 bo'lganiga bog'liq bo'lsa, _{sodir bo'ladi} .

Statistik bog'lanishlar qo'shni elementlarning juftlarini (bu holda ular oddiygina bog'langan Markov zanjiri), qo'shni elementlarning uchliklarini (ikki marta bog'langan Markov zanjiri), ..., n + 1 - qo'shni elementlarni (n - bog'langan Markov zanjiri, n) qamrab olishi mumkin.
 ).
Barcha haqiqiy xabarlar n - bog'langan Markov zanjirlari. Elementlarning X xabarini ko'rib chiqing x ₁ , x ₂ , , x _n ifodalaydi o'zingiz
oddiygina bog'langan Markov zanjiri, ya'ni. qo'shni elementlarning juftlari statistik munosabatda bo'ladi.
Belgilang p(x _i /x _{j ) - x i} elementning paydo bo'lish ehtimoli , agar undan oldin x _{j elementi} (j=i-1) bo'lsa. X ₁ \u003d 1 yoki 0, x ₂ \u003d 0 yoki 1 bo'lsin, keyin quyidagi holatlar mumkin
p(0/0) p(0/1)
p(1/0) p(1/1) .
Entropiya H ^* (x _i ) = log 1/( p(x _i /x _j )). Barcha x _i ni o'rtacha hisoblab, p(x _i /x _j ) va x _j ni hisobga olgan holda, p( x _{j ni hisobga olgan holda} , biz oddiy bog'langan Markov zanjiri entropiyasining o'rtacha qiymatini olamiz:
n n
H ^ ( X )  _ p ( x / x ) p ( x ) H ^ ( x ) 

i = 1
n n


j  1
i j j i

. (*)

 _-  p ( x _i / x _j ) p ( x _j ) log p ( x _i / x _j )
i  1 j  1
Ikki cheklovchi holat uchun (*) ifodasini ko'rib chiqing. x _i va x _j bir-biriga bog'liq emas, ya'ni. p(x _i /x _j ) = p(x _i ) va

i
H ^ ( X )   _ p ( x
i = 1
n
) log p ( x



_i ) _ p ( x _j ) 
j  1

 H ( X ), t . ga . _ p ( x _j )  1.
j  1
_i va x _j elementlari o'rtasida to'liq funktsional bog'liqlik mavjud , ya'ni. p(x _i /x _j ) = 0 yoki 1 va keyin H ^* (X) = 0.
Shunday qilib, 0  H ^* (X)  H(X). (**)
Binobarin, xabar elementlari o'rtasida statistik bog'lanishlarning mavjudligi entropiyani kamaytiradi va ko'proq darajada statistik bog'lanishlar bilan qoplangan qo'shni elementlarning soni shunchalik ko'p bo'ladi.
Rus tilidagi xabarning misolini ko'rib chiqing. Agar biz e va e , b va b ni ajratmasak va bo'sh joy kerakligini hisobga olsak, bizda 32 ta belgi mavjud. Maksimal entropiya qancha? Belgilarning teng ehtimoli va mustaqilligi shartida, har bir belgi uchun o'rtacha entropiya maksimal va teng bo'ladi.
H _max \u003d lb 32 \u003d 5 bit / belgi.

Rus tilidagi so'zlardagi belgilarning paydo bo'lishi bir xil darajada emas. Agar belgilarning turli xil ehtimolini hisobga olsak, u holda
H ₁ = 4,39 bit/belgi.
Ikki belgi o'rtasidagi statistik munosabatni hisobga olgan holda, entropiya qiymatga kamayadi
H ₂ \u003d 3,52 bit / belgi (yakka bog'langan Markov zanjiri), uchta belgi orasida - qiymatgacha
H ₃ \u003d 3,05 bit / belgi (ikki marta bog'langan Markov zanjiri),
......................
sakkizta belgi orasida - qiymatgacha
H ₈ = 2 bit / belgi (etti bog'langan Markov zanjiri) va keyin o'zgarishsiz qoladi.
Xulosa:
Xabarlarni samarali kodlash uchun entropiyani oshirish kerak
tekshiring:
Belgilarning paydo bo'lish ehtimolini tekislash. Elementlar orasidagi statistik munosabatlarni yo'q qilish. Xabarning ortiqchaligi
Agar xabardagi elementlar bir xil ehtimolga ega bo'lsa va bir-biriga bog'liq bo'lmasa, bunday xabarni optimal tarzda kodlash mumkin. Bunday xabarni yuborish uchun siz n _opt elementini yuborishingiz kerak. Agar xabar optimal tarzda kodlanmagan bo'lsa, uni uzatish uchun n  n _opt belgilar talab qilinadi . Bunday holda, ortiqchalik paydo bo'ladi, uning raqamli xarakteristikasi ortiqcha koeffitsientdir:
k _va = (H _max (X) - H (X))/ H _max (X), bu erda
H _max (X) - optimal kodlash uchun entropiya; H (X) - optimal bo'lmagan kodlash uchun entropiya.
Shunday qilib, 0  k _va  1. Rus tili uchun k _va = (5 - 2)/5 =0,6.