8.6. Универсальное кодирование

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

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

Пример. (Грэй Рассмотрим гауссовский источник без памяти с нулевым средним и дисперсией Скорость как функция погрешности при квадратично-разностной мере погрешности определена соотношением (7.7 20).

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

где скорость как функция погрешности для соответствующего источника без памяти. Из теоремы 7.7.3 следует неравенство

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

то окажется

причем равенство будет иметь место в том и только в том случае, когда источник гауссовский.

Рис. 8.4. Составной источник

Теперь рассмотрим составной источник, содержащий два гауссовских подысточника с нулевым средним каждый. Дисперсия одного подысточника равна дисперсия другого Выходом составного источника с вероятностью 1/2 служит выход первого подысточника и с вероятностью 1/2 — выход второго подысточника. Схема составного источника представлена на рис 8.4.

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

и, как нетрудно видеть, не является гауссовской, так как Составной источник обладает памятью и стационарён, однако ой неэргодичен. Плотность вероятностей первого порядка этого источника равна

где

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

где так как плотность вероятностей (8.6.6) негауссовская.

Пусть произвольный блочный код с длиной блока N и скоростью Если этим кодом закодировать составной источник, то средняя по ансамблю погрешность

Но величина

определяет среднюю погрешность для гауссовского источника с нулерым средг ним и дисперсией Согласно обратной теореме кодирования

и соответственно

откуда следует, что

где согласно

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

Но из (8.6.1) и (8.6.3) получим соотношение откуда следует

Тогда силу (8.6.13)

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

Приведенный пример показывает, что хотя функция определена для лроизвольных стационарных источников, но фактически применять ее можно только к стационарным эргодичерким источникам. Но стационарный источник общего вида можно рассматривать как объединение стационарных эргодических подысточников (Грэй и Дэвиссон [1974]). (В приведенном примере источник состоял из двух подысточников.) Это указывает на возможность обобщения теорем кодирования применительно к стационарным источникам без предположения об их эргодичности. Проиллюстрируем обобщение с помощью простого примера. I

Рис. 8.5. Стационарный неэргодический двоичный источник

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

где — число символов 1 в и. Яано, что этот двоичный источник стационарный, но неэргодический, так как для любой реализации выходной последовательности среднее по времени N

если выходная последовательность порождена подысточником в то время как математическое ожидание по ансамблю L

Предположим, что заданы алфавит представления и мера погрешности типа ошибки в символе Какова наименьшая средняя погрешность, которую можно достичь для этого двоичного источника? Хотя функция и может быть определена в виде соотношения (8.2.5), но, как показывает предыдущий пример, не обязательно означает минимальную скорость, при которой достигается средняя погрешность Можно быть уверенным лишь в том, что для любого заданного существует последовательность блочных кодов с длиной блока N и скоростью таких, что первый подысточник можно закодировать кодом 38 со средней погрешностью

где удовлетворяет уравнению

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

где удовлетворяет уравнению

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

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

Так как в каждом из подкодов имеется по кодовых слов, то в композиционном коде будет

Таким образом, скорость композиционного кода

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

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

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

В § 8.2 были оценены характеристики наилучшего из возможных способов кодирования стационарных эргодических источников. Обобщая рассмотренный пример, можно показать, что если источник можно смоделировать в виде конечного набора стационарных эргодических подысточников, то, применяя для каждого подысточника свой достаточно хороший код и образуя из этих кодов композиционный код для всего источника, который в данном случае стационарен, но необязательно эргодичен, можно достичь минимально возможной средней погрешности, соответствующей заданной скорости. Этот прием обобщается на широкий класс неэргодических стационарных источников, поскольку всякий такой источник представим как набор стационарных эргодических источников с заданным априорным распределением вероятностей того, что выходная последовательность данного подысточника является выходной последовательностью всего источника. Хотя для многих источников число необходимых для такого представления подысточников бесконечно, при некоторых дополнительных топологических ограничениях, относящихся как к источнику, так и к мере погрешности, этот набор подысточников можно аппроксимировать конечным набором подысточников. Но если имеется конечная аппроксимация, то дальше можно действовать как в вышерассмотренном примере. Чтобы проиллюстрировать этот подход, вернемся к случаю двоичного источника, но уже с несчетным числом стационарных эргодических подысточников (Грэй, Нейхоф к Шилдс [1975]).

Пример. (Двоичный источник со случайным параметром Рассмотрим двоичный источник без памяти, у которого вероятность появления на выходе символа -случайная величина, принимающая значения от 0 до 1. Закодируем этот источник, используя меру погрешности Если бы значение было известно, то имелся бы двоичный источник, обладающий свойствами стационарности и эргодичности. Поскольку параметр случайный, то источник, рассматриваемый в целом, стационарен, но не эргодичен. Чтобы свести задачу к предыдущему примеру, нужно аппроксимировать множество всех возможных подысточников конечным множеством подысточников. Для этого определим расстояние между двумя двоичными источниками без памяти с известными, но различными параметрами.

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

и

Это значит, что совместное распределение -ностей с маргинальными распределениями, соответствующими источникам Определим расстояние между источниками как

где совокупность всех таких совместных распределений. Тогда

так как расстояния. Легко показать (см. задачу 8.17), что

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

Тогда

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

Усредняя либо (8 6.35), либо (8.6 36) по совместному распределению удовлетворяющему (86.30) — (8.6.32) и (8.6.34), получим неравенство

где и - средние погрешности, достижимые при кодировании кодом источников соответственно. Это неравенство для невязки определяет максимальный проигрыш, который обусловлен применением кода, предназначенного для одного источника, к другому источнику. Оно позволяет производить конечную аппроксимацию пространства источников, так как из близости двух источников в метрике вытекает, что хороший для одного источника, будет хорошим и для другого. Наконец, если значения скорости как функции погрешности двух источников равны то, как нетрудно показать (см. задачу 8.18),

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

средние точки интервалов. Из построения следует, что так что для любого

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

Из неравенства (8.6.37) следует, что для любого источника с параметром имеем среднюю погрешность

где величина такова, что Тогда силу того, что [см. (8.6.29)], получим

где удовлетворяет уравнению [см. (8.6.24)]

Наименьшая средняя погрешность, возможная для источника с параметром равна где

Но из (8.6.38) следует, что

откуда

Подставляя эту оценку в (8.6.42), окончательно получаем

Скорость композиционного кода

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

Метод, описанный в этом примере, обобщается на широкий класс неэргодических стационарных источников и мер погрешностей. Основная идея метода вытекает из того, что неэргодические источники можно представлять как набор стационарных эргодических подысточников (Рохлин [1967]). Вводя расстояние в

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

Термин «универсальное кодирование» относится ко всем методам кодирования источников, у которых характеристики кода, выбранного без предварительного знания «истинного» источника, сходятся к оптимальным характеристикам кода, специально построенного для известного источника. Способ представления или аппроксимации источника посредством конечного набора стационарных эргодических источников и построения объединенного кода является лишь одним из примеров универсального кодирования. Другой близкий к нему способ состоит в том, чтобы использовать малую часть кодовых символов для опознавания и описания стационарного источника, а остальные кодовые символы — для собственно кодирования выходной последовательности источника. В § 8.6 рассматривалась более сильная робастная техника кодирования для источников с конечным алфавитом, согласно которой выходные последовательности источника распределялись по конечному числу классов композиций. Такой способ также не зависит от статистики источника и по существу связан с подходом, рассмотренным в этом параграфе. Во всех случаях задача заключается в том, чтобы кодировать неизвестные или неэргодичеекие источники, которые часто можно определить в целом как источники с неизвестными параметрами. Основной результат двух последних параграфов состоит в доказательстве того, что с асимптотической точки зрения универсальные способы кодирования могут быть так же эффективны, как если бы эти неизвестные параметры были нам точно известны. Вторая цель, которая преследовалась в этом параграфе, — показать, что в отличие от стационарных эргодических источников для неэргодических стационарных источников не существует единой функции, выполняющей роль скорости как функции погрешности.