5.5. Вычисление пропускной способности дискретных постоянных каналов

Перейдем к вычислению пропускной способности дискретного постоянного канала [см. равенство (5.16)]. Обозначим через число символов входного алфавита и через число символов в выходном алфавите У. Распределение вероятностей входных символов так же как и в предыдущем разделе, удобно представить точкой в -мерном пространстве с декартовыми координатами

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

и

Таким образом, геометрическим местом точек, представляющих распределение вероятностей, является область гиперплоскости [определяемой равенством (5.57)], ограниченная гиперплоскостями Нашей целью является определение максимального значения средней взаимной информации

внутри или на границах определенной таким образом области.

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

где С — максимальное значение т. е. пропускная способность канала.

Доказательство. Согласно методу неопределенных множителей Лагранжа [I], функция переменных стационарна на гиперплоскости, определяемой выражением (5.57), когда переменных удовлетворяют системе уравнений

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

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

Выражая все информационные меры в натуральных единицах и дифференцируя по получим

Следовательно, выражение (5.61) с учетом равенства (5.59) преобразуется в

что можно также переписать в виде

где

— постоянная, которую нужно определить. Умножая равенство (5.66) на и суммируя по получим с помощью равенства (5.57) выражение

Так как, по предположению, вероятности удовлетворяют равенству (5.61), соответствующее значение есть относительный максимум и, следовательно, постоянная С есть пропускная способность канала. Ч. Т. Д.

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

Для того чтобы определить [7] распределение вероятностей для которого принимает максимальное значение С, удобно переписать выражение (5.60) в виде

где задается формулой

Суммируя по выходному алфавиту эти последние выражения, получаем с помощью выражения (5.57), что

Условия, задаваемые равенствами (5.69), (5.70) и (5.71), образуют систему уравнений с тем же числом неизвестных (С — одно из этих неизвестных). Таким образом, значения вероятностей входных символов можно найти, решая эту систему уравнений, если ее решение существует.

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

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

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

Пусть

— число символов в каждом из двух алфавитов и матрица, обратная

Элементы задаются равенствами

где алгебраическое дополнение элемента матрицы Тогда равенство (5.69) дает

откуда, выражая получаем

Тогда равенство (5.70) дает

что и является искомым выражением для определяемым через элементы матрицы канала.

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

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

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