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

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

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

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

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

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

2. не зависит от состояния Это доказывается следующим образом. Выберем некоторую последовательность букв на входе ведущую из состояния в состояние и другую последовательность У, ведущую из состояния в состояние Ни одна из этих последовательностей не содержит более чем букв, где число (конечное) состояний канала. Выберем таким образом, чтобы выполнялось неравенство и чтобы в то же время было достаточно большим, так что

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

Сконструируем теперь некоторую совокупность последовательностей X для состояния используя имеющиеся последовательности для состояния и добавляя к ним вначале последовательность а в конце — последовательность V. В случае когда каждой из полученных последовательностей для состояния приписана вероятность, равная той; которая приписывалась последовательности X для состояния с целью достижения пропускной способности скорость передачи для канала из последовательностей будет в точности равна но на этот раз длины цепочек будут уже самое большее равны т. е. немного больше Отсюда следует, что

Очевидно, что, поменяв местами и мы получим обратный результат и поэтому . (Отметим, что если имеется несколько классов эквивалентности, то для каждого из них существует своя пропускная способность С и пропускные способности для различных классов не обязательно совпадают друг с другом.)

3. Пусть — пропускная способность, вычисленная для последовательностей длины которые начинаются в состоянии и оканчиваются в Пусть

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

Сейчас мы хотим показать, что, начиная с состояния можно вести передачу с произвольно малой вероятностью ошибки и со скоростью где С — величина, определенная ранее в формулировке свойства 3. Точнее, нами будет доказано следующее.

Теорема 5. Для любого существует величина такая, что для любого (равного некоторому целому числу, умноженному на -основную длину цикла) найдется блоковый код длины с М возможными словами, для которого и вероятность ошибки удовлетворяют неравенству Не существует никакой последовательности кодов, для которой с увеличением длины блока вероятность ошибки стремилась бы к нулю и скорость передачи была бы больше С.

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

это лишь уменьшает коэффициент при в показателе степени в раз. Следовательно, положительное утверждение теоремы доказано для чисел, кратных Чтобы доказать это же утверждение для всех чисел, кратных заметим сначала, что оно справедливо для всех достаточно больших чисел, кратных . В самом деле, при достаточно больших числах, кратных эффект добавления кодовых слов, переводящих состояние снова в после числа букв, кратного может быть сделан произвольно малым (так что скорость передачи фактически не изменится). Для меньших чисел, кратных можно использовать теперь любой код с некоторой вероятностью ошибки меньше чем 1 (например, интерпретировать любое полученное слово как сообщение 1 с При этом будем иметь некоторую конечную совокупность кодов вплоть до некоторого числа, кратного начиная с которого справедлива единая экспоненциальная оценка. Ясно, что здесь можно будет выбрать некоторый коэффициент такой, что для любого кратного

Обратное утверждение теоремы (то, что пропускная способность С не может быть превзойдена) доказывается методом, подобным тому, который использовался в случае, когда состояние было вычислимо также и на приемном конце. В самом деле, рассмотрим канал определенный следующим образом. Вначале данный канал К помещается в произвольное состояние и номер этого состояния передается без помех на приемный конец. Затем передаются букв при таких же ограничениях и с такими же вероятностями, как у данного канала К. Конечное состояние также передается. Этот процесс повторяется далее блоками длины Теперь имеется некоторый канал без памяти, который для любого «включает в себя» данный канал. В канале можно использовать любое кодирование, предназначенное для канала К, и оно будет приводить к столь же хорошим вероятностям ошибок. Следовательно, для любого пропускная способность данного канала должна быть меньше или равна пропускной способности канала . С другой стороны, в действительности является «суммой» множества каналов, соответствующих последовательностям, переводящим из состояния в состояние за шагов (т. е. каналов, пропускные способности которых были обозначены ранее через Как мы видели выше, для всех достаточно больших и для всех и имеет место неравенство . Следовательно, для всех пропускная способность канала меньше, чем где — число состояний. Отсюда следует, что пропускная способность канала К не больше, чем С.

Интересно сравнить результаты этого раздела, в котором считалось, что состояния вычислимы только на передающем конце, с результатами, полученными в предыдущем разделе, где

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

ЛИТЕРАТУРА

(см. скан)