8.2. Источники с памятью

Многие источники, встречающиеся на практике и допускающие представление в виде модели с дискретным временем и действительными выходными символами, обладают, вообще говоря, той

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

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

Обратимся теперь к рассмотрению дискретных по времени источников со статистически зависимыми выходными символами. Для удобства будем рассматривать источники только с дискретным алфавитом Пусть означает случайную последовательность букв, производимых таким источником. Последний описывается вероятностями

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

не зависят от времени для всех последовательностей букв и всех длин

В дополнение к предположению о стационарности источника временно предположим, что источник эргодичен. (В § 8.6 опустим требование эргодичности и рассмотрим пример неэргодического стационарного источника, который тем не менее можно успешно кодировать.) По существу эргодичность равносильна требованию эквивалентности усреднения по времени любой реализация выходной последовательности источника и усреднения по ансамблю. Точнее, пусть реализованная выходная последовательность и последовательность и, сдвинутая во времени на I позиций. Это значит, что

Пусть далее некоторая функция от и, зависящая только от Стационарный источник эргодичен тогда и только тогда, когда для всех и всех функций таких, что

имеет место равенство

справедливое для всех последовательностей источника (за исключением, быть может, множества меры нуль). Здесь означает обычное усреднение по ансамблю. Предположение об эргодичности позволяет утверждать, что если код годится для кодирования некоторой реализации выходной последовательности, то он годится также для всех реализаций стационарного эргодического источника. Более очевидным это станет после того, как мы рассмотрим пример неэргодического стационарного источника.

Предположим, имеется дискретный по времени стационарный источник, описанный выше, и пусть алфавит источника, алфавит представления, а ограниченная побуквенная мера погрешности такая, что для всех Пусть распределение вероятностей этого источника. Шенноя [1959] и Галлагер [1968] показали, что скорость как функция погрешности определяется как предел

где

Доказательство теоремы кодирования для этого случая довольно трудное. Здесь будет дано доказательство только для гауссовского источника с квадратично-разностной мерой погрешности. Общее доказательство можно найти в работах Галлагера [1968] и Бергера [1971].

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

Модель с таким конечным интервалом зависимости представляется приемлемой для многих реальных источников. Но с математической точки зрения она основана на довольно сильном предположении, которое существенно упрощает эвристические доводы в пользу того, что соотношение (8.2.5) — действительно скорость как функция погрешности.

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

и погрешность через

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

погрешности Если воспользоваться результатами, приведенными в § 8.1, относящимися к векторному источнику без памяти, то окажется, что скорость как функция погрешности для нашего расширенного источника

где

В данном случае величина имеет размерность нат на символ расширенного источника. Но каждому символу расширенного источника соответствует действительных символов источника. Следовательно, функция (8.2.14), измеряемая в натах на символ источника, согласно (8.2.6) равна

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

Переходя к пределу при можно достичь средней погрешности при скорости кодирования

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

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

Лемма 8.2.1. Справедливо соотношение -

Доказательство. Рассмотрим целые и положим Пусть условные распределения вероятностей, на которых достигаются и пусть

Тогда

Следовательно, принадлежит и по лемме

где

Таким образом,

Теперь обозначим Тогда для любого можно найти такое что

Полагая из (8.2.22) находим, что

Точно так же

Для любого целого можно найти такие, что , где . Тогда

где

Так как произвольное, то

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

Теорема 8.2.1. Обратная теорема кодирования — стационарные эргодические источники. Для любой пары кодер-декодер источника при средней погрешности, не превышающей скорость удовлетворяет неравенству

Доказательство. Любая пара кодер-декодер задает некоторое отображение последовательностей источника в последовательности пользователя. При любом N рассмотрим отображение, действующее из и определим как число различных последовательностей в в которые отображаются последовательности Введем распределение вероятностей

По условию это отображение обеспечивает среднюю погрешность, не превышающую поэтому

и, следовательно, Таким образом,

Но

поэтому

Доказанная обратная теорема вместе с эвристически доказанной прямой теоремой кодирования завершает объяснение функции определяемой соотношением (8.2.5), — скорости как функции погрешности для стационарных эргодических источников.

Такие рассуждения легко переносятся и на стационарные эргодические источники, если вместо требования ограниченности меры погрешности ввести требование ограниченности ее моментов.

Для стационарных эргодических источников можно получить и другую форму функции если вместо минимизации по множеству случайных векторов с последующим переходом к пределу использовать методы случайных процессов. В этом случае определение скорости как функции погрешности аналогично определению пропускной способности канала, данному Хинчиным [1957] в терминах случайных процессов. Рассмотрим еще раз стационарный эргодический источник, описанный выше. Предположим, что существует совместно стационарный эргодический случайный процесс состоящий из пар Это значит, что для всех N существует некоторое непустое семейство распределений удовлетворяющих условию

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

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

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

Теорема 8.2.2. Если заданы некоторое и определенный выше совместно стационарный эргодический процесс, удовлетворяющий условию источника (8.2.30), то существует последовательность блочных кодов со скоростью и средними погрешностями удовлетворяющими неравенству

Доказательство. Средняя погрешность любого блочного кода равна

где

Пусть

Тогда

При преобразовании первого члена воспользуемся оценкой

а при преобразовании второго

Тогда

Определяя

применим для оценки второго члена неравенство Гёльдера. Тогда

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

независимыми кодовыми словами, выбираемыми в соответствии с распределением вероятностей находим

Здесь первое неравенство следует из неравенства Иенсена, - первое равенство — из полной симметрии множества Таким образом,

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

Далее положим для любого и выберем так, чтобы

Заметим, что

и рассмотрим неравенство

Подставляя неравенство в границу (8.2.42), найдем, что существует код Для которого

для любого и достаточно больших N таких, что

Для совместно эргодических источников (Макмиллан [1953])

где сходимость имеет место с вероятностью 1. Следовательно,

Наконец, выберем где тогда

Согласно теореме наименьшая возможная скорость при средней погрешности Таким образом,

где минимизация проводится по всем стационарным эргодическим процессам, удовлетворяющим требованиям и условию (8.2.30). Грэй и другие [1975] показали, что минимизацию можно проводить по всем совместно стационарным источникам, так как такие источники, на которых достигается минимум, могут быть как угодно близко аппроксимированы стационарным эргодическим источникам. Более того, Грэй и другие [1975] доказали обратную теорему кодирования, аналогичную теореме 8.2.1, согласно которой

Для стационарных эргодических источников существуют два равносильных определения скорости как функции погрешности задаваемые соотношениями (8.2.5) и (8.2.49). Согласно определяется как предел минимумов по случайным векторам, тогда как согласно (8.2.49) она определяется как минимум по случайным процессам. Но в обоих случаях вычисление для большинства стационарных эргодических источников представляет трудную задачу. Это одна из наиболее слабых сторон всей теории.

Наиболее простой путь вычисления состоит в том, чтобы найти сначала выражение для а затем уже перейти к пределу при Функцию определяемую (8.2.6), можно представить как функцию скорости от погрешности -мерного векторного источника без памяти, компоненты которого не обязательно независимы между собой, а погрешность между вектором на выходе источника и представляющим вектором является суммарной мерой погрешности. Таким образом, является в точности скоростью как функцией погрешности векторного источника с суммарной мерой погрешности, рассмотренной в разд. 8.1.1. Там было найдено простое выражение для этой функции в случае источника с независимыми компонентами. Если с помощью соответствующих преобразований удается свести вычисление

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

Пример. (Гауссовский источник, квадратично-разностная погрешность.) Рассмотрим дискретный по времени стационарный гауссовский источник с нулевым средним. Источник «порождает выходную последовательность для которой величина коррекции между буквами равна

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

для любых где Начнем с вычисления

Последовательность имеет совместную функцию плотности

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

имеем

Произведем следующие преобразования вектора источника и представляющего вектора: где ковариационная матрица для и равна а плотность вероятностей

Заметим, что компоненты вектора и — независимые случайные величины, а так как то

Пусть произвольная условная плотность вероятностей и соответствующая условная плотность случайной величины при Так как преобразование обратимо, то оно сохраняет среднюю взаимную информацию

В свою очередь, равенства ( следует, что

Таким образом, можно выразить в терминах преобразованного пространства

где

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

Согласно лемме 8.1.1 функция задаваемая в натах на измерение, описывается параметрическими уравнениями

где скорость как функция погрешности, соответствующая компоненте источника. Для примера, приведенного в § 8.1, эти уравнения при принимают вид

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

Теорема 8.2.3. Теорема Тёплица о распределении собственных чисел. Пусть бесконечная ковариационная матрица. Тогда собственные числа матрицы заключены в интервале где и А означают соответственно существенные нижнюю и верхнюю грани 1 функции

Более того, если и А — конечные числа, любая непрерывная функция от К, то

где — собственное число ковариационной матрицы размерами

Доказательство. (Гренандер и Сеге [1958, §

Применяя эту теорему к соотношениям (8.2.65) и (8.2.66), получаем параметрическое уравнение для

и

Для рассматриваемого гауссовского источника с квадратично-разностной мерой погрешности докажем теорему кодирования, следуя доказательству, которое уже применялось для источников без памяти. При этом будем кодировать

выходные последовательности преобразованного источника кодом, состоящим из кодовых слов и обозначаемым Тогда, следуя теореме кодирования (см. § 7.2), для любой условной плотности

находим оценку погрешности, усредненной по ансамблю источника и кода,

где

Следуя Тану [1975], при заданном параметре 9 выберем вероятность

где

При таком выборе

а

Следовательно,

По теореме Теплица

где

Полученная функция обладает всеми свойствами, сформулированными в лемме 7.2.2, так что

Обозначая

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

где

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

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