1.4.2 Границы случайного кодирования

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

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

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

Определим как число кодовых слов в коде находящихся на расстоянии от переданного кодового слова Тогда средняя вероятность ошибочной последовательности может быть записана в виде

Последнее неравенство было выведено для границы

Подставляя (1.57) в (1.56) и меняя порядок суммирования, получаем

Поскольку член в квадратных скобках содержит усреднение по всем возможным кодовым словам, он представляет собой «среднее» число кодовых слов, находящихся на расстоянии от переданного кодового слова. Это число не зависит от и равно Таким образом,

Определим параметр экспоненциальной границы равенством

Тогда среднюю вероятность ошибочной последовательности можно оценить следующим образом:

Величину называют также вычислительной скоростью и обозначают . (Этот параметр важен в теории последовательного

декодирования, рассматриваемого в гл. 7.) Параметр можно определить и для дискретных каналов без памяти. Его значение для таких каналов будет приведено далее.

Граница (1.61) показывает, что при вероятность ошибки можно сделать сколь, угодно малой, если использовать достаточно длинные коды. Поскольку в эту границу входит вероятность ошибки, усредненная по всем возможным кодам, должны существовать коды с еще меньшей вероятностью ошибки. Положив где очень мало, можно получить границу для достижимого выигрыша от кодирования. Результат показан на рис. 1.12. На этом рисунке приведена зависимость от минимально возможного при данном значения для которого (1.61) еще можно сделать сколь угодно малым. Поскольку при вероятность ошибки стремится к 0, любое ненулевое значение вероятности ошибки можно получить при некотором конечном Поэтому мы получаем границу для выигрыша от кодирования. Известно, например, что для обеспечения вероятности ошибки в системе с идеальной ФМ без кодирования необходимо иметь Из рис. 1.12 следует, что, используя код с можно получить сколь угодно малую вероятность ошибки при уровне Таким образом, при можно обеспечить выигрыш от кодирования, не меньший используя код с Заметим также, что, когда скорость кода стремится к 0, достижимый выигрыш от кодирования приближается к Таким образом, можно утверждать, что использование кодов со скоростью, намного меньшей 1/2. приводит лишь к небольшому улучшению характеристики. Наконец, отметим, что при увеличении скорости кода и сохранении двоичной модуляции получить выигрыш от кодирования оказывается все более трудным.

Рис. 1.12. Зависимость значения необходимого для достижения при двоичных сигналах, от скорости кода:

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

то при неограниченном увеличении длины кода можно вести передачу со сколь угодно малой вероятностью ошибки. Можно

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

где показатель вероятности ошибки для дискретного канала без памяти определяется формулой

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

Эта функция определена для дискретного канала без памяти с К входными символами, выходными символами и переходными вероятностями Вектор является распределением вероятностей на входном алфавите. Результат максимизации функции Галлагера по обозначается Для симметричных каналов (которые представляют наибольший интерес) оптимизирующее распределение является равномерным, т. е.

Показатель вероятности ошибки неотрицателен при всех скоростях, меньших пропускной способности канала С. Таким образом, для приведенной формы границы случайного кодирования при любом и при достаточно большом существует код, вероятность ошибки которого не больше произвольного заранее заданного значения Типичное «поведение» показателя вероятности ошибки показано на рис. 1.13, где приведен график для Там же приведен показатель вероятности ошибки в виде (1.61), который равен Ясно, что границы (1.61) и (1.62) совпадают при низких скоростях, однако при высоких скоростях граница (1.62) существенно лучше. Оказывается, что для любого дискретного канала без памяти величина равна показателю вероятности ошибки при нулевой скорости, т. е.

Рис. 1.13. Показатель вероятности ошибки при

Рис. 1.14. Выигрыш от кодирования, предсказываемый границами случайного кодирования, при

Поэтому для симметричного канала

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

Эти выражения для были использованы при построении кривых для на рис. 1.12.

Приведенные границы можно также использовать для вычисления длины блока, которая наверняка позволит добиться данного выигрыша от кодирования. Результат для кода с показан на рис. 1.14. Оказывается, однако, что при этом получаются слишком большие значения Известно, например, что квадратично-вычетный -код (который будет рассматриваться в подразд. 2.3.5) с бесконечным квантованием дает выигрыш от кодирования примерно а -код Голея — примерно при двухуровневом и при многоуровневом квантовании. Фактические характеристики обоих кодов существенно лучше характеристик, предсказываемых границами.

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

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