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

В § 7.6 было найдено, что скорость как функцию погрешности для симметричных источников с балансной мерой погрешности нетрудно задать в компактной параметрической форме [см. (7.6.69) и (7.6.70)]. Теперь покажем, что эти же симметричные источники с балансной мерой погрешности обладают тем свойством, что при любой, даже сколь угодно близкой к скорости существуют коды с достаточно большими длинами блока, которые кодируют каждую выходную последовательность источника с погрешностью или меньше. Такой результат является существенно более строгим, чем устанавливаемый теоремой 7.2.1, согласно которой получаемый результат справедлив для средней погрешности. Аналогичный строгий результат имеет место и в случае кодирования последовательностей с фиксированной композицией, порождаемых любым дискретным источником, что позволит нам перейти в следующем параграфе к изучению техники робастного кодирования источников, которая не зависит от статистики источников. Начнем с того, что переформулируем определения симметричного источника и балансной меры погрешности.

8.5.1. Симметричные источники с балансной мерой погрешности

Симметричный источник — это дискретный источник без памяти с равновероятными выходными буквами. Это значит, что

где

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

Скорость как функция погрешности задается параметрически соотношениями (7.6.69) и (7.6.70), где независимый параметр.

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

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

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

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

Лемма 8.5.1. Если заданы длина блока уровень погрешности и произвольная выходная последовательность то в среднем по ансамблю блочных кодов с длиной блока N и скоростью

где

а величина

не зависит от

Доказательство. Пусть Так как кодовые слова независимы и одинаково распределены, то согласно (8.5.6)

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

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

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

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

найдем, что

Из леммы сразу следует, что средняя погрешность удовлетворяет неравенству

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

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

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

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

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

Далее, усредняя результат по ансамблю кодов, определяем

где неравенство следует из леммы 8.5.1. Это значит, что существует по крайней мере один код для которого

или

Выбирая N достаточно большим, можно сделать эту оценку при меньше 1. Таким образом, получим

Но по определению (8.5.17) функция при каждом и может равняться только 0 или 1. Следовательно, из (8 5.21) вытекает, что для всех а это, в свою очередь, означает, что для всех и

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