Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
кодов делает возможным такой обмен.________
Теперь найдем верхнюю границу W$ при р ^ 1. Из (6.9.12) имеем
Применяя в правой части (6.9.24) неравенство Минковского (см. задачу 4.15 (е)), получаем
Так как w [т (/), г] принимает лишь значения 0 и 1, то w [т (/), г']р = w 1т (/), г] и из (6.9.14) и (6.9.16) имеем
Оценивая сверху (/ + 1)!/р величиной I + 1 и суммируя эти ряды таким же образом, как и ряды в (6.9.17), убеждаемся, что суммы сходятся, если
К 1№|П1/Р вновь применима та же самая граница. Если смещение В равно ?0(1,Q),to W„, как нетрудно убедиться, конечно при R, меньших, чем Е0 (1, Q)/p. Границу (6.9.28) можно использовать для оценки функции распределения Wn. Применяя обобщенное неравенство Чебышева, имеем
Наши результаты можно сформулировать в виде следующей теоремы.
Теорема 6.9.2. При применении последовательного декодирования в дискретном канале без памяти среднее число F-проверок, приходя-
297
(6.9.24)
1 = 0 тО) / = 1
w [т (I), г]р <;(/+!) ехр
0-2) Л
vl Eq (1 ’ Q) + В
1 = 0 m(l) l*= 1
2
(f—2) А
2р
R ?0 (1. Q)+ Д
(6.9.27) )_2 (6.9.28)
и
ехр [А/(2р)]
1 — ехр —v
?о(1. Q) + 5 | ^
1 —ехр [ — Л/(2р)]
2р
(6.9.29)
щихся на декодированный подблок, удовлетворяет неравенству
Wn < 4 {1 — ехр [ — VE0 (1, Q) + vtf ]}-а (6.9.30)
при R <?0(1, Q).
Здесь v означает число символов канала, приходящихся на подблок, R = (A,/v)ln 2 является скоростью кода в натах на символ канала, Ео (1, Q) определяется соотношением (6.9.15). Смещение В выбирается равным Ео (1, Q), а пороговый интервал — равным 2 In 2. Усреднение проводится по ансамблю кодов бесконечной длины, определенных на стр. 292. Кроме того, при любом 1, для которого R<.E0 (1, Q)/p,
величина Wn также конечна.
Севэдж (1966) получил более сильные оценки для Wn с помощью рассмотрения большего ансамбля кодов. Он рассмотрел ансамбль случайно выбираемых древовидных кодов, в котором кодовые последовательности имеют такую же древовидную структуру, как и на рис. 6.9.2, но где каждый символ в дереве выбирается независимо с вероятностями Q(k), 0 ^ k ^ К— 1. Севэдж показал, что в этом ансамбле при целых р величина №g конечна, если R < Е0 (р, Q)/p. Отсюда не обязательно следует, что для этих скоростей существуют сверточные коды, для которых Wg конечно. Однако довольно правдоподобно, что
при всех положительных р и всех R <. Е0 (р, Q)/p величина Wn конечна, где усреднение производится по ансамблю сверточных кодов с бесконечной длиной кодового ограничения и скоростью R. Это предположение было доказано Фэлконером (1966) для случая 0 < р ^ 1.
Вопрос о том, что произойдет с Wn при R > Е0 (р, Q)/p, детально исследован Джекобсом и Берлекэмпом (1967). Их результаты применимы к произвольным древовидным кодам (т. е. кодам, структура которых описывается рис. 6.9.2) и к классу последовательных алгоритмов, включающему описанный здесь алгоритм Фано. Пусть
Ео (р) =шах ?0(р, Q) и пусть Е0 (р) выпуклая ^ оболочка Е0 (р), т. е.
Q
Ео (р)—минимальная выпуклая ^ функция, равная или большая чем Ео (р). Она образуется заменой всех невыпуклых участков Е0 (р) прямолинейными сегментами. Джекобе и Берлекэмп показали, что в наших обозначениях для любого древовидного кода со скоростью R >> Ё о (р)/р
/ Г N—1 \ р
lim -77-2*4= °°- (б-9-31)
N-ос \ n „-е0 /
Бесконечность моментов Wn высокого порядка указывает на то, что длинные очереди являются трудной проблемой в последовательном декодировании. Джекобе и Берлекэмп показали, что вероятность того, что либо очередь при декодировании символа превысит данную длину i, либо будет сделана ошибка, не может убывать с ростом i быстрее, чем i~f>, для скорости кода, равной Ё0 (р)/р.
298
Вероятность ошибки при последовательном декодировании
Чтобы оценить вероятность ошибки при последовательном декодировании, следует рассмотреть коды с конечной длиной кодового ограничения. Если для кодов с бесконечной длиной кодового ограничения Wn конечно при любом п, то из (6.9.18) следует, что вероятность проверки узла на глубине I дерева неправильных путей стремится к нулю с возрастанием I и вероятность ошибки, очевидно, равна нулю.
Предположим, что длина ограничения кодера равна L подблокам. Предположим также, что в кодер вместо бесконечной последовательности подблоков поступает от источника конечное число подблоков Lt, где Ьт, как правило, гораздо больше L. После того как в кодер поступит Lt подблоков сообщения, в него подается известная последовательность L — 1 подблоков, состоящих из нулей. В такой ситуации каждый узел дерева принятых цен, лежащий на глубине не больше Lt — 1, имеет 2% непосредственных потомков, а каждый узел на глубине, не меньшей Lt, только одного непосредственного потомка. Декодирование проводится согласно правилам, указанным на рис. 6.9.4, за исключением того, что декодер распознает, что узел порядка Lt или больше имеет лишь одного непосредственного потомка и поэтому правила 3 и 5 всегда приводят к движению назад для узлов порядка, большего чем Lt. Декодирование заканчивается при первой проверке в узле порядка Lt + L — 1 и гипотетическая последовательность источника при этой проверке выбирается в качестве декодированной последовательности. При конечных L и Lt декодирование в конце концов должно закончиться.
