Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Из рассмотрения ансамбля кодов, введенных после соотношения
(6.9.10), с конечным L, следует, что две кодовые последовательности, соответствующие двум заданным последовательностям источника, статистически независимы в первых L подблоках, исходящих из первого подблока, в котором они отличаются, но зависимы в остальных. Вероятность ошибки декодирования для этого ансамбля может быть ограничена сверху величиной, по существу, эквивалентной границе случайного кодирования для блоковых кодов (см. задачу 6.42). Однако интереснее здесь слегка модифицировать ансамбль и затем вывести гораздо меньшую верхнюю границу для вероятности ошибки. Для этого рассмотрим двоичный сверточный кодер, изменяющийся во времени; двоичная выходная последовательность кодера образуется по правилу [сравнить с (6.9.10)]:
s“)= 2 2&,i(«. W; K*'<av. (6.9.32)
l = n-L+1 /=1
В данном ансамбле каждый элемент gjt г (п, I) выбирается так, что он является статистически независимой от других величин двоичной случайной величиной, принимающей оба значения с одинаковыми вероятностями. В остальном ансамбль аналогичен прежнему; s суммируется со случайной двоичной последовательностью v, после чего сумма отображается во входные буквы канала. В обозначениях
299
рис. 6.8.3 это соответствует случайному перемешиванию связей между к регистрами сдвига и v сумматорами по модулю 2, порождающими двоичную выходную последовательность; перемешивание производится после поступления в кодер каждого из подблоков символов сообщения.
Лемма 6.9.4. В рассмотренном выше ансамбле кодов кодовая последовательность, соответствующая какой-либо данной информационной последовательности, представляет собой последовательность статистически независимых букв, выбираемых с вероятностями, равными Q (k), где Q (k) — относительная частота появления k-и входной буквы при отображении двоичной последовательности длины а во входную букву канала. Пусть далее кодовые последовательности х и х' соответствуют последовательности сообщений и и и'; тогда х и х' совпадают в некотором подблоке, если и и и' совпадают в этом подблоке и L — 1 предыдущих. Во всех остальных подблоках последовательности х и х' статистически независимы.
Доказательство этой леммы почти идентично доказательству леммы 6.9.1 и потому опускается.
Утверждение леммы в обозначениях рис. 6.8.3 означает, что х и х' совпадают в тех подблоках, которые соответствуют одним и тем же символам в регистре сдвига. В других случаях хих' независимы.
Пусть задан код из рассмотренного выше ансамбля. Обозначим через и переданную последовательность сообщения и через и' — декодированную методом последовательного декодирования последовательность сообщения. Как правило, ошибки декодирования, если они происходят, имеют тенденцию группироваться в пакеты. Точнее, пакетом ошибок декодирования называется последовательность одного и более подблоков, обладающих следующими свойствами: первый и последний подблоки последовательности содержат ошибки (т. е. и и и' отличаются в этих подблоках)', никакие L— 1 последовательных подблоков внутри этой последовательности не являются одновременно безошибочными', по L—1 подблоков с каждой стороны последовательности не содержат ошибки. Это определение однозначно определяет множество одного или более пакетов ошибок для любого и' Ф и.
Обозначим через Ре (b, с) вероятность (в ансамбле кодов, сообщений и шумов в канале) того, что с началом в Ь-м подблоке и концом в с-м подблоке имел место пакет ошибок. Обозначим через Ре<п вероятность ошибочного декодирования п-то подблока. Согласно нашему определению пакета любой подблок, ошибочно декодированный, должен входить в некоторый пакет ошибок декодирования, поэтому
Ре.п< 2 2Ре{Ь,с). (6.9.33)
6=1 с —п
Чтобы найти верхнюю границу Ре{Ь, с), рассмотрим сначала простейший случай, т. е. случай b = 1. Пусть и — переданная информационная последовательность и пусть Uc+l— i —первые с + L — 1 подблоков декодированной последовательности. Для того чтобы в промежутке от 1-го до с-го подблока появился пакет ошибок декодиро-
300
вания, должно быть и[ Ф иг, и'с Ф ис и иё + i = uc+i, 1 ^ i ^ L — 1. Так как каждый внутренний подблок может быть выбран не более
чем 2х способами, то последовательность z._____i, содержащая пакет
ошибок декодирования в промежутке от 1-го до с-го подблока, может быть выбрана менее чем 2Хс, способами.
Обозначим через Гь + L — 1 путь цен вдоль правиль-
ного пути в дереве полученных цен, и пусть
Г mln= min Гг-
0^l^LT + L — 1
Пусть далее является ценой узла где вы-
брано таким образом, что он соответствует пакету ошибок декодирования в промежутке от 1-го до с-го подблока. Совершенно ясно, что проведение в узле Uc-\-l— 1 F-проверки необходимо для того, чтобы Uc+l_i было декодировано. Вместе с тем согласно лемме 6.9.2 F-проверка u^l-i может наступить только тогда, когда rc'+?_i^s ^ Гт1п — А. Поэтому
