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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «== Оценка длины кодового слова == {{Теорема |statement=При арифметическом кодировании длина ко…»)
 
 
Строка 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>.
 
Из алгоритма арифметического кодирования <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>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>.
 
}}
 
}}

Текущая версия на 01:39, 27 июня 2021

Оценка длины кодового слова

Теорема:
При арифметическом кодировании длина кодового слова не превышает энтропии Шеннона случайного источника с частотами, равными долям вхождения символа в строку, умноженной на длину строки.
Доказательство:
[math]\triangleright[/math]

Условные обозначения:

  • [math]A(s)[/math] — размер кодового слова [math]s[/math],
  • [math]L[/math] — длина последнего отрезка в арифметическом кодировании [math]s[/math],
  • [math]l[/math] — длина исходной строки [math]s[/math],
  • [math]A(s)[/math] — размер кодового слова [math]s[/math],
  • [math]n[/math] — размер алфавита,
  • [math]f_i[/math] — частота встречаемости символа,
  • [math]p_i = \dfrac{f i}{l}[/math] — вероятность вхождения символа,
  • [math]H(p_1 \ldots p_n)[/math] — энтропия случайного источника с частотами [math](p_1 \ldots p_n)[/math].


Пусть в результате арифметического кодирования мы получили число [math]\dfrac{x}{2^q}[/math], где [math]q[/math] — количество бит в кодовом слове, т.е. [math]q = A(s)[/math].

Из алгоритма арифметического кодирования [math] L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}[/math].

Тогда [math]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 [/math].

Энтропия источника вычисляется по следующей формуле [math]H(p_1 \ldots p_n) = -\sum\limits_{i=1}^n p_i\cdot \log_2 p_i[/math].

Следовательно, [math]A(s) \leq l \cdot H(p_1 \ldots p_n)[/math].
[math]\triangleleft[/math]