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

Материал из Викиконспекты
Перейти к: навигация, поиск

Оценка длины кодового слова[править]

Теорема:
При арифметическом кодировании длина кодового слова не превышает энтропии Шеннона случайного источника с частотами, равными долям вхождения символа в строку, умноженной на длину строки.
Доказательство:
[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]