Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Обозначим теперь через хг = (л:!1’, ..., x\v), ..., , •••, х\у))
первые vl символов кодовой последовательности, и через уг == = (у\1), ..., y\v)) первые v/ символов принятой последовательности. Определим функцию Г(хг; уг) следующим образом:
1 v Г Р (u{i) \ хи))
<6'92)
п= 1 1= 1 L \t,n > J
В этом выражении В есть произвольное число, определяющее смещение, значение которого будет выбрано позднее, и со (/) есть вероятность появления /-й буквы выходного алфавита канала,
к-1
«(/')- hQ(k)P(j\k), (6.9.3)
k = 0
где Q (k) — относительная частота k-й буквы при отображении двоичных символов во входные символы канала [см. (6.2.6)]. Назовем Г (хг; уг) ценой гипотезы хг и будем использовать ее как меру согласования хг с принятой последовательностью уг. Это разумная мера, так как при фиксированном уг величина Г является возрастающей функцией вероятности Рг (уг|хг). При таком подходе довольно трудно понять назначение члена со(//^) в соотношении (6.9.2); грубо говоря, он вводится для того, чтобы уменьшить зависимость источника от безусловных вероятностей символов выходной последовательности.
В случае двоичного симметричного канала с переходной вероятностью е последние два блока описанного выше кодера могут быть отброшены и соотношение (6.8.8) полностью описывает кодирование. Тогда является постоянной и Г (хг; уг) упрощается:
Г (хг; уг)== — d(x,; y^ln^—^- + v/{ln [2(1 —е)]—5},
В
где d (хг; уг) — расстояние Хэмминга между хг и у;.
*) При таком отображении теряется некоторая информация относительно закодированной двоичной последовательности, но если код выбран соответствующим образом, то не теряется никакой информации относительно источника. Теорема кодирования § 6.2 убеждает нас в справедливости этого утверждения для блоковых кодов; ниже оно будет аналогичным образом доказано и для сверточных кодов.
285
Назначение декодера, выраженное в терминах цены Г, состоит в проверке гипотез так чтобы величина Г (х,; у,) возрастала с ростом /. Когда Г начинает убывать с ростом /, по всей видимости, декодер попал на ложный путь и необходимо провести соответствующий поиск. Более наглядно эта идея иллюстрируется на рис. 6.9.3, на котором графическое представление величины Г (хг; уг) отражает древовидную структуру возможных значений х*. Этот рисунок, который называется деревом принятых цен, соответствует кодеру рис. 6.9.1 и принятой последовательности 010 101
001 000.
На рис. 6.9.3 узлы отмечены в соответствии с информационными последовательностями, ведущими в них. Иначе говоря, каждый узел на глубине / в дереве соответствует различным информационным последовательностям и г из I% двоичных символов. Например, узел в верхнем правом углу рисунка соответствует информацион-
Рис. 6.9.3. Дерево принятых цен; ДСК; е=0,15; кодер изображен на рис. 6.9.1; у4= 010 101 001 000; В = = 1/3 1п2.
ной последовательности и4=1100,
при передаваемой последовательности х4 = 111 101 001 000.
В принципе декодер может построить дерево принятых цен, аналогичное изображенному рис. 6.9.3, для произвольного сверточного кода и произвольной принятой последовательности. Однако на практике такое дерево декодер построить не может, так как число узлов в дереве растет экспоненциально с ростом /.То, что возможно — это включение в состав декодера точного аналога сверточного декодера.
Для любой заданной гипотетической последовательности информационных символов U; декодер может, прогнав иг через аналог кодера, найти соответствующую последовательность хг и вычислить Г (хг; уг), что является ценой узла, соответствующего иг.
Алгоритм декодирования, который будет описан, есть совокупность правил, определяющих движение от одного узла к другому. Мы будем допускать лишь три вида движений: вперед, вбок и назад. При движении вперед декодер продвигается в дереве полученных цен на одно ребро вправо от ранее проверенного узла. Технически это соответствует сдвигу вправо регистра сдвига в аналоге кодера и поступлению в него слева % новых гипотетических информационных символов. Так как новая информационная последовательность u;+i отличается от старой лишь наличием % символов, прибавленных к ней,, новая цена Г (х;+]; y^+i) может быть найдена из Г (хг; уг) добавлением еще одного члена в сумме (6.9.2):
/ = 1
р(у\1)
1+1
>№i)
-в
(6.9.4)
286
Символы, входящие в эту сумму, есть просто v входных символов канала, порождаемых аналогом кодера. Движение вбок определяется как движение из одного узла в другой, отличающийся лишь в последнем ребре дерева. Технически это соответствует изменению крайне левых X символов в регистре сдвига аналога .кодера. Как и ранее, изменение в цене при переходе от одного узла к другому определяется изменением последних v входных символов канала. Движение назад определяется как движение на одно ребро влево в дереве принятых цен. Технически это соответствует сдвигу регистра сдвига кодера влево и восстановлению последних X символов, вышедших из регистра
