Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
337
положительного значения. Наконец, с помощью разбиения выходного пространства на множества, сопоставления одного множества разбиения каждому /, L < j ^ L + К и одного множества всем остальным выходам, после устремления L и К к оо видим, что С = оо, Er (R) = оо. Таким образом, для этого примера нельзя достичь Ре^ехр [—NET (R) ], хотя можно достичь (7.2.5) для любого конечного Е.
Теорема 7.2.2. (Обращение теоремы кодирования.) Пусть дискретный стационарный источник с алфавитом объема М имеет энтропию Нх (U) и порождает одну букву каждые т3 секунд. Пусть дискретный по времени канал без памяти имеет пропускную способность С и используется один раз каждые тс секунд. Пусть последовательность символов источника длины L связана с адресатом каналом, по которо-
Рис. 7.2.1. Канал со стиранием и с бесконечным алфавитом.
му передается последовательность N символов, где N равно |_Lt/cc_|. Тогда в пределе при L->oо вероятность ошибки на букву источника <Ре> удовлетворяет соотношению
<Ре> log (М- 1) + Ж «Ре» > (L0-— С. (7.2.10)
Тс
Доказательство. Формулировка этой теоремы совпадает с формулировкой теоремы 4.3.4. Однако она применима к более широкому классу каналов. В доказательстве теоремы 4.3.4 канал рассматривается лишь при установлении следующих двух соотношений:
/ (UL; VL)^I(XN; Y"), (7.2.11)
7(XW; Yn)^NC. (7.2.12)
Таким образом, здесь достаточно установить справедливость этих двух соотношений для дискретного по времени канала без памяти.
Доказательство соотношения (7.2.11). Для любого заданного значения L и для любых заданных источника и кодера число кодовых слов конечно. Следовательно, только конечное множество входных букв канала может быть использовано в соответствующем ансамбле
338
XN и, таким образом, XN— дискретный ансамбль. Аналогично, любой заданный декодер разбивает пространство YN не более чем на ML областей декодирования, соответствующих элементам пространства \L. Обозначим разбиение выходного пространства через Yр. Теорема 4.3.3 устанавливает, что
/(I/; VLX I(XN; Yp). (7.2.13)
Далее, по определению (2.5.1),
I(XN] YA/) = sup/(XA/; Y*'), (7.2.14)
где верхняя грань берется по всем разбиениям YN. Сравнивая (7.2.13) и (7.2.14), получаем (7.2.11).
Доказательство соотношения (7.2.12). Выражение I (XN; YN) может быть переписано следующим образом*);
/(X"; Y N)=--I(Xl...XN; ' (7.2.15)
Повторно применяя соотношение (2.2.29) к правой части (7.2.15) и
замечая, что все члены конечны, получаем
/(X"; Y")= 2 /(X"; Yn \ Y,... Кп_г). (7.2.16)
П= 1
Используя (2.5.4) и (2.5.5), имеем
I(XN; Уп|К1...Уп-1) = /(У„; XN Y, -
— I (Уп\ Х^П-.У^), (7.2.17)
l(Yn; X" ... = У (К„; АГ„)
+ l(Yn; Y1...Yn„1X1...Xn„1Xn+1...XN\Xn). (7.2.18)
Согласно теореме 2.3.3 последнее слагаемое в (7.2.18) равно нулю; сопоставляя эти соотношения, получаем
I(XN; Y")< 2 ПХп, Yn). . (7.2.19)
п — 1
Так как Хп дискретно, то I (Хп; Yn) определяется как верхняя грань по всем разбиениям Yп и в соответствии с определением С в (7.2.4) имеем I (Хп; Yn)^C, а отсюда непосредственно следует (7.2.12). |
Устанавливая справедливость теоремы кодирования и ее обращения при большой степени общности, представленные выше результаты дают слабое указание на то, как вычислять ET(R) или С. В § 2.5 было показано, что 1 (Xd\ Yp) не убывает при измельчании разбиения пространства Y. Теперь установим тот же самый результат для ?„ (р, Xd, Yp). Пусть Yp — разбиение с событиями Ви ..., Bj и пусть Yp’ — подразбиение Yp с событиями Btj, где (J Bi3 — Bj.
*> Это нетривиальная подстановка, см. обсуждение, следующее за формулой (2.5.3).
339
По неравенству Минковского (см. задачу 4.15.з) для р^О имеем
1 + р
<(2QK)[2 я,и(^|«л)11/(1+р)ГР
2QK)/Vix(fi;K)1/(I+p>
k
l+p
(7.2.20)
Суммируя обе части (7.2.20) по / и беря минус логарифм от результата, получаем
Е0(р, Xd, У»>?о(Р, Xd, Yp). (7.2.21)
С физической точки зрения этот результат не удивителен. При более тонком разбиении выхода канала декодер имеет большую информацию о принятой последовательности и вероятность ошибочного декодирования будет меньше.
