Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
m(k) = min d' (k\ j), i
to d (k\ j) — d! (/?; j) — m (k) будет иметь требуемый вид. Так как разность между d (k\ j) и d' (k\ j) является функцией только буквы k источника, то она не зависит от преобразований, проводимых между источни-
458
ком и адресатом. Иногда мы будем ограничиваться рассмотрением конечных мер искажения (при этом считается, что d (k; j) конечна для всех k, /), но в большей части изложения будут допускаться и бесконечные значения d (/г; /). Бесконечное искажение между заданными k и / равносильно абсолютному запрещению того, чтобы буква k источника была представлена у адресата буквой /. Полное искажение между последовательностью и.ъ ..., букв источника и последовательностью Vi, ..., vL букв адресата определяется как
L
S Vl).
I= 1
Примером меры искажения является d (k\ j) = 0 при j — k и d (k;j)= 1 при j=?k в случае, когда J = K. Такая мера искажения букв будет приемлемой, если требуется точное воспроизведение букв источника и все ошибки считаются одинаково серьезными. Во втором примере положим J — К + 1, и путь d (k; j) = 0 при } = k, d (k; /) = = 1 при j фк, j < J — 1, и d (k; J — 1) = V2 для всех k. В этом примере выход J — 1 можно интерпретировать как стертый символ. Такая мера искажения является разумной, если все ошибки одинаково опасны, а стирание лишь наполовину опасно по сравнению с ошибкой. В третьем примере положим J — К, и путь d (k; j) = (j — k)2 для всех j, k. Такая мера искажения приемлема, если буквы источника представляют собой значения амплитуды и большие ошибки в амплитуде более опасны, чем малые. В последнем примере положим J = 2, и пусть d (k; j) = 0, когда k +/ четно, и d (k; j) = 1, когда k + / нечетно. Такая мера искажения является подходящей, если существенно только то, четны или нечетны буквы источника. Этот последний пример несколько искусствен, однако он показывает, что мера искажения может быть использована для указания степени важности воспроизведения отдельных сторон выхода источника.
Когда источник связан с адресатом каналом и некоторыми преобразованиями, статистика источника, статистика канала и операции преобразующих устройств определяют совместную вероятностную меру на входной последовательности и и выходной последовательности v. Вероятностная мера в свою очередь определяет среднее искажение на букву источника. Нас интересует нахождение минимума среднего искажения, которое может быть достигнуто при заданном канале. Будет показано, что этот минимум зависит лишь от пропускной способности канала и к нему можно подойти сколь угодно близко с помощью преобразователя, который отображает сначала выход источника в двоичный поток данных со скоростью, сколь угодно близкой к пропускной способности канала, а затем кодирует двоичный поток данных для передачи по каналу.
Начнем с изложения фундаментального определения, которое на первый взгляд кажется несколько произвольным. Скорость как функция искажения для заданных дискретного источника без памяти и меры искажения определяется следующим образом. Рассмотрим произвольное множество переходных вероятностей Р (/\k), где Р (j\k) —
459
условная вероятность буквы / у адресата при условии, что k была буквой источника. Эти вероятности вместе с вероятностями букв источника определяют среднюю взаимную информацию
Я (Q; Р) , 2 1«<*>р (/I ¦«УД,,,. <9-2- Ц
k = 0 / = 0 г
и среднее искажение
d='Z'ZQ(k)P(j\k)d(k\j). (9.2.2)
& i
Tогда скорость как функция искажения для источника относительно заданной меры искажения определяется равенством
R(d*) - min Cf(Q; P). (9.2.3)
P :d^d*
Минимизация в (9.2.3) проводится по всем переходным вероятностям при ограничении, что среднее искажение меньше или равно d*. Ниже будет показано, что если для заданного d* пропускная способность канала, связывающего источник и адресат, меньше чем R (d*) натуральных единиц на символ источника, то независимо от того, какие преобразования проводятся до и после передачи по каналу, среднее искажение должно быть больше d*. Обратно, будет показано, что источник может быть закодирован в R (d*)lIn 2 двоичных символов на букву
источника и что двоичные символы могут быть декодированы в буквы
адресата таким образом, что среднее искажение на букву не будет превышать d* более чем на произвольно малую величину. В свете этих результатов разумно рассматривать R (d*) как скорость источника в натуральных единицах на символ относительно критерия верности d*.
Отложим вопрос о том, как вычислять R (d*) до вывода указанных выше результатов и вывода некоторых общих свойств этой функции. Покажем сначала, что R (d*) неотрицательна, не возрастает с d* и выпукла по d*. Неотрицательность очевидна, так как Г/(Q;
