Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
С =
б^(б)+Е^(б)
Qo -
Р
-6 +
+ log2 [2-^ <в>/Р+ 2—^ (е)/р] , 2^ (в)/р
. Р = 1‘
б.
4.21. Если D [/ (х\ у)] = 0, то / (х; у) является постоянной, скажем, С, на тех парах х, у, для которых Q (х) Р (у | х) ф 0. Так как по предположению
О (х) > 0 для всех входов к, то I (х\ у) = С для всех х, у, для которых Р (у | х) =/= 0. Поэтому Р (у | х) I (х; у) = Р (у | х) С для всех х, у. Получаем
I (* = *; Y) = %Р (;| k) I (k\ /) = 2 Р U \k)C — С.
/ /
Теорема 4.5.1 показывает теперь, что пропускная способность достигается на Q (k).
4.22. Нетрудно проверить, что теоремы 4.4.2 и 4.5.1 применимы к каналу с дискретным входом и недискретным выходом. Поэтому, используя симметрию, получаем, что пропускная способность достигается на равновероятных входах. Пусть Сг и С2 являются пропускными способностями каналов, в которых используются у и знак у в качестве выходов соответственно. Имеем Ct > С2 в соответствии с рассуждениями о последовательном соединении каналов на стр. 41. При рассмотрении лишь знака у теряется информация относительно того, насколько вероятным является каждый вход. Позднее при изучении кодирования будет показано, что эта информация является важной, несмотря на то, что при отсутствии кодирования она не может быть использована при приеме одиночных двоичных символов. Имеем
Ci= J Pz (г — I/S) In
Pz (z — У^)
Pz (z—~V S) +Pz (z +"1/5)
dz -
= Pz (Z~VS) In
1 +e-2zYs/o^
dz (натуральных единиц).
(1)
Разлагая логарифм в ряд по степеням ~[/s, получаем
2 YSz z2 S
In
1 +e-2zYs/o* I Rz (S)I
2a*
+ Rz (S),
l?4
3a6
s3/2.
Подставляя это выражение в (1) и выполняя интегрирование, будем иметь
S
где R (S) ограничено сверху постоянной, умноженной на S и стремится к нулю при S —> 0.
Используя знак у в качестве выхода, получаем двоичный симметричный канал с переходной вероятностью 8, которая удовлетворяет неравенствам
— - < 8 < — - 1 4- 53/2
2 |/ 2ло2 2 |/ 2ло2 6 ~[/2л а3
Верхняя граница может быть получена таким же методом» как и в задаче 2.23, т. е. с помощью неравенств
г > е-г/2/(2а=) > li 2а2 ‘
Положив 8 = — е, получаем
( 1 \ 1/2 — 8 ( 1 1 /2 + 6 С* = (т - 6) 1п~~i}2~ + [2 +6)1п 1/2 •
Разлагая с точностью до второго порядка по 8 (при этом обязательно сохраняется первый порядок по S), получаем
S
Со = 2б3= — натуральных единиц. яа2
4.23. Для канала, изображенного на рис. 4.6.3, и для четного N пусть Qn Ф) обозначает вероятность входа k при n-м использовании канала и пусть
N/2 j
9= 2 [Q2B-i(0) + Qsb-1(1)+Qsb(2)+Qjb (3)] — .
п = 1
При условии, что канал начинает работать в состоянии 0, значение q является средней по последовательности N символов вероятностью использования одного из неискаженных символов (т. е. 0 или 1 при нечетных посылках и 2 или
3 при четных посылках). Аналогично 1 — q является такой же вероятностью при условии, что начальным состоянием было 1. При заданном q и'при условии, что начальным состоянием является 0, лег ко понять, используя выпуклость, что максимальная средняя взаимная информация на символ равна q log (2/q) + -f- (1 —q) log [1/(1 —q)] и достигается при статистически независимых входах, для которых 02п-1 (0) = 0ап_1 (1) = 02п (2) = 02п (3) — q 12 при 1 < п <
< N/2. Аналогично при условии, что начальным состоянием является 1, максимальная взаимная средняя информация на символ равна (1 — q) log [2/(1 — q)\ -f- q log \/q. Максимальное значение минимума из этих двух выражений равно ?/2 бит и имеет место при q — V2. Чтобы убедиться в этом, заметим, что любое изменение q уменьшает либо то, либо другое выражение.
Для канала, изображенного на рис. 4.6.4, используем тот же самый ме-
1 N
тод, положив q — ^ Qn (0). Тогда получим (в битах)
Л=1
Iq(Xn; Y^l s0 = 0) < N [—q log2 q—(1 —q) log2 (1 —q)],
Iq(XN\ Y"|s0= 1) </V[(l-<j-)log23].
Оба неравенства удовлетворяются с равенством на независимых одинаково распределенных входах с Q (0) = q, Q (1) = Q (2) = Q (3) = (1 — q)/3. Правые части неравенств равны при q = 0,391, и любое изменение q уменьшает то или другое выражение.
Для канала, изображенного на рис. 4.6.5, можно заметить, что если канал начинает работать с состояния 1, то выход не содержит информации о входе
600
и С = 0. Если канал начинает работать с состояния 0, то можно передать один бит при одном использовании канала, если использовать входы 0 и 1 независимо и с равными вероятностями. Следовательно, С > 1 бит. Так как выход является двоичным, то также С < 1 бит.