ЗАМЕЧАНИЯ О ЧАСТИЧНОМ УПОРЯДОЧИВАНИИ КАНАЛОВ СВЯЗИ

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

Рис. 1. Примеры, иллюстрирующие отношение включения,

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

Рассмотрим три дискретных канала без памяти, изображенные на рис. 1. Про первый можно сказать, что он включает второй, так как первый сводится ко второму, если в нем использовать только буквы А, В, С. Все, что можно передавать по второму каналу, можно с помощью такого искусственного сведения передавать и по первому (но по первому каналу можно, конечно, передать больше, используя полный алфавит). Второй в некотором смысле включает третий, так как третий можно получить из второго, объединив буквы А и В на выходе в одну и ту же букву. Можно представить себе как бы некоторое приспособление, поставленное

на выходе второго канала, которое выдает букву А, когда на выходе появляется буква А или В и пропускает букву С без изменения.

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

Рис. 2. Еще один пример включения.

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

Рис. 3. Сведение левого канала, изображенного на рис. 2, к правому с помощью предыдущего канала.

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

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

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

и

и, кроме того, существуют

при которых выполняется равенство

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

Определим чистый канал требованием, чтобы все переходы имели вероятности либо 0, либо 1; иными словами, в таком канале каждая буква на входе безошибочно переходит в определенную букву на выходе. Любую пару, составленную из предварительного и заключительного каналов и Та, фигурирующую в (1), можно представить себе как взвешенную сумму чистых каналов, предварительного и заключительного для канала и действующих на него. Рассмотрим всевозможные отображения входных букв канала на его выходные буквы и сопоставим каждому отображению вероятность,

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

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

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

Отношение включения сохраняется при сложении и умножении каналов. Если — каналы и то

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

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

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

Предположим, что и что имеют матрицы соответственно. Тогда включает канал, матрица которого имеет вид

Следовательно, если каналы характеризовать матрицами перехода, то совокупность каналов, меньших данного канала образует в пространстве матриц выпуклое тело. В самом деле, канал с матрицей может быть получен из канала объединением Та) и

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

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

Доказательство. Пусть и множество превращает канал в канал где Т и — чистые каналы.

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

Рис. 4. Общий двоичный канал.

Рис. 5. Шестиугольник из двоичных каналов, включенных в типичный двоичный канал.

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

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

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

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

Рис. 6. Наибольшая нижняя граница X и наименьшая верхняя граница У двух сравниваемых двоичных каналов.

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

На рис. 5 двоичные симметричные каналы лежат на диагонали, идущей от (1,0) к (0,1). Из этого следует, что взятый нами канал включает, в частности, некоторый двоичный симметричный канал X, изображенный точкой квадрата, что для нашего примера дает (3/5, 5/8). Кроме того, наш канал включается в двоичный симметричный канал с координатами что для нашею частного случая превращается в 1/3, 2/3. Такие включения дают простые верхние и нижние оценки для пропускной способности общего двоичного канала через более удобные характеристики подходящим образом подобранных симметричных каналов.

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