3.7.2. Симметричные по выходу каналы с двоичным входом

Нижнюю границу при нулевой скорости для этого более общего класса так же легко получить, как и для ДСК. Первым шагом опять будет оценка сверху минимального расстояния между кодовыми векторами. Рассуждения напоминают рассмотренный выше случай гауссовского канала. Мы резюмируем их в следующей лемме, принадлежащей Плоткину [1951].

Лемма 3.7.1. Оценка Плоткина. Для любого двоичного кода, состоящего из векторов размерности нормированное минимальное расстояние между кодовыми векторами оценивается сверху неравенством

Доказательство. Сведем все двоичные векторы в матрицу размерами

Обозначим через расстояние Хэмминга между рассмотрим сумму всех попарных расстояний Хэмминга (подсчитывая, следовательно, каждый недиагональный член дважды и не заботясь о случаях поскольку их вклад в сумму равен 0):

где

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

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

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

Сложив (3.7.8) с (3.7.9), получим

поскольку множитель достигает максимума при Подставив это неравенство в (3.7.7), получим

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

имеем

Объединив неравенство (3.7.11) с (3.7.12), получаем

что в точности совпадает с (3.7.6), и, следовательно, лемма доказана.

Дальнейшие рассуждения аналогичны рассуждениям в случае АБГШ канала. Обозначив через два кодовых вектора на минимальном расстоянии, воспользуемся еще раз неравенством (3.7.2).

В § 3.5 мы показали, что вероятность ошибки для двух сообщений оценивается неравенством (3.5.8), где

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

где индексом пронумерованы компоненты, такие, что Допустим, для I из этих компонент и для остальных. Тогда (3.7.13) переписывается в виде

Но для рассматриваемого класса каналов выходное пространство симметрично [т. е. всякому соответствует , такое, что Следовательно,

Откуда

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

Следовательно, выбирая из получим

Теперь, как и в (3.7.5), воспользуемся (3.7.2):

где

Положив для любой фиксированной скорости, получим из леммы 3.7.1 при растущих

Поэтому

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

Мы вновь получили результат, асимптотически точный при нулевой скорости. Он справедлив для широкого класса каналов без памяти с дискретным, входом (Шеннон, Галлагер и Берлекэмп [1967]).