9.4. Оптимизация нижней границы

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

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

Доказательство. Обозначим через

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

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

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

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

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

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

где

и величины, определенные в соотношениях (9.27), (9.36) и (9.37) с подстановкой вместо

Далее мы видим, что правая часть неравенства (9.83) отличается от правой части неравенства (9.84) на Следовательно, при любом фиксированном значении правые части неравенств (9.83) и (9.84) одновременно минимизируются при одном и том же Кроме того, поскольку имеет одно и то же значение для всех последовательностей приписанных сообщениям, то правая часть неравенства (9.81) минимизируется, а нижняя граница для задаваемая неравенством (9.82), максимизируется при одном и том же для всех входных последовательностей Мы приходим к выводу, что наименьшая нижняя граница вероятности ошибки и наибольшая нижняя граница соответствующей скорости передачи получаются, когда все входные последовательности, приписанные сообщениям, имеют одинаковую композицию. Ч. Т. Д.

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

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

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

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

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

Доказательство. Используя выражение (9.69), имеем для отрезка

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

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

Тогда подстановка правой части этой формулы в равенство (9.88) дает соотношение

которое, если отождествить с совпадает с верхним выражением в формуле (9.86).

В частном случае надо минимизировать предел при стремящемся к нулю. Получаем

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

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

Обозначим через значения а и I для оптимальной композиции, значения координат пунктирной линии на

рис. 9.3. Из (9.69) имеем

Следовательно, пунктирная линия на рис. 9.3 касается оси при Соответствующее значение равно

где С — пропускная способность канала. С помощью выражений (9.70) и (9.86) в окрестности мы получаем

где

Для из выражений (9.24) и (9.86) имеем

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

В частном случае двоичного симметричного канала эти формулы приводят для к выражениям (7.58) и (7.57) соответственно. Для стремящегося к единице, равенства (9.96) и (9.97) дают

где множество выходных букв для которых множество входных букв для которых есть предел Тогда из равенства (9.75) мы получаем

Как и в предыдущем разделе, мы приходим к выводу, что вертикальная часть графика оптимальной зависимости между лежит на оси а тогда и только тогда, когда существует одна или более выходных букв у, для которых для всех входных букв х. Кроме того, если это условие не удовлетворяется, то выражение, задаваемое правой частью равенства (9.102), должно служить верхней границей пропускной способности канала при нулевой ошибке. В самом деле, соотношения (9.100), (9.101) и (9.102) идентичны соотношениям, полученным Шенноном [8], для верхней границы пропускной способности дискретного канала при нулевой ошибке. Необходимо, однако, подчеркнуть, что из того, что не всегда следует, что пропускная способность канала при нулевой ошибке также отлична от нуля.

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

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