7.3.1. ВЕРОЯТНОСТЬ ОШИБКИ ОПТИМАЛЬНОГО ДЕКОДИРОВАНИЯ ДЛЯ КОДОВ С ФИКСИРОВАННОЙ ДЛИНОЙ БЛОКОВ (ЭКСПОНЕНТЫ ВЕРОЯТНОСТЕЙ ОШИБОК)

Пусть имеется некоторый канал связи, который описывается условными переходными вероятностями где его входной и выходной алфавиты, а и означают всевозможные последовательности длины из алфавитов соответственно. Обозначим через вероятность ошибочного декодирования в таком канале при использовании некоторого кода V, состоящего из комбинаций, и алгоритма декодирования по максимуму правдоподобия, если передаётся сообщение Достаточно общая верхняя граница для при наилучшем выборе кода V была получена Галлагером [8]. Сформулируем её в виде теоремы.

Теорема 7.2. Существует блоковый код V длины состоящий из комбинаций, для которого при передаче произвольного сообщения

где переходная условная вероятность для блоков длины в заданном канале связи; произвольное вероятностное распределение на входных блоках длины

Для доказательства теоремы потребуется следующая простая лемма.

Лемма. Пусть вероятности событий Тогда при любом вероятность объединения событий имеет границу

Доказательство леммы. Используя известную аддитивную границу (неравенство Буля) и тривиальную границу для вероятности любого события, получаем

Если оказывается меньше 1, то эта величина лишь увеличивается при возведении в степень и (7.9) следует из (7.10). Если же то и тогда (7.9) следует из (7.11).

Доказательство теоремы Верхняя граница (7.8) выводится с помошью рассмотрения так называемого ансамбля кодов, а не одного "хорошего" кода. Ансамбль блоковых кодов задаётся следующим образом. Определим сначала произвольное распределение вероятностей на всех блоках длины составленных из входных символов канала связи, и будем считать, что все кодовые слова выбираются независимо друг от друга с этими вероятностями. Таким образом, вероятность выбора некоторого частного кода в этом ансамбле равна Каждый код из ансамбля имеет свою вероятность ошибочного декодирования при декодировании по максимуму правдоподобия. Если рассчитать среднюю по всему ансамблю кодов вероятность ошибочного декодирования, то она даст верхнюю границу ров для наилучшего кола (т.е. кода с инимальной величиной .

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

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

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

Если в (7.13) имеет место строгое неравенство, то декодер максимального правдоподобия примет решение о передаче сообщения сделает ошибку (При наличии равенства в (7 13) ошибка произойдёт не обязательно.) Поэтому, используя лемму, получаем

Согласно определению события имеем

Легко убедиться, что правую часть (7.15) можно ограничить сверху, если умножить каждое слагаемое в нём на при любом распространяя суммирование на все Это даёт верхнюю границу для

Видно, что является "глухой" переменной суммирования в (7.16), и поэтому эта граница фактически не зависит от Подставляя (7.16) в (7.14), получаем

Далее, подставляя (7.17) в (7.12), будем иметь

Подставляя в (7.18) и замечая, что является также "глухой" переменной суммирования, получаем утверждение теоремы в виде неравенства (7.8)

Используем неравенство (7.8) для оценки в дискретных каналах без памяти, описываемых переходными вероятностями где Определим в этом случае вероятность случайного выбора кодового слова х как

Тогда (7.8) преобразуется к виду

где объёмы алфавитов входа и выхода канала соответственно.

Границу (7.19) можно представить в экспоненциальной форме, заменив на среднюю по сообщениям вероятность ошибки при произвольном наборе вероятностей этих сообщений:

где

Чтобы найти наилучшую верхнюю границу, необходимо максимизировать

Решение этой задачи для произвольных дискретных каналов представляет определённые трудности. Однако для без памяти с вероятностью ошибки символа получается решение в замкнутом виде

где

при

и

где удовлетворяет уравнению

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

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

Экспоненты вероятностей (7.20), (7.21) позволяют рассчитать энергетический выигрыш от применения кодирования (ЭВК) как функцию заданной верности скорости кода и длины кодового блока Однако в отличие от асимптотического случая здесь возникает одна дополнительная сложность. Пусть, например, два кода с одинаковыми скоростями длинами имеют одинаковые вероятности Можно ли считать, что в обоих случаях обеспечивается действительно одинаковая верность передачи сообщений? Интуиция подсказывает нам, что во втором случае надёжность передачи будет, наверное, больше, чем в первом. Постараемся облечь теперь наши интуитивные ощущения в более строгую форму. Пусть передаётся информация такого типа, что количество ошибок на сеансе связи, состоящем из информационных бит, не играет существенной роли для оценивания качества передачи. Критерием верности тогда служит вероятность абсолютно правильного приёма всех элементов. Очевидно, что при использовании двоичного кода

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

где число кодовых комбинаций на интервале анализа.

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

для которой сделанный выше вывод также оказывается справедливым.)

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

Преобразуя (7.27), получаем

(Видно, что оказалось не зависящей от

Если то для справедливо следующее приближённое выражение:

Величину (соответственно для наилучшего кода можно найти из (7.21).

Расчёт энергетического выигрыша одной дискретной системы передачи над другой (ЭВС) можно в общем случае вычислить при по формуле (5.108), ЭВК. для заданного кода можно находить при заданной вероятности и по формуле (6.61).

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

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

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