§ 3.8. Неравенство Файнстейна

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

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

где Будем обозначать через некоторое подмножество множества а через V — множество таких пар что взаимная информация каждой пары больше, чем где некоторое положительное число:

Теорема 3.8.1 (неравенство Файнстейна). Пусть произвольное положительное число, произвольное подмножество множества произвольное распределение вероятностей на Тогда для каждого существует код каждое слово которого принадлежит а максимальная

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

где

и

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

Рис. 3.8.1. К доказательству теоремы 3.8.1.

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

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

Тогда множество можно определить следующим образом:

Пусть — кодовые слова. Будем считать, что решающие области определяются следующим способом:

где знак вычитания множеств есть множество всех элементов, принадлежащих С, но не принадлежащих

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

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

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

Тогда должно выполняться следующее неравенство:

С другой стороны, из формулы (3.8.7) следует, что

Так как

то

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

Как было сказано, есть объем максимального кода. Другими словами, к выбранному коду нельзя добавить ни одного слова так, чтобы оно принадлежало множеству и не были нарушены условия (3.8.9). Следовательно, для любого должно выполняться неравенство

В противном случае выбор кодовых слов можно было бы продолжить, положив при этом и построенный код не был бы максимальным.

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

Это неравенство имеет место для всех последовательностей поэтому левую и правую его части можно осредннть по 5. Для этого умножим обе части (3.8.14) на и просуммируем по . В результате получим

Из соотношений (3.8.11) и (3.8.12) следует, что

Используя это и предыдущее неравенство, можно получить, что

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

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

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

Суммируя обе части последнего неравенстга по всем получим следующую цепочку неравенств:

где последнее неравенство — следствие того, что -подмножество множества Таким образом,

Учитывая неравенства (3.8.15), (3,8.16), (3.8.19), а также что получим неравенство (3.8.3). Теорема доказана.

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

Предположим, что тогда при любом распределении на входе. Положим и

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

и верхняя грань разыскивается по всем и по всем распределениям вероятностей на входных последовательностях. Тогда, как это следует из (3.8.3), первое слагаемое равно и стремится к нулю при возрастании Второе слагаемое определяется поведением вероятности которую можно представить следующим образом:

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

взаимной информации Тогда найдется такое, что

и

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

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