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

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

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 45 46 47 48 49 50 < 51 > 52 53 54 55 56 57 .. 355 >> Следующая


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) меньше или равна выражению
Предыдущая << 1 .. 45 46 47 48 49 50 < 51 > 52 53 54 55 56 57 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed