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

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

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


(а) Показать, что последовательность xlt х2, ... представляет собой неоднородную цепь Маркова.

(б) Предположим, что каждый канал имеет входной и выходной алфавиты объема К и что имеется б > 0, не зависящее от п, такое, что п-й канал в соединении имеет по крайней мере одну выходную букву, хп+1, для которой P(xn+il*n)'>

> б при любых входах хп. Показать, что ЦХ^, Хп) стремится к нулю с ростом п и эта информация ограничена сверху выражением 2^(1 — б)п loge.

Указание: примените лемму 4.6.2.

¦ 4.26. Предположим, что канал с конечным числом состояний, в котором имеется только память, связанная с межсимвольной интерференцией (т. е sn является функцией sn-i и хп), переходит в некоторое известное состояние. Показать, что он может перейти в это состояние не более чем после 2А — А—1 входов, где А — число состояний.

Указание: пусть для последовательности входов, которая приводит канал в некоторое известное состояние, Вп обозначает множество возможных состояний канала после re-го входа.

Покажите, что если последовательность Вп имеет какие-либо повторения до достижения известного состояния, то последовательность входов может быть укорочена.

Г л а в а 5

5.1. Будем считать, что целые числа от 1 до Ai кодируются в последователь ности входов канала хх, ..., х^. Пусть у будет последовательностью на выходе канала и пусть заданы Рдг(у|хт), 1 < т < М. В случае, когда стоимость деко-

537
дирования переданного сообщения т в т' задается функцией С(т, т'), а распределение вероятностей на входных целых числах от 1 до М задается функцией Q(m), найти правило декодирования, которое приводит к минимальной средней стоимости.

5.2. (а) Вычислить

ёп (*)=1>Р(Уп\0)1-$ Р(Уп \ 1)S Уп

для каждого из следующих каналов и для каждого из них минимизировать gn(s) на 0 < s < 1. Используйте этот результат для получения верхней границы вероятности ошибочного декодирования по максимуму правдоподобия Ре, т(т = «= 1,2), достижимой при использовании кода с двумя кодовыми словами xt (последовательность из N нулей) и х2 (последовательность из N единиц).

(б) Для первых трех указанных выше каналов найти точные выражения для вероятности ошибки. Найдите численные значения этих выражений с точностью до двух значащих цифр (используя в случае необходимости формулу Стирлинга N1 л;"1/2яN(N/e)N при N = 25 и е = 0,1 и сравните их с границей из пункта (а).

(в) Показать, что в ДСК для больших четных N вероятности Рв: t и P6t 2 [см. (5.3.14) и (5.3.15)] приближенно задаются равенствами

Показать, что для больших нечетных N имеем

(г5?) ¦ч'йлпв*-

Указание: используйте то, что в окрестности i= N/2 значение изменяется медленно по сравнению с вг(1 — e)N~?.

(г) Для Z-канала найдите верхнюю границу и оцените Ре,т(т — 1,2) для кода с двумя кодовыми словами, в котором xt образовано из N/2 нулей, за которыми следуют N/2 единиц, а х2 образовано из N/2 единиц, за которыми следуют N/2 нулей. Заметьте, что для остальных каналов это изменение кода не дает различия.

5.3. (а) Найти границу (5.5.10) для средней вероятности ошибки по ансамблю кодов с двумя кодовыми словами для каналов из задачи 5.2. Найти минимумы границ по Q(k).

(б) Для того же самого ансамбля и тех же самых каналов найти верхнюю границу для l/N\nPetTn, т. е. для среднего показателя экспоненты вероятности ошибки, используя <?(0) = <?(1) = 1/г. и истолковать полученный результат как границу вероятности ошибки для типичного кода из ансамбля.

5.4. Заданные М сообщений кодируются в последовательности двоичных символов длины N; М последовательностей выбираются независимо из 2N возможных последовательностей с равномерным распределением вероятностей. Так как любая ошибка, которая происходит при декодировании принятой последо-

538
вательности по максимуму правдоподобия, происходит потому, что одно или больше из М —• 1 неправильных сообщений являются более правдоподобными, чем правильное сообщение, то используйте границу средней вероятности ошибки, полученную вами для случая кода с двумя случайно выбранными словами, и тот факт, что вероятность наступления одного или большего числа событий меньше или равна сумме их вероятностей, для того чтобы получить границу вероятности ошибки при передаче М сообщений в каждом из четырех каналов задачи 5.2. Найти максимальную скорость передачи R = (\nM)/N, при которой ваша граница будет экспоненциально убывающей с ростом N.

5.5. Пусть

N

г= 2 п= 1

где хп — статистически независимые одинаково распределенные случайные величины со средним значением, равным нулю, и дисперсией, равной единице.
Предыдущая << 1 .. 251 252 253 254 255 256 < 257 > 258 259 260 261 262 263 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed