7.6. Вычисление R(D). Дискретные источники без памяти

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

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

где А — объем алфавита дискретного источника без памяти и Таким образом, имеем границу

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

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

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

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

Это есть двумерное условие стационарности. Оно позволяет определить двумерную спектральную плотность соотношением

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

Применяя эту теорему к выражениям (8.4.39) и (8.4.40), находим

где определяется из уравнения

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

Далее из (7.6.2) следует, что

Единственным условным распределением вероятностей обеспечивающим равенство служит распределение

где удовлетворяет равенству Здесь

где

Отсюда видно, что в случае, когда для выполняется условие имеет место равенство следовательро, Это условие выполняется в тех случаях, когда В, число букв в алфавите У, больше или равно А, числу букв в алфавите 41. Но, как правило, именно эти случаи и представляют наибольший интерес.

Рис. 7.12. Типичный график скорости как функции погрешности

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

по переменным при ограничениях

Если бы не ограничение (7.6.13), то это была бы обычная задача минимизации с неопределенными множителями Лагранжа. Начнем действовать так, словно это так и есть в действительности, и будем считать

множителями Лагранжа, соответствующими ограничениям именно: рассмотрим задачу минимизации величины

не забывая одновременно о необходимости соблюдения неравенства (7.6.13). Удобно ввести обозначения

так что (7.6.16) перепишется в виде

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

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

Теорема 7.6.1. Для того чтобы достигался минимум функции определяемой переменным при ограничении (7.6.13), необходимо и достаточно, чтобы эти переменные удовлетворяли условиям

где

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

и полагая

находим

Первый член в (7.6.21) равен

тогда как второй член

так как для из условия (7.6.19), справедливого по предположению, следует, что

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

Пользуясь неравенством [см. (1.1.6)], находим

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

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

Необходимость. Пусть минимизирует при ограничениях в виде неравенств (7.6.13). Аналогично доказанному выше для любого и любых таких, что для всех

Прежде всего выберем для всех о, для которых Тогда

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

Далее выберем функцию входящую в (7.6.27), в виде

Тогда

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

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

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

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

Доказательство. Чтобы получить (7.6.32) и (7.6.33), подставим в выражения

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

Лемма 7.6.2. Параметр в (7.6.32) и (7.6.33) равен наклону кривой скорости как функции погрешности в точке е.

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

С помощью (7.6 33) отсюда находим

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

выполняющемуся при Дифференцируя по находим

Умножая на и суммируя по получаем

Здесь первый член равен а

откуда вытекает равенство

Таким образом, из (7.6.36) получаем, что

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

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

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

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

Второе неравенство следует из выпуклости, доказанной в лемме Так Кал

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

или

Здесь и - значения к соответствующие Так как левая часть этого равенства не зависит от то либо либо Если то

Суммируя по всем для которых получаем

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

и, следовательно, так как Но так как то заключаем, что

Дополнительно к утверждению леммы доказано (Галлагер [1968], Бергер 197l), что обращается в когда приближается к и что единственное нарушение непрерывности может наблюдаться при Зададим функцию в другой форме, которая может быть более удобной для получения ее нижних оценок.

Теорема 7.6.3. Скорость как функция погрешности может быть представлена в виде

Необходимые и достаточные условия того, что и X соответствуют максимуму, совпадают с теми, которые указаны в формулировке теоремы 7.6.2.

Доказательство. Пусть Замечая, что находим

Применяя вновь неравенство имеем

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

и, следовательно, неравенство

Но из теоремы 7.6.2 следует, что существуют такие, что

Поэтому

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

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

Найдем для Ясно, что для любого распределения Рев, у которого выполняется равенство если же то

Следовательно, если то для любого должны выполняться условия Условное распределение вероятностей, (на котором достигается скорость как функция погрешности, должно иметь вид

Умножая на и суммируя по получаем систему равенств

имеющую решение

Найдем значения , соответствующие оптимальному условному распределению из Из (7.6 31) следует, что

Вместе с (7.6.57) эти выражения дают систему уравнений

решениями которой являются

Отсюда находим параметрическое уравнение для

Таким образом, множитель Лагранжа должен удовлетворять равенству

Из (7.6.33) находим

Заметим, что так как то скорость как функция погрешности симметричного источника равна наибольшей скорости, какая может потребоваться для достижения средней погрешности в случае двоичного источника. Это естественно, так как наибольшая неопределенность соответствует выходной последовательности двоичного симметричного источника. Ниже показано, как этот пример можно обобщить. Дальнейшее изучение скорости как функции погрешности, выходящее за рамки этого специального обобщения, представляется слишком сложным, чтобы уделить ему здесь внимание (подробнее см. Бергер [1971]). Вместо этого можно воспользоваться теоремой 7.6.3 и найти нижнюю границу Пример. (Погрешность — ошибка в символе.) Рассмотрим естественное обобщение предыдущего примера. Пусть заданы алфавиты вероятности букв источника и мера погрешности Вместо того, чтобы выводить точиое выражение для найдем

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

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

Тогда

Положим

так что

Так как выбрано то

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

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

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

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

симметрии легко догадаться, что Теперь проверим, выполняются ли при этом необходимое и достаточное условия теоремы 7.6.2. Условные вероятности должны быть равны

и согласно (7.6.31)

Эти условные вероятности удовлетворяют условиям (7.6.19) при соответствующем значении Я. Тогда выражения (7.6.32) и (7.6.33), определяющие скорость как функцию погрешности в параметрической форме, приводятся к виду

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

Лемма 7.6.4. Нижняя граница скорости как функции погрешности для дискретного источника без памяти с энтропией определяется неравенством

где можно найти из равенства

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

Доказательство. Выберем так, что

тогда

так что При таком выборе из теоремы 7.6.3 следует, что

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

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