Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
/ (UL; VL | s0) / (X"; Y^ | s0) < NCn. (9.2.27)
Согласно теореме 4.6.1
С^<С + -^- (9.2.28)
Сочетая (9.2.24), (9.2.27) и (9.2.28), получаем (9.2.20). |
Предыдущая теорема несколько неестественна в том, что она относится только к двум классам каналов. Единственная трудность в установлении эквивалентной теоремы для других каналов лежит в нахождении подходящего определения для пропускной способности. Как показано в § 4.6, максимум средней взаимной информации на букву даже для канала с конечным числом состояний может существенно зависеть от начального состояния и от того, известно или нет это начальное состояние передатчику. Для наиболее интересных частных каналов, не входящих в эти классы, таких, как канал с аддитивным гауссовым шумом, изучавшийся в последней главе, сравнительно легко определить пропускную способность как максимум средней взаимной информации на единицу времени в пределе для больших интервалов времени. Как только пропускная способность будет определена и проблема, связанная с влиянием прошлой истории будет каким-то образом обойдена, то так же, как в последней теореме, можно будет найти, что R (dx) ^ т5С, где С — пропускная способность канала в натах в секунду.
465
9.3. ТЕОРЕМА КОДИРОВАНИЯ ДЛЯ ИСТОЧНИКОВ ПРИ ЗАДАННОМ КРИТЕРИИ ВЕРНОСТИ
Обратимся теперь к установлению того, что R (d*)/ln 2 является числом двоичных символов на символ источника, требуемых для достижения среднего искажения, произвольно близкого к d*. Для заданных источника U и алфавита адресата V код источника из М кодовых слов с длиной блока L определяется как отображение множества последовательностей длины L источника в множество М кодовых слов, где каждое кодовое слово vm = (vmU и=(и,иги}) xt-(ofvz vs) vmL) является последовательно-
стью из L букв алфавита адресата. Пример рис. 9.3.1 иллюстрирует код источника с двумя кодовыми словами с длиной блока
3 для двоичных алфавитов источника и адресата.
Для заданной меры искажения d (k\ j) среднее искажение на букву кода источника задается равенством
dL= —¦ 2&.(“)D lu'> v (“Я-
U
(9.3.1)
где v (u) — кодовое слово, в которое отображается и и
D(u;v)=^p d(ui,vi). (9.3.2)
i = i
Для кода источника с М кодовыми словами каждое кодовое слово может быть представлено отличной от других двоичной последовательностью ДЛИНЫ ri0g2 М |ИЛИ с помощью (1IL) | log2 М j двоичных символов на символ источника. Из теоремы кодирования для канала с шумами следует, что эти последовательности могут быть переданы с любой надежностью по каналу, пропускная способность которого больше чем (1 /L)\ log2 М | двоичных символов на символ источника. Следовательно, основная задача сводится к нахождению, насколько малым может быть сделано dL при заданных L и М.
С этого момента, и это не должно быть удивительно, мы попытаемся решить эту задачу, анализируя поведение случайно выбранного множества кодовых слов. Пусть Р (j\k) — заданное множество переходных вероятностей между буквами источника и адресата. Для удобства будем называть дискретный канал без памяти с этим переходным вероятностным тест-каналом и, если на Р (/1 k) для заданного d* достигается R (d*), то будем говорить, что на соответствующем тест-канале достигается R(d*) для этого d*. Выходные вероятности со (j) для заданного тест-канала равны
466
ООО
Г t 1
Рис. 9.3.1. Код источника с двумя кодовыми словами и длиной блока 3 (линии указывают отображение
»(/) = ZQ(k)P(j\k).
k
Для любого заданного тест-канала рассмотрим ансамбль кодов источника, в котором каждая буква каждого кодового слова выбирается независимо с распределением вероятности со (/). Для заданного множества кодовых слов vb ..., \м из ансамбля каждая последовательность источника и отображается в такое кодовое слово vm, для которого D (u; vm) минимально по т.
В последующих рассуждениях одновременно будут рассматриваться две различные вероятностные меры на входных и выходных последовательностях; одна — на ансамбле тест-канала, другая — на ансамбле случайного кода. Для ансамбля тест-канала вероятностная мера на входных последовательностях u = (ult ..., uL) и выходных последова-тёльностях v = (vlt ..., vL) задается выражением QL (u) PL (v|u), где
L
Ql(и) = П Q(U[), (9.3.3)
1= 1 L
#l(v|u)= П P(w,|uz). (9.3.4)
i = i
