Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Доказательство. Покажем, что для любого 6 > 0 может быть достигнуто среднее искажение на букву d < d* + 6. Если С = 0, то теорема тривиальна, так что будем предполагать, что С = R (d*) > 0. .Из условий теоремы следует, что dmax конечно, где dmax — наименьшее значение, для которого R (dmax) = 0. Следовательно, d* < dmax и R (d*) строго убывает по d*, где С = R (d*). Пусть dx = d* + 6/2 и пусть 6Х равно наименьшему из чисел 1/2 [С— R (dj] и 6/4. Из теоремы 9.6.2 следует, что можно выбрать код столь большой блоковой длины L, что число кодовых слов удовлетворяет неравенству
оо
(9.6.14)
М < ехр ILR (dj) + L6J <; ехр [L (С — 6^] (9.6.15)
и искажение на букву удовлетворяет неравенству 488
dL < dy + 6, < d* + 3/46, (9.6.16)
и для всех v из кода d (u; v) < oo.
Так как имеется конечное число букв в этом заданном коде, то d <
< оо можно выбрать равным максимуму d (и; v) по буквам v из кода. Теперь среднее искажение на последовательность при условии, что кодовое слово источника vm ошибочно воспроизводится каналом как \т>, равно среднему искажению между vm- и теми и, которые отображаются в vm. Оно ограничено сверху Ld/Рг (vm). Так как вероятность ошибочного декодирования в канале может быть сделана произвольно малой (быть может, одновременным кодированием многих блоков источника), то вклад в среднее искажение из-за ошибок в канале может быть сделан сколь угодно малым для заданного кода источника, и среднее искажение на букву, включающее ошибки в канале, удовлетворяет неравенству dL ^ d* + б. |
Для того чтобы глубже понять, почему в теореме требуется, чтобы d (и\ v) < оо для всех v, полезно рассмотреть код, для которого d(u;vitin) = о°, скажем для /-й буквы т-то кодового слова кода. Предположим, что этот код источника используется для передачи по дискретному по времени каналу без памяти с минимальной переходной вероятностью Pmin > 0- Если для кода канала с длиной блока N имеется какой-либо выход канала, который декодируется в vm, то при любом выборе Ui последовательность vm (и, следовательно, уг> т) будет возникать с вероятностью, не меньшей Ртш- Тогда среднее искажение для /-й буквы кода удовлетворяет соотношению
W) >| Я (Щ) Pi (vi,m | Щ) d (hz; vlim) dut >
> Pmin j Ц («/) d {ui, vt>m) dut = oo.
При попытке вычислить функцию R (d*) для любых заданных непрерывного по амплитуде источника и меры искажения удобно (как и в § 9.4) иметь дело с функцией
R0 (р, Р) = / (U) V) + pd, (9.6.17)
где через Р обозначен заданный тест-канал, а через I (U\ У) и d обозначены средняя взаимная информация и среднее искажение для совокупности источника и тест-канала. Как и ранее, нижняя грань R0 (р, Р) по всем тест-каналам (т. е. по всем совместным вероятностным мерам с соответствующей входной вероятностной мерой) равна координате точки пересечения оси R с касательной наклона — р к кривой R (d*). Если q (и) — плотность вероятности букв источника, то нижняя граница R0 (р, Р) теоремы 9.4.1 принимает вид
R0{p,P)> [ q(u)\n-?^)-du, (9.6.18)
J q (и)
где f (и) удовлетворяет ограничению
|/(u)e~prf<"’ du ^ 1 для всех v. (9.6.19)
489
Необходимые и достаточные условия, накладываемые на / (и) и на плотность переходной вероятности р (v | и) для того, чтобы в (9.6.18) имело место равенство, заключаются в том, что функция со (v) ^ 0 удовлетворяет соотношению
| со(у) e~pd (u; 0) dv = Для всех и (9.6.20)
и что (9.6.19) удовлетворяется с равенством для всех v, для которых со (v) > 0. Тогда
p(v\u) = a(v)f(u)e~pd u,;v). (9.6.21)
q(u)
Доказательство этих утверждений совпадает с доказательством первой половины теоремы 9.4.1 при замене сумм на интегралы. Однако мы не можем показать, что всегда существуют функции р (v \ и) и / (и), для которых (9.6.18) удовлетворяется с равенством. Мы не можем даже доказать, что к равенству можно приблизиться путем все более и более тщательного выбора р (v\ и) и / (и), хотя это последнее утверждение кажется верным. К счастью, для важного примера, изложенного в следующем параграфе, равенство может быть достигнуто и нижняя граница дает возможность легко вычислить R (d*).
9.7. ГАУССОВСКИЕ ИСТОЧНИКИ С КВАДРАТИЧНО-РАЗНОСТНЫМ
ИСКАЖЕНИЕМ
Рассмотрим источник, выход которого представляет собой последовательность статистически независимых одинаково распределенных гауссовских случайных величин ..., и_г, и0, иъ ..., каждая из которых имеет плотность вероятности
Найдем для этого источника скорость как функцию искажения R (d*) с мерой искажения d (и; v) = (и — v)2. Найдем сначала нижнюю границу для min R0 (р, Р) [точки, в которых ось R пересекается с касательной наклона — р к кривой R (d*)] и используем эту границу для построения нижней границы для R id.*). Затем покажем, что нижняя граница равна R (d*) и рассмотрим получающийся тест-канал. Из
