Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
На рис. 6.9.6 также изображен путь порогов до прорыва в ul2. Эти пороги полностью определяются пунктом (а) теоремы 6.9.1 через путь цен и окончательный порог в последовательности. Чтобы убедиться в этом, начнем с рассмотрения окончательного порога (Т12 на рис. 6.9.6) и продвинемся по горизонтали влево. Согласно (6.9.8) пороги понижаются только, если необходимо избежать пересечения с траекторией пути; согласно (6.9.7) понижение не больше чем это необходимо для того, чтобы избежать пересечения.
Сложность последовательного декодирования
Число проверок, которое последовательный декодер должен произвести при декодировании последовательности принятых символов, является случайной величиной, зависящей от принятой последовательности, последовательности на выходе источника и сверточного кодера. Если принятые символы поступают в декодер с фиксированной по времени скоростью, и проверки проводятся с фиксированной скоростью, на входе декодера образуется очередь из принятых символов. Ясно, что изучение поведения этой очереди имеет первостепенное значение при рассмотрении работы последовательного декодера.
Чтобы лучше понять поведение этой очереди, удобно представить себе дерево принятых цен (соответствующее данной последовательности источника, данному кодеру и данной принятой последовательности) состоящим из правильного пути, соответствующего передаваемой последовательности источника, и множества деревьев неправильных путей, причем из каждого узла правильного пути исходят различные деревья. Обозначим через Wn число F-проверок, проведенных в п-м узле правильного пути и во всех узлах дерева неправильных путей, исходящих из «-го узла. Сумма по п величин Wn равна общему числу F-проверок, которые необходимо провести для декодирования последовательности; Wn можно интерпретировать как число F-проверок, которые необходимо провести для декодирования /г-го подблока. Если п-й узел правильного дерева — прорвавшийся, то все F-npo-верки, входящие в W0, ..., Wn— ь будут выполнены раньше любой F-проверки, входящей в Wn, Wn-\, ¦¦¦
В дальнейшем нас будет интересовать исследование распределения Wn. Это позволит нам лучше понять статистическое поведение очереди; если вероятность того, что Wn примет очень большое значение не мала, то будет существовать тенденция к созданию больших очередей. Оправданием для рассмотрения только F-проверок и пренебрежения движениями вбок и назад могут служить следующие соображения. Каждый узел имеет 2х непосредственных потомков и на каждую F-проверку данного узла из каждого из этих потомков приходится 10* 291
лишь одно движение вбок или назад. Поэтому при любой фиксированной длине I дерева общее число боковых и обратных движений на длине I не более чем в раз превышает число движений вперед на длине I — 1. Суммируя по I, получаем, что общее число проверок за некоторое фиксированное время не более чем в 2х + 1 раз превышает число F-проверок.
В свете доказательства теоремы кодирования не должно показаться неожиданным, что поведение случайной величины Wn легче исследовать для ансамбля кодов, чем для некоторого частного кода. В каждом из кодов ансамбля, который будет рассматриваться, кодовые последовательности получаются следующим образом: информационная последовательность подается в двоичный несистематический сверточный кодер, выходная последовательность этого кодера суммируется с произвольной двоичной последовательностью, а сумма затем преобразуется во входные символы канала. Точнее, двоичная последовательность сообщения разбивается на подблоки по к символов в каждом,
up, ..., u”>...... u^), .... Каждым к входным символам
сверточного кодера соответствуют av выходных символов (для соответствующим образом выбранных а и v), образующих двоичную последовательность sp, ..., s<av>, s<‘>, .... Как и в соотношении (6.8.8) (и на рис. 6.8.3), выходные символы образуются из входных по правилу
si° = 21 2 gj, i (0 г- 1 <г < av- (б-9-10)
1 = 0/=1
где g}i t (I) — О при I < 0.
Для простоты исследования будем считать L (длину кодового ограничения в блоке) бесконечной. Позднее, при изучении вероятности ошибки мы, естественно, будем рассматривать кодовые ограничения конечной длины. Выходная последовательность сверточного кодера s суммируется далее по модулю 2 с произвольной двоичной последовательностью v, при этом образуется последовательность
s(,° ©и*,1*....s<av>©u<av>, S(D©00),....
Эта последовательность затем разбивается на подблоки по а символов в каждом, и каждая двоичная последовательность из а символов отображается во входную букву канала с помощью отображения, аналогичного представленному на рис. 6.2.1; при этом k-я буква входного алфавита канала используется с относительной частотой Q (k), определенной как ив (6.2.6). Так же как и в (6.2.6), используемое значение а определяется по значениям Q (k). Можно заметить, что после выполнения этих этапов кодирования на каждые к на двоичных символов источника будет приходиться v символов канала, поэтому скорость кода равна R = (к/v) In 2 нат на символ канала.
