Теория информации
Конспект лекций
назад | содержание | вперед

6. АРИФМЕТИЧЕСКИЙ КОД

 

Идея арифметического кодирования была впервые предложена П. Элиасом. В арифметическом коде кодируемое сообщение разбивается на блоки постоянной длины, которые затем кодируются отдельно. При этом при увеличении длины блока средняя длина кодового слова стремится к энтропии, однако возрастает сложность реализации алгоритма и уменьшается  скорость кодирования и декодирования. Таким образом, арифметическое кодирование позволяет получить произвольно малую избыточность при кодировании достаточно больших блоков входного сообщения, процесс кодирования и декодирования достаточно трудоемкий.

Рассмотрим общую идею арифметического кодирования. Пусть дан источник, порождающий буквы из алфавита и вероятностями . Для кодирования сообщения источника арифметическим кодом необходимо выполнить следующие действия.

1)Вычислим кумулятивные вероятности ,



2) Разобьем интервал  (т.е. интервал [0,1)) на отдельные интервалы так, чтобы каждой букве алфавита источника соответствовал свой интервал, равный ее вероятности (см. рис. 7). Таким образом, символу  соответствует интервал , .

3) В процессе кодирования будем выбирать интервал, соответствующий текущей букве исходного сообщения, и снова разбивать его  пропорционально вероятностям  букв алфавита источника. Постепенно происходит сужение интервала до тех пор, пока не будет закодирован последний символ кодируемого сообщения. Двоичное представление любой точки, расположенной внутри интервала, и будет кодом исходного сообщения.

На рисунке 7 показан  процесс  кодирования последовательности

 

 

 

Рисунок 7 Схема арифметического кодирования


Для удобства вычислений введем следующие обозначения:
 - нижняя граница отрезка, соответствующего i -той букве исходного сообщения;
 - верхняя граница этого отрезка;
 - длина отрезка ,  т.е. .
Инициализируем начальные значения этих величин




и далее будем вычислять границы интервала, соответствующего кодируемой букве  по формулам:



где m -  порядковый номер кодируемой буквы в алфавите источника m=1,...,n,  а i– номер кодируемого символа в сообщении.

Таким образом, окончательная длина интервала равна произведению вероятностей всех встретившихся символов, а начало интервала зависит от порядка расположения символов в кодируемой последовательности.

Для однозначного декодирования исходной последовательности достаточно взять  разрядов двоичной записи любой точки из интервала  , где  - длина интервала после кодирования  символов сообщения источника.

 

Пример 6.1. Рассмотрим кодирование арифметическим кодом бесконечной последовательности , которая порождается источником с алфавитом  с вероятностями , , , .

Вычислим кумулятивные вероятности

 




Получим границы интервала, соответствующего первому символу кодируемого сообщения :

 


Для второго символа кодируемого сообщения  границы интервала будут следующие:

 


и т.д.

 

В результате всех вычислений получаем следующую последовательность интервалов для сообщения



Кодом последовательности  будет двоичная запись любой точки из интервала [0.56112, 0.5616), например, 0.56112. Для однозначного декодирования возьмем  разрядов, получим код 100011111010.

Таким образом, при арифметическом кодировании сообщение представляется вещественными числами в интервале [0,1). По мере кодирования сообщения отображающий его интервал уменьшается, а количество битов для представления интервала возрастает. Очередные символы сообщения сокращают величину интервала в зависимости от значений их вероятностей. Более вероятные символы делают это в меньшей степени, чем менее вероятные, и следовательно, добавляют меньше битов к результату.

 

Алгоритм на псевдокоде


 Арифметическое кодирование


В начале декодирования известен конечный интервал (например, [0.56112; 0.5616)) или любое число из этого интервала (например, 0.56112). Сразу можно определить, что первым закодированным символом был , т. к. число 0.56112 лежит в интервале [0.5; 0.7), который соответствует символу . Затем в качестве интервала берется [0.5; 0.7) и в нем определяется диапазон, соответствующий числу 0.56112. Это интервал [0.52, 0.6), выделенный символу и т.д. Для декодирования необходимо знать количество закодированных символов и исходные вероятности символов.

 

Алгоритм на псевдокоде


 Арифметическое декодирование


Обозначим


Заметим, что при кодировании и декодировании  для экономии памяти достаточно  использовать не массивы, а переменные l, r и h.

При реализации арифметического кодирования возникают две проблемы:

Для решения этих проблем реальные алгоритмы работают  с целыми числами и оперируют с дробями, числитель и знаменатель которых являются целыми числами (например, знаменатель равен , , ). При этом с потерей точности можно бороться, отслеживая сближение и и умножая числитель и знаменатель представляющей их дроби на одно и то же число, например на 2. С переполнением сверху можно бороться, записывая старшие биты и в файл только тогда, когда они перестают меняться (т.е. уже не участвуют в дальнейшем уточнении интервала), когда и одновременно находятся в верхней или нижней половине интервала.

 

 

наверх

 


назад | содержание | вперед