3.6. Нижняя граница сферической упаковки

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

3.6.1. Неограниченный на полосе АБГШ канал с сигналами равной энергии

Допустим, что каждый из сигналов имеет продолжительность секунд и энергию тогда как канал с аддитивным гауссовским шумом имеет одностороннюю спектральную плотность Под отсутствием ограничений на полосу частот мы понимаем отсутствие ограничений на размерность сигналов N или на (см. § 2.6). Как было показано в § 2.1, любой набор из сигналов конечной энергии можно представить, используя не более измерений. Следовательно, отсутствие ограничений на полосу частот означает, что мы не требуем, чтобы N было меньше В § 2.1 мы убедились, что функция правдоподобия при условии, что по такому каналу передан сигнальный вектор, задается равенством (2.1.15), где

Для наших целей ее удобнее записать в виде

Сначала проведем нижнюю оценку вероятности

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

а граничные точки распределяются по областям произвольным образом. В нашем распоряжении имеется теорема 3.5.1. Ясно, что мы хотели бы связать одним из неравенств теоремы, но мы пока не знаем, какую условную плотность и область суммирования выбрать для другого неравенства. Нам удастся продвинуться в решении задачи, если, как и в последнем примере предыдущего параграфа [см. формулы (3.5.31) — (3.5.38)], выбирать для второго неравенства некоторую удобную «фиктивную» плотность

и принять

положив

Тогда мы удовлетворим условиям и предположениям теоремы

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

где

Подставив (3.6.2) и (3.6.5) в (3.6.9) и воспользовавшись (3.6.1) получим

Таким образом, функция инвариантна по отношению к ориентации сигнального вектора и зависит только от его энергии. Чтобы понять, насколько важна в (3.6.7) вспомогательная переменная просуммируем ее по всем сообщениям Оптимальные решающие области (3.6.4) не пересекаются и в сумме покрывают все -мерное пространство; поэтому имеем

Следовательно, хотя бы для одного из сообщений должно выполняться неравенство

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

мы получаем из (3.6.12), (3.6.13) и (3.6.7) — (3.6.10), что должна выполняться хотя бы одна из следующих пар неравенств

где

Следовательно,

В последних трех соотношениях мы воспользовались обозначениями § 2.5, а именно,

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

С помощью соотношений (3.6.16) - (3.6.18), (2.5.13) и (2.5.14) нижние границы (3.6.14) и (3.6.15) превращаются в альтернативные границы

или

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

где

или, что то же

где

Тогда неравенство (3.6.19) не удовлетворяется и, следовательно, должно удовлетворяться неравенство (3.6.20) при В результате получаем

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

Выберем лучший код, состоящий из сигналов. Из (3.6.22) следует, что максимальная вероятность ошибки для этого набора сигналов оценивается снизу неравенством

где

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

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

где

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

Как побочное следствие из приведенных результатов вытекает, что в неограниченном по полосе АБГШ канале ортогональные сигналы асимптотически оптимальны (при (Наборы регулярных симплексных сигналов всегда лучше наборов ортогональных сигналов, но асимптотически они неразличимы.) Однако главной целью частного примера явилась демонстрация весьма сильного метода вывода нижних границ, асимптотически точных всех скоростях, исключая малые. По причинам исторического характера, связанным с классическим выводом для уже рассмотренного частного случая и следующего ниже примера (Фано [1961]), эта граница называется границей сферической упаковки. (Другой вывод границы сферической упаковки см. в задачах 3.22 и 3.24.)