Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
D1[u-v(u)]^T[d + V3P(B)d1
где dmax — (1/7") 2Х; — средняя мощность источника. Подставляя
(9.7.69), (9.7.51), (9.7.40) и (9.7.45) в (9.7.49), получаем
dT<d*+-^ + yW(B)dtmax. (9.7.70)
Наконец, Р (В) оценивается сверху правой частью (9.7.63). Доказательство будет завершено, если будет показано, что это выражение стремится к 0 при Тоо. Заметим, что L является функцией Т и из теоремы Каца, Мардока и Сеге следует (см. лемму 8.5.2), что
lim А = Г df. (9.7.71)
Т~*со Т J
f ¦¦ F (f)>l/(2p)
Если F (f)= 1/(2р) в ненулевой области частот, то (9.7.71) не справедливо, но LIT может быть ограничена сверху в пределе при больших Т, если использовать меньшее значение р в (9.7.71). Следовательно, Р (В) стремится к нулю при Т -> оо, и для достаточно больших Т имеем dr d* + б, что завершает доказательство. (
9.8. дискретные эргодические источники
В этом параграфе рассматривается дискретный стационарный эргодический источник с алфавитом (0, 1, .., К — 1). Выход источника ..., и_j, и0, иъ ... представляется у адресата последовательностью букв ..., v0, vx, каждая из которых выбирается из алфавита
(0, 1, .., J—1). Предположим, что имеется мера искажения d (u, i>0) между последовательностью букв источника и отдельными буквами адресата. Например, если адресата интересует только появление пар последовательных единиц на выходе двоичного источника, то приемлемая мера искажения должна бы иметь вид
d(u^, и0; v0) = (°’ = 0»*
[ 1 в других случаях.
В этом примере искажение для l-й буквы выходной последовательности должно иметь вид d («г-i. иь Vi), где d — указанная выше функция. Для общей меры искажения d (u; v0) можно задать искажение для /-й буквы адресата, сначала определяя /-й сдвиг входной последовательности и равенством Т1и = и', где и'п = ип+г. В обозначениях этого оператора сдвига искажение между и и иг определяется какй (Т1 и; кг). Наконец, с помощью меры искажения d (и; о0) определим общее искажение между и и последовательностью и„, ..., vL как
L
D{u; v0, ..., vL)-= 2 d(Tlu\ vt). (9.8.1)
г = 1
Для простоты примем в дальнейшем, что d (и; о0) неотрицательна и ограничена. Однако не будем предполагать, что для каждого и можно выбрать v0, для которого d (и; и0) = 0. Меры искажения только что 504
определенного класса назовем аддитивными инвариантными во времени мерами искажения.
В последующем изложении сначала определим скорость как функцию искажения для таких источников и мер искажения. Затем докажем теорему кодирования для источника, показав, что эта скорость как функция искажения допускает такое же истолкование, что и скорость как функция искажения для дискретных источников без памяти с мерой искажения для одиночной буквы.
Пусть и = (..., и_ъ и0, ии ...) обозначает бесконечную последовательность источника и пусть uL = (иь ..., uL) обозначает последовательность L букв из и. Аналогично пусть vL = (vlt ..., vL) обозначает соответствующую последовательность букв адресата. Рассмотрим передачу последовательности uL по каналу с шумами; пусть vL — принимаемая последовательность. Канал и любые преобразования, сопровождающие передачу, можно описать с помощью переходной вероятности L-ro порядка PL (vL | uL). Примем, что при заданном uL принятая последовательность статистически не зависит от других букв последовательности бесконечной длины и, т. е. что Р (vL | и) = PL (vL|uL). В соединении с вероятностной мерой источника PL (vL | иь) определяет среднюю взаимную информацию / (?/1; ..., UL; Vlt ..., VL) между последовательностями uL и vL. Аналогично PL (vL | uL) определяет среднее значение общего искажения*) между и и vl, т. е. D (u; vL).
Скорость как функция искажения L-ro порядка для заданных источника и меры искажения определяется как
RL(d*)= min -i- / (i/x, ..., UL; V1,...,VL). (9.8.2)
l — L
PL : -j- D < d*
Минимизация проводится по всем заданиям переходных вероятностей Pl (vl | иь), таким, что среднее искажение на букву (1 /L)D (u; vL) не превосходит d*. Для тех ситуаций, когда min d (u; v0) не равен 0 при
всех и, множество ограничений в приведенной выше минимизации может быть пусто для малых d* ив этих случаях полагаем RL (d*) равной оо. Так же как и в § 9.2, показывается, что функция RL (d*) неотрицательная невозрастающая и выпуклая w по d*. Скорость как функция искажения для источника определяется как
R («.'*) lim RL{d*). (9.8.3)
L -> оо
Следующая простая теорема утверждает, что этот предел существует, а также что для любого L значение RL (d*) ограничивает сверху
