Читать реферат по информатике, вычислительной технике, телекоммуникациям: "Арифметическое кодирование. Кодирование длин повторений" Страница 3

(Назад) (Cкачать работу)

Поскольку теперь мы знаем уже две декодированные буквы - РА, исключим из итогового интервала влияние буквы А. Для этого вычтем из остатка 0,015174886 нижнюю границу для буквы А 0,015174886 – 0.0 = =0,015174886 и разделим результат на ширину интервала, отведенного для буквы А, то есть на 0,1. В результате получим 0,015174886/0,1=0,15174886. Результат лежит в диапазоне, отведенном для буквы Д, следовательно, очередная буква будет Д.

Исключим из результата кодирования влияние буквы Д. Получим (0,15174886 – 0,1)/0,1 = 0,5174886. Результат попадает в интервал, отведенный для буквы И, следовательно, очередной декодированный символ – И, и так далее, пока не декодируем все символы:

ДекодируемоеСимволГраницыШирина

числона выходенижняя верхняяинтервала

0,8030349772 Р0.8 1.00.2

0,015174886А0.0 0.10.1

0,15174886Д 0.1 0.2 0.1

0,5174886И0.3 0.60.3

0,724962О 0,7 0,80,1

0,24962В 0,2 0,20,1

0,4962И 0,3 0,60,3

0,654З 0,6 0,70,1

0,54И 0,3 0,60,3

0,8Р 0,6 0,80,2

0.0 Конец декодирования

Это основная идея арифметического кодирования, его практическая реализация несколько сложнее. Некоторые проблемы можно заметить непосредственно из приведенного примера.

Первая состоит в том, что декодеру нужно обязательно каким-либо образом дать знать об окончании процедуры декодирования, поскольку остаток 0,0 может означать букву а или последовательность аа, ааа, аааа и т.д. Решить эту проблему можно двумя способами.

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

Другой способ – включить в модель источника специальный символ конца блока, например #, и прекращать декодирование, когда этот символ появится на выходе декодера.

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

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

Похожие работы