Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
93
Рассмотрим вначале последовательность и = (иъ ... , щ) из L букв дискретного источника, изображенного на рис. 4.3.1. Энтропия на букву для последовательности из L букв определяется равенством
HL (U) = ^ Рг (u) log Рг (и). (4.3.1)
L L и
Как было показано в теореме 3.5.1, для стационарного источника HL (U) не возрастает вместе с L и стремится к пределу (U) при L-> оо. Для дискретного источника без памяти, очевидно, Hi (U) = = Н (U) при всех L.
Рис. 4.3.1. Система связи.
Предположим, что выходом декодера является последовательность у = (иь ..., vl) букв того же самого алфавита, что и алфавит источника. При любых заданных источнике, кодере, канале и декодере существует совместная вероятностная мера*’ на множестве возможных входных последовательностей и п множестве возможных выходных последовательностей v.
Целью системы связи является получение последовательности v, воспроизводящей последовательность и. Если и1фх)1, то считается, что произошла ошибка в l-м переданном символе. Вероятность такой ошибки Ре г определяется совместным ансамблем ULVL. Средняя вероятность ошибки <Ре> в последовательности из L символов определяется следующим образом:
<Pe> -T%Pe.t- (4-3.2)
L 1=1
Математическое ожидание числа ошибок в последовательности равно L(Pe). В последующих главах мы часто будем иметь дело с вероятностью одной или более ошибок в последовательности длины L. Здесь, однако, мы хотим показать, что надежная передача невозможна, если энтропия источника больше, чем пропускная способность. Таким образом, даже, если бы было показано, что вероятность ошибки в последовательности равна 1 для больших L, то это бы гарантировало лишь су-
*) Как будет отмечено в § 4.6, для каналов с памятью это утверждение требует некоторого разъяснения. Однако до этого времени предполагается существование такой вероятностной меры.
94
шествование одного ошибочного символа среди L или <Pe>^l/L. Следовательно, для того чтобы показать, что <РеУ отлично от нуля в пределе при L-^-oo, надо непосредственно рассмотреть <Ре> а не вероятность ошибки в последовательности.
Начнем с установления соотношений между <РеУ, Hl (U) и / (UL; VL) в частном случае, когда L = 1. Затем распространим этот результат на случай произвольного L и, наконец, свяжем / (UL; \L) с пропускной способностью канала.
Теорема 4.3.1. Пусть UV является совместным ансамблем, в котором выборочные пространства U и V состоят из одних и тех же М элементов аъ ..., аМ- Пусть Ре является вероятностью того, что случайные величины и и и не равны друг другу:
Ре-ПР(«,»). (4.3.3)
и V-/--U
Тогда
Ре log (М—
где
Ж(Ре) = -Ре 1<
Обсуокдение. Функция Ре log (М — 1) -г Ж (Ре) изображена на рис. 4.3.2. Теорема утверждает, что, если Н (U\V) принимает заданное значение, отложенное на оси ординат на рис. 4.3.2, то Ре должно быть не меньше соответствующей абсциссы. Так как Я (U\V) =
= H(U) — I(U, V), то теорема ограничивает Ре с помощью выражения, представляющего собой превышение энтропии источника над средней взаимной информацией, справедливость (4.3.4). Средняя неопределенность и при заданном v может быть разбита на два члена: первый, представляющий неопределенность, относящуюся к тому, была совершена ошибка или нет при заданном v, и второй, представляющий неопределенность переданной входной буквы в случаях, когда была сделана ошибка. Первый член ограничен сверху значением Ж(Ре), а второй член — значением, равным Р е, умноженным на максимальную неопределенность при условии, что произошла ошибка. Так как неопределенность при условии, что произошла ошибка, состоит в выборе между М — 1 альтернативами, то второй член ограничен сверху значением Р е log (М — 1).
Доказательство. Можно записать Н (U\V) как сумму двух слагаемых; одно, включающее пары и, v, которые приводят к ошибке,
95
+ Ж(Ре)>Н(и IV), (4.3.4)
¦ Pe — U—Pe) l0g(l—-Ре). (4.3.5)
__юдм
Щ(М-1)
Рис. 4.3.2. Интерпретация теоремы 4.3.1.
Легко эвристически установить
ифь, и другое, содержащее пары и, и, для которых и = и:
1
А иф V
(4.3.6)
Согласно (4.3.3) разность между выражениями, стоящими в разных частях (4.3.4), равна
Н (U\V)-Pe log (М-1) - Ж (Ре) =
=2 2 и)1о§ш-1)Рр(И|0")'+ 2 р(«> и)1о§-
У «7^ У
1-Ре
Р (и I и)
(4.3.7)
С помощью неравенства log z< (loge) (2 — 1) приходим к тому, что правая часть (4.3.7) меньше или равна выражению