Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
РU1 и2.. . Ul ^
== Рц.+1 и.+2... vь U2> ••• ’ Ul) (3.5.1)
для всех длин L, целых чисел / и последовательностей и\, ..., и'ь. Это означает, что вероятность того, что источник производит последо-72
вательность и'на интервале от 1 до L, равна вероятности того, что производится в точности такая же последовательность на интервале от / + 1 до / + L.
Дискретный источник называется периодическим, если (3.5.1) справедливо для всех /, которые являются кратными некоторого целого числа т > 1. Период —• это наименьшее значение т, удовлетворяющее этому условию. Если рассмотреть m-блоки букв периодического источника с периодом /и как «супербуквы» большего алфавита, то последовательность супербукв окажется стационарной. По этой причине в дальнейшем рассматриваются только стационарные источники.
Пусть uL = (иъ ..., uL) — последовательность L букв дискретного стационарного источника и пусть U^U2 ... UL — совместный ансамбль для uL. Определим теперь энтропию на букву источника для дискретного стационарного источника. Имеются два подхода, которые мы можем принять, и, к счастью, оба они приводят к одному и тому же результату. При первом подходе следует определить энтропию на букву в последовательности L букв как
HL {U) ^ ±H(U1Ut...UL)~ log -L-. (3.5.2)
L L Pr (uL)
Теперь можно было бы определить энтропию на букву источника как предел HL (U) при L —оо. При втором подходе следует определить условную энтропию L-й буквы в последовательности при условии, что заданы первые L — 1 букв, Н (UL \ U± ... Ul-i) и затем определить энтропию на букву источника как
lim H(UL\U1...UL^l).
L—> со
Следующая теорема утверждает, в частности, что оба этих предела существуют и равны друг другу.
Теорема 3.5.1. Для дискретного стационарного источника с (U) < 00 имеем
(а) H(UL\ U±... UL~i) не возрастает с L,
(б) HL(U)^H(UL\U1...UL-l), (3.5.3)
(в) Hl{U) не возрастает с L,
(г) Um HL{U) = \im Н (UlIUj^ ... UL^i). (3.5.4)
L —> оо L —> со
Доказательство. Используя вначале то, что наложение условия не может увеличить энтропию (2.3.13), а также используя стационарность источника, получаем при L > 2
Н (UL | иг... UL-i) < Н (UL \ U2... UL-i) =
= H(UL-i\U1...UL-2). (3.5.5)
Это доказывает утверждение (а).
73
Используем ценное равенство (2.2.30) для разложения Нь (U), HL (U) т + H(U2\U1) + ... + H(UL\U1...UL-1)]. (3.5.6)
Согласно утверждению (а) последнее слагаемое в (3.5.6) является границей снизу каждого из L слагаемых. Применяя эту границу, получаем утверждение (б).
Согласно определению HL (U) имеем
HL (и) ^~H(U1...Ul-i) + -j-H(Ul\U1...Ul-i)^
<J~-HL-,(U) + ~HL(U). (3.5.7)
После простых преобразований получаем HL (U) HL—\ {U), устанавливая справедливость утверждения (в).
Так как HL (U) и Н (UL\U1 ... Ul-i) являются неотрицательными и невозрастающими с L, то оба предела существуют. Обозначим lim Hh (U) через Используя опять цепное равенство, получаем
L -> оо
HL+j{U) = ~H(U1..ML-,)-h~j[H(UL\U1...UL-i) +
+ H{UL+i\U1...UL)+... + H(UL+i\U1...UL+i-i)\<
^-'—H{Ul...UL-x)+'i^H(UL\Ui...UL-i). (3.5.8)
L 4~ / ‘-~г l
Здесь было использовано то, что первое слагаемое в квадратных скобках является верхней границей для каждого из остальных слагаемых. Переходя в (3.5.8) к пределу при /-> оо, получаем
HobM^HiULlU^-.UL-i). (3.5.9)
Так как (3.5.9) справедлива при всех L, то будем иметь
Ноо (U) < lim Н (UL | Ux... UL-1). (3.5. Ю)
L-* оо
Неравенства (3.5.10) и (3.5.3) устанавливают справедливость (3.5.4), что завершает доказательство теоремы. [
Теорема 3.5.2. (Теорема кодирования для источника неравномерным кодом.) Пусть HL (U) — энтропия на букву в последовательности длины L дискретного источника с алфавитом объема К. При заданном кодовом алфавите с D символами можно так закодировать последовательности из L букв источника префиксным кодом, что среднее число кодовых букв на букву источника п будет удовлетворять неравенствам
------------------1-----. (о.5.11)
logD log D L
Более того, левое неравенство справедливо для любого однозначно декодируемого множества кодовых слов для последовательностей L
74
букв источника. И, наконец, если источник является стационарным, то для любого б > 0 можно выбрать L столь большим, чтобы п удовлетворяло неравенствам
„К10ч
