ПРИЛОЖЕНИЕ 7А. ВЫЧИСЛИТЕЛЬНЫЙ АЛГОРИТМ ДЛЯ R(D) (Блахут [1972])

Алгоритм вычисления подобен алгоритму вычисления пропускной способности, описанному в приложении Напомним, что для дискретного источника без памяти с алфавитом распределением вероятностей букв алфавитом представления и погрешностью скорость как функция погрешности задается выражением (7.2.53)

и

Параметрическое представление через параметр определяется с помощью (7.6.32) и (7.6.33) соотношениями

где согласно (7.6. 31) для всех

Переходные вероятности на которых достигается удовлетворяют необходимым и достаточным условиям (7.6.19):

Алгоритм вычисления основан на следующей теореме.

Теорема 7А.1. Пусть задан параметр вектор вероятностей, для которого для всех Для каждого целого определим

Тогда при

где - точка на кривой определяемая параметром

Доказательство. Рассмотрим плоскость с координатами показанную на рис. Рассмотрим величину которая соответствует пересечению оси I с прямой, имеющей наклон и проходящей через точку Напомним, что точка на кривой задаваемой параметрически через параметр имеет касательную, параллельную каждой из этих прямых с наклоном При этом указанная точка лежит ниже всех этих прямых, так как определяется как минимум

Рис. 7А.1. Вид плоскости

Величина строго убывает с ростом до тех пор, пока точка не обращается в точку на кривой Из (7А.2) следует, что

Отсюда получаем следующую оценку для разности:

где использовалось соотношение Равенство в выполняется тогда и только тогда, когда и

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

Таким образом, удовлетворяет условиям, необходимым и достаточным для достижения так что

Точность вычислений этого алгоритма после конечного числа шагов устанавливается следующей теоремой.

Теорема Пусть для некоторого заданного распределения вероятностей

Если распределение удовлетворяет равенству

то точке

справедлива граница

Доказательство. Если и

так что

Из теоремы 7.6.3 следует, что

где произвольный вектор, такой, что

Выберем

где Тогда выполняется:

Отсюда следует, что для всякого распределения на котором достигается точка выполняются равенство

и неравенство

где равенство достигается при Таким образом,

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

Шаг 1. Положить и выбрать начальные вероятности Можно взять равномерное начальное распределение.

Шаг 2. Для заданных и некоторого вычислить

Шаг 3. Если то вычислить

и остановиться.

Шаг 4. Если то заменить на и перейти к шагу 2.

Задачи

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)