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

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

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 288 289 290 291 292 293 < 294 > 295 296 297 298 299 300 .. 355 >> Следующая


5.8. (а) Применение формулы Стирлинга дает



что равносильно N /

N

2л j (N— j)

N

N-j

N-i

ехр[8д, —Bj — ew_/],

,~N&e (UN)

N

2 nj(N-j)

exp [e

e;—

Так как eN < г. и e,N_j> 0, то, замечая, что ехр [Ед, —г. — < 1,

получаем искомую верхнюю границу. Для нижней границы eN > 0 и

1 1

ехр [8дг — ej—ед/-— /1 > ехр

12/ 12 (N—j)_

607
1 1 1

Заметим теперь, что —-------—------------- >—— с исключением случаев

12/ 12 (N— /') 9

/ = 1, N — j= 1; /= 1, N — j — 2 и /=2, N—/ = 1. Таким образом, за этими исключениями имеем

ехр [6yv -г}-eN_ ,] > ехр [ ) >

/т- ¦

>/-snbr/T-V

V / ; г 2nj(N-j) V 8 У 8/(JV-/)

Нижняя граница должна быть оценена численно для указанных выше исключительных случаев и можно увидеть, что неравенство имеет место при/ = 1 и N — /= 1.

jV

(б) Минимизируя !/ —------------ по /', 0</<jV, находим, что минимум

8 j(N — i) ______________

N , / 1

1 / " 1 / 1

достигается при j=N/2, что дает I/ ---------- -------> I/ ——. Аналогично

___________ V 8 l(N—j) \ 2N

N

максимизируется по целым /, 1< j < N—1, и достигает

2 nj(N-j)

V/ N _ / 1

------------< I / -----< 1 .

2nj(N—j) ^ ^ 2п

/"У

Заметим, что 1/ ------- является границей, в которую не входят ни N, ни /.

у 2я Далее отметим, что

2N~1 ^ —( 2N \ > -i- (1/2) |/ __L_ __ 1 / 1 22N~ 1

N j 2 \ N j " 2

]/ AN AN ‘

(в). Нижняя граница является очевидной, а верхняя граница следует непосредственно из указания; получаем

N \ ( N \ I N—п \ ( N \ (N—п

<

/ N \ ( N \ / N—(j + tn—1) \ / JV \ ( N—/

\/+« / \/+/я —1 J V } + т— 1 1 \/ + т—1

По индукции будем иметь

(/+.М")(-т*Г-

Из пунктов (а) и (в) следует, что

f N

\ Sj(N-j) ехр {yV-^(//jV) + /lne+ (N~i) In (1 —е)}

<2 CI)'"у

N

X

п=/ ¦ ¦ 2л/ (Л/— /)

608
(г) Первый результат получается легко. Для границы Чернова имеем Рг [ш > /] e“s/ [se^-f (1—e)]‘v при всех s > 0.

Правая часть достигает минимума по s > 0 при

(1-6) UN

s = ln

После преобразования получаем Pr [w > j] < ехр jN

в(1 — j/N)

М — )+ — 1пе + —------------ In (1 — е)

\ N ) N N У .

Сравнивая с (в), получаем, что граница Чернова дает правильную экспоненциальную зависимость от N.

5.9. (а) Рг (у j xm) = srf(Xm’ У) (1 — ?)N~d(x™’ у>.

Это выражение убывает с ростом d (хт, у) так, что выбор т для минимизации d (хт, у) равносилен выбору пг для максимизации Рг (у | хт).

(б) Когда сообщение т поступает на кодер и какое-нибудь частное значение хт передается по каналу, то d (хт, у) является числом ошибок, которые происходят в канале. Следовательно, Pr [d (хт, у) = г] просто равна вероятности г ошибок для N символов. Поэтому

Pr [d {хт, у)=,'] = ^ ) е‘(1 -в)"-'.

Точно так же при каждом т' ф т кодовое слово хт, статистически не зависит как от хт, таки от переходов в канале и поэтому хт, не зависит от у при условии, что т поступает на кодер. Так как каждая компонента хт, является 0 или 1 с рав-ными вероятностями, независимо от у, то отсюда следует, что каждая компонента хт’ отличается от соответствующей компоненты у с вероятностью Va, так что

СИ

Pr [d (хш/, у) = г] —вероятность г отличий в N символах—равна

(в) Ошибка происходит только тогда, когда d (хт,, у) < d (хт, у) при т’ Ф т. Ограничивая сверху вероятность объединения этих событий суммой вероятностей, получим

Рг [ошибка | d(xm, у). /] 2 Pr[d(xm,, y)<t|d(xm, у) = »'] -

т ’ т

Однако, как уже было показано, на ансамбле кодов d (хт,, у) не зависит от d (хт, у) и поэтому

Pr [d (хт,, у) < i I d (хт, у) = /] = V ( ) 2~N-

п—0 \ П )

Так как имеются М — I возможных значений для т’ Ф т и так как вероятность не превосходит 1, то

Рг [ошибка ] d (хт,, у) = i] ~

Предыдущая << 1 .. 288 289 290 291 292 293 < 294 > 295 296 297 298 299 300 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed