3.6.2. Двоичный симметричный канал

Теперь займемся применением теоремы 3.5.1 к ДСК, рассматривавшемуся чаще других, и, по существу, повторим рассуждения, использованные в случае АБГШ канала, по-другому объяснив их. В § 2.8 мы показали, что функция правдоподобия этого канала задается равенством (2.8.3), где расстояние Хэмминга между входным и выходным векторами канала. В качестве фиктивного распределения в этом случае возьмем равномерное распределение

Здесь мы отождествляем следовательно, Поскольку в этих

обозначениях условия теоремы 3.5.1 удовлетворяются, можно воспользоваться (3.5.1) и (3.5.2), из которых следует, что для сообщения справедливо хотя бы одно из пары следующих неравенств:

где

а . Поскольку некоторый -мерный двоичный вектор, а у пробегает множество всех таких векторов, то существуют в точности один такой вектор (именно что векторов с (на расстоянии Хэмминга 1 от векторов, для которых и вообще векторов у, таких, что Поэтому (3.6.30) можно переписать в виде суммы

Чтобы задать следует учесть, что суть непересекающиеся решающие области, в сумме покрывающие все пространство Следовательно, суммируя по всем сообщениям, имеем

Поэтому

для некоторого и из (3.6.28) и получаем два альтернативных неравенства:

где из (3.6.31) имеем

и где

Подставив

получим из (3.6.35) и (3.6.36) после ряда алгебраических преобразований равенства

где

Отметим, что это соотношение союпадает с (3.4.1), задающим для ДСК основную функцию показателя экспоненты при оптимизированном входном взвешивающем распределении

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

и выбрав положительное Положив и воспользовавшись равенством (3.6.40), получим

При подстановке этого значения в неравенство (3.6.33) оно обращается в равенство, и, следовательно, в (3.6.34) должно выполняться строгое неравенство. Поэтому из (3.6.41) имеем

Рассуждая точно так же, как и при выводе неравенства (3.6.26) получим

где задается параметрическими соотношениями

Предельные значения определяются свойствами функции (см. § 3.2): ее выпуклости и монотонного убывания, а также Но тогда (3.6.46) совпадает в области больших скоростей, с верхней границей для поскольку для ДСК последняя оптимизируется выбором при всех скоростях. Для меньших скоростей, показатель экспоненты нижней границы продолжает убывать быстрее, чем линейно, поскольку эта функция выпукла тогда как показатель экспоненты верхней границы линеен (рис. 3.10). В следующих двух параграфах мы уменьшим зазор между верхней и нижней границами при малых скоростях.

По аналогия с (3.2.6), (3.2.8) и (3.2.12) показатель экспоненты (3.6.46) нижней границы можно записать также в виде

Поэтому ее можно построить по функции (см. рис. 3.1 и 3.2) так же, как и в случае верхней границы, с той лишь разницей, что построение не ограничивается значением при (см. рис. 3.3а), а продолжается при всех следовательно, достигается точка Этим, кстати, объясняется, почему границы расходятся при скоростях менее .

Таким образом, для ДСК мы получили почти тот же результат, что и для АБГШ канала, а именно, показали, что нижняя граница ведет себя асимптотически так же, как и верхняя (экспоненциально совпадает) при всех скоростях, превышающих некоторую критическую промежуточную скорость. Для двух приведенных выше частных случаев этот результат можно получить, воспользовавшись более ясными традиционными рассуждениями, называемыми методом упаковки сфер (см., например, Галлагер [1968]). Мы выбрали менее очевидный способ по двум причинам: во-первых, он дополняет и иллюстрирует возможности теоремы 3.5.1 — усиленного варианта леммы Неймана-Пирсона; во-вторых, на нем мы продемонстрировали основные моменты доказательства для случая произвольного дискретного времени канала без памяти.

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

Теорема 3.6.1 (Шеннон, Галлагер и Берлекэмп [1967]).

Рис. 3.10. Экспоненты и нижняя граница при малых скоростях

Рис. 3.11. Границы для верхняя граница Плоткина; 2 — верхняя граница Элайса; 3 — нижняя граница Варшамова — Гилберта

При использовании наилучшего кода из векторов [со скоростью в произвольном дискретном канале без памяти выполняется неравенство

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