Каналы с обратной связью

Рассмотрим теперь соответствующую задачу для каналов с полной обратной связью. Под этим будем понимать то, что существует «обратный» канал, безошибочно посылающий принятые на самом деле буквы из точки приема обратно на передающий конец. Предполагается, что эта информация принимается на передающем конце до того момента, когда должна быть передана следующая буква. Поэтому при желании она может быть использована при выборе следующей подлежащей передаче буквы.

Рис. 5.

Интересно, что в канале без памяти обычная пропускная способность в прямом направлении равняется одной и той же величине в присутствии и в отсутствии обратной связи. Это будет показано в теореме 6. Иначе обстоит дело с пропускной способностью при нулевой ошибке, которая в некоторых случаях может быть больше в присутствии обратной связи, чем при ее отсутствии. Например, в канале, изображенном на рис. 5, . Однако, как будет показано на основании теоремы 7, пропускная способность при нулевой ошибке и обратной связи .

Сначала определим код из блоков длины для системы с обратной связью. Это означает, что на передающем конце имеется устройство с двумя входами или математически — функция двух аргументов. Один аргумент — это сообщение, которое должно быть послано, другой — принятые ранее слова, поступившие по каналу обратной связи. Значение функции представляет собой букву, которую следует передать. Таким образом, функция может быть представлена как , где есть буква, переданная в блоке, -индекс, принимающий значения от 1 до М и выделяющий специфику переданного сообщения, принятое слово длины Так изменяемся в пределах от 0 до это значит, что принимает значения всех принятых слов этой длины.

Передача осуществляется следующим образом. Если подлежит передаче сообщение то вычисляется как где знак минус

означает «слово отсутствует», и посылается первая буква. Если канал обратной связи в качестве первой принятой буквы приносит, например, букву а, то следующей передаваемой буквой будет . Если далее принимается то следующей переданной буквой будет

Теорема 6. Пропускная способность в прямом направлении дискретного канала без памяти при наличии обратной связи равна обычной пропускной способности С (в отсутствии обратной связи). Среднее приращение взаимной информации принятой последовательности относительно сообщения на одну букву текста не превосходит С.

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

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

Так как вторая сумма может быть записана в виде

Объединяя обе суммы, получим теперь, что

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

Рассмотрим теперь скорость передачи в канале (в обычном смысле при отсутствии обратной связи) так, как будто бы значениям х приписаны вероятности При этом вероятности для пар х, у и вероятности просто для у были бы равны

Скорость, следовательно, равнялась бы

Так как где С — пропускная способность канала (С является максимально возможным значением по всем заключаем, что

Так как среднее изменение I на одну букву не превосходит С, среднее изменение на букв не превосходит Следовательно, в блоковом коде длины при скорости на входе, равной ненадежность при окончании блока будет по крайней мере т. е. точно такая же, как в случае канала без обратной связи. Иначе говоря, невозможно достигнуть нулевой ненадежности (или, что легко следует отсюда, нулевой вероятности ошибки) в случае, когда скорость превышает пропускную способность канала. Это, конечно, возможно сделать при скоростях, меньших С, ибо, наверняка, все, что может быть сделано без обратной связи, может быть сделано и с обратной связью.

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

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

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

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

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

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

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

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

Рассмотрим теперь такой случай, при котором не все пары являются смежными. Сначала, введя в рассмотрение блоковый код длины докажем, что при кодировании, не дающем ошибок, нельзя превзойти скорости Для это утверждение, очевидно, справедливо. Пусть доказываемая по индукции гипотеза будет состоять в том, что не существует блокового кода длины передающего со скоростью, превышающей или, иначе говоря, нельзя однозначно различить более чем различных сообщений. Предположим теперь (в противоположность ожидаемому результату), что имеется блоковый код длины различающий М сообщений при Первая передаваемая в коде буква делит эти М сообщений между входными буквами канала. Пусть — доля сообщений, приписанных к букве! (т. е. таких сообщений, для которых является первой передаваемой буквой). Эти теперь подобны вероятностям, заданным для различных букв, и поэтому, согласно определению существует некоторая выходная буква, скажем буква такая, что Рассмотр им множество сообщений, для которых первая передаваемая буква принадлежит Число сообщений в этом множестве равно по меньшей мере . Каждое из них может дать выходную букву в качестве первой принимаемой буквы. Тогда, когда это случится, существуют еще букв, подлежащих передачи, и так как то имеем Таким образом, существует не дающий ошибок блоковый код длины дающий скорость передачи, большую чем что противоречит предположению индукции. Отметим, что кодирующая функция для кода длины определяется формально из первоначальной кодирующей функции с помощью фиксирования в качестве применяемой буквы.

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

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

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

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

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

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

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

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

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

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

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

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

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

так как выше было показано, что

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

Итак получено скольугодно близкое приближение к при помощи кодов, не дающих ошибок.

В качестве примера к теореме 7 рассмотрим канал, изображенный на рис. 5. Требуется вычислить Легко увидеть, что, составляя минимакс, входящий в формулировку теоремы 7, можно положить так как, если бы они были неравными, максимум Для соответствующих трех выходных букв можно было бы снизить уравнением. Очевидно также, что тогда

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

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

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