2. Оптимальные блоковые коды

При заданном блоковом коде решение вопроса об оптимальном способе передачи по ДСК непосредственно вытекает (по крайней мере, в принципе) из элементарных правил теории статистических решений, изложенных выше. Остается открытым вопрос о дальнейшей минимизации вероятности ошибки — теперь уже относительно выбора кодовой книги

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

Рассмотрим кодовую книгу, содержащую последовательностей длины Так как ДСК может породить с некоторой ненулевой вероятностью любую из возможных двоичных шумовых последовательностей то совокупность всех возможных сообщений у на

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

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

Границу для вероятности ошибки в случае кодового множества мы можем найти непосредственными рассуждениями. Каждая из непересекающихся областей декодирования будет содержать последовательностей, всего областей декодирования будет а последовательностей, которые должны быть разделены по областям, будет Итак, мы получаем границу Хэмминга [16] для у.

Для того чтобы найти наибольшее удовлетворяющее этому неравенству, удобно ввести новые параметры положив

Тогда соотношение (2.12) можно продолжить влево, написав, что

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

Подставляя в соотношение (2.15), замечая, что и переходя к логарифмам, находим

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

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

Обозначение с подстрочным индексом используется здесь и ниже для обозначения вероятности, вычисленной для шумовой последовательности действительно имевшей место. В приложении мы покажем также, что

где

Положив в соответствии с (2.17), мы получаем, что асимптотически при больших

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

Геометрическая интерпретация. Мы заинтересованы в первую очередь в том, чтобы научиться оценивать ошибки кодов в пределе при Ясно, что с этой точки зрения поучительно исследовать экспоненциальное поведение нашей границы при больших

На рис. 5 изображена кривая энтропии Производная функции по равна Таким образом, равенство (2.19) представляет собой уравнение касательной к кривой в точке с абсциссой, равной переходной вероятности в канале. Величина представляет собой расстояние по вертикали между кривой энтропии и касательной к кривой в точке Из соотношения (2.21) вытекает, что

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

Из соотношения (2.22) и рис. 5 просто вытекают необходимые условия, которые должны выполняться, если мы хотим приблизить к нулю вероятность ошибки. Существуют три следующие альтернативы.

1. Уменьшить улучшив канал.

2. Увеличить разность уменьшив скорость передачи

3. Увеличить длину блока

Выводы, аналогичные полученным для двоичного симметричного канала, верны также для непрерывного канала, заключенного внутри двоичной системы передачи — мы рассматривали его в гл. 1.

Рис. 5. Геометрическая интерпретация. Пропускная способность С равна Прямая То касательная к в точке Скорость передачи равна Условие эквивалентно условию

До сих пор практически использовались только методы 1 и 2. Однако по мере того, как цифровые вычислительные машины становятся доступными для использования в технике связи,

создаются реальные возможности использования метода 3. Настоящая публикация связана в основном с применением именно этого третьего метода.