11. Приложения свойства выпуклости. Каналы с симметричной структурой

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

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

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

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

Примером этого типа каналов служит канал с такими переходными вероятностями, что все входные и выходные буквы являются двоичными (так что имеется двоичный канал без шума, осуществляющий передачу от конца 2 к концу 1). Если тогда если же то с вероятностями 1/2 принимает значения 0 или 1. Другими словами, если то двоичный канал для передачи в прямом направлении является каналом без шума, если же то на приемном конце получается только шум. Заметим здесь, что если сделать перестановку букв алфавита и одновременно переставить буквы алфавита то канал останется прежним и условные вероятности не изменятся. Из проведенного выше анализа видно, что внутренняя и внешняя границы совпадают и дают область пропускной способности канала. Кроме того, граничные точки будут здесь получаться при распределениях матрица которых имеет равные строки, как показано в табл. II.

Таблица II

Для фиксированного такое распределение дает скорости

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

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

Рис. 9.

Рис. 10.

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

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