Капелюшок Георгий Александрович в 22:39, 26 июня 2021

2021-06-26T22:39:50Z

Капелюшок Георгий Александрович: Новая страница: «== Оценка длины кодового слова == {{Теорема |statement=При арифметическом кодировании длина ко…»

2021-06-24T03:06:01Z

Новая страница: «== Оценка длины кодового слова == {{Теорема |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>.
}}

@@ Строка 17: / Строка 17: @@
-В результате арифметического кодирования мы получили число <tex>\dfrac{x}{2^q}</tex>, где <tex>q</tex> {{---}} количество бит в кодовом слове, т.е. <tex>q = A(s)</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>.
@@ Строка 25: / Строка 25: @@
 Энтропия источника вычисляется по следующей формуле <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>.
+Следовательно, <tex>A(s) \leq l \cdot H(p_1 \ldots p_n)</tex>.
 }}

Участник:Капелюшок Георгий Александрович - История изменений

Капелюшок Георгий Александрович в 22:39, 26 июня 2021

Капелюшок Георгий Александрович: Новая страница: «== Оценка длины кодового слова == {{Теорема |statement=При арифметическом кодировании длина ко…»