Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Ре,т= 2 pw(y|xm). (5.2.6)
уеу^
Тогда общая вероятность ошибочного декодирования, в случае, когда априорные вероятности сообщений имеют вероятности Рг (т),
137
равна
м
Ре= % Рг (т)Ре<т.
т= 1
(5.2.7)
Для примера рассмотрим код, представленный на рис. 5.2.1. В нем есть два кодовых слова Х!=(0,0,0) и ха = (1,1,1). Правило декодирования (которое, как можно заметить, является правилом максимального правдоподобия для ДСК) состоит в том, чтобы декодировать каждую из последовательностей (0,0,0), (0,0,1), (0,1,1) и (1,0,0) в сообщение 1 и другие последовательности в сообщение 2. Следовательно, Y{ совпадает с У2 и является множеством последовательностей (0,1,1), (1,0,1) (1,1,0) и (1,1,1)- Для ДСК, изображенного на рис 5.2.1, .Р3[(0,1,1) | (0,0,0)] = (1—е)е2, например, и подобное вычисление /’з (у | хх) для других у из Y{ дает Ре 1==3(1— е)е2+е3.
Соотношения (5.2.5) и (5.2.7) по виду довольно безобидные.
Однако, если алфавит на выходе канала состоит из J букв, то в этих суммах оказываются JN слагаемых. Для умеренных длин блоков, таких, как N = 50, вычисления сумм выходят далеко за возможности современных вычислительных машин. Даже если такие вычисления могли бы быть выполнены, они дали бы лишь небольшое проникновение в задачу выбора подходящей длины блока для кода или подходящего множества кодовых слов. Развиваемый здесь подход направлен скорее не на то, чтобы вычислить Ре, а чтобы найти простые верхние границы для достижимой вероятности ошибки. Идя по этому пути, мы не только докажем теорему кодирования, но также получим значительное понимание задачи выбора подходящих параметров кодирования. Начнем с рассмотрения вероятности ошибки для множества из двух кодовых слов и затем обобщим результат на произвольно большое множество кодовых слов.
5.3. ВЕРОЯТНОСТЬ ОШИБКИ ДЛЯ ДВУХ кодовых СЛОВ
Пусть хх и х2 — два кодовых слова длины N и предположим, что используется декодирование по максимуму правдоподобия, т. е. декодируется сообщение 1, если PN (у | хг) > PN (у | х2); в противном случае декодируется сообщение 2. Согласно (5.2.6) вероятность ошибки при посылке сообщения 1 равна
т
Канал(ДСК)
1/Z
Рис. 5.2.1. Код и правило декодирования для N=3, М—2.
138
Ре, 1= 2 Pn(У | Xi).
y6Y?
При любом у ? Y{ можно оценить сверху PN (у | хх) следующим образом:
Рм(у\х1ХРы(у\х-1У-$Рм{у\х2У> s —любое, 0<s< 1. (5.3.1)
Граница (5.3.1) следует из того, что PN (у | х2) ^ PN (у | хх) при у ? Y\ и, следовательно, PN (у | x2)s ^ РЛг (у | xx)s. Граница (5.3.1) справедлива также при s ^ 1, но это здесь не будет использовано. Подставляя (5.3.1) в (5.2.6) и строя границу сверху с помощью суммирования по всем у, будем иметь
1 < 2 Pn (У I Хх)1-5 PN (у 1 x2)s, s—любое, 0<s<l. (5.3.2)
у
Оценивая Ре,ъ аналогичным образом, получаем
2 ^ 2 Pn (у | х2)1~г Pn (у | х1)г, г—любое, 0< г < 1. (5.3.3)
у
Если подставить 1—s вместо г в (5.3.3), то можно заметить, что мы получили одинаковые границы для Ре_ 2 и Ре х. Это не приводит к потере общности, так как s все еще остается произвольным, 0 -<
< s < 1:
Pe,m<2^(y|xi)1-sPw(y|x2)s, m = 1, 2; 0<s< Г. (5.3.4)
у
Как будет видно из дальнейшего, если соответствующим образом выбрать s, то граница (5.3.4) будет удивительно точной. Для канала без памяти (5.3.4) можно упростить и привести к виду:
Ре,т<22---2 П Р(уп\хип)1-'Р(Уп\х2,пУ. (5.3.5)
Hi У2 УN п— 1
Расписывая произведение, получаем
Pe.m<I1P(yi\xi,i)l-$P(yi\xitl)s'^P(ij2\x1:2y-sP(y2 |,i'2i2)sX .. .
Ух У г
•¦¦'xliP{yN\xl мУ~5Р(Ум\х2 N)s,
,JN
Pe,m< П 'hP(yn\xl,ny-sP(yn\x2Js, ГП = 1,2. (5.3.6)
n = 1 yn
Сумма по yn в (5.3.6) имеет фундаментальное значение для последующего изложения и ей будет дана дополнительная интерпретация
в следующем параграфе. Обозначим ее через
ёп (s) = 2 Р (Уп I *i,n)I-s Р (Уп I *2, Js- (5-3.7)
Уп
При этом (5.3.6) можно переписать в виде
Pe,m<Tlgn(s), m==l,2; 0<s<l. (5.3.8)
л= l
139
Функция gn (s) изображена для ряда каналов на рис. 5.3.1. Во всех случаях х1п обозначает вход канала О, а х2 п — вход канала 1. Для каналов, подобных тому, который представлен на рис. 5.3.1, б и в котором некоторые переходные вероятности равны нулю, gn (0)
/-?
/-?
/-ff
