Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Обсуждение. Интерпретация Н (VL) и М с помощью числа двоичных символов на символ источника, требуемых для представления источника, аналогична той, которая была в дискретном случае. Условие min d («; а$) < оо означает, что имеется способ разбиения (или квантования) выхода источника на конечное число областей с конечным средним искажением. Если это условие не имеет места, то любой блоковый код с конечным числом кодовых слов должен иметь бесконечное среднее искажение, так как он использует лишь конечное множество букв адресата.
Доказательство. Выберем тест-канал (т. е. совместную вероятностную меру), для которого d ^ d* и /(?/; V) R (d*) + 6/4. Применим лемму 9.3.1 к этому тест-каналу, выбирая d, = d* +6/2, R — R (d*) +
Так как I (U, V) и d конечны, то закон больших чисел утверждает, что для фиксированного 6 вероятность Pt(A) стремится к 0 при возрастании L и, следовательно,
db^Ld* + 6.
+ 6/2 и
Тогда, как и в (9.3.11), имеем
PC[D>L (d* + 6/2)1 < Pt (А) + ехр [~е^ + Ц, (9.6.3)
где
Л (А) < Рг {/ (u; v) > L [R (d*) + 6/2]} +
+ Pr [D (и; v)> L (d* + 6/2)} <
(9.6.4)
< Pr {/ (и; v) > L (I (?/; V) + 6/4)} + +Pr {D (u; v) > L (d + 6/2)}.
(9.6.5)
486
lim Pc [D >L (d* + 6/2)] = 0.
L~+ oo
(9.6.6)
Пусть для любого заданного кода В — множество последовательностей источника, для которых D [u; v (и)] > L (d* + 6/2). Для любого L некоторый код в ансамбле с заданным М удовлетворяет неравенству Р (В) < Рс [D > L (d* -f 6/2)]. Добавим к этому коду множество J1 кодовых слов, одно кодовое слово для каждой последовательности из L букв алфавита аъ ..., aj. Отобразим последовательности источника, не содержащиеся в Б, в первоначальные М кодовых слов с искажением на букву, небольшим d*+6/2. Отобразим последовательности источника из В в ближайшее из добавочных JL кодовых слов. Энтропия всего множества кодовых слов ограничена так же, как в (9.3.28),
Я (VL) < L (d*) + 8/2 + Р (В) In J + j. (9.6.7)
Если InJ ^ R (d*), то общее число кодовых слов равно
М' = М + JL < 2 ехр L [R (d*) + 6/2]. (9.6.8)
Следовательно, для достаточно больших L удовлетворяются ограничения на Я (VL) и М'.
Пусть хв — случайная величина,
1, и ев,
О, и ?в,
и пусть zt, 1 I ^ L, являются одинаково распределенными случайными величинами
Zj = min d(uf, aj).
/
L
Искажение на букву для последовательности и ? В имеет вид -у-2 Zl'
1=1
Среднее искажение на букву для заданного кода, таким образом, ограничено выражением
хв^\у iZ’ (9-6-9)
4<d* + 6/2+-^2Zi, (9.6.Ю)
L i = \
где d* + 6/2 — верхняя граница искажения, связанная с и (? В, а последнее выражение является искажением, связанным с uffi. Пусть z' — некоторое число, которое будет выбрано позднее, и пусть для каждого /, 1 ^ I ^ L,
1 Zl<Z'’ (9.6.11)
0, Z;>Z'.
Тогда
x~z~t = хвzt xL + xB zL (1 — х,) s^xBz' + zt (1 — *,). (9.6.12)
Первое из указанных выше слагаемых было ограничено сверху на
основе того, что так как xt — 0 для zt > г', то ^ г'. Второе слагае-
487
мое было ограничено сверху с помощью неравенства хв ^ 1. Используя определения хв и хи имеем
оо
Р(В)=хв; z, (1 — х,) = j 2, dF [zi),
(9.6.13)
где F (zt) — функция распределения zt. Подставляя (9.6.12) и (9.6.13) в (9.6.10), получаем
Так как по предположению zx < оо, то последний интеграл в (9.6.14) стремится к 0, когда г' стремится к оо; следовательно, последний интеграл меньше чем 6/4 при достаточно больших г'. Для такого г' имеем z' Р (В) ^ 6/4 при достаточно больших L. Следовательно, при достаточно больших L имеем dL ^ d* + 6. |
Хотя эта теорема показывает, что коды источника могут иметь скорость, сколь угодно близкую к R (d*) при средних искажениях, сколь угодно близких к d*, однако условия теоремы не достаточно сильны, чтобы можно было утверждать, что искажения, близкие к d*, могут быть достигнуты после передачи по каналу с шумами. Требуемые дополнительные условия приведены в следующей теореме.
Теорема 9.6.3. Если дискретный по времени источник без памяти с мерой искажения d (и; v) удовлетворяет условию d (и; v) <. оо для каждого v, где математическое ожидание взято по ансамблю источника, и если этот источник связан с адресатом с помощью канала, имеющего пропускную способность С нат на букву источника, и для которого произвольно малая вероятность ошибки может быть достигнута при любой скорости передачи данных, меньшей С, то может быть достигнуто среднее искажение на букву, произвольно близкое к d*, где С = R (d*). В более общем случае условие d (и; v) < оо заменяется на условие, что R (d*) может быть аппроксимирована сколь угодно точно на совместных мерах вероятностей, для которых равна нулю вероятность множества таких v, что d (и; v) = оо.
