4.5. НАХОЖДЕНИЕ ПРОПУСКНОЙ СПОСОБНОСТИ ДИСКРЕТНОГО КАНАЛА БЕЗ ПАМЯТИ

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

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

Более того, число С равно пропускной способности канала.

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

по всем Взяв частные производные, получим

Рис. 4.5.1.

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

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

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

Рис. 4.5.2. Пропускная способность двоичного симметричного канала и двоичного стирающего канала.

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

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

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

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

ДКБП называется симметричным, если множество выходов может быть разбито на подмножества таким образом, что для каждого подмножества матрица переходных вероятностей (используя входы как строки и выходы подмножества как столбцы) обладает тем свойством, что каждая строка является перестановкой любой другой строки и каждый столбец (если их больше чем 1) является перестановкой любого другого столбца. Так, например, разбивая выходы канала (в) на рис. 4.5.1 на 0, 2 и 1

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

Теорема 4.5.2. В симметричном дискретном канале без памяти пропускная способность достигается при использовании входных букв с равной вероятностью.

Доказательство. При равновероятных входах имеем

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

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

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

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

где выходные вероятности равны

Из (4.5.9) и (4.5.10) имеем

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

Где все логарифмы взяты по основанию 2. К сожалению, нет уверенности в том, что С, задаваемая равенством (4.5.12), является пропускной способностью канала. Сначала нужно использовать С, чтобы найти а» и затем провести решение (4.5.10) относительно входных вероятностей Если все неотрицательны, то решение правильно, в противном случае — неправильно.

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

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

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

Доказательство. Пусть со является вероятностью выхода на основании (4.5.2) имеем

Если какая-либо со то любой вход, который дает выход с ненулевой переходной вероятностью, должен иметь Для такого левая часть (4.5.13) равна бесконечности, что приводит к противоречию.

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

Доказательство. Пусть какие-либо два входных вероятностных вектора, на которых достигается пропускная способность С. При 0, лежащем между 0 и 1, входной вектор вероятностей также приводит к пропускной способности, так как выпуклость информации показывает, что средняя взаимная информация при не может быть меньше чем С. Используя те же самые условные вероятности

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

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

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

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