Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Pe{N, Г ехр [NR (б, N)] ~\] > f (б) — е, где функция /(б) является положительной при всех б, возрастающей по б, и
¦ I = V,.
5.37. (а) Пусть задан канал с конечным числом состояний. Предположите, что передатчик знает начальное состояние и использует отдельный код для каждого начального состояния. Пусть декодер использует то же самое правило декодирования, как и в (5.9.1) — (5.9.5), показать, что в этом случае можно изменить порядок взятия минимума и максимума в (5.9.5) [см. Юдкин (1967)].
(б) Предположим, что приемник знает начальное состояние и декодирует сообщение т, которое максимизирует Рдг(у/х, s0). Показать, что (5.9.5) также
справедливо и в этом случае, и что множитель А1^~р можно опустить в выражении для границы.
(в) Для канала, изображенного на рис. 4.6.3, показать, что минимакс в
(5.9.5) достигается на входном распределении, соответствующем равновероятным независимым входам. Показать, что максмин в пункте (а) достигается на том же самом распределении, на котором достигается С (см. § 4.6').
5.38. Рассмотрим канал с двоичными входом и выходом, в котором выходные, символы уп связаны со входными символами хп равенством уп = хп ф гп. Предположим, что шумовая последовательность гх, г2, ... не зависит от входа и представляет собой выход марковского источника с эргодической последовательностью состояний (см. § 3.6).
(а) Показать, что пропускная способность канала равна log 2 — (Z),
где H^Z) является энтропией шумовой последовательности [см. (3.6.21)]. Показать, что эта пропускная способность больше, чем пропускная способность ДСК с вероятностью ошибки PZfl( 1).
(б) Рассмотрим ансамбль кодов с QN(x)= 2~N для всехх. Показать, что
Я0.лг(Р. s„) = pln2-^P 1п2М2Ы1/(1+0).
Z
(в) Пусть [а(р)] — матрица порядка А X А с элементами
аг, i ¦= 2 P(Zn' Sn = i I sn-i = 0l/(l+p)-
zn
§51
Пусть А.(р) является наибольшим собственным значением матрицы [а(р)]. Показать, что
lim Е0' N (р, Од,, s0) =р 1п 2 — (1 -f р) In Л. (р).
N -* ОО
5.39. Рассмотрим класс неразложимых каналов с конечным числом состояний, в которых отсутствует память, связанная с межсимвольной интерференцией (т. е. последовательность состояний не зависит от входа) и в которых sn является функцией уп при каждом п. Например, канал, изображенный на рис. 5.9.1, принадлежит этому классу. Показать, что для любого канала из этого класса, пропускная способность достигается на независимых одинаково распределенных входах и что пропускная способность равна пропускной способности ДКБП с
Р (Уп I хп) = ^ Р (уп | xn, sn_i) q (s7i_1).
Глава 6
6.1. Код отображает пары информационных символов в кодовые слова длины 5 по следующему правилу:
Информационные Кодовые слова
последовательности
00 00000
0 1 01101
1 0 10111
1 1 11010
(а) Показать, что полученный код является систематическим кодом с проверкой на четность и выразить каждый символ кодового слова в виде линейной комбинации информационных символов.
(б) Найти для этого кода порождающую и проверочную матрицы.
(в) Привести таблицу декодирования для случая декодирования по максимуму правдоподобия в ДСК с переходной вероятностью е < V2.
(г) Сколько конфигураций 1, 2, и 3 ошибок исправляется при использовании этой таблицы декодирования? Сколько вообще существует конфигураций 1,
2 и 3 ошибок? Найти вероятность неправильного декодирования.
6.2. Представленное на рисунке устройство используется для кодирования двоичных символов при передаче по двоичному симметричному каналу с пере-
ходной вероятностью е < 1/2. Первоначально регистр сдвига заполнен нулями; затем в регистр поступают четыре информационных символа и одновременно передаются по каналу. После этого передаются три проверочных символа; перед
552
Вычислением каждого проверочного символа все четыре информационных символа сдвигаются в регистре сдвига на одну позицию вправо по сравнению с пре-дыдущим положением.
Найти проверочную матрицу, порождающую матрицу, таблицу декодирования и вероятность ошибочного декодирования для этого кода.
6.3. (а) Показать, что в коде с проверкой на четность либо все кодовые слова со ержат четное число единиц, либо половина кодовых слов содержит нечетное число единиц и половина — четное.
(б) Пусть хт, п — я-й символ в т-и кодовом слове кода с проверкой на четность. Показать, что при любом заданном п или ровно половина, или все хт,п равны нулю. Объяснить, как можно улучшить код, если все хт<п при данном’л равны нулю.
(в) Показать, что среднее число единиц в кодовом слове, усредненное по всем кодовым словам блокового кода длины N с проверкой на четность, не должно превышать NJ2.
