8.5.2. Последовательности с фиксированной композицией. Двоичный пример

Существует тесная взаимосвязь между симметричными источниками с балансной мерой погрешности и выходными последовательностями с фиксированной композицией, производимыми произвольным дискретным источником. Для последовательностей с фиксированной композицией можно доказать теорему, аналогичную 8.5 1 Хотя сформулированное в ней свойство легко обобщается на случай источников с произвольным дискретным алфавитом и ограниченной побуквенной мерой погрешности (Мартин [1976]), здесь покажем его только для двоичного алфавита с погрешностью типа ошибки в символе.

Предположим, что имеется алфавит источника , алфавит представления и мера погрешности типа ошибки в символе

Для любой последовательности определим ее вес как единиц в и и классы композиций

сопоставляя каждому классу распределение вероятностей

и скорость как функцию погрешности [см. (7.6.62)]

С помощью границы Чернова (см. задачу 1.5) находим, что число последовательностей в обозначаемое удовлетворяет неравенству

Это означает, что всегда можно найти код, скорость которого удовлетворяет неравенству

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

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

Заметим, что величины можно сделать сколь угодно малыми, но удовлетворяющими, тем не менее, условию (8.5.27). Определим двоичное распределение через величины в следующей параметрической форме:

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

можно получить соотношения

Таким образом, для любого класса композиций у которого , можно найти блочный код со скоростью и длиной N такой, что

у которого согласно (8.5.26)

Поскольку число последовательностей представления больше, чем число последовательностей в классе, то таким кодом можно закодировать последовательности из с нулевой погрешностью, если только I удовлетворяет (8.5.29).

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

определим из условия

Такое значение может быть найдено внутри отрезка (рис. 8.3). Покажем теперь, что, как и в случае

Рис. 8.3. Вид функции двоичной энтропии

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

где

-условное распределение вероятностей, на котором достигается скорость как функция погрешности

Лемма 8.5.2. Пусть величины и скорость удовлетворяют условиям (8.5.27) и (8.5.28). Тогда для любого класса композиций удовлетворяющего (8.5.34), любого уровня погрешности удовлетворяющего (8.5.35), и любой последовательности в среднем по ансамблю блочных кодов, определяемом распределением вероятностей (8.5.36), существует граница

Доказательство.

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

Подставляя (8.5.35) в правую часть неравенства (8.5.40), а полученный результат в (8.5.39), приходим к нужной границе

Легко видеть, что если то откуда задачу 8.12). Следовательно, показатель экспоненты в (8.5.38) положителен, Из этой леммы следует искомый результат.

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

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

если

в противном случае. Здесь удовлетворяет уравнению

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

Усредняя по выходным последовательностям, получаем

Рассмотрим далее ансамбль блочных кодов, в котором код выбирается с вероятностью, определяемой (8.5.36) и (8.5.37). Усредняя (8.5.43) по этому ансамблю, находим

где неравенство следует из леммы 8.5.2. Так как то существует блочный код с длиной блока N и скоростью такой, что

Выбирая любое целое для которого правая часть (8.5.45) меньше единицы, так же как и при доказательстве теоремы 8.5.1, найдем, что для всех

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

Естественно определить композиционный код как код

содержащий элементов (по элементов для каждого из классов композиций) и обладающий, следовательно, скоростью

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

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

До сих пор полученные результаты были связаны только с алфавитом источника, оставаясь независимыми от статистики источника. Композиционный код удовлетворяет неравенству (8.5.48) независимо от того, какой статистикой обладает источник. Предположим, однако, что двоичный источник — это источник без памяти с вероятностями Его скорость как функция погрешности Насколько успешно композиционный код будет кодировать именно этот источник? Средняя погрешность композиционного кода

Когда N растет, то функция концентрируется около своего среднего значения Это следует из свойства асимптотической равнораспределенности (Макмиллан [1953]), которое утверждает, что с увеличением длины блока почти все последовательности источника стремятся иметь одну и ту же композицию. Таким образом, находим (см. задачу 8.13 и гл. 1)

где удовлетворяет (8.5.35) при Это значит, что

Скорость кода становится равной

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

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

Предыдущий пример с двоичным алфавитом и погрешностью типа ошибки в символе может быть обобщен на произвольные дискретные алфавиты и произвольные погрешности типа ошибки в букве (см. задачу 8.14). Дальнейшие обобщения можно строить, выбирая в качестве элементов новых расширенных дискретных алфавитов конечные фиксированные выходные последовательности источника. Это позволяет применить технику робастного кодирования источников к источникам с памятью (Мартин [1976]).

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

стационарных источников. Это относится уже к области универсального кодирования источников, которое будет рассматриваться в § 8.6.

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

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

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