Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
9
КОДИРОВАНИЕ ИСТОЧНИКА С ЗАДАННЫМ КРИТЕРИЕМ ВЕРНОСТИ
9.1. ВВЕДЕНИЕ
В гл. 3 расссматривалось кодирование выхода источника для минимизации среднего числа кодовых букв на букву источника, при условии, что буквы источника можно было восстановить по кодовой последовательности. Если выход источника — последовательность непрерывно-значных случайных величин или случайный процесс, то, очевидно, невозможно закодировать выход источника в последовательность дискретных кодовых букв, по которой выход источника может быть точно восстановлен. В таких случаях можно только потребовать, чтобы восстановленное сообщение аппроксимировало источник с заданным критерием верности. Например, если выход источника порождает последовательность действительных чисел ult «2> •••, и эта последовательность восстанавливается как последовательность vlt v2, ..., то можно потребовать, чтобы математическое ожидание (и; — иг)2, взятое по ансамблю источника и усредненное по времени, было меньше некоторого предписанного значения. В более общем случае можно определить меру искажения [(иг -— уг)2 — в рассмотренном выше примере] как произвольную действительную функцию выхода источника и восстановленной последовательности. Тогда критерий верности определяется как максимум допустимого значения среднего искажения.
Основная цель этой главы — найти минимальное число двоичных символов на букву источника или на единицу времени, требуемых для кодирования источника так, чтобы по кодовой последовательности можно было восстановить сообщение, удовлетворяющее заданному критерию верности. Естественно, что этот предел зависит от статистики источника, меры искажения и критерия верности.
Смысл представления выхода источника последовательностью двоичных символов заключается в том, чтобы отделить задачу представления источника от задачи передачи информации. Мы уже знаем из теоремы кодирования, если скорость двоичной последовательности (в битах в секунду) меньше пропускной способности канала (в битах в секунду), по которому последовательность должна быть передана, то последовательность может быть воспроизведена на выходе канала с произвольно малой вероятностью ошибки. Так как при стремлении к 0 вероятности ошибки влияние этих ошибок на полное искажение обычно становится малым, то можно в действительности отделить задачу кодирования для канала от задачи кодирования для источника.
457
В дальнейшем будет показано, что в некотором смысле ничего не теряется при таком промежуточном представлении двоичными символами. Точнее, будет показано, что если пропускная способность канала слишком мала для надежной передачи с минимальной скоростью, требуемой для представления источника с заданным критерием верности, то этот критерий не может быть удовлетворен, независимо от того, какого вида обработка используется между источником и каналом.
В принципе теория, развиваемая здесь, применима к задачам, обычно классифицируемым как квантование, преобразование аналог— цифра, сжатие полосы частот и редукция данных. На практику эта теория еще не оказывает большого влияния. Частично это объясняется отсутствием множества эффективных методов для осуществления кодирования источника при условии, что удовлетворяется критерий верности. Более существенной причиной является трудность нахождения приемлемых математических моделей для практически важных источников. Например, трудно дать статистическое описание речевого сигнала и еще труднее найти разумную меру искажения в этом случае. Однако даже в такой сложной проблеме могут быть весьма полезными те результаты и то понимание, которые возникают, из развиваемого здесь теоретического подхода.
9.2. ДИСКРЕТНЫЕ ИСТОЧНИКИ БЕЗ ПАМЯТИ И МЕРЫ ИСКАЖЕНИЯ
ОТДЕЛЬНОЙ БУКВЫ
В этом и последующих трех параграфах будет изучено кодирование источника с критерием верности для следующего случая. Будет рассматриваться дискретный источник U без памяти с алфавитом (0, ..., ..., К — 1) и вероятностями букв Q (0), ..., Q (К — 1). Всюду в дальнейшем предполагается, что К конечно и что Q (k) > 0 для всех k,
0 k ^ К — 1 (если Q (k) равно 0, то можно просто исключить эту букву из рассмотрения). Выход источника представляет собой последовательность «1; и2, ... значений, выбранных независимо из заданного алфавита с заданными вероятностями букв. Последовательность источника должна быть представлена при поступлении ее адресату последовательностью букв vlf v2, ..., каждая из которых выбрана из алфавита (0, 1, ..., J — 1), J < оо. Наконец, имеется мера искажения d. (k; j), определенная для — 1, 0 ^ ^ / — 1 и задающая чис-
ленное значение искажения в случае, если буква k источника воспроизводится у адресата как буква /. В дальнейшем изложении всюду будем предполагать, что d (k\ /') ^ 0 и что для каждого k имеется по крайней мере одно /, для которого d (k; j) = 0. Легко видеть, что это предположение в действительности не приводит к потере общности, так как если d' (k; j) — произвольная функция k, j и по определению
