7
правок
Изменения
Новая страница: «== Оценка длины кодового слова == {{Теорема |statement=При арифметическом кодировании длина ко…»
== Оценка длины кодового слова ==
{{Теорема
|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>n</tex> {{---}} размер алфавита,
*<tex>f_i</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>H(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_i</tex>.
Следовательно, <tex>A(s) = l \cdot H(p_1 \ldots p_n)</tex>.
}}
{{Теорема
|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>n</tex> {{---}} размер алфавита,
*<tex>f_i</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>H(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_i</tex>.
Следовательно, <tex>A(s) = l \cdot H(p_1 \ldots p_n)</tex>.
}}
