Часть III. КОДИРОВАНИЕ ИСТОЧНИКОВ ДЛЯ ЦИФРОВОЙ СВЯЗИ

Глава 7. ТЕОРИЯ ПЕРЕДАЧИ С ПОГРЕШНОСТЬЮ: ОСНОВНЫЕ КОНЦЕПЦИИ ДЛЯ ИСТОЧНИКОВ БЕЗ ПАМЯТИ

7.1. Задача кодирования источников

Теория передачи с погрешностью служит теоретической основой сжатия данных. Она устанавливает минимальное среднее число двоичных единиц на символ источника (илин в единицу времени), называемое скоростью, которое теоретически требуется для такого представления выходной последовательности источника, при котором ее можно было бы восстановить, удовлетворяя заданному критерию точности, т. е. в пределах допустимой погрешности. Хотя основы этой теории были заложены Шенноном еще в 1948 г., полностью он развил ее только в 1959 г., когда установил основные теоремы, определяющие скорость как функцию от погрешности, соответствующей заданному критерию точности. Эти теоремы определили и практический смысл функции. Первоначально теория передачи с погрешностью не привлекла столь пристального внимания, как теория кодирования для каналов связи, рассмотренная в гл. 2—6. Со временем, однако, стал расти интерес к этой теории и к той роли, которую она призвана сыграть в практике сжатия данных.

Рассмотрим еще раз общую структурную схему системы связи, изображенную на рис. 7.1. Как всегда, предполагаем, что у нас

Рис. 7.1. Модель системы связи

нет возможности как бы то ни было воздействовать на источник, канал или на пользователя. Мы свободны только в построении кодеров и декодеров. В гл. 1 было определено минимальное число двоичных символов на символ источника исходя из требования, чтобы последовательность источника могла быть полностью восстановлена по наблюдению двоичной последовательности. Там было показано, что именно теорема Шеннона о бесшумном кодировании придает практический смысл функции энтропии источника. В этой главе обобщим теорию бесшумного кодирования источников, изложенную в гл. 1, вводя меру погрешности и решая задачу представления символов источника в соответствии с заданным критерием точности. Будем изучать соотношение обмена между скоростью передачи информации, необходимой для представления символов источника, и точностью, с которой символы источника могут быть восстановлены по этой информации.

Главы 2—6 были посвящены задаче кодирования в канале, поэтому там мы ограничивались лишь той частью структурной схемы, представленной на рис. 7.1, которая состоит из кодера канала, канала и декодера канала. В этих главах было показано, что можно найти такие кодеры и декодеры, которые обеспечивают произвольно малую вероятность ошибки передачи до тех пор, пока скорость передачи сообщения остается меньше, чем пропускная способность канала. Развивая теорию передачи с погрешностью, будем предполагать, что кодер и декодер канала работают идеально, т. е. обеспечивают бесшумную линию связи между кодером и декодером источника, как показано на рис. 7.2. Для этого необходимо предположить, что скорость передачи на линии меньше пропускной способности канала.

Рис. 7.2. Модель кодирования источника

Предположение о том, что кодирование источника можно рассматривать отдельно от кодирования в канале, найдет свое оправдание в том, что, допуская достаточно сложные кодеры и декодеры, всегда можно избежать потери эффективности, связанной с таким разделением. Представление выходной последовательности источника в виде последовательности двоичных символов позволяет выделить задачу кодирования источников из общей задачи

передачи информации. С точки зрения практики такое разделение представляется целесообразным, так как дает возможность проектировать кодеры и декодеры канала независимо от свойств источника и пользователя. Кодер и декодер источника являются согласующим звеном между источником и пользователем, с одной стороны, и системой кодирования в канале, с другой стороны.

Начнем с того, что введем алфавит источника алфавит пользователя (называемый иногда алфавитом представления), меру погрешности определенную для каждой пары символов из и и заданную статистическую характеристику источника. Располагая этими определениями и предположениями, можно приступить к изучению теории передачи с погрешностью. В этой главе рассмотрим дискретные по времени источники без памяти, которые в каждый момент времени, скажем каждые секунд, производят некоторый символ и, принадлежащий алфавиту Алфавит вообще говоря, зависит от пользователя, но часто это будет тот же самый алфавит, что и алфавит источника. В этой главе будем также предполагать, что мера погрешности является побуквенной мерой погрешности между символами источника и пользователя, удовлетворяющей условию

Иногда будем называть ее бесконтекстной мерой погрешности, так как она не зависит ни от каких других символов последовательностей источника и пользователя.

Теперь обратимся к рис. 7.2 и решим задачу кодирования и декодирования источника со средней погрешностью, не превышающей Рассмотрим все возможные пары кодеров и декодеров, обладающих средней погрешностью или меньше, и обозначим через множество скоростей, соответствующих этим парам. Скорость понимается как среднее число натов на символ источника, переданных, согласно рис. 7.2, от кодера источника к декодеру источника. Тогда скорость как функция погрешности для заданного определится как минимальная возможная скорость необходимая для достижения средней погрешности или меньше. Формально определим ее соотношением

Эта функция, естественно, зависит от статистики источника и меры погрешности. Такое непосредственное определение скорости как функции погрешности не позволяет в действительности вычислять для различных значений Но, как увидим, оно справедливо для всех стационарных эргодических дискретных по времени источников с побуквенной мерой погрешности. Покажем, что во всех этих случаях может быть выражена в терминах

функции средней взаимной информации которая будет выведена в § 7.2.

Можно по-другому взглянуть на ту же задачу и рассматривать погрешность как функцию скорости. Рассмотрим все пары кодеров и декодеров источника с фиксированной скоростью и обозначим через множество всех средних погрешностей, соответствующих этим парам. Тогда, подобно предыдущему определению, определим погрешность как функцию скорости соотношением

Для стационарных эргодических источников с побуквенной мерой погрешности определения и равносильны и различаются только выбором зависимой и независимой переменных.

Изучение теории передачи с погрешностью может быть грубо разделено на три этапа. Сначала для каждого типа источников и каждой меры погрешности требуется найти точное выражение и доказать теоремы кодирования, согласно которым можно достичь среднюю погрешность или меньше, используя кодеры и декодеры со скоростями При этом должны быть выведены и обратные теоремы, показывающие, что если пара кодер—декодер обладает скоростью то достижение с помощью этой пары средней погрешности или меньше невозможно. Эти две теоремы (прямая и обратная) показывают, что и тем самым определяют практический смысл функции На втором этапе изучается достижимая эффективность кодирования, что требует умения находить вид функции для различных источников и мер погрешности. Когда это трудно сделать в точной форме, прибегают к вычислению различных границ для Заключительный этап состоит в приложении теории передачи с погрешностью к практическим задачам сжатия данных. Разработка эффективной техники кодирования источников, позволяющей достигать скоростей, близких к нахождение мер погрешности, согласующихся с требованиями пользователя, и нахождение приемлемых статистических моделей важнейших источников — вот три основные задачи, связанные с приложением этой теории к практике.

В данной главе развиты основы этой теории для источников без памяти, начиная с излагаемой в следующем параграфе теории блочных кодов для дискретных источников без памяти и ее связи с кодированием для каналов, рассматриваемым в § 7.3. Результаты по древовидным и решетчатым кодам представлены в § 7.4. Все эти результаты затем перенесены в § 7.5 на непрерывные (дискретные по времени) источники без памяти. В § 7.6 и 7.7 рассмотрена задача вычисления скорости как функции погрешности для дискретного и соответственно непрерывного источников без памяти. В гл. 8 представлены различные обобщения теории, включая источники с памятью и универсальное кодирование.