Приложение 4. МАКСИМИЗАЦИЯ СКОРОСТИ ДЛЯ СИСТЕМЫ ОГРАНИЧЕНИЯ

Допустим, что на данные последовательности символов наложен ряд ограничений, задающих систему с конечным числом состояний, которая может быть поэтому изображена графически, как на рис. 2. Пусть будут длительности различных символов, которые могут появиться при переходе из состояния в состояние Каково распределение вероятностей для различных состояний и вероятностей выбора символа при переходе из состояния в состояние для которого максимизируется скорость создания информации при данных ограничениях? Эти ограничения определяют дискретный канал, а максимальная скорость должна быть меньше или равна пропускной способности С этого канала. Действительно, если все группы большой длительности были бы равновероятны, то в результате получилась бы именно эта скорость, и если это возможно, то такая скорость была бы наилучшей. Покажем, что эта скорость может быть достигнута при надлежащем выборе Рассматриваемая скорость равна

Пусть

где удовлетворяют системе уравнений

Эта однородная система имеет ненулевое решение, так как обращает в нуль детерминант из коэффициентов

Определенные таким образом могут служить переходными вероятностями, так как, во-первых,

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

Подставляя эти значения в общее выражение для скорости, получим

Следовательно, скорость, достигаемая для этого набора вероятностей перехода, равна С, и так как эта скорость не может быть превышена, то она и является максимальной.