Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
0,8 20 5,91 ХЮ_3 2,12хЮ-2 6,29хЮ-3 6,95хЮ-3
100 5,60хЮ-10 4.26ХЮ-9 5,66ХЮ-10 1,82x10-»
Иллюстрация поведения различных оценок хвостов биномиального распределения Рг (w>jVoc), где w— сумма N независимых одинаково распределенных двоичных случайных величин, принимающих значение 1 с вероятностью е. Гауссовское приближение имеет вид:
1—Ф
N(a — е)-
VNe(l — е)
, где ф(х)=| (2я) У* exp (—z"/2)dz.
Рис. 5.4.2.
Эти выражения остаются также в силе для непрерывных случайных величин гп, если exp (szn) <Z оо для s в некоторой окрестности нуля.
Для различных биномиальных распределений на рис. 5.4.2 проведено сравнение асимптотического выражения, границы Чернова, истинного значения и гауссовского приближения. Можно заметить, что граница Чернова и асимптотические выражения в (5.4.24) являются плохими приближениями при А, близких к w (при малых s), но что при больших А гауссовское приближение является плохим, а граница Чернова и асимптотическое выражение — хорошими.
5.5. СЛУЧАЙНЫЕ КОДОВЫЕ СЛОВА
В последнем параграфе было показано, что вероятность ошибочного декодирования для двух кодовых слов стремится к нулю экспоненциально с ростом длины блока. Вместе с тем в этом случае передается только один двоичный символ источника на блок, так что вероятность ошибки уменьшается только за счет скорости передачи. Ясно, что единственной возможностью для снижения вероятности ошибки без уменьшения скорости передачи является рассмотрение большего множества кодовых слов.
Мы хотим исследовать минимально достижимую вероятность ошибочного декодирования как функцию скорости R, длины блока N и канала. Будет найдена верхняя граница для этой вероятности ошибочного декодирования, которая убывает экспоненциально с длиной блока для всех скоростей, меньших пропускной способности. Эта граница выводится с помощью рассмотрения ансамбля кодов, а не одно-
147
го-единственного хорошего кода. Этот своеобразный подход продиктован тем, что для представляющих интерес значений N и R не известно метода отыскания кодов, которые минимизируют вероятность ошибочного декодирования; и даже, если бы такие коды могли быть найдены, прямое вычисление вероятности ошибки было бы невозможным из-за большого числа последовательностей, возможных на приемном конце. В следующей главе будут рассмотрены несколько конкретных методов блокового кодирования и декодирования, которые интересны в силу относительной простоты их реализаций. Для некоторых из этих методов можно подсчитать вероятность ошибки, но при больших значениях N эта вероятность ошибки будет на много больше, чем верхняя граница для минимальной вероятности ошибки, выведенная здесь.
Для того чтобы определить ансамбль блоковых кодов, обозначим через Qn (х) произвольное распределение вероятности на множестве последовательностей длины N на входе канала и будем считать, что все кодовые слова выбираются независимо с одними и теми же вероятностями. Таким образом, вероятность некоторого частного кода х1;
м
..., хм в этом ансамбле кодов равна П QN (хт). Каждый код из ан-
т— 1
самбля имеет свою собственную вероятность ошибочного декодирования, возникающую при декодировании по максимуму правдоподобия для этого кода. Мы оценим сверху математическое ожидание (по ансамблю) этой вероятности ошибки. Так как по крайней мере один код из ансамбля должен иметь такую же вероятность ошибки, как среднее по ансамблю, это даст границу для вероятности ошибки наилучшего кода (т. е. кода с минимальной Ре).
Для того чтобы понять, почему этот подход является разумным, рассмотрим опять двоичный симметричный канал. Если выбрать для этого канала два кодовых слова длины N случайно, выбирая символы каждого слова независимо и принимающими значения 0 или 1 с равными вероятностями, то при больших N эти два кодовых слова будут с большой вероятностью отличаться приближенно в половине позиций блока. Из (5.3.12) следует, что если х1пф х2п, то mingn(s) — = 2Уе(1 —е). Если xlt п = х% п, то gn (s) = 1 при 0 < s < 1. Следовательно, для двух кодовых слов, отличающихся в А72 позициях, вероятность ошибки ограничена выражением
Ре,т. [2У б (1 — г)]ы 12, т — 1,2. (5.5.1)
Это не является средней вероятностью ошибки по ансамблю кодов; это просто вероятность ошибки для типичного кода из ансамбля. Это отличие в дальнейшем будет обсуждено более детально.
Показатель степени в (5.5.1) равен половине показателя для двух кодовых слов, отличающихся в каждой позиции, но Р е все еще стремится к 0 экспоненциально по N. В качестве компенсации за это уменьшение показателя степени появляется способ рассмотрения больших множеств кодовых слов, не требующий заботы о детальном выборе слов. Однако для больших множеств кодовых слов каждое кодовое слово не может отличаться от любого другого кодового слова во всех 148
