Изменения

Энтропия||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>n</tex> {{---}} размер алфавита,*<tex>f_i</tex> {{---}} частота встречаемости символа,*<tex>p_i = \dfrac{f i}{l}</tex> {{---}} вероятность вхождения символа,*<tex>H(p_1 \ldots p_n) = </tex> {{---\sum\limits_{i=1}^n p_i} энтропия случайного источника с частотами <tex>(p_1 \cdot \log_2 p_ildots 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>H(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_i</tex>. Следовательно, <tex>A(s) \leq l \cdot H(p_1 \ldots p_n)</tex>.