Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Арифмитическое кодирование.rtf
Скачиваний:
1
Добавлен:
01.05.2025
Размер:
121 Кб
Скачать
☆

Монитор 1.94

Таблица 3

Шаги алгоритма арифметического кодирования при обработке сообщения

ОчереднойСимвол

НижняяГраница

ВерхняяГраница

0.0

1.0

В

0.2

0.3

I

0.25

0.26

L

0.256

0.258

L

0.2572

0.2576

Пробел

0.25720

0.25724

G

0.257216

0.257220

А

0.2572164

0.2572168

Т

0.25721676

0.2572168

Е

0.257216772

0.257216776

S

0.2572167752

0.2572167756

Таким образом, согласно нашей схеме, число 0.2572167752 однозначно кодирует сообщение “BILL GATES”.

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

Число = ПрочитатьЧисло();

Всегда

Символ =

НайтиСимволВинтервалКоторогоПопадаетЧисло

(Число)

Выдать (Символ) Интервал = ВерхняяГраницаИнтервалаДля (Символ) -

НижняяГраницаИнтервалаДля (Символ);

Число = Число - НижняяГраницаИнтервалаДля(Символ); Число = Число / Интервал; Конец Всегда

В приведенном алгоритме не рассматривается вопрос остановки декодера. В листинге приведенной в конце статьи программы декодер останавливается при обнару­жении специального символа EOF (конец файла).

Для нашего примера декодер будет работать следу­ющим образом (табл. 4).

Таким образом при обработке числа после опреде­ления символа, в интервал которого оно попадает, этот символ выдается как раскодированный, а его влияние на число устраняется действиями, обратны­ми действиям при кодировании.

______Вопросы реализации______

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

ко на компьютерах с математическим сопроцессором, наилучшим образом он может быть реализован на основе стандартной 16 или 32-битовой целочисленной арифметики.

Ранее было отмечено, что при работе алгоритм от­слеживает верхнюю и нижнюю границы возможного выходного кода. Сразу после старта нижняя граница установлена в 0.0, а верхняя — в 1.0. Первое упроще­ние для работы с целочисленной арифметикой — это заменить 1 на 0.999..., или .111... в двоичном коде. Это упрощает и кодирование, и декодирование.

Будем располагать в целочисленных регистрах дроб­ные части значений границ, выравнивая их влево (стар­шие биты значения в старших битах регистра). Запол­ним регистры битами 1 для верхней границы и 0 для нижней соответственно. В нашей реализации будут ис­пользованы 16-битовые регистры, и их начальные зна­чения будут равны 0xFFFF для верхней границы и 0x0000 — для нижней. Поскольку известно, что значе­ния в регистрах соответствуют бесконечным дробям, то впоследствии можно будет сдвигать их влево, втягивая дополнительные биты по мере необходимости.

Рассмотрим работу описанного алгоритма на при­мере воображаемых пятизначных десятичных регист­ров. (Такие “некомпьютерные” объекты вводятся только для удобства понимания). Как и в предыдущем примере, будем сжимать сообщение “BILL GATES”.

После инициализации регистры будут хранить сле­дующие значения:

ВерхняяГраница: 99999 (99999999...до бесконечности) НижняяГраница: 00000 (00000000...до бесконечности)

На следующем шаге вычислим Интервал. Разница между верхней и нижней границей будет 100000, а не 99999, так как мы подразумеваем бесконечное коли­чество 9 в верхней границе.

Затем вычислим новое значение верхней границы. ВерхняяГраницаИнтервалаДля символа В равна 0.30, что должно привести к установке соответствующего ре­гистра в 30000. Однако перед сохранением нового значе­ния в регистре, принимая во внимание то, что мы моде­лируем бесконечную дробь, уменьшим это значение на единицу. Таким образом новое значение в регистре верх­ней границы равно 29999. Вычисление нового значения нижней границы дает 20000 в соответствующем регистре.

В этот момент регистры выглядят так:

ВерхняяГраница : 29999 (999...) НижняяГраница : 20000 (000...)

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

Таблица 4

Шаги работы алгоритма арифметического декодирования

Число

Символ

НижняяГраница

ВерхняяГраница

Интервал

0.2572167752

В

0.2

0.3

0.1

0.572167752

I

0.5

0.6

0.1

0.72167752

L

0.6

0.8

0.2

0.6083876

L

0.6

0.8

0.2

0.041938

Пробел

0.0

0.1

0.1

0.41938

G

0.4

0.5

0.1

0.1938

А

0.2

0.3

0.1

0.938

Т

0.9

1.0

0.1

0.38

Е

0.3

0.4

0.1

0.8

S

0.8

0.9

0.1

0.0