Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Теперь мы почти подготовлены для отыскания верхней границы ~Ре, т Для более чем двух кодовых слов, но вначале приведем другой вывод границы (5.5.4). Заметим, что Рд х является средним по хь х2 и у. Когда сообщение 1 кодируется в Xi, то у происходит с вероятностью -P^(y|xi), и будем считать, что ошибка возникает, если PN (у | х2) ^ PN (у | Xi). Таким в виде
Рис. 5.5.1. Граница ошибочного декодирования для двух кодовых слов. Сравнение между случайным выбором и случаем, когда имеется отличие в N/2 позициях.
образом, Ре 1 можно записать
Ре,\ =2iQw (хх)ЕРлг(у |хх)Рг [ошибка |m= 1, xlt у], (5.5.12)
х< У
где Рг [ошибка \т = 1, хь у] — вероятность (по ансамблю выборов х2) того, что произойдет ошибка, при условии, что на кодер поступило сообщение 1, первым кодовым словом является хх и было принято у. Имеем
Рг [ошибка | т = 1, хх, у]
2 Qn (х2). (5.5.13)
(у! х2) >Pn (у f xi)
При PN (у | х2) > 0 выражение (5.5.13) можно ограничить сверху, умножая каждое слагаемое на [/V (у ] х2)/РN (у | Xi)]s при любом s > 0. Далее, строя границу с помощью суммирования по всем х2, получаем
Рг [ошибка | m = 1, Xi, у]< ^ Qn (х2)
PN (У I хг)
PN(y I Xl)
(5.5.14)
Вместе с тем этот результат можно интерпретировать как границу Чернова для
Pr In
Pn (У I хз)
PN (У I xi)
О
где в качестве вероятностной меры используется QN (х2).
Подставляя (5.5.14) в (5.5.12), получаем снова (5.5.4). Другое доказательство понадобилось здесь потому, что оно может быть легко обобщено на случай произвольного числа кодовых слов.
151
5.6. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ КОДА С ЧИСЛОМ СЛОВ, БОЛЬШИМ ДВУХ
Теорема 5.6.1. Пусть PN (у | х) — переходные вероятности для последовательностей длины N ^ I ъ дискретном канале. Пусть QN (х) — произвольное распределение вероятности, заданное на входных последовательностях. Для данного числа М ^ 2 кодовых слов с длиной блока N рассмотрим ансамбль кодов, в котором слова выбираются независимо с вероятностной мерой QN (х). Предположим, что на кодер подступает некоторое произвольное сообщение т, 1 < т М, й что используется декодирование по максимуму правдоподобия. Тогда средняя по этому ансамблю кодов вероятность ошибочного декодирования ограничена при любом выборе р, 0<р ^ 1, неравенством
Ре,т<(М- 1)Р5Ц2 <Мх)РИУ|х)1/(1+Р)]1+Р. (5.6.1)
У X
Для доказательства теоремы понадобится следующая простая лемма.
Лемма. Пусть Р (Лх), ..., Р (Ам) являются вероятностями событий Alt ..., Ам и Р (U Ат) является вероятностью их объедине-
т
ния. При любом р, 0 < р 1, имеем
Р("Ч
(5.6.2)
Доказательство леммы. Имеем
м
^(и (т1,Р(Лт)’ {5-6-3)
1т 1 ( 1. (5.6.4)
Неравенство (5.6.3) является обычной границей для вероятностей
(см. задачу 2.16), а (5.6.4) является очевидной границей для вероятности. Если 2Р(Лт) меньше чем 1, то 2Р (Ат) увеличивается
при возведении ее в степень р и (5.6.2) следует из (5.6.3). Обратно, если 2Р (Ат) ^ 1, то [2Р (Лт)]р ^ 1, так что (5.6.2) следует из (5.6.4). | Доказательство теоремы. Имеем
Ре. rn = S Ъ Qn (Xj Pn (у | xm) Рг [ошибка | т, хт, у], (5.6.5)
хту
где Рг [ошибка | т, хт, у] — условная вероятность ошибочного декодирования при условии, во-первых, что на кодер поступило сообщение т, во-вторых, что заданная последовательность хт была выбрана в качестве т-vo кодового слова, и, в-третьих, что была принята последовательность у. Суммирование производится соответственно по всем входным и всем выходным последовательностям канала длины N.
152
При заданных т, хт, у определим событие Ат> для каждого fri ф т как событие, состоящее в том, что выбирается такое кодовое слово хт', для которого
Pn (у| Xm')>PN (y|xj.
Теперь имеем
Рг [ошибка | т, хт, у] ^ Р ( U Ат- ^ (5.6.6)
\т'фт )
<Г 2 Р(Ат’) 1Р, р —любое, 0<р<1. (5.6.7)
[т'=?т J
Неравенство (а не равенство) в (5.6.6) возникает потому, что декодер по максимуму правдоподобия не обязательно делает ошибку, если Pn (y|xm') = Pn (y|xm) при некотором т’.
Согласно определению Лт< имеем
Р (Ат’) =2 Qn (Хт') <
xm’-pN (У I хт') > Pn (У1хт)
< 2 Qn (Хт-) ) S—любое, s > 0. (5.6.8)
хт- Рм(У\хтУ
Так как хт, является глухим переменным суммирования в (5.6.8), то индекс т’ можно опустить и граница становится не зависящей от /и'. В силу того, что существуют М—1 различных т' Ф т, то, подставляя
(5.6.8) в (5.6.7), получаем
(«-и!«»(«) Р"<,”‘)'
