Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
/-б
Z - канал
Яп($)
ДСтК
8)
двоичнь/й канал
г)
j— 1
Рис. 5.3.1. Функция gn (s)= 2 -Р 01 0)'~3-Р (/1 5 )s ¦
¦/=о
и gn (1) могут быть не определены. Для этих случаев определим gn (0) и Sn (1) равенствами
Sn (0) = lim gn (s) = 2 Р(Уп\х1,п)> (5.3.9)
S-9-0+ по Уп, для которых
Р(УП\Х2,П^0 +
140
gn (1) = lim gn (s) = 2 P(yn\x2,n)- (5.3.10)
s + 1— no yn, для которых
P (yn |*l,
Можно заметить, что gn (0) и gn (1) всегда меньше или равны 1. Отсюда также следует, если взять вторую производную, что gn(s) выпукла w при 0 i=C s <С 1. Следовательно, gn (s) s;'! 1 при 0 ^ 1.
В задаче 4.15(a) показано, что gn (s) < 1 при 0 -< s < 1, если Р (yn\xi,n) — Р (Уп\х2,п) не имеет места одновременно для всех выходов Уп.
Используя определения (5.3.9) и (5.3.10), находим, что неравенство (5.3.8) справедливо для всех s, 0 ^ s ^ 1. Очевидно, можно получить наилучшую границу, если провести минимизацию по s:
Ре,т<: min Г1 gn (s); tn — I, 2. (5.3.11)
0<s<l л= 1
Пример. Рассмотрим двоичный симметричный канал, изображенный на рис. 5.3.1, а. Пусть хх — последовательность N нулей, а х2 — последовательность N единиц. Тогда
gn (s) = eI-s(l —e)s + es (1 —e)1-"; 1 N.
Это выражение минимизируется при s = 1/2, что дает
mingn (s) =gn (V2) = 2 Ye (1 — e), (5.3.12)
^,m<[2f8(l-ef; m = 1, 2. (5.3.13)
Для этого простого примера Pe,i и Р е> 2 можно точно подсчитать.
Pn (у|х2) будет больше или равна PN (у | хх), если принятая последо-
вательность содержит N12 или более единиц. Вероятность этого, когда сообщение 1 было передано (в предположении, что N четно), равна
ре.1= 2 Vo-e)"-'. (5.3.14)
i = N/ 2' 1 >
Слагаемые этой суммы являются членами биноминального разложения, сконцентрированного около i = eN. В силу того, что е < V2, наибольшим слагаемым в сумме является первое слагаемое, в котором i=N!2. Применяя формулу Стирлинга для факториала N1 « \г2nN X X NNe~N, получаем
{ N )&]/~ —2N’ (5.3.15)
\ N/2 ) V nN ’
Ре 1« "[/^-^ [2 Уг (1—• e)]w + меньшие слагаемые. (5.3.16)
В задаче 5.2 (в) построена аппроксимация для меньших слагаемых в (5.3.16), что дает явную аппроксимацию для Ре х. Вопрос, который, однако, нас интересует здесь, состоит в выяснении экспоненциальной зависимости РеЛ от N\ нам также интересно то, что эта экспоненци-
141
альная зависимость согласуется с той, которая представлена границей (5.3.13).
Так как, по условию, декодируется сообщение 2, если Рм(у !x2) = PiV(y|x1), то получаем
Р..ш = S (*V(l-e)"-'.
i = (W/2) + l ' 1 '
В задаче 5.2 (в) показано также, что экспоненциальная зависимость Ра гот N является той же самой, что и для Рвг ь и что та же самая экспоненциальная зависимость имеет место, если N нечетно.
Для более сложных каналов получение хорошей аппроксимации для Ре<! и Рез 2 много труднее. Однако оказывается, что (5.3.11) всегда дает правильную экспоненциальную зависимость У2 (Ре г + Ре< 2) от N (см. Шеннон, Галлагер и Берлекэмп 1 (1967), § 3). Это будет рассмотрено более детально в конце настоящей главы.
5.4. ОБОБЩЕННОЕ НЕРАВЕНСТВО ЧЕБЫШЕВА И ГРАНИЦА ЧЕРНОВА
В этом параграфе результаты § 5.3 будут выведены вновь в более общем виде, что даст тем самым дополнительное понимание использованных там методов. При передаче сообщения 1 и декодировании по максимуму правдоподобия для двух кодовых слов ошибка происходит, если PN (у|х2) Г;::- PN (y|xj). Другими словами, ошибка происходит, если логарифм отношения правдоподобия w (у) удовлетворяет условию
w (у) 4 In > 0. (5.4.1)
PN( ylxi)
Для каналов без памяти согласно (5.2.1) w (у) можно представить в виде суммы N слагаемых
Иу) = %гп(уп), (5.4.2)
П = 1
где
(Уп) - In -(- (5 4 3)
При условии, что передается сообщение 1, zn, 1 ^n^N, являются независимыми случайными величинами, каждая из которых принимает указанные значения с вероятностями Р (уп | xlt „). Таким образом, w (у) является суммой независимых случайных величин и значение Ре> г задается равенством
