Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
lim Рг [(х y)$rw|m] = 0.
(2)
(в) Рг [(хт,, у)6Г.|т] =
= 2 №^(хт')ш^(У^)]>
<*т',У)еТ JV
(3)
так как при заданном m величина yN выбирается независимо от хт с распределением вероятности <aN (у) = 2 Qn (xm) Pn (У I *m)- Согласно определению
618
типичного множества TN имеем
п. Л
<е при (хт„ у)?Tn>
1 . МУ Кг') „
— In--------------------— С
N (Уы)
1 P/v(ylxm')
— In N\ ч—>c-e при (xm„ у)?Tn,
N ®n{Vn)
ам(Уы) <pn(V I x™) e~N(c~E) при (Xm,, у)?TN'
Подставляя эти выражения в (3) и строя границу сверху с помощью суммирования по всем хт>, у, получаем
Pr[(*„-.y)^ff|ra]<e-W-‘l. (4)
(г) 2 Рг[(Хщ. y)?TN\m] <
т'=т
<(Л1_ 1)е-тс-г) <e-N(C-R-E)=e-NS' (5)
Используя (5) и (2) совместно с (1), будем иметь
lim Р
N->-oo
Заметим, что сходимость не зависит от т и поэтому
1 vr-
hmPe=hm—ZiPe,m = 0.
N-rCQ Л' гп
С помощью того же самого доказательства, что и в следствии 2 на стр. 157, можно показать, что для любой R < С, любом 6> 0 и достаточно большом N существуют коды, для которых
Ре,т^& при всех т, 1 < т L ехр NR_\ .
5.19. (а) Заметим, что в ДСК PN (у|х) = ei<x' у*(1 — e)w~d(x' у), где d (х, у) равно числу позиций, в которых х и у отличаются друг от друга. Отсюда можно заметить, что при е < V2 декодирование по максимуму правдоподобия равносильно выбору такого т, которое минимизирует d(xm, у) (т. е. выбору ближайшего кодового слова). Вероятность того, что PjV (y|xm,) > PN (y|xm), равна вероятности того, что у совпадает с хт-, по крайней мере, во стольких же позициях, как с и хт, или, другими словами, вероятности того, что у отличается от хт, по крайней мере, в половине из d (хт, хт,) позиций, в которых хт и х1п, отличаются друг от друга. Следовательно, из (5.3.13) будем иметь
Рг \PN (У I хт’) > PN [(У I хт) | т] < [2 УГО^Т)}* (*т' Х'п'').
Для того чтобы произошла ошибка при передаче хт, значение PN(у | xm,) должно быть больше или равно значению PN{y \хт), по крайней мере, для одного т’ Ф т. Имеем
ре,т< 2 ехр {d(xm, xm,)ln[2"l/e(l— в)]}. т'Фт
(б) Так как 1п[ 2 "|/е (1—в)]<0, то Ре,т можно оценить сверху с помощью оценки снизу d(xm, хт,). Поэтому
Ре,т ^ (М~— 1) ехр {dmin 1п [2~У в (1 — б)3}> 1^/п^М* (1)
619
(в) Каждое новое кодовое слово вызывает устранение из списка не более
V (»\
2j \ i J слов- Поэтому, если после выбора М кодовых слов
d— 1 м 2
г = О
'•N
<2n,
то можно выбрать следующее кодовое слово. Таким образом, после окончания
процедуры М 2
г = о\ 1 >
(г) Из задачи 5.8 (г) при е = 1/2 имеем
d- 1
S (")2~A, = _ 2 1 )2-"<ехр^
I —In 2
i=N—d+1
Следовательно, число слов, которое выбирается с минимальным расстоянием dminI удовлетворяет границе
— 1
-N
ехр IN
' dr,
l~ 1
N
(2)
Пусть R < In 2 и пусть б<1/2 удовлетворяет равенству & (д) = 1п2—i?.
djYlin- 1 С" dmin
Выберем нужное значение dmjn так, чтобы'---------------<о<---------.
N N
(д)Из(2) следует, что можно выбрать код с минимальным расстоянием dmin и с 7И^>ехр {N [In 2—Ж (S)]} = eNR М — 1 кодовыми словами. Для такого кода неравенство (1) приводится к виду
Ре,т<ехр {-NE(R)}, R = \n 2—&6 (б),
Е (R) = —R-б In [2 Уе ( 1—е)] = - In 2 + Ж (б)-б In [2 >"е (1 — е)J.
При 6 = 0,01 получим следующее графическое изображение.
5.20. Пусть А(т^, т$....... mL) будет событием, состоящим в том, что
PN (У I хт) >PN(y\ хт) при всех I, 1< / < L. Для возникновения ошибки при
декодировании списком должно произойти событие А (т1.........т1) при некоторых
значениях ........mL. Следовательно,
Рг (ошибка при декодировании списком \т,хт, y)^Pr[lM(mi
mL)] < [2 Рг (Л (mi....wL))]p«, 0<р0<1. (1)
где объединение и сумма берутся по всем наборам L различных целых чисел, 620
не равных т. Так как хШ1, хт^ являются независимыми, то
L
Рг [Л (mx.... mL)] — Г1 рг [Pw (у | х,П/) ^>PN(y \ хт) | т, хт, у],
1 = \
Pr [Л^,..., mL)]< 'М-
PN(y\*)s
PN (У I хт)5
(2)
В силу того, что имеется ^ ^ J различных наборов по L целых чисел, молено
подставить (2) в (1) и получить (при 0<р<!1), Рг [ошибка при декодировании