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

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

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

Таблица № 5
	Верхняя граница	Нижняя граница	Интервал	Текущий код сообщения
Начальное состояние	99999	00000	100000
Кодируем 'В' (0.2-0.3)	29999	20000
Выдвигаем 2	99999	00000	100000	.2
Кодируем 'I' (0.5-0.6)	59999	50000		.2
Выдвигаем 5	99999	00000	100000	.25
Кодируем 'L' (0.6-0.8)	79999	60000	20000	.25
Кодируем 'L' (0.6-0.8)	75999	72000		.25
Выдвигаем 7	59999	20000	40000	.257
Кодируем ' ' (0.0-0.1)	23999	20000		.257
Выдвигаем 2	39999	00000	40000	.2572
Кодируем 'G' (0.4-0.5)	19999	16000		.2572
Выдвигаем 1	99999	60000	40000	.25721
Кодируем 'А' (0.1-0.2)	67999	64000		.25721
Выдвигаем 6	79999	40000	40000	.257216
Кодируем 'Т' (0.9-1.0)	79999	76000		.257216
Выдвигаем 7	99999	60000	40000	.2572167
Кодируем 'Е' (0.3-0.4)	75999	72000		.2572167
Выдвигаем 7	59999	20000	40000	.25721677
Кодируем 'S' (0.8-0.9)	55999	52000		.25721677
Выдвигаем 5	59999	20000	40000	.257216775
Выдвигаем 2				.2572167752
Выдвигаем 0				.25721677520

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