Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Доказательство того, что п < 2А‘. Для заданных п, х определим матрицу связности
^,x(s0,sj = {(1’ q\Sn (4-6.45)
{0, q (sn | x, s0) = 0.
Эта матрица размера Л на Л из нулей и единиц, в которой индексом строки является s0, а индексом столбца является sn. Данный элемент равен 1, если соответствующее ему sn может быть достигнуто из соответствующего ему s0 при заданном х. Так как q(sn\x,s0) = = h<?(sn\xn’ sn~i) q (sn-i | xn_i, s0), то можно выразить Tn,x (s0, sn) с помощью Tn-U Xfl____! в виде
( 1, Тп-1. (s0, Sjj-j) q (sn | xn,s„_1)>0 для
Tn,As0, некоторого sn_lf
[0 во всех остальных случаях. (4.6.46)
В силу того, что существует лишь 2А2 — 1 ненулевых матриц размера Л на Л из двоичных элементов, то последовательность матриц*’ Тп, х (s0, sn), п = 1, ..., 2А', должна содержать две одинаковые матрицы, допустим с i<zj^.2A\ Если исходя из последовательности символов (хг, ..., Xj) выбрать Xj+N — Xi-|-дг при всех N^1, то из (4.6.46) следует, что Tj+N.-x = Ti+Ni х при всех N~^\. Если при этом выборе х, Тп, х не имеет столбцов из единиц при п <1 /, то она не будет иметь столбцов из единиц при всех больших п. Но это означает, что при этих х, не существуют ti, sn, для которых q (s„ |х, s0) > 0 при всех s0 и, таким образом, канал не является неразложимым. Поэтому для того чтобы канал был неразложимым, при любом х матрица Тп, х должна иметь единичный столбец при некотором 2А\ Наконец, если Тп,х имеет единичный столбец при некотором п, то из (4.6.46) следует, что эта матрица имеет столбец из единиц при всех больших п, и, следовательно, для неразложимого канала имеется некоторое наименьшее п ^ 2А\ для которого Тп, х имеет столбец из единиц для всех х. |
Для канала, изображенного на рис. 4.6.1, условие (4.6.42) удовлетворяется при п= 1, и, следовательно, этот канал является неразложимым.
Теорема 4.6.4. Для неразложимого ККЧС
С = С. (4.6.47)
*> Здесь х — (х1г ..., хп) — отрезок некоторой последовательности (xt.........
хп, ..., ха2). (Прим. ред.)
125
Доказательство. При произвольном N пусть QN (х) и so являются распределением на входе и начальным состоянием, которые максимизируют Iq(Xn; Y^jSo), и пусть So обозначает начальное состояние, которое минимизирует /а при том же самом распределении на входе. Таким образом, по определению Си и Сn имеем
Cw-~/Q(X'v; YN\sl), (4.6.48)
/q (X‘v; YA’js;>. (4.6.49)
Положим теперь п + I = N, где пи/ — положительные целые числа. Пусть X, обозначает ансамбль входных последовательностей х L — = (хи ..., хп), а Х2 обозначает ансамбль последовательностей х2 =
— (xn+i, ..., Xn), соответствующих распределению на входе QN (х). Аналогично пусть YjH Y2 обозначают ансамбли выходов ух = (уъ ..., ..., уп) и у2 = (уп+ j, ..., yN) при условии, что задано s'0. Имеем теперь
CN = ± [/ (Xj; Yj Y21 s’) + / (X2; Y, | Xlt s') +
N
+ I{Xi-Yi\X1Y1,s'0)]. (4.6.50)
Вероятность элемента из произведения указанных выше ансамблей» включая и состояние в момент п, может быть выражена в виде
Q(x1)Q(x2|x1)P„(y1, s„ )хь s')Рг(у21 х2, s„). (4.6.51)
Отсюда можно заметить, что второе слагаемое в правой части (4.6.50) равно нулю. Также первое слагаемое ограничено сверху числом ti log К, так как в ансамбле Х2 содержится Кп элементов. Наконец, из леммы 4А.1 следует, что последнее слагаемое не больше, чем log А + / (Х2; Y2|X1Y3Sn, So). Таким образом,
С* < [п log К + log А + / (Ха; Ya | Хх Yx Sn, s'0)]. (4.6.52)
Оценивая подобным же образом CN снизу, используя sQ вместо So и ограничивая снизу первое слагаемое в (4.6.50) нулем, получаем
Cw > [ - log Л + / (Х2; Y21 Хх Sn, s0')]. (4.6.53)
— Л
Используя (4.6.51), заметим, что среди условий, при которых рассматривается информация, условие на Yx может быть опущено в (4.6.52) и (4.6.53), будем иметь
Cw-Cw^_L[nlogtf-f21og,4 + /(X2; YJX^.s;)-
- / (Х2; Y21 Xj Sn, s;')] = ±[n log2 log A + (4.6.54)
+ 2Q(xi)2['?(Sn |*i. «о)—^(sn|*i. s;')l/(X2; Y2 j sn, xj)]. (4.6.55)
V
126
Далее можно оценить сверху это выражение, взяв модуль каждого слагаемого в сумме и оценив сверху значение / для каждого sn и хх с помощью I log К. В результате получим:
CN—CN < -i- [п \ogK + 2 log A + dn (s', s'') I log /С],
где dn является верхней границей для dn (so, s'o), справедливой при всех хх. Согласно определению неразложимого канала при любом б > 0 можно выбрать п так, чтобы dn < е. Для этого фиксированного значения п
