55
правок
Изменения
→Адаптивное арифметическое кодирование
</tex>
}}
{{Следствие
|id = th1.
|statement=При адаптивном арифметическом кодировании строки длины <tex>l</tex>, символы которой принадлежат алфавиту мощности <tex>n</tex>, количество бит, необходимых для кодирования сообщения будет лежать в диапазоне <tex>[-\sum_{i=1}^{l} log_2{\dfrac{1}{n+i-1}}, -\sum_{i=0}^{l-1}log_2\dfrac{i+1}{n+i}]</tex>
|proof=
Произведём оценку количества бит, необходимых для записи кода $L$ в общем случае:
<tex>
log_2 L = -\sum_{i=1}^{l} log_2 \frac{w_{\alpha_i}}{n+i-1}
</tex>
Все коды лежат в диапазоне <tex>[0, 1)</tex>.
Таким образом:
Максимальное количество бит будет затрачено при записи кода, являющегося минимальной дробью:
<tex>
log_2 L_{min} = -\sum_{i=1}^{l} log_2 \frac{1}{n+i-1}
</tex>
Минимальное число бит будет затрачено в случае записи кода максимального размера:
<tex>
log_2 L_{max} = -\sum_{i=0}^{l-1} log_2 \frac{i+1}{n+i}
</tex>
}}
