Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
W (/') = 2 Q (*)/»( л А)-
к
Пусть для блока любой длины N N
Р„(у|х)=П Р(Уп\хп), QjV (Х) -=* П Q (АГт»).
п— 1 п
Шдг (У) =П<й (Уп).
Предположим, что R является произвольной скоростью, R < С, и для каждого N выберем код из М — r eNR- кодовых слов с помощью независимого выбора слов с распределением вероятности QN(x). Пусть е = (С — R)l2 и для каждого N определим «типичное» множество Т N как множество пар х, у, для которых
I (х; у) —С
N
< 8,
где
I (х; у) — 1 п
PN( У 1 х) ®л(у)
18 Зак. 210
545
Для любого N и любого кода из ансамбля рассмотрим декодер, который при заданном у выбирает т, для которого (хт, у) принадлежит TN. Если такие кодовые слова отсутствуют или их больше чем одно, то будем считать, что произошла ошибка.
(а) Показать, что при заданном N вероятность ошибки при условии, что на кодер поступило сообщение т, удовлетворяет неравенству
?e.m<Pr[(Xm, У) 6 1 т]^ 2 РГ [(хт', у)?Гд,[т].
т'т^т
(б) Показать, что в ансамбле кодов Рг[(хт, у) (? TN\m\ стремится к нулю при N, стремящемся к оо.
Указание: рассмотрите 1(хт; у) как сумму независимых одинаково распределенных случайных величин и используйте закон больших чисел.
(в) Показать, что в ансамбле кодов при любом т! ф т имеем
Рг[(хт', У)€:7’^|от] < ехр[ —N(C — е)].
Указание: покажите, что
РгКх«'» y)^rw|m]= 2
(хт', y)?TN Затем покажите, что при (хт, ) у)?Тм
aN (У) < PN (У i хт') ехр [ —iV (С—в)].
(г) На основе результатов пунктов (а), (б) и (в) показать, что Ре< m стремится к нулю для каждого m при N, стремящемся к оо.
5.19. Пусть хх....хм является множеством кодовых слов с длиной блока Nt
которые используются в ДСК с вероятностью ошибки 8. Пусть d(xm, xm.) — расстояние Хэмминга между хт и хт, (т. е. число позиций, в которых хт отличается от хт.).
(а) Используя границу Чернова и аддитивную границу, показать, что для декодера по максимуму правдоподобия
Ре,т< 2 ехр [d (хт, хт.) In 1/(48 (I — 8)) ].
т'^т
(б) Минимальное расстояние в коде определяется как
d-min =min d(x xm>).
ТПт^ТП
Показать, что при всех m
Pe.m<(M—l) ехр [dmin lnУ(48 (1 —ej) ]•
(в) Рассмотрим код с заданным минимальным расстоянием dmin = d, выбираемый в соответствии со следующей процедурой.
I. Запишем все 2W различных двоичных последовательностей длины N.
II. Выберем произвольное кодовое слово из этого списка.
III. Удалим из списка только что выбранное кодовое слово и все последовательности длины N, находящиеся на расстоянии d — 1 или меньшем от этого кодового слова.
Если список окажется пустым, то произвести остановку, в противном случае перейти к шагу (II).
Показать, что число кодовых слов, выбранных таким образом, удовлетворяет неравенству
I'd —1 /<-дг-\ 1-1
М > 2n
2 (?)
/=*0 V- 1 -5-' .
646
Оно называется границей Гилберта (1952).
(г) Объединяя полученные выше результаты С результатами задачи 5.8, показать, что при d < jV/2 имеем
dmin 1
N
Показать, что отсюда вытекает, что при любой скорости R = (In М)/N < 1п 2 существует код с минимальным расстоянием dmin > ON, где 6 < V2 определяется из уравнения Ж(Ь) = 1п 2 — R.
(д) Объединяя результаты пунктов (б) и (г), получить границу вероятности ошибки в виде Ре < ехр [— NE(R)] и выписать параметрические выражения, определяющие E(R). Показать, что при нулевой скорости эта граница согласуется с (5.5.1). Вычертить график E(R) при е = 0,01 и произвести сравнение с Er(R). [Заметьте, что, как показано в § 5.7, E(R) < ?еж(Я)].
5.20. Предположим, что условия теоремы 5.6.1 видоизменены так, что декодер при заданной принятой последовательности у выдает список L из сообщений ти ..., mL, для которых Р^(у|хт) являются наибольшими (здесь L — заданное целое число). Если переданное сообщение не входит в список, то считается, что произошла ошибка при декодировании списком. Пусть PL е является вероятностью ошибки при декодировании списком.
(а) Показать, что для любого р„, 0 < р0 < 1, и любого s > 0 имеем
