Теория информации |
Конспект лекций |
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. С переполнением сверху можно бороться, записывая старшие биты
и
в файл только тогда, когда они перестают меняться (т.е. уже не участвуют в дальнейшем уточнении интервала), когда
и
одновременно находятся в верхней или нижней половине интервала.