2018-03-09
88
Идея арифметического кодирования была впервые предложена П. Элиасом. В арифметическом коде кодируемое сообщение разбивается на блоки постоянной длины, которые затем кодируются отдельно. При этом при увеличении длины блока средняя длина кодового слова стремится к энтропии, однако возрастает сложность реализации алгоритма и уменьшается скорость кодирования и декодирования. Таким образом, арифметическое кодирование позволяет получить произвольно малую избыточность при кодировании достаточно больших блоков входного сообщения.
Рассмотрим общую идею арифметического кодирования. Пусть дан источник, порождающий буквы из алфавита А ={ a 1 ,a 2 ,…, an } с вероятностями pi = P (ai), 
. Необходимо закодировать последовательность символов данного источника Х=х 1 х 2 х 3 х 4.
1. Вычислим кумулятивные вероятности Q 0, Q 1,…, Qn:
Q 0=0
Q 1= p 1
Q 2 =p 1 +p 2
Q 3 =p 1 +p 2 +p 3
...
Qn=p 1 +p 2 + … +pn= 1
2. Разобьем интервал [ Q 0, Qn) (т.е. интервал [0,1)) так, чтобы каждой букве исходного алфавита соответствовал свой интервал, равный ее вероятности (рис. 1):
|
|
|
a 1 [ Q 0, Q 1)
a 2 [ Q 1, Q 2)
a 3 [ Q 2, Q 3)
a 4 [ Q 3, Q 4)
...
an [ Qn- 1, Qn)
3. В процессе кодирования будем выбирать интервал, соответствующий текущей букве исходного сообщения, и снова разбивать его пропор-ционально вероятностям исходных букв алфавита. Постепенно проис-ходит сужение интервала до тех пор, пока не будет закодирован последний символ кодируемого сообщения. Двоичное представление любой точки, расположенной внутри интервала, и будет кодом исходного сообщения.
На рис. 1 показан этот процесс для кодирования последовательности а 3 а 2 а 3…
 |
Рис. 1. Схема арифметического кодирования
Для удобства вычислений введем следующие обозначения:
li - нижняя граница отрезка, соответствующего i- той букве исходного сообщения;
hi - верхняя граница этого отрезка;
ri - длина отрезка [ li, hi), т.е. ri = hi - li.
Возьмем начальные значения этих величин:
l 0 = Q 0 = 0, h 0 = Qk= 1, r 0 = h 0 - l 0 = 1
и далее будем вычислять границы интервала, соответствующего кодируемой букве, по формулам:
, 
,
где m - порядковый номер кодируемой буквы в алфавите источника, m= 1,..., n.
Таким образом, окончательная длина интервала равна произведению вероятностей всех встретившихся символов, а начало интервала зависит от порядка расположения символов в кодируемой последовательности.
Для однозначного декодирования исходной последовательности достаточно взять 
разрядов двоичной записи любой точки из интервала [ li, hi), где rk - длина интервала после кодирования k символов источника.
Пример. Рассмотрим кодирование бесконечной последовательности X=a 3 a 2 a 3 a 1 a 4 ... в алфавите A= { a 1, a 2, a 3, a 4} с помощью арифметического кода. Пусть вероятности букв исходного алфавита равны соответственно
|
|
|
p 1 = 0.1, p 2 = 0.4, p 3 = 0.2, p 4 = 0.3.
Вычислим кумулятивные вероятности Qi:
Q 0 = 0,
Q 1 =p 1 = 0.1,
Q 2 =p 1 +p2 = 0.5,
Q 3 =p 1 +p 2 +p 3 = 0.7,
Q 4 =p 1 +p 2 +p 3 + p 4 = 1.
Получим границы интервала, соответствующего первому символу кодируемого сообщения a 3:
l 1 = l 0 + r 0 ·Q 2 = 0 + 1·0.5 = 0.5,
h 1 = l 0 + r 0 ·Q 3 = 0 + 1·0.7 = 0.7,
r 1 = h 1 - l 1 = 0.7 - 0.5 = 0.2.
Для второго символа кодируемого сообщения a 2 границы интервала будут следующие:
l 2 = l 1 + r 1 ·Q1 = 0.5 + 0.2·0.1 = 0.52,
h 2 = l 1 + r1·Q 2 = 0.5 + 0.2·0.5 = 0.6,
r 2 = h 2 - l 2 = 0.6 - 0.52 = 0.08и т.д.
В результате всех вычислений получаем следующую последовательность интервалов для сообщения a 3 a 2 a 3 a 1 a 4:
В начале [0.0, 1.0)
После пpосмотpа a 3 [0.5, 0.7)
После пpосмотpа a 2 [0.52, 0.6)
После пpосмотpа a 3 [0.56, 0.576)
После пpосмотpа a 1 [0.56, 0.5616)
После пpосмотpа a 4 [0.56112, 0.5616)
Кодом последовательности a 3 a 2 a 3 a 1 a 4 будет двоичная запись любой точки из интервала [0.56112, 0.5616), например, 0.56112. Для однозначного декодирования возьмем élog2(r 5)ù = élog2(0.00048)ù = 12 разрядов, получим 100011111010.
Таким образом, при арифметическом кодировании сообщение представляется вещественными числами в интервале [0,1). По мере кодирования сообщения отображающий его интервал уменьшается, а количество битов для представления интервала возрастает. Очередные символы сообщения сокращают величину интервала в зависимости от значений их вероятностей. Более вероятные символы делают это в меньшей степени, чем менее вероятные, и следовательно, добавляют меньше битов к результату.
