Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(а) Считая, что хп являются гауссовскими случайными величинами, оценить Рг(г > 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; у) является расстоянием Хэмминга между хт и У (Т- е- равно числу символов, в которых отличаются хт и у).
(а) Показать, что этот декодер является декодером по максимуму правдоподобия.