Главная > Теория информаци и связи > Передача информации. Статическая теория связи
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

9.2. Нижняя граница вероятности ошибки

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

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

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

В разд. 6.1 мы видели, что операцию кодирования можно рассматривать как отображение пространства сообщений, состоящего из точек в пространство входных последовательностей (сигналов) состоящее из всех возможных последовательностей и из событий, принадлежащих пространству Обозначим через входную последовательность, в которую отображается сообщение Соответственно операция декодирования может рассматриваться как разбиение пространства выходных последовательностей V, состоящего из всех возможных последовательностей из событий, принадлежащих пространству на подмножеств Каждое подмножество состоит из всех последовательностей которые должны быть декодированы в сообщение Условная вероятность зависит от композиций букв в двух последовательностях Обозначим через число букв в некоторой последовательности и и через число букв некоторой последовательности Аналогично будем обозначать через число соответствующих пар букв в двух последовательностях, рассматриваемых как единая последовательность пар букв. Очевидно, для любой пары последовательностей имеем

и

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

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

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

будут декодированы правильно, задается формулой (7.40). Для удобства ссылок мы воспроизведем ее здесь

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

Поскольку все сообщения равновероятны, то при этих условиях, соответствующих декодированию по максимуму правдоподобия, максимизируется апостериорная вероятность. Введем расстояние

где - условное распределение вероятностей, характеризующее канал, и произвольная положительная функция от у, для которой

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

где

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

Теорема. Рассмотрим некоторый способ сопоставления сообщениям последовательностей на входе канала и разбиения пространства V последовательностей на выходе канала на непересекающихся подмножеств декодирования

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

Доказательство. Обозначим через разбиение, состоящее из подмножеств до, удовлетворяющих условию, указанному в теореме, и через некоторое другое разбиение, состоящее из подмножеств не удовлетворяющих этому условию. Каждая последовательность принадлежащая подмножеству для которого должна принадлежать в разбиении некоторому подмножеству связанному с некоторой другой входной последовательностью для которой Это означает, что сумма в правой части равенства (9.8) содержит в случае разбиения слагаемое в то время как в случае разбиения на месте этого слагаемого она содержит слагаемое Поэтому вероятность правильного декодирования для меньше, чем для Обратно, каждая последовательность не принадлежащая связанному с входной последовательностью для которой должна принадлежать связанному с для которой Тогда слагаемое в равенстве (9.8), содержащее меньше для чем для

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

Каждая из вероятностей в правой части неравенства (9.14) есть сумма условных вероятностей

следовательностей для которых С другой стороны, из соотношений (9.7), (9.12) и (9.13) видно, что как для так и для зависимость от пары щи выражается только через ее композицию В силу равенств (9.5), следует, что зависимость от последовательности -выражается только через ее композицию эта вероятность имеет одно и то же значение для всех последовательностей с одинаковой композицией.

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

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

где V — дополнение к т. е. множество последовательностей для которых

Доказательство. Рассмотрим какой-либо способ сопоставления сообщениям последовательностей с заданной композицией и разбиение пространства V выходных последовательностей на подмножества декодирования удовлетворяющих условиям теоремы, содержащей неравенство (9.14). В этой теореме устанавливается, что вероятность ошибки при любом осуществимом разбиении пространства V должна удовлетворять неравенству (9.14). С другой стороны, каждое слагаемое суммы в правой части неравенства (9.14) зависит только от значения и композиции входной последовательности Отсюда следует, что неравенство (9.14) сводится к неравенству (9.16).

Далее, рассмотрим связь между и значением целого числа Заметим с этой целью, что функции можно рассматривать как распределения вероятностей на пространстве У и на пространстве выходных последовательностей V,

Тогда если выделить индексом вероятность какого-либо события относительно распределения то знаменатель в неравенстве (9.15) можно записать в виде

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

С другой стороны, подмножества декодирования не пересекаются и вместе с тем должны содержать все пространство Следовательно, из неравенства (9.18) получаем

что приводит сразу к неравенству (9.15). Иначе говоря, из условия, состоящего в том, что каждая последовательность из V должна содержаться в некотором подмножестве следует, что и соответствующее множество должны быть достаточно большими, чтобы удовлетворить условию (9.15). Конечно, любое большее значение соответственно приводит к большему множеству следовательно, к меньшему множеству а это влечет за собой уменьшение нижней границы вероятности ошибки в неравенстве (9.16). Ч. Т. Д.

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

Теорема. Рассмотрим дискретный постоянный канал, характеризуемый условным распределением вероятностей

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

где

и

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

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

где

— наименьшее значение — число входных букв; число выходных букв и

Доказательство. Теорема, содержащая соотношения (9.15) и (9.16), устанавливает, что для любой скорости передачи на событие в канале

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

где - какая-либо входная последовательность с заданной композицией, вероятность определена в равенстве (9.7) и функция определена в равенстве (9.13). Множества выходных последовательностей представляют собой взаимно дополнительные подмножества пространства V выходных последовательностей

где расстояние, определенное выражением (9 12), а независимый параметр. Теперь нам надо получить нижние границы сумм в неравенствах (9.30) и (9.31).

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

где, в силу соотношения (8.130),

и

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

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

где подставлено вместо параметра в неравенство (8.125) для того, чтобы отличить его от параметра, использованного в соотношении (9.34), удовлетворяет неравенству (9.35) и

Суммирование в этих соотношениях распространяется на все выходное пространство У, а не на поскольку не обращается в нуль для любой выходной буквы.

Слагаемые, соответствующие обращаются в нуль для но становятся бесконечными для В силу этого неравенство (9.39) справедливо только для но не для

Так как в соотношениях (9.37) и (9.41) обе величины полагаются равными то параметры должны быть таковы, чтобы

или, что эквивалентно,

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

которое может быть удовлетворено, если положить

Так как то из соотношений (9.34) и (9.35) получаем

где определено соотношением (9.27) и в выражения для можно подставить У вместо Кроме того, поскольку величина не может превосходить единицу, то из соотношений (9.35) и (9.39) мы получаем

Отсюда следует, что неравенство (9.30) удовлетворяется, если скорость передачи

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

Далее, мы видим, что неравенства (9.47) и (9.49) имеют место для любой положительной функции удовлетворяющей равенству (9.11). В частности, они имеют место для

Можно показать, что такой выбор минимизирует

для любого фиксированного значения

так что это значение а приближенно максимизирует правую часть неравенства (9.47) для любого фиксированного значения правой части неравенства (9.49). Однако для доказательства теоремы этот факт несуществен.

Наконец, подставляя вместо в неравенства (9.47) и (9.49), получаем соотношения (9.26) и (9.25) теоремы. Неотрицательность величин I и а легко доказывается с помощью выражения (2.91)

Ч. Т. Д.

9.3. Асимптотическое поведение нижней границы

Величины правых частей неравенств (9.25) и (9.26) для больших зависят в основном от и а соответственно. Точнее, имеем

Следовательно, при обсуждении вышеприведенной теоремы мы можем ограничиться изучением связи между величинами задаваемыми формулами (9.28) и (9.29), как функции параметра Имеем при

где - средняя взаимная информация между входными и выходными буквами, когда распределение вероятностей на входе совпадает с композицией входных последовательностей, сопоставленных сообщениям. Исследование поведения величин для лучше всего провести, вычисляя их производные по . В этой связи мы заметим, что, согласно выражениям (9.20) и (9.24), зависит от как через так и непосредственно. То же справедливо и для определяемого в выражении (9.21) как частная производная по при постоянном Нижеследующая теорема устанавливает, однако, что последовательные полные производные от по совпадают с соответствующими частными производными, взятыми при постоянном

Теорема. Пусть

Тогда

Доказательство. Полная производная по равна

С другой стороны,

и

Следовательно, равенство (9.59) сводится к левому соотношению в формуле (9.58). Аналогично

С другой стороны, с помощью равенства (9.60), имеем

Так что, в силу равенства (9.61), соотношение (9.62) сводится к среднему соотношению в формуле (9.58). Вообще, с помощью равенства (9.60) мы получаем, что

из которого аналогичным образом выводим правое соотношение в формуле (9.58). Ч. Т. Д.

Мы теперь в состоянии вычислить производные по от Из соотношений (9.28) и (9.29) с помощью последней теоремы получаем

а из тождества (9.20),

где

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

Отсюда мы можем сделать вывод, что а монотонно возрастает с ростом в то время как монотонно убывает. Кроме

того, если рассматривать а как функцию то из соотношений (9.68) получаем

и

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

Рис. 9.2. Типичный характер зависимости а от

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

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

Из тождества (9.23) имеем

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

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

из которого можно найти . А тогда соответствующие значения находятся из выражений (9.28) и (9.29)

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

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

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

Кривые, изображенные на рис. 9.2, в действительности не кончаются в точках как мы увидим, продолжаются по вертикали до бесконечности. Ограничение в выражениях (9.25) и (9.26) возникают из ограничения в формуле (9.39)

и связи между задаваемой условием (9.46). В свою очередь эта связь является результатом того, что в выражениях (9.37) и (9.41) мы полагаем равными Следовательно, неравенство (9.26) справедливо также и для 1, т. е. для Однако для выражения (9.25) это не так. С другой стороны, видно, что левая часть неравенства (9.39) возрастает с возрастанием с возрастанием множества Поэтому правая часть выражения (9.37) остается справедливой для Отсюда следует, что для

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

где задаются выражениями (9.36) и (9.37). Тогда, поскольку правая часть неравенства (9.77) стремится к бесконечности с ростом то кривые на рис. 9.2 при должны переходить в вертикали. Другими словами, нижняя граница вероятности ошибки обращается в нуль для Факт обращения в нуль нижней границы для ненулевых значений будет обсужден в следующем разделе.

<< Предыдущий параграф Следующий параграф >>
Оглавление