Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
п— 1 ___
п sup d (u; v0) + V I (d:+1 + Sj
---------------------------------. (9.8.21)
In2 -f n
Можно дальше построить границу сверху, уменьшая знаменатель до Ln2 и применяя (9.8.18) и (9.8.20), в результате получим
--p-rf + d* + — . (9.8.22)
Ln n
Следовательно, для достаточно больших L среднее искажение на букву между суперисточником i-й фазы и i-м большим кодом ограничено сверху d* -+- б, где б > 0 произвольно.
Если все кодовые слова этих п больших кодов объединить в один код, то независимо от того, какой эргодический супер источник действует, среднее искажение на букву будет не больше d* + б. Общее число кодовых слов равно
М = п "п Mi < п ехр (V [II (у; V' I 0 + 6j) <
i = 0 1г=0 j
п ехр [Lnl (?/'; V') + Ln8] = п ехр [Ln2 Rn (d*) + Ln8]
< exp ULn* + n) |>n (d*) + - + -^-1) • (9.8.23)
I L n Ln2 -f-n J J
17 Зак. 210 513
Таким образом показано, что для любого n> 1, любого 6> О и достаточно большого L можно найти коды длины Lri2 + п с
М < ехр {[(Ln2 + п) [Rn (d*) + б])
и средним искажением на букву, меньшим или равным d* + б. Кроме того, очевидно, ограничение, состоящее в том, что длина блока должна иметь вид?п2+п, не является необходимым, так как для блока любой достаточно большой длины V можно найти наибольшее L, такое, что Ln2 + n^L', далее для этого L найти код, удовлетворяющий (9.8.22) и (9.8.23), и затем добавить последовательность, содержащую не более п2 — 1 фиксированных символов, к концу каждого кодового слова. Среднее искажение на букву возрастает, таким образом, не более чем на sup d (u; v0)IL, что для больших L пренебрежимо мало. Наконец, так как п может быть выбрано достаточно большим, так чтобы Rn (d*) было сколь угодно близко к R (d*), то тем самым доказана следующая фундаментальная теорема.
Теорема 9.8.3. Пусть R (d*) — скорость как функция искажения для дискретного эргодического источника с аддитивной инвариантной во времени мерой искажения. Для любого d* с R (d*) < оо, любого 6>0 и достаточно больших L существует блоковый код источника длины L с Л[ < ехр [Li? (d*) + L6] кодовыми словами и средним искажением на букву, не большим d* + б. ___________
При желании терпеливый и настойчивый читатель может соединить метод доказательства этой теоремы с результатами § 9.3 и 9.6 и снять как условие, что d (u; vQ) ограничено, так и условие, что источник дискретный.
итоги и выводы
В этой главе рассмотрена проблема воспроизведения выхода источника у адресата при выполнении заданного критерия верности. Источник был описан с помощью множества возможных выходов источника и вероятностной меры на этих выходах. За критерий верности было выбрано среднее искажение на букву или единицу времени между источником и адресатом. С точки зрения теории мера искажения является неотрицательной функцией выхода источника и его воспроизведенного варианта. С точки зрения приложений, конечно, мера искажения должна быть выбрана так, чтобы она отражала в некотором смысле стоимость для потребителя любого заданного воспроизведения любого заданного выхода источника.
Мы начали с дискретных источников без памяти с мерами искажения отдельной буквы и затем обобщали результаты на все более и более общие случаи. В каждом случае сначала определялась скорость как функция искажения R (d*) и затем этой функции придавался смысл с помощью доказательства теоремы кодирования для источника и ее обращения. То, что говорится в теореме кодирования для источника, по существу, сводится к тому, что для заданного d* выход источника может быть закодирован с помощью R (d*)l 1п2 двоичных символов на символ источника (или на единицу времени, в зависимости от Б14
единиц измерения R (d*)) и что эти двоичные символы могут быть преобразованы в буквы адресата таким образом, что среднее искажение на букву (или на единицу времени) будет сколь угодно близко к d*. Этот же результат остается справедливым, если двоичные символы кодируются и передаются по каналу с шумами и пропускной способностью, большей чем R (d*), где пропускная способность выражается в- натах на букву источника (или в натах на единицу времени). Обращение теоремы устанавливает, что если выход источника передается по каналу с пропускной способностью, меньшей чем R (d*), то независимо от преобразований выхода источника и сообщений, поступающих адресату, среднее искажение на букву (или на единицу времени) должно быть больше d*.
Читатель должен заметить много аналогий между полученными здесь результатами для кодирования источника и теорией кодирования для канала с шумами, однако может быть полезно обратить здесь внимание на некоторые отличия. Теорема кодирования для канала с шумами связывает достижимую вероятность ошибочного декодирования Ре с длиной кодового блока и скоростью кода R. Было найдено, что для фиксированного R, меньшего чем пропускная способность канала, Ре убывает экспоненциально с увеличением длины блока. При кодировании источника эквивалентными параметрами, представляющими интерес, являются среднее искажение на букву d, длина кодового блока L и скорость кода R. Здесь для фиксированного R при возрастании L число d убывает к d*, задаваемому R = R (d*). Сходимость d к d* происходит не'медленнее чем ]/^(ln L)IL и, по-видимому, не быстрее чем 1/L [см. Пилк (1967)]. Таким образом, при кодировании источника следует затратить весьма много усилий (в смысле увеличения длины блока) для того, чтобы достичь весьма незначительного уменьшения d, в то же время для каналов с шумами весьма умеренное возрастание длины блока может привести к сильному убыванию вероятности ошибки.
