3.9. Гипотезы и обращения

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

Улучшение нижней границы в указанной области вероятнее всего будет связано с улучшением верхней границы минимального расстояния. Для симметричных по выходу каналов с двоичным входом мы нашли в § 3.7 нижнюю границу [см. § 3.7, неравенство (3.7.18)]. Чтобы закончить оценку вероятности ошибки, нужно получить верхнюю границу для В § 3.7 была выведена граница Плоткина где при приведшая нас к асимптотически точной при нулевой скорости нижней границе (3.7.19). Ясно, что чем больше скорость, тем больше векторов располагается в N-мерном пространстве и тем меньше становится достижимое минимальное расстояние. Можно так модифицировать границу Плоткина, что получающаяся граница убывает со скоростью линейно (см. задачу 3.33), а именно:

но и она не точна. Более точная верхняя граница для принадлежит Элайсу [1960]. Представляет интерес также лучшая из известных нижних границ для она была, по существу, конструктивно получена Гилбертом [1952] (см. задачу 3.34). Границу Гилберта можно также получить, воспользовавшись верхней границей с выбрасыванием (3.4.8) и нижней границей вероятности ошибки (3.7.18) для симметричных по выходу каналов с двоичным входом. Нижняя граница Гцлберта и верхняя граница Элайса нормированного минимального расстояния для двоичного кода с N символами имеют следующий вид:

где функция, определяемая из соотношения

Верхние границы Плоткина и Элайса и нижняя граница Гилберта приведены на рис. 3.11 (см. с. 170).

Соблазнительно предположить, как это сделали Шеннон, Галлагер и Берлекэмп [1967], что в действительности граница Гилберта точна, т. е. что

где задается уравнением (3.9.3). Тогда по крайней мере для симметричных по выходу каналов с двоичным входом с помощью (3.7.18) и (3.9.3) получим неравенство

где (гипотеза),

Довольно интересно, что для рассматриваемых каналов это асимптотически совпадает с границей с выбрасыванием, выведенной в § 3.4 [см. (3.4.8)], так что

И, наконец, для скоростей из области верхняя граница представляет собой отрезок прямой с наклоном —1, касательной к криволинейным участкам, соответствующим малым и большим скоростям в точках соответственно. Аналогичным образом, если бы была справедлива нижняя граница (3.9.6), мы могли бы, воспользовавшись теоремой 3.8.1, соединить ее точку, соответствующую максимальной скорости с точкой границы сферической упаковки, соответствующей скорости той же самой прямой. Следовательно, по крайней мере для симметричных по выходу каналов с двоичным входом отсутствующее звено в доказательстве асимптотической точности лучшей верхней границы состоит в доказательстве справедливости гипотезы об асимптотической точности границы Гилберта (3.9.4).

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

В настоящей главе рассматривалось поведение каналов только при скоростях ниже пропускной способности. Поскольку показатели экспонент как верхних, так и нижних границ стремились к нулю, когда снизу, должно быть ясно, что на хорошее поведение при скоростях, больших пропускной способности С, надежд мало. И действительно, при скоростях, превышающих пропускную способность, можно получить два негативных утверждения. Они известны под названием обращений теоремы кодирования. Первое, более общее принадлежит Фано [1952] (см. § 1.3). Согласно результатам этого параграфа, независимо от методов кодирования и декодирования, средняя (на символ) вероятность ошибки всегда превышает некоторую положительную величину. Второе обращение, справедливое только для блочных кодов, представляет собой следующий более сильный результат.

Теорема 3.9.1. Строгое обращение теоремы кодирования [Аримото, 1973]. Для любого дискретного по входу канала без памяти с пропускной способностью С и для любого кода размерности N со скоростью вероятность

ошибки при равных априорных вероятностях сообщений оценивается снизу неравенством

а задается в (3.1.18).

Заметим, что двойственна по форме к функции введенной в § 3.1. Главное отличие состоит в том, что параметр ограничен интервалом .

Доказательство. Оценим среднюю вероятность ошибки правильного декодирования, рассмотрев соотношение

Оно следует из того, что оптимальные решающие области задаются соотношением

Для произвольного имеем

Определив на кодовых словах распределение специального вида, а именно

Подставив последнее выражение в (3.9.9), получим границу

где максимум берется по всем распределениям на а не только по распределениям специального вида (3.9.12). Введем параметр

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

В лемме 3.2.2 мы показали, что функция

выпукла на множестве распределений заданных на при Для это же самое доказательство показывает, что функция (3.9.17) выпукла на множестве распределений на Ограничим теперь полуоткрытым интервалом Теорема Куна-Таккера (см. приложение 3Б) показывает, что функция (3.9.17) имеет единственный максимум по распределениям на и что он удовлетворяет необходимому и достаточному условию

где

для всех причем равенство в (3.9.18) достигается, если Условию максимума удовлетворяет распределение вида

где, в свою очередь, удовлетворяет необходимому и достаточному условию

а

причем равенство (3.9.20) достигается для всех таких, что Поэтому из (3.9.16) получаем следующее соотношение:

Минимизация границы по приводит к неравенству

а отсюда при использовании равенства получается неравенство (3 9.7)

Исследуя свойства при можно показать, что больше нуля при Применяя доказанную в приложении лемму 3.2.1, получим для

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

и

Используя эти свойства и рассуждения, двойственные проведенным в § 3.2 при доказательстве того, что при можно показать, что при

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