Научная литература
booksshare.net -> Добавить материал -> Физика -> Галлагер Р. -> "Теория информации и надежная связь" -> 95

Теория информации и надежная связь - Галлагер Р.

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 89 90 91 92 93 94 < 95 > 96 97 98 99 100 101 .. 355 >> Следующая


2 ~т'-Рл' (у | xm, s0),

So Л

и он остается хорошо определенным независимо от того, существует или нет вероятностная мера на начальных состояниях. Объединяя предыдущие рассуждения, видим, что при любой длине блока N и любом числе кодовых слов М существует код, такой, что вероятность ошибки для сообщения т при условии, что задано начальное состояние s0, ограничена, независимо от т и s0, следующим образом:

Ре, т (®о)

< 4А (М- l)pmin 2 (2 Qn (х) [Z~Pn (у | х, s0)]‘/(I + PM ‘ + Р

Qjv у I х L s0 А

(5.9.2)

при всех р, 0 ^ р ^ 1.

Для упрощения этого выражения удобно сначала вынести сумму по s0 из квадратных скобок (5.9.2).

Используя неравенства (Sa*)' ^ 2аг- при О С г ^ 1 (см. задачу 4.15(e)), находим, что правая часть (5.9.2) будет ограничена сверху следующим выражением:

Ре, тп (So) ^

^4Л (М— 1)р min 2 (S2 Qn (х) (У I Х)11/<1 + р)\1 + р_ (5 9 3)

Qn у

А

192
Умножая и деля сумму по s0 на А, понимая 1 /А как распределение вероятностей для s0 и используя неравенство (2Р;йг)' 2Р,й; при

г ^ 1 (см. задачу 4.15(г)), будем иметь

Ре, т («о) <

< 4А (М — 1)р Арт\п 22 (2 (х) \-^rpN (у I х, s0)l1/O 4 р)|‘+ р ^

Qat si у [ х L A J )

(5.9.4)

^4А (М— 1)РЛРш1пшах2/2Сл?(х)Р^(у|х, s0)1/<I + pH1+p, (5.9.5)

Одг So У I X I

где сумма no s0 была ограничена наибольшим слагаемым, умноженным на А.

Порядок, в котором разыскиваются минимум и максимум в (5.9.5), является существенным. Нетрудно заметить (см. задачу 5.37), что, если передатчик знает начальное состояние и может использовать различные коды для каждого начального состояния, то минимакс в (5.9.5) можно заменить на максимин и при этом граница, как правило, уменьшается.

Теорема 5.9.1. В произвольном канале с конечным числом А состояний при любом положительном целом числе N и любой положительной R существует (N, R)-код, у которого для всех сообщений т, 1 ^

т М = j eWjR |, всех начальных состояний и всех р,0^р^ 1,

Ре, т (So) < 4А ехр { — N [ — pR + iV(p)]}, (5.9.6)

где

/W(p)=—-^Ц^ + maxrminfo л,(р, СЬ, s0)| , (5.9.7)

N Qn L So J

E0,n(p, Qn, s0) = --^ln|{2<Mx)PWy|x, s0)>/<> + p) ji + P. (5.9.8)

Доказательство. Подставляя (5.9.7) и (5.9.8) в (5.9.6), видим, что (5.9.6) будет совпадать с (5.9.5), если (М — 1) заменить на большую величину eNR ,|

Хотя это не понадобится нам в дальнейшем, следует отметить, что эта теорема в равной степени применима для любого составного канала с А состояниями.

’ Граница в (5.9.6) имеет экспоненциальный вид и теперь будет установлено, что Pjv (р) стремится к постоянной величине при N—*~ оо. В процессе доказательства этого станет ясно, почему удобно было включить выражение — р (In A)IN в определение функции FN (р).

Лемма 5. 9. 1. В любом заданном канале с конечным числом состояний функция Fn (р), определенная равенством (5.9.7), удовлетворяет неравенству

FN(p)>-^Fn(p)+-LFl(p) (5.9.9)

при всех положительных целых числах пи/, таких, что N = п I.

7 Зак. 210 193
Доказательство. Разобьем последовательность на входе х =

= (хг....xN) на подпоследовательности Xj = {хг....хп) и х2 = (хп +1(

xN) и разобьем у = {уг....... yN) на ух = (уи ..., уп) и уг = (уп + 1,

..., yN). Пусть Qn и Q; при заданном р будут распределениями вероятностей, на которых достигаются максимумы Fn (р) и Ft (р), соответственно; рассмотрим распределение вероятностей для х = (хь ..., xN), задаваемое равенством

Qn (х) = Qn (хг) Q, (х2). (5.9.10)

Пусть, наконец, So является начальным состоянием, на котором достигается минимум Е0 (р, QW) s0). Тогда

^(р)>--?-1,пЛ + ?o.*(p, Qn, so)

N

и имеем

ехр [ — NFn (р)] <

< Лр 2 {2 Qn (х) Pn (У | х, s5)i/d + P)ji + р =

(5.9.11)

<Л2р 222 (22 Qn(xi) Qi (х2) [Рп (ylt sjx^ s5) Рг (y2lx2,s„)]1/(i+P)i i+p.

sn yt Уs Ul Xg J

(5.9.12)

При переходе от (5.9.11) и (5.9.12) были использованы те же неравенства для суммы по sn, которые были использованы при переходе от (5.9.2) к (5.9.4). Преобразуя суммы [как при переходе от (5.5.7) к (5.5.9)], получаем

ехр [—NFn (р)1 < А2р 2 {2 [2 Ы Рп (ylt snjXl, s^)1/ч+ P>j1+^J X

Х{2[2^(х2)Рг(у2|х2, s„)>/(i+P)]i + Pj< (5.9.13)

<^p22f2Qn(Xi)P„(yi, s^lXi, s^)!/(I + P>]1 + Pexp[ — /^(p)], (5.9.14) sn yi J
Предыдущая << 1 .. 89 90 91 92 93 94 < 95 > 96 97 98 99 100 101 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed