7.2. Дискретные источники без памяти. Блочные коды

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

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

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

а среднюю погрешность, достижимую в коде как

в соответствии с предположением о том, что источник не имеет памяти.

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

кодовое слово, соответствующее переданному, и выдает его пользователю. Эта схема блочного кодирования показана на рис. 7.3. Так как для каждой последовательности из N символов источника по бесшумному каналу, соединяющему кодер с декодером, передается один из индексов (который может быть представлен как некоторая двоичная последовательность, длина которой есть наименьшее целое, большее или равное то скорость передачи нат/символ источника. Ниже код Я называется блочным кодом с длиной блока N и скоростью

Рис. 7 3. Система блочного кодирования источника

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

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

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

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

где Не будем придавать никакого физического смысла условным вероятностям а просто используем их как удобный инструмент для вывода оценок средней погрешности при использовании кода 31 с объемом и длиной блока Напомним, что согласно (7.2.4) средняя погрешность, достижимая при пользовании кодом 38,

Так как то можно переписать это выражение как

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

Так как

Применяя к первой сумме в (7.2.11) неравенство, вытекающее из определения (7.2.10),

а ко второй сумме неравенство, следующее из (7.2.1),

получаем границу

Первый член в этой границе упрощается:

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

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

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

где

Доказательство. Применяя неравенство Гельдера (см. приложение 3А), для любого находим

поскольку из определения (7.2.10) следует, что Усредняя это неравенство по ансамблю кодов и применяя неравенство Иенсена в том же интервале значений параметра находим

Для второго из выражений, заключенных в скобки, имеем

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

Теперь исследуем поведение этой границы при различных значениях параметра Как сказано в вышеприведенной лемме, граница (7.2.17) верна для всех в интервале и для любого выбора условных вероятностей Выражение подобно показателю экспоненты случайного кодирования в теории кодирования для каналов, развитой в § 3.1. Единственное отличие состоит в том, что в данном случае параметр меняется от —1 до 0, тогда как в случае кодирования для каналов этот параметр менялся от 0 до 1. Кроме того, здесь можно произвольно выбирать условные вероятности которые одновременно влияют на тогда как при изучение показателя экспоненты случайного кодирования для каналов условные вероятности канала были фиксированы, а варьировать разрешалось только распределение на ансамбле кодов. В нижеследующих леммах воспользуемся прежними результатами изучения границы случайного кодирования для каналов. При этом будет иметь форму функции Галлагера, впервые определенной в (3.1.18).

Лемма 7.2.2. Функция

обладает следующими свойствами при

где

означает функцию средней взаимной информации.

Доказательство. Лемма совпадает с леммой 3.2.1. Ее доказательство приведено в приложении

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

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

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

В силу того, что имеем

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

Выбирая находим

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

для

Эти соотношения представлены на рис. 7.4.

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

ансамблю значение и оценим его суммой величины (7.2.15) и границы, указанной в лемме 7.2.1. Отсюда следует граница величины в виде

справедливая для любых Минимизируя найденную границу по находим

где Чтобы минимизировать полученную границу величины: можно выбирать произвольные условные вероятности;

Рис. 7.4. Вид функции

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

Очевидно, что — непустое, замкнутое, выпуклое множество для всех

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

которое принадлежит и достигает нижней границы.

Определим функцию надежности источника

и функцию

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

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

где для

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

где для Но из определения следует, что Далее, так как для где в качестве можно взять любое находим, что для Следовательно,

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

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

Тогда параметрическое уравнение (7.2.29) принимает вид

(см. также § 3.4). Функция представлена на рис. 7.5 для где

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

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

Рис. 7.5. Вид функции для двоичного симметричного источника с погрешностью типа ошибки

Доказательство. Если удовлетворяет условию то достаточно выбрать такое большое, что

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

находим следующие неравенства:

Из неравенства (7.2.46) следует, что выпуклая функция от Р. Это утверждение доказано в лемме в приложении

Неравенство (7.2.47) может быть доказано с помощью рассуждений, аналогичных доказательству леммы 1.2.2 относительно приведенному в гл. 1 (см. задачу 7.1).

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

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

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

Предположим, что отображению соответствует средняя погрешность или меньше. Тогда

где отображается в Но по определению (7.2.2)

где неравенство следует из (7.2.50). Следовательно, распределение определяемое формулой (7.2.49), принадлежит так что

Здесь воспользовались неравенствами (7.2.46), (7.2.47) и неравенством (см. задачу 1.7). Таким образом, из следует что и доказывает теорему

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

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

где

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

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

Теорема 7.2.4. Существует код с длиной блока N и скоростью передачи такой, что

при , где константа, такая, что для всех

Доказательство. Из (7.2.30) следует, что для каждого в интервале и для каждого условного распределения вероятностей существует код с длиной блока N и скоростью такой, что

Напомним, что согласно (7.2.18)

Дважды интегрируя при фиксированном находим, что

Так как

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

Тогда

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

Теперь выберем Рев, при котором Тогда

Положим и выберем

где предполагается достаточно малым, чтобы выполнялось неравенство Тогда

Подставляя это неравенство в (7.2.55), находим

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

получаем

В другом случае, выбирая

получаем

откуда видно, что если со скоростью то со скоростью для любого фиксированного

Хотя теорема 7.2.4 и не приводит к наиболее строгим среди известных границам скорости сходимости (см. Бергер [1971], Галлагер [1968], Пилк [1968]), устанавливаемые ею оценки легко вычисляются. Но для источников, называемых симметричными, существуют блочные схемы кодирования, в которых достигается гораздо более высокая скорость сходимости с ростом длины блока (см. § 8.5).