Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Рс {D>Ld | u)<
1
2 Mv)f '6^
(9.3.18)
где сумма берется по всем v из дополнения Аи. Для v ? Аси имеем
PL (v I и)
/ (и; v) = In
¦s^LR,
coL (v)
с«)д (v)>Pz.(v |u)e-^,
Pc {D > Ld | u)<
1-e-^ S Pz.(v|u) ve/„
м
(9.3 19)
(9.3.20)
(9.3.21)
Теперь потребуются следующие неравенства:
[1 — ах\м = ехр [М In (1 — ах)\ ехр ( — М ах),
ехр (— Мах)^ 1—х + e~Afct, O^x^l.
Равенство (9.3.23), очевидно, удовлетворяется при х = 0 и х = 1 и так как левая часть выпукла w по х, а правая часть линейна по х, то оно
469
(9.3.22)
(9.3.23)
PC(D^> Ld) 2jQl(u) У- Pl(v I u) + exp (—- Me— L$)
u v€ ли
удовлетворяется при 0 ^ х 1. Применяя эти неравенства к (9.3.21) и полагая х равным сумме по v, выводим
Pc{D>Ld j u) < 1 — J Pl(v I u)+ exp (— Л4е~^). (9.3.24)
ve/u
Подставляя это выражение в (9.3.16), получаем
(9.3.25)
= Pt {A) -j- ехр (—Ме~ L^)- | (9.3.26)
Нетрудно увидеть, что только что доказанная теорема кодирования для источника и различные ее обобщения играют ту же роль в теории передачи с заданным критерием верности, какую играет теорема кодирования для каналов с шумами. Этот результат даже при беглом знакомстве с ним кажется довольно удивительным.
Теорема 9.3.1 рассматривает только меры с конечным искажением, и это ограничение используется в (9.3.10) при оценке искажения для тех маловероятных последовательностей источника, для которых искажение каждого кодового слова больше чем d* -f 6/2. Следующая теорема применима к мерам с бесконечным искажением.
Теорема 9.3.2. Пусть R (d*) — скорость как функция искажения для дискретного источника без памяти с произвольной мерой искажения отдельной буквы. Для любых d* ^ 0, 6 > 0 и достаточно большого L существует код источника, для которого энтропия множества кодовых слов Н (VL) удовлетворяет неравенству Н (VL) L [R (d*) -f 6] и среднее искажение на букву удовлетворяет неравенству dL <1 d* + S.
Доказательство. Применим лемму к тест-каналу, на котором достигается R (d*), выбирая d равным d* -f 6 и R равным R (d*) -+ 6/3.
Для ансамбля сМ=)_ехр [LR (d*)+ 2L6/3]__________|кодовыми словами, как
и в (9.3.14), имеем
2 2
Pe[D>L(d* + 6)]<^ + + ехр (—ei6/3+ 1). (9.3.27)
Lo2, L о2
Имеем ol <С оо, поскольку тест-канал всем переходам с бесконечным искажением соотносит вероятность, равную нулю. В любом частном коде этого ансамбля имеется множество В последовательностей источника, которые не могут быть закодированы с искажением d* + 6 или меньшим на букву, и должен быть по крайней мере один код, для которого Р (В) ограничена сверху правой частью (9.3.27). Возьмем этот код и добавим к нему по одному кодовому слову v для каждого и из В, выбирая v так, чтобы D (u; v) = 0. Отображая каждое и, не принадлежащее В, в одно из первоначальных М слов с искажением на букву d* + 6 или меньшем и отображая каждое и из В в одно из новых кодовых слов с искажением 0, имеем dL^d* + 6. Первоначальные М слов кода имеют общую вероятность 1 — Р (В). Энтропия множества кодовых слов оценивается сверху с помощью предположения, что все перво-
470
начальные кодовые слова равновероятны и все новые слова равновероятны. Так как имеется не более KL новых слов, то
Н (VL)< [ 1 — Р (В)] In М + Р (В) In KL + Ж [Р (Б)] <
< L {Д (d*) + 26/3 + Р(В) In К + ^[^(Д)1). (9.3.28)
Так как Р (В) стремится к 0 при возрастании L, то можно выбрать L столь большим, что Н (VL) L [R (d*) + 6], что завершает доказательство теоремы. |
Из теоремы кодирования источников неравномерными кодами (см. гл. 3) следует, что это множество кодовых слов может быть закодировано двоичным неравномерным кодом и даст среднюю длину не более чем [Н (VL) + In 2]/ (L ln 2) двоичных символов на символ источника.
Подытоживая сказанное, мы видим, что источник может быть закодирован числом двоичных символов на символ источника, сколь угодно мало превышающим R (d*)/ln 2, и так, что среднее искажение на букву в последовательности, восстановленной для адресата, будет сколь угодно мало превышать d*.
Основное отличие между бесконечной и конечной мерой искажения возникает, когда мы пытаемся передать закодированный выход источника по каналу с шумами. Для конечных мер искажения существует максимальное искажение, которое может возникнуть, когда будет сделана ошибка при декодировании в канале и, следовательно, вклад ошибок канала в среднее искажение стремится к нулю, когда вероятность ошибки при передаче по каналу стремится к нулю. Для бесконечной меры искажения, если какое-либо используемое кодовое слово имеет бесконечное искажение по отношению к какой-либо последовательности источника, то в канале, все переходные вероятности которого отличны от нуля, искажение наступит с ненулевой вероятностью и, следовательно, среднее искажение бесконечно.
