Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
-ехр
N(R-C)1
(5.8.59)
где А — конечная положительная постоянная, зависящая от канала и не зависящая от N и R.
Обсуждение. Как видно из (5.8.59), при любой фиксированной скорости R> С значение Р е должно стремиться к 1 при неограниченном возрастании N. Можно также заметить, что если выбрать R = = С + б/]/N при некотором фиксированном значении б > ]/"8А +2, то Р е будет строго больше чем 0 при всех N.
Доказательство. Пусть Р (/1 k), 0 ^ J—1, 0 ^ k ^ К — 1, — переходные вероятности канала, а К и J — объемы входного и выходного алфавитов соответственно. Пусть Q (0), ..., Q (К— 1) будут вероятностями на входе, на которых достигается пропускная способность, и пусть и (/) = y,Q (k)P (j \k), 0 ^ j ^ J — 1, — соответст-
k
вующие вероятности на выходе. Согласно теореме 4.5.1 имеем
I(k\Y)л= S P(j\fyln —1. (5.8.60) v ' 1=0 со (/)
*) Исторически, этот результат принадлежащий Вольфовицу, был назван сильным обращением теоремы кодирования, а результат теоремы 4.3.1, принадлежащий Фано,— слабым обращением теоремы кодирования. Так как результат, полученный Вольфовицем, не следует из теоремы 4.3.4, которую мы назвали обращением теоремы кодирования, то мы будем называть результаты, изложенные здесь, теоремой обра щения по Вольфовицу или обращением теоремы кодирования для блокового кодирования.
188
N
Пусть PN (у I X) = п Р (уп I хп),
/1 = 1
где у = (г/1, , г/дО и х = (*г,..., xN), и пусть
N
Юд,(у)= П со (уп).
П= 1
Определим
/(х;у) = 1п^1^ = 2 7(^;«/„), (5.8.61)
П=1
где
/ foil «/„) •¦= 1п [Р (уп I Хп)/(й [уп)\.
Рассмотрим теперь (N, У?)-код с кодовыми словами х1( ..., Хуи и областями декодирования Ух, ..., Ум- Вероятность правильного декодирования для этого кода равна
J м
Рс = — 2 2 Pn(y|xj. (5.8.62)
М т=1у6Ут
Пусть б >> 0 будет произвольным числом; определим для 1 ^ т ^ М Вт = [у:/ (хт; у) > N (С + 8)]. (5.8.63)
Обозначая через дополнение Вт, представляем (5.8.62) в виде
I М j m
Рс = -гг^ 2 /My|xj+—2 2 f^(y|xm).
М "1=1 УбУт n Brn ^ m=l УбУ* П Д'
(5.8.64)
Для у ? имеем /V (у | xm)/<oiV (у) < ехр [Л/ (С + е)] и поэтому вторая сумма в (5.8.64) ограничена следующим образом: j м
— 2 2 Pn (у | xj <
™ т = 1 у6^ Л Вс J т т
М
<тг 2 2 <o„(y)exp[tf(C + e)]<
М т=1 У&т Г) Вс
ехр [N (С + г)]
т М
2 2 %(У)< exptJVjC+e)]^ (5_g_65)
М ni=l уЁУт М
где использовано то, что области декодирования не пересекаются и что со^ (у) является распределением вероятности.
Первую сумму в (5.8.64) можно оценить сверху с помощью суммирования при любом заданном пг по у ? 5т, анепоу?Ут f] Вт. Получим
2 Pn (у\ хт) = Р[1 (хт; у) > jV (С + е) | хт], (5.8.66)
189
где при заданном хт величина / (хт; у) понимается как случайная величина, принимающая значение / (хт; у) с вероятностью PN (у) хт). Согласно (5.8.61) эта случайная величина является суммой независимых случайных величин 2/ (хт п; уп) и в соответствии с (5.8.60) среднее значение этой суммы меньше или равно NC. Отсюда согласно неравенству Чебышева имеем
N
2 Pn (У | хт)
у
^ D [/ (Хт,п> Уп) I хт,п] п= 1____________________________
N- е2
(5.8.67)
где
j-1
^ IV {Хщ ,7г > Уп) | Хт п] 2 P(j\Xm,n) 1=0
J—1
S P(i\xm,n)ln
1=0
Р (i | хт,п)
ОЭ U)
In ^ 1 хт,п)
«(/)
2
(5.8.68)
Так как хт п является одной из букв на входе 0, ..., К—1, то эта дисперсия всегда ограничена сверху конечным числом А, равным
А = max D [I (k; уп)) k],
о < 1
Отсюда при всех т имеем
h Pn(y|xj<-^-. у евт А'е2