Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Заметим, что для двоичного симметричного канала это согласуется с (5.5.1).
5.4. Пусть задан ансамбль кодов и на кодер поступает сообщение т и пусть Ет^т. является событием, состоящим в том, что PN (у \ хт,)> PN {у \ хт). В силу того, что ошибочное декодирование может произойти только тогда, когда для некоторого т’ ф т происходит Ет^т., то имеем
Ре.т < Рг [ U ,2
Ym' Ф т J т фт
Из (5.5.10) находим, что
P4?m->m'l<{2
605
^iQwVpuw
k
2\N
при каждом пг' ф т.
Таким образом, суммируя по М — 1 возможным значениям т! ф т, получаем
Ре.т < {М- 1) [2 2 Q (k) VpUik) 'j" .
Используя неравенство М — 1 < М = eNR, можно переписать это в виде
Pe,m<expjjv Я+> 2 QW У PU\ j.
Следовательно, граница экспоненциально убывает по N при
2
ж -1п2
. к
(1)
Положив Q (0) = 1/2, получим, что правые части (1) для каждого из каналов, рассмотренных в задаче 5.2, равны
(I) —1п
(II) —1п
у-+ VВ (1—е) 1+8
(III) —In
(IV) -In
1+У1
2
'1+8
+ l/e2 (1 —вх — e2)
5.5. (а) Здесь г является гауссовской случайной величиной с нулевым средним значением и дисперсией N. Поэтому
У 2nN
2 N
dz :
V2№V
-N/2
(1)
Границей Чернова для этого случая будет
Рг [z > N] < e~sN jj pz (z)eszdz=e~sN+s‘N^.
После минимизации по s > 0 получаем наиболее точную границу такого вида при s = 1
Рг [z > N] < е~ Nl2.
Неравенство Чебышева дает
Рг [г > N] < Рг [ | z | > N]
N
№
(2)
Можно заметить, что граница Чернова имеет правильную экспоненциальную зависимость от N и что неравенство Чебышева является здесь довольно слабым.
(б) Имеем z > N только тогда, когда хп = 1 при всех tt, 1 < п < N, и, таким образом, Рг [г > N] = 2~N.
Границей Чернова будет
N
Pr [z > N] < е sN
[_Le,+ie-,jW = 2-*(i +е"2Т.
Минимум по s > 0 здесь достигается при s=oo, что дает Рг [г > N] < 2~n. Приближение с помощью центральной предельной теоремы дается правой частью (1). Заметим, что центральная предельная теорема утверждает, что функция распределения г сходится к гауссовской функции распределения, но она ничего
606
не говорит о том, какова доля ошибок на хвостах. Отличие между выражением (I) и 2~N исчезает, но экспоненциальная зависимость от N яёляется неверной. Неравенство Чебышева задается (2) и является еще худшим приближением.
5.6. В соответствии с неравенством Гёльдера [см. задачу 4.15 (в)], полагая А, = 1/(1 +-р), получаем
1 +р
2V,I+P U2«1‘!'+P>'‘,V
Чтобы согласовать это с соотношением, содержащимся в указании, положим а' + Р =Рд, (у | x),~sp , ь\1 + р)1р = Ры (у | х)-5.
Это значит, что a* 6; = PN(y [ xm)'^1 и поэтому
2 Qn (х) pn (У I х)
i/d +р)1, + р
2 Qn (хт) РN
]’
:|2 Qn WPw(y]x)5
(У I
xl — sp
Так как левая часть равна -правой части при s= 1/(1 + р), то получаем, что правая часть достигает минимума при s = 1/(1 + р). Это показывает, что каждое слагаемое в сумме по у в (5.6.10) достигает минимума по s при s = 1/(1 + р).
Применение неравенства Гёльдера здесь довольно типично. Сначала возникает желание построить доказательство и затем используется неравенство Гёльдера, чтобы выполнить это доказательство.
5.7. (а) Имеются две входные буквы, которые приводят к каждой из выходных букв в заданном канале, и, следовательно, имеются 2N последовательностей на входе, приводящих к любой заданной последовательности на выходе. Заметим, что PN (у | х) = 2~N является одной и той же величиной для всех таких х. Вероятность того, что х2 принадлежит этому множеству 2N последовательностей, равна 2n/3n или (2/3)N.
(б) Для М кодовых слов можно применить аддитивную границу к результату, полученному в пункте (а); будем иметь
\N
(М-1) (2/3)'
(1)
Согласно (5.6.11) Ре,т < (А4 — 1)р (2/3)pw • Минимум правой части по р, 0<р<1, достигается при р = 1, что приводит к тому же самому результату, что и в (1).
(в) При хх = (0,0, ..., 0), х2 = (I, 1. 1) ошибка происходит только тог-
да, когда принимается (1, 1, ..., 1). Поэтому Ре, i = 2~N, Ре,2 = 0. Отличие возникает потому, что этот код является наилучшим кодом из двух кодовых слов, а (1) получено для ансамбля кодов.
