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

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

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 252 253 254 255 256 257 < 258 > 259 260 261 262 263 264 .. 355 >> Следующая


(а) Считая, что хп являются гауссовскими случайными величинами, оценить Рг(г > iV). (Используйте оценку

оо

J У~2ла V2nW

y = \V

справедливую при больших W.) Сравните полученный результат с границей Чернова и обычным неравенством Чебышева.

(б) Пусть хп — 1 с вероятностью 1/2 и хп = — 1с вероятностью 1/2. Показать, что при N = 100 имеем Pr(z > N) = 2~100. Сравните это с границей Чернова для Pr(z > N), неравенством Чебышева и оценкой, получаемой на основе центральной предельной теоремы. (Это дает хороший пример для того, чтобы понять, почему слово «центральной» стоит в названии центральной предельной теоремы.)

5.6. Доказать, что в (5.6.10) минимум по s > 0 достигается при s = 1/(1 +

+Р)-

Указание: используйте неравенство Гёльдера (см. задачу 4.15) для того, чтобы показать, что

[2<Ых)^(у1х)1/1+р]1+р<

5.7. Предположим, что два кодовых слова длины N для канала, изображенного ниже, выбираются так, что каждая буква каждого кодового слова выбирается независимо с распределением вероятности Q(0) = Q(l) = Q(2) = 1/3.

(а) Найти среднюю по ансамблю вероятность ошибки в предположении, что используется декодирование по максимуму правдоподобия. В случае неопределенности предположите, что декодер делает ошибку. Не применяйте здесь теорему кодирования; начните с начала и используйте специфику этого канала.

539
Указание: пусть посылается хх и принимается у. Подсчитать, сколько последовательностей на входе канала х могут привести к у и найти РЛ,(у|х1) для каждой из них. Затем найти вероятность того, что кодовое слово х2 было выбрано в этом множестве.

(б) Используйте ваш результат, полученный в пункте (а), для того чтобы ограничить сверху вероятность ошибки для кода с М словами, выбираемыми независимо из того же самого ансамбля. Используйте аддитивную границу для множества неправильных сообщений. Сравните ваш ответ с тем, что утверждает теорема кодирования.

(в) Предположим, что код состоит из двух кодовых слов Xj = (0, 0, 0..0)

их, = (1, 1, 1, ..., 1). Найти вероятность ошибки для этого кода при той же самой процедуре декодирования, что и в пункте (а). Объясните отличие в ваших ответах в пункте (а) и в пункте (в).

5.8. При рассмотрении двоичных каналов часто полезно иметь точные границы для биномиальных коэффициентов

(а) Показать, что при j > 1, N - j > 1

N____ ( N \ —NtfC(HN) / N

8j(N—j) V i J V 2nj(N-j)

где

Ж (jiN)=—— In—— f 1—— | In j I—— u ' N N \ N J \ N

Указание: используйте формулу Стирлинга (см. Феллер (1950), т. 1, гл. II,

§ 9)

I N

,-------( N \ N

ЛМ = /2яЛГ^ —J ехр(ед,);

где вд, убывает с ростом N и находится в пределах 0 < bn < Нижняя гра-

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

(б) Используя пункт (а), доказать более слабые границы

— ' ( N \ e-N#?uiN)

2N j ) ^ ’

/ 2N— 1 \ 1

>------22N~ 1

\ N ) yw1

Указание: для последнего неравенства покажите, что (д/^j = 2 ^ ,

(в) Пусть 6 произвольно, 0<б< 1, / < /V и j/N > в. Показать, что

^ j в1 (1 —B)N~i < ^ ^ ^ j е" (I — е)^-п <

------1Л1-е)--------/лм,

/ (1_е) —(Д^—/) е V / J У 1

Указание: для верхней границы покажите, что N \ ? N \ / N—п

я + 1/ <'1я/\ п

540
и использовать это для того, чтобы установить неравенство

( N \ ( N \ ( N—/

Затем просуммировать по / как геометрическую прогрессию. Используйте этот результат совместно с результатом пункта (а) для того, чтобы получить верхнюю и нижнюю границы для

где хп — статистически независимые случайные величины, принимающие значение 1 с вероятностью е и значение 0 с вероятностью 1 — е. Показать, что

Сравнить это с вашим результатом в пункте (в).

5.9. (Теорема кодирования для ДСК, использующая биномиальные коэффициенты.) В ДСК с вероятностью ошибки s рассмотрим ансамбль блоковых ко-

вах выбираются независимо с Q(0) = 0(1) = V2- Для любого кода из ансамбля рассмотрим декодер, который при заданном у выбирает сообщение т, для которого d(xm; у) минимально, где d(xm; у) является расстоянием Хэмминга между хт и У (Т- е- равно числу символов, в которых отличаются хт и у).

(а) Показать, что этот декодер является декодером по максимуму правдоподобия.
Предыдущая << 1 .. 252 253 254 255 256 257 < 258 > 259 260 261 262 263 264 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed