3. Реализация модели.

Сама реализация обсуждается в следующем подразделе, а здесь мы коснемся только конструкции модели. В языке Си байт представляет собой целое число от 0 до 255 (тип char). Здесь же мы представляем байт как целое число от 1 до 257 включительно (тип index), где EOF трактуется как 257-ой символ. Предпочтительно отсортировать модель в порядке убывания частот для минимизации количества выполнения цикла декодирования (стpока 189). Перевод из типа char в index, и наоборот, реализуется с помощью двух таблиц - index_to_char[] и char_to_index[].В нашей модели эти таблицы формируют index, присваивая часто используемым символам маленькие индексы.

Вероятности представляются в модели как целочисленные счетчики частот, а накапливаемые частоты хранятся в массиве cum_freq[]. Как и в предыдущем случае, этот массив - "обратный", и счетчик общей частоты, применяемый для нормализации всех частот, размещается в cum_freq[0].Накапливаемые частоты не должны превышать установленный в Max_frequency максимум, а реализация модели должна предотвращать переполнение соответствующим масштабированием. Необходимо также хотя бы на 1 обеспечить различие между двумя соседними значениями cum_freq[], иначе рассматриваемый символ не сможет быть передан.

4. Приращаемая передача и получение.

В отличие от псевдокода на рисунке 1, наша программа представляет low и high целыми числами. Для них, и для других полезных констант, определен специальный тип данных BITS_IN_REGISTER. Это - Top_value, определяющий максимально возможный BITS_IN_REGISTER, First_qtr и Third_qtr, представляющие части рабочего интервала. В псевдокоде текущий интервал представлен через [low; high), а в нашей программе это [low; high] - интервал, включающий в себя значение high. На самом деле более правильно, хотя и более непонятно, утверждать, что в программе представляемый интервал есть [low; high + 0.1111...) по той причине, что при масштабировании границ для увеличения точности, нули смещаются к младшим битам low, а единицы смещаются в high. Хотя можно писать программу на основе разных договоренностей, данная имеет некоторые преимущества в упрощении кода программы.

По мере сужения кодового интервала, старшие биты low и high становятся одинаковыми, и поэтому могут быть переданы немедленно, т.к. на них будущие сужения интервала все равно уже не будут влиять. Поскольку мы знаем, что low<=high, это воплотится в следующую программу:

for (;;) {

if (high < Half) {

output_bit(0);

low = 2 * low;

high = 2 * high + 1;

}

else if (low >= Half) {

output_bit(1);

low = 2 * (low - Half);

high = 2 * (high - Half) + 1;

}

else break;

}

гарантирующую, что после ее завершения будет справедливо неравенство: low<Half<=high. Это можно найти процедуре encode_symbol(). Кроме того, есть несколько дополнительных сложностей, связанных с возможностями потери значимости (см. следующий подраздел). Как отмечено выше, нужно внимание при сдвиге единиц к началу high.

Приращаемый ввод исходных данных выполняется с помощью числа, названного value. В нашей программе, обработанные биты перемещаются в верхнюю часть, а заново получаемые поступают в нижнюю. Вначале, start_decoding() заполняет value полученными битами. После определения следующего входного символа процедурой decode_symbol(), происходит вынос ненужных, одинаковых в low и в high, битов старшего порядка сдвигом value на это количество разрядов (выведенные биты восполняются введением новых с нижнего конца).

for (;;) {

if (high < Half) {

value = 2 * value + input_bit();

low = 2 * low;

high = 2 * high + 1;

}

else if (low > Half) {

value = 2 * (value - Half) + input_bit();

low = 2 * (low - Half);

high = 2 * (high - Half) + 1;

}

else break;

}

В том случае, когда для представления чисел value, low и high выбраны двухбайтные величины, можно пренебрегать значением старших битов в этих числах перед сдвигом влево, т.е. не вычитать значение Half.