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

7.3. Верхняя граница вероятности ошибки

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

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

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

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

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

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

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

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

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

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

где вероятность искажения в канале.

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

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

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

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

Решая это неравенство относительно и применяя соотношения (7.65), (7.66) и тождество

получаем неравенство (7.63).

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

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

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

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

где

и

Множитель в показателе а и для может быть также представлен в виде

где

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

где

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

где - целое число, определяемое ниже.

Подстановка вместо в выражение (7.63) дает

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

Следующим шагом в нашем выводе является подстановка вместо верхних границ, данных в выражениях (7.3), (7.8), (7.18) и (7.26). Для мы получаем

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

Это соотношение устанавливает связь между скоростью передачи и параметром от которых зависит правая часть выражения (7.81). Правые части неравенств (7.70), (7.72), (7.73) и (7.74) для следуют немедленно из соотношения (7.81) и (7.82).

Соответствующее выражение для может быть получено с помощью неравенства (7.27). Полагая и подставляя

правую часть формулы (7.27) в получившуюся сумму в выражении (7.80), получаем выражение

которое согласуется с неравенствами (7.72), (7.73) и (7.74) для

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

Далее подстановка для из выражения (7.70) при дает

Здесь мы используем соотношение

вытекающее из выражения (7.71). Выражение для задаваемое соотношениями (7.75) и (7.76), следует из неравенств (7.70) и (7.74). Ч. Т. Д.

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

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

как функции показано на рис. 7.4. Для график совпадает с кривой задаваемой выражением (7.82).

Для график совпадает с прямой линией

Эта прямая касательна к кривой в критической точке соответствующей критической скорости передачи

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

Важно заметить, что соотношение между тождественно соотношению между и предельным значением данным в выражении (7.57). Это очевидно из сравнения рис. 7.3 и 7.4. Следовательно, для верхняя граница вероятности ошибки, выведенная в этом разделе, и нижняя граница вероятности ошибки, выведенная в предыдущем разделе, имеют одинаковый экспоненциальный рост с ростом Однако для имеем Другими словами, для любой скорости передачи верхняя граница в неравенстве (7.72) с возрастанием экспоненциально отклоняется от нижней границы в выражении (7.52).

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

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

того, что -вероятность ошибки при декодировании будет больше удовлетворяет неравенству

где А — любая константа, большая 1,

Рис. 7.4. (см. скан) Графическое определение

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

равна по определению

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

Тогда с помощью выражения (7.91) мы получаем из выражения (7.90) следующее неравенство:

откуда немедленно вытекает выражение (7.89). Ч. Т. Д.

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

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