Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
(б) При условии, что на входе кодера было сообщение т, показать, что
Указание: используйте ваши результаты в задаче 5.7. (в) при е = г!г и ? = = N — /.
(г) Пусть
N
п= 1
и использовать границу Чернова для того, чтобы показать, что
In (1 —е) |.
дов с длиной N и с М = eNR кодовыми словами, в котором буквы в кодовых ело
Pr[d(xm/) у) = г']= 2 N, при всех т'фт,
где вторая вероятность взята по ансамблю кодов,
(в) Показать, что для заданного сообщения т
Рг [ошибка | d(\m, y) = t] <
1,
N—i
2-"<
< jW—2i
(г) Используя пункты (б) и (в), показать, что средняя по ансамблю вероятность ошибки ограничена при любом / < N/2 неравенством
¦ 2
»=/
(д) Выбрать / так, чтобы удовлетворялись неравенства
и построить границу сверху для каждой из этих сумм, либо с помощью метода геометрической прогрессии [см. задачу 5.7 (в)], либо оценивая сверху сумму наибольшим слагаемым, умноженным на число слагаемых в сумме. Внимательно следите за тем, выполняется ли неравенство
Показать, что вами получена та же самая экспонента по N, как и в примере 1
5.10. Найти показатель экспоненты случайного кодирования ET(R) (в параметрической форме) для двоичного стирающего канала с вероятностью стирания е. Построить график ET(R) при е = 1/2, выбрав некоторые определенные числовые значения Ет(0), Rcr = Е0(р)!др | р=1 и Er(Rcr). Дать геометрическую интерпретацию Er(R) подобную той, которая была дана на рис. 5.6.4 для ДСК.
5.11. (а) Найти показатель экспоненты случайного кодирования Er(R) для изображенного ниже канала с пятью входами, пятью выходами и всеми переходными вероятностями, равными 1/2.
(б) Найти код с длиной блока1 и скоростью R = 1п2 (т. е. со скоростью один двоичный символ на одно использование канала), такой, для которого Ре — 0. Найти код с длиной блока 2 и R — (In 5)/2 (т. е. с пятью кодовыми словами), такой, что Ре = 0.
Замечание: пропускная способность канала с нулевой ошибкой С0 определяется как наибольшая скорость, для которой Ре = 0 может быть достигнута при конечной длине блока [Шеннон (1956)]. Таким образом, вы показали, что С0 > (1п5)/2 для этого канала. Неизвестным является то, будет ли С0 строго больше, чем (1п5)/2.
5.12. Пусть Q будет распределением вероятностей на входе, на котором достигается пропускная способность дискретного канала без памяти. Показать, что при R, близких к С, функция Er(R, Q) ведет себя как а (С — R)2, и подсчитать постоянную а.
§ 5.6.
542
5.13. Показать, что в произвольном ДКБП с двоичным входом функция ?о(Р| Q) Достигает максимума по Q при р = 1 в точке <J(0) = <J(1) = Vs-
5.14. (Декодирование со стираниями и ошибками.) Рассмотрим ДКБП с переходными вероятностями P(j\k). Пусть Q(k) обозначает входные вероятности, на которых достигается пропускная способность, и пусть
w(/)=Sq (k)pu\k).
k
Рассмотрим ансамбль кодов с длиной блока /V и с М = 2NR кодовыми словами, в которых все символы кодовых слов выбраны независимо с распределением вероятности Q(k).
Рассмотрим декодер, который работает следующим образом. При заданной принятой последовательности у декодер вычисляет
N
PN (у 1 хт) 2 ,_Р(Уп\Хт,п)
п= 1
= !п—' —-= У, In
Юдг (у) ю (уп)
для каждого кодового слова хт, 1 < т < М. Декодер сравнивает все 1т с TN, где Т — некоторый фиксированный порог. Если имеется одно и только одно значение т, для которого Im > TN, то декодер декодирует это сообщение. В противном случае декодер производит стирающий символ и не декодирует никакого сообщения.
Пусть Рг будет вероятностью в ансамбле кодов того, что переданное кодовое слово не удовлетворяет порогу, и пусть Р2 будет вероятностью того, что одно или большее число других кодовых слов удовлетворяют порогу.
(а) Примените границу Чернова для того, чтобы показать, что
Ру < ехр [—Na],
Р2 <ехр [—/V (а-\-Т— #)],
a = max —1п Г2^(^)ш (/)s Р (/1 k)1 — s esr o<s<i L/.ft
(б) Показать, что а > 0 при Т < С, где С пропускная способность канала в натуральных единицах, и что а -> О при Т С.
(в) Показать, что Ру + Р2 является верхней границей вероятности стирания при декодировании и что Р2 является верхней границей для вероятности ошибочного декодирования. Изобразить графически а + Т — R как функцию R в пределе при Т С и проведите сравнение с показателем экспоненты случайного кодирования. Указать, что это означает для канала, в котором имеется бесшумная обратная связь от приемника к передатчику. Подобная, но более сильная граница для вероятности стирания и ошибки имеется у Форни (1968).
