§ 3.6. Симметричные дискретные каналы без памяти

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

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

Заметим, что сумма элементов любой строки равна единице.

Определение 3.6.1. Дискретный канал называется симметричным по входу, если все строки матрицы переходных вероятностей образованы перестановками элементов первой строки.

Определение 3.6.2. Дискретный канал называется симметричным по выходу, если все столбцы матрицы переходных вероятностей образованы перестановками элементов первого столбца.

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

Имеют место следующие два свойства рассматриваемых каналов.

Свойство 1. Если канал симметричен по входу, то условная энтропия не зависит от распределения вероятностей на входе и равна

где элементы первой строки матрицы (3.6.1).

Для доказательства заметим, что причем для любого

Свойство 2. Если канал симметричен по выходу и распределение вероятностей на его входных сигналах равномерное, то равномерным является распределение вероятностей на его выходных сигналах.

Действительно, пусть тогда

где элементы первого столбца матрицы (3.6.1). Так как правая часть (3.6.4) не зависит от то выходные сигналы канала равновероятны.

Найдем информационную емкость С симметричного дискретного канала без памяти.

Как показано в предыдущем параграфе,

где максимум разыскивается по всем возможным распределениям вероятностен на множестве X входных сигналов канала.

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

Рис. 3.6.1. Информационная емкость ДСК как функция от вероятности ошибки.

Если канал симметричен по входу, но не симметричен по выходу, может не существовать распределения на входе, при котором выходные сигналы равновероятны. В этом случае

Пример 3.6.1. Найдем информационную емкость L-ичного симметричного канала, переходные вероятности которого

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

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

При получается двоичный симметричный канал (ДСК), для которого

На рис. 2.5.2 приведен граф переходов в таком канале. На рис. 3.6.1 показана зависимость информационной емкости ДСК от вероятности ошибки Вероятность соответствует «обрыву канала и нулевой пропускной способности. При стратегия приемника заключается в том, чтобы при получении решение принимать в пользу Такая стратегия соответствует каналу с вероятностью ошибки

Пример 3.6.2. Найдем информационную емкость двоичного стирающего канала. Предположим, что множество X состоит из двух сигналов, которые мы

условно обозначим, через множество из трех сигналов 0, 1, 0. Матрица переходных вероятностей имеет вид

где обозначено

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

и

В частном случае, когда в ошибки отсутствуют, т. е. когда