Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Если бы это было неверно, то множество L+ 1 кодовых слов {хт 2} при tn = т 1 (yi), tn.L +1 (yi) и множество областей декодирования
{Ym,2 (У1)} ПРИ гп = т1 (ух)...ть + 1 (Уг) все давали бы вероятности
ошибок, меньшие, чем Ре w (N2, L + 1), что приводит к противоречию. Теперь получаем следующую нижнюю границу:
Изменяя порядок суммирования по т и ух в (5.8.43) и подставляя
(5.8.45) в полученное выражение, имеем
Наконец, можно рассмотреть множество префиксов {хтд} как множество М кодовых слов с длиной блока А^ и можно рассмотреть mi (Уг), I — L L, как правило декодирования списком для этого множества кодовых слов. Поэтому
Объединяя (5.8.47) и (5.8.46), завершаем доказательство леммы. | Используем теперь четыре доказанные леммы для нахождения прямолинейного отрезка показателя экспоненты, представленного в теореме 5.8.2. Пусть 6, е <С б <С 1/2, является вначале произвольным числом; введем обозначения
Для (N, R)-кода с заданными N я R определим число X с помощью равенства
так, что 0 ^ 1. Обозначим теперь Л^ = [_XN____| и N2 = N — А^.
Заметим, что N2 ^ 1. Используя (5.8.50), можно показать, что число 186
Рс,тп (Уl) ^ Pe.w (^2. L+ 1).
S P(y2|xm,2)> 2(у‘>
(5.8.46)
I > L
(5.8.47)
I > L
R1= In 2 —ЯР (6),
Esp (R±) -¦= —Ж{8)~6 In е —(1 —б) In (1 — е).
(5.8.48)
(5.8.49)
(5.8.50)
Будем рассматривать лишь скорости из интервала
-J-ln [2 (W+1)]
(5.8.51)
КОДОВЫХ слов М
= [ ехр NR | удовлетворяет неравенству
- > V 8 (N + 1) ехр (NKRJ > (5.8.52)
> /8(AVPT) ехр (N1 «j). (5.8.53)
Теперь из леммы 1 следует, что Pe(NvM,N+ 1)>
(l-e) V8 (ЛГх+1)
ехр [—(^i Esp (Ri)]>
IS;
(1-е) /8(ЛГ + 1) Согласно лемме 3, также имеем
ехр [—XNEsp (/?!>].
(5.8.54)
,w (N2, N + 2)> ^ ехр [ - N2 Еех (0)] >
------5--------- ехр { [(1 Я) iV+ 1] Еех (0)} =
¦ ехр { (1 Я) NEex (0)>.
(Л, + 4)(1-е)
Т/2е5/4
(jV + 4) (1 —е)3/4 Сочетая (5.8.54) и (5.8.55) с леммой 4, получаем
(5.8.55)
Pe(N,M)>i
,9/4
X
2(1— е)7/4 1/7V+ 1 (JV + 4)
X ехр {-N [lEsp (R,) + (1 -1)Еех (0)1}. (5.8.56)
Наконец, используя (5.8.50), чтобы выразить Я через R, и перенося коэффициент в показатель экспоненты, получаем
Ре (N, М) > ехр | -где
-N
Eex(0)-R
Еех (0) Esp (Ri)
Ry
о (N)
, (5.8.57)
o(N) = —
4 ’ N
?e*(0)—Esp(Ri)_ _3_ln [2 (N+ Ri 2
-In
„9/4
2(1— e)7/4 YN+\ (W + 4)-
(5.8.58)
Показатель экспоненты в (5.8.57) является линейной функцией R, которая изменяется от значения Е ех (0) при R = 0 до значения Esp (Ri) при R=R1. Если выбрать R=Rj (т. е. б), при которой указанная выше линейная функция имеет минимум, то, очевидно, получим наиболее точную экспоненциальную границу. Следующая теорема подытоживает полученные результаты.
Теорема 5.8.4. Пусть задан ДСК с вероятностью ошибки е и пусть Ri обозначает R, при которой прямая линия, проходящая через точку R = 0, Е = Еех (0), является касательной к кривой Esp (R)- Тогда при любом N ^ 1 и любой R из интервала (5.8.51) Ре для любого (N, R)-кода удовлетворяет (5.8.57).
187
Вероятность ошибки на блок при скоростях, больших пропускной способности
Здесь будет показано, что в любом дискретном канале без памяти и при любой фиксированной скорости, большей пропускной способности, Ре стремится к единице с ростом N*K Как было указано в § 4.3, такой результат не обязательно исключает возможность надежной передачи данных на скоростях, больших пропускной способности, так как большая вероятность ошибочного декодирования блока не означает, что будет большая вероятность ошибки в отдельном символе источника. Кроме того, такой результат ничего не говорит о вероятности ошибки для неблоковых кодов. Вместе с тем этот результат является более простым для понимания по сравнению с обращением теоремы кодирования (теоремы 4.3.4), так как он касается только канала, а не источника и канала вместе взятых, и он дает дополнительное понимание природы пропускной способности.
Теорема 5.8.5. [Вольфовиц (1957).] В произвольном дискретном канале без памяти с пропускной способностью С (в натуральных единицах) для любого (N, R)-кода при R > С имеем
Р*> 1-
4 А N (R—С)2
