Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
В этом параграфе граница случайного кодирования будет усилена при малых скоростях с помощью выбрасывания плохих кодовых слов
166
из кодов, принадлежащих ансамблю. Этот подход аналогичен рассмотренному в следствии, устанавливающем границу (5.6.20). Вначале рассмотрим ансамбль, состоящий из кодов, каждый из которых содержит М' = 2М — 1 кодовых слов. Затем покажем, что по крайней мере в одном коде из ансамбля, имеются не меньше чем М слов, для которых Ре, т удовлетворяет заданной границе. Эта граница будет выражена через произвольный параметр s > 0, который в дальнейшем может быть оптимизирован. На ансамбле кодов вероятность Р^ т при каждом т, 1 < т^.М', является случайной величиной. Применяя к этой случайной величине неравенство Чебышева (5.4.6), получаем
Pr[pU>2PU] < 1/2. (5.7.1)
Лемма. Для любого s> 0 в ансамбле кодов с М' = 2М — 1 кодовыми словами существует по крайней мере один код, в котором для по меньшей мере М кодовых слов выполняется неравенство
Pe,m<2l!sPl~m1IS. * (5.7.2)
Доказательство. Пусть срт при каждом т является случайной величиной на ансамбле кодов. Пусть срт = 1 для кодов, для которых справедливо (5.7.2) и пусть срт = 0 во всех остальных случаях. Согласно (5.7.1) вероятность того, что (5.7.2) будет справедливо, не меньше 1/2 и, следовательно, фт^1/2. Число кодовых слов в случайно выбранном коде, которые удовлетворяют (5.7.2), является случайной величиной
М'
2 фт.
т = 1
Математическое ожидание числа слов, которые удовлетворяют (5.7.2), равно, следовательно,
М'
V - \ м'
Z <Рт> -Г'
гп = 1 z
Отсюда вытекает, что существует по крайней мере один код, для которого 2фт ^ М'12, и для такого кода 2фт ^ М. [
Если все слова, кроме М слов, удовлетворяющих (5.7.2), будут выброшены из кода, рассмотренного в лемме, то области декодирования остающихся кодовых слов не могут быть уменьшены и, таким образом, мы получаем код с М кодовыми словами, удовлетворяющими
(5.7.2). Теперь нужно найти удобную верхнюю границу для Р|, т. Для частного кода с кодовыми словами хх............хм- имеем
Ре,т< S 2j Y Pn (у | Xj Pjv (у 1 (5.7.3)
у
Для того чтобы показать справедливость (5.7.3), заметим, что согласно (5.3.4) для заданного кода
2j V Pn (У | хга) Pjv (у | хт-)
У
167
является верхней границей вероятности того, что PN (у | хт') ^ ^PN (у | хт) при условии, что была передана хт. Так какРв! т является вероятностью объединения этих событий при т' =? т, то Ре< т можно оценить так, как указано в (5.7.3).
Рассмотрим теперь s из интервала 0 < s ^ 1. Используя известное неравенство (2a,)s ^ 2а* (см. задачу 4.15 (е)), будем иметь
Р'е;т< 2 [2 V~Pn (у I х J Р N (у \ *т') ] * , 0<S<1. (5.7.4)
т’фт L у J
Рассмотрим ансамбль кодов, в котором кодовые слова выбираются независимо с распределением вероятности QN (х). Имеем
В силу того, что хт' является глухим переменным суммирования в (5.7.5), слагаемое в фигурных скобках не зависит от т’ и мы имеем М' — 1 = 2 (М — 1) одинаковых слагаемых. Подставляя упростившееся таким образом выражение (5.7.5) в (5.7.2), получаем
ft.m<2«/*/2(Al-l)2 2<Mx)Qtf(x') х I X х'
X [2 K/Wh^MyhO]5}1^- (5.7.6)
Эта граница по своему виду подобна границе, установленной в теореме 5.6.1. Это сходство может быть выявлено, если положить р = = 1/s. Так как s является произвольным параметром в (5.7.6), 0<s^l, то р является произвольным параметром, р ^ 1. Имеем
Ре,т<{4 (М — 1)]р X x(2|;Qn(x)Qw(x0[2K/WI^W>o]i/p)p> (5.7.7)
Неравенство (5.7.7) справедливо для любого дискретного канала как с памятью, так и без памяти, для которого можно определить PN (у) х). Применим теперь эту границу к дискретному каналу без памяти, для которого
pN (у I X) =п Р{Уп\хп).
п
Положим также 0Л- (х) равным произведению распределений, т. е.
Qn (х)= UQ{xn).
П
После подстановки этого произведения в (5.7.7) и после преобразований, которые аналогичны проведенным при переходе от (5.5.6) к (5.5.10), получим
¦Х~ЖР(Уп\Хп)Р(Уп\х'п)]11Р\0
e[4(M-l)]p 2 2 Q(k)Q(i) 2 YP(j\b)P(j\i) .(5.7.8)
(. *=о / = o L/,=o J J
В (N, R)-коде имеются (M — 1) < eNR ^ M кодовых слов, поэтому
(5.7.8) приводится к виду
Полученные результаты можно подытожить следующей теоремой.
