Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
4.24. Пусть sn = хп и уп = sn-i¦ Другими словами, канал является
двоичным каналом без шума с задержкой, т. е. уп = xn~i. Входная последовательность х = (%, xN) в этом случае точно определит у2.........уN (и yN_^x),
но никак не связана с yv Поэтому / (KN; Y N | s0) меньше или равна N — 1 бит с равенством, когда входы являются независимыми и равновероятными.
Поэтому Cw = 1 —-jy- и С = С= 1. Найдем теперь двоичный канал с двумя
состояниями, для которого СN — MN — С = С при всех N. Пусть последовательность состояний {sn} будет последовательностью независимых и равновероятных двоичных символов и пусть уп — хп ©Sn-!. Тогда CN = 1 /N, так как условие, состоящее в том, что состояние в момент 0 является известным, позволяет передать один бит информации в первый момент. Очевидно, С = С = 0.
4.25. (а) Под предположением, что имеет место статистическая независимость шумов, в каналах понимается, что при заданном входе в п-й канал выход n-го канала не зависит от входов всех предыдущих каналов, т. е. Р (хп+11 хп) = Р (хп+] | хп, ¦¦¦, Хх). Таким образом, последовательность xlt х2, ... является марковской цепью, которая в общем случае является неоднородной (за исключением случая, когда все каналы являются одинаковыми).
(б) Пусть х'х и х'{ — какие-либо два символа на входе канала 1. Используя лемму 4.6.2 при л = 1 и ^ вместо sN_ j получим
2 \pxN | х, (% I xi)~pxN | X, (xn | xi) | < 2 (!—S)W 2. xn
Так как каждое слагаемое суммы, в свою очередь, ограничено правой частью неравенства и так как Р% (xN) является взвешенным средним Р (xN \ х х) по
xlt то получим для всех xN и хх:
\pxN 1 (*N | *i)-PxN Ы I < 2(1-б)"-2, (1)
2P (Хы I X!) р(х1>х») !°8- ' ¦< xlt x r (XN)
p (*i- xn)
N
P(XN 1 *l)
. p (xn)
log e =
У
p (*i | xn) [p (xn | *i)—P (%)] loS e -
P (*x | %)2 (1— 6)" 2 log e = 2ЛГ (1 — 8)" 2 log e.
1 N
Степень N — 2 может быть заменена на N — 1, что можно понять, просматривая доказательство леммы 4J5.2, для случая п = 1. Однако ее нельзя заменить на N, что можно понять, если рассмотреть случай, когда N = 2 и канал является двоичным стирающим каналом с вероятностью стирания, близкой к 1.
4.26. Как предлагается в указании, пусть Вп обозначает множество возможных состояний канала после n-го входа. Если Вп = Вт для т>п при вход-
xN, то входная последовательность хх, х2,
т. — п способны 601
ной последовательности хъ х2,
..., Хп, Хт +1, *7П + 2>
, xN приведет канал в известное состояние на моментов времени раньше, так как по предположению *m+i> *m+2
привести канал в известное состояние, начиная с неизвестного множества со-
жество имеется в момент 0; пустое множество невозможно и не должно быть множества, содержащего одно состояние до того, как канал окажется в известном состоянии. Таким образом, последовательность Въ В2, ... может проходить ке более чем 2А ~ А — 2 различных множеств до того, как она достигнет известного состояния, и поэтому известное состояние может быть достигнуто не более чем за 2А — А — 1 переходов.
5.1. Стоимость декодирования последовательности у как сообщения т'
равна
Так как Рг (у) не зависит от того, какое решение было сделано, то правилом решения с минимальной стоимостью является следующее: выбрать гп', которое минимизирует
См. пункт (в), в котором рассмотрено четное N. По формуле Стирлинга
стояний Вп = Вт. Имееются 2А различных множеств состояний. Полное мно
C(m'[y)=2C(m, т') Pr (т | у) =
т
=2 С (т, m')Q (т) PN (у | хт)/Рг (у), т
2 С (т, т') Q (tn) PN (у \ хт).
т
5. 2. (a) (I)^n(5) = (l-8)1-s8s + s1-s(l-8)s,
rain gn (s)=2 VC1— e) e, при s = 1/2,
0<s<~ 1
Pe.m<[4( 1-S)S]N'2.
(II) Sn (s) = e; min gn (s) =e,
(III)^n=e1 s; min gn (s) =e,
(IV) gn (s)—(1—ej — 62)1 sE|+ej+(l Ej e2)s Ej s,
1—s „s
rain gn(s)= 2"l/(l—8! —82)8Z +8!,
N+1
N—i
(1)
Pe, m = 2,87- IQ-7.
602
Граница в этом случае равна
Ре,т < (0,36)12’5 = 2,843-Ю-о.
(II) В ДСтК, очевидно, происходит ошибка только тогда, когда все символы стираются. По условию в этом случае декодируется сообщение 2. Таким образом,
Ре. 1 = (0, 1)2§ = 10-25, ре> 2 —0.
Граница будет Ре,т < Ю-2?, т= 1, 2.
(III) Для Z-канала сообщение 2 декодируется, если среди принятых символов имеется единица и сообщение 1 декодируется во всех остальных случаях. Следовательно,
Ре. 1 = 0, Ре. 2 = 10-25.
