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

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

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

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

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

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

где - условная вероятность какой-либо выходной последовательности когда входная последовательность.

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

Доказательство. Предположим, что условие (7.41) не удовлетворяется для некоторой выходной последовательности принадлежащей подмножеству и некоторой входной последовательности Тогда из выражения (7.40) следует, что вероятность правильного декодирования может быть увеличена

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

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

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

Тогда, если наименьшее целое, для которого

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

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

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

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

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

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

что совпадает с условием (7.44).

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

и отсюда с помощью выражения (7.42) получаем неравенство (7.43). Ч. Т. Д.

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

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

Метод, использованный в приведенном доказательстве, иногда называют «сферической упаковкой». Это наименование возникло из следующей геометрической интерпретации. Рассмотрим -мерное пространство, в котором декартовы координаты могут принимать только два значения 1 и 0. Ясно, что любая последовательность из двоичных символов может быть представлена как точка в этом пространстве. Далее, если число символов, в которых различаются некоторые две последовательности, равно то расстояние между двумя соответствующими точками равно Тогда каждое из подмножеств выходных последовательностей, рассматриваемых в доказательстве теоремы, состоит из точек, лежащих внутри или на сфере радиуса с центром в точке, соответствующей входной последовательности Аналогично всевозможные последовательности из двоичных символов лежат внутри или на сфере радиуса с центром в начале координат. Кроме того, мы видим, что задаваемая в выражении (7.45) вероятность перехода какой-либо последовательности в другую действием шума в канале монотонно убывает с увеличением расстояния между точками, соответствующими этим двум последовательностям.

Аргументация, использованная в доказательстве теоремы, соответствует тогда упаковке. сфер радиуса в сфере радиуса при которой все точки, соответствующие возможным последовательностям из символов, лежат внутри или на поверхности одной и только одной из сфер. Каждая сфера радиуса содержит точек, где задается формулой (7.42), а сфера радиуса содержит точек. Отсюда следует, что если удовлетворяет условию (7.43), то вероятность ошибки не может быть меньше, чем правая часть выражения (7.44). Соответственно его правая часть есть вероятность того, что какая-либо входная последовательность, представленная

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

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

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

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

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

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

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

при

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

Доказательство. Учитывая выражение (7.16) и подставляя нижнюю границу, задаваемую неравенством (7.18) в правую часть соотношения (7.44), получаем

Затем, заменяя в этом выражении его нижней границей из выражения (7.3), после некоторых преобразований получим правую часть неравенства (7.52).

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

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

где правая часть неравенства (7.50). Отсюда следует, что условие (7.54) удовлетворяется при любой скорости передачи большей или равной так что неравенство (7.52) удовлетворяется всегда, когда для скорости передачи имеет место неравенство

Ч. Т. Д.

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

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

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

Эти две величины связаны друг с другом через параметр График изображен на рис. 7.3 как функция

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

Далее определим величину

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

Отсюда следует, что представляется на рис. 7.3 как разность между кривой и прямой линией

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

Рис. 7.3. Графическое определение

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

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

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

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