Изменения

|statement=При арифметическом кодировании длина кодового слова не превышает энтропии исходного текстаШеннона случайного источника с частотами, равными долям вхождения символа в строку, умноженной на длину строки.

  ||proof=Введём следующие Условные обозначения: *<tex>A(s)</tex> {{---}} размер кодового слова <tex>s</tex>,*<tex>L</tex> {{---}} длина последнего отрезка в арифметическом кодировании <tex>s</tex>,*<tex>l</tex> {{---}} длина текстаисходной строки <tex>s</tex>,*<tex>A(s)</tex> {{---}} размер кодового слова <tex>s</tex>,

*<tex>p_i= \dfrac{f i}{l}</tex> {{---}} вероятность вхождения символа,*<tex>H(p_1 \ldots p_n)</tex> {{---}} энтропия случайного источника с частотами <tex>(p_1 \ldots p_n)</tex>.   Пусть в результате арифметического кодирования мы получили число <tex>\dfrac{x}{2^q}</tex>, где <tex>q</tex> {{---}} количество бит в кодовом слове, т.е. <tex>q = A(s)</tex>. Из алгоритма арифметического кодирования <tex> L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}</tex>. Тогда <tex>A(s) = q \leq -\log_2 L = -\log_2 \prod\limits_{i=1}^n p_{i}^{f_{i}} = -\sum\limits_{i=1}^n f_i\cdot \log_2 p_i = -l \cdot \sum\limits_{i=1}^n p_i\cdot \log_2 p_i </tex>.

Размер сообщения <tex>L</tex> можно найти Энтропия источника вычисляется по следующей формуле: <tex> L H(p_1 \ldots p_n) = -\prodsum\limits_{i=1}^l p_{fi} = n p_i\prodcdot \limits_{i=1}^n p_{i}^{f_{i}}log_2 p_i</tex>.

Число бит в закодированном тексте: Следовательно, <tex>A(s) \log_2 L = -\sum\limits_{i=1}^n f_i\cdot \log_2 p_i = -l \cdot \sum\limits_{i=1}^n p_i\cdot \log_2 p_i = -leq l \cdot H(p_1 \ldots p_n)</tex>.