Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
288
Если действие шумов сильнее обычного, поведение алгоритма существенно сложнее, что иллюстрируется схемой рис. 6.9.5. Грубо говоря, ситуация, представленная на рисунке, вызвана тем, что декодер пытается найти путь в дереве принятых цен, который находится выше текущего порога. Как мы- позднее увидим, если такого пути не существует, декодер вынужден двигаться назад к узлу, где порог согласовывался бы с его текущей ценой. В этом узле порог понижается (по правилу 4) и декодер снова движется вперед, пытаясь найти узел, остающийся выше этого пониженного порога. Ограничение Гг_] <
< Т + А в правиле 1 введено с целью предохранить порог от нового повышения в одном из тех узлов, которые были предварительно проверены. В самом деле, если бы это ограничение не было введено, декодер быстро вошел бы в цикл, проверяя снова и снова один и тот же узел при одном и том же пороге.
Прежде чем сформулировать эту идею точнее, необходимо ввести дополнительные определения. Назовем F-проверкой проверку по правилам 1, 2 или 4 (т. е. по тем правилам, для которых последующее движение совершается вперед). Предшественниками узла ut являются узлы, связывающие ut с началом и0, т. е. узлы, соответствующие префиксам информационной последовательности и*. Путь цен Г0.........Гг,
относящийся к узлу ии образован ценами предшественников узла ui и ценой самого иг. Путь порогов Т0, Тг, относящийся к проверке Uj, образован окончательными порогами при последних проверках гипотез относительно их предшественников иг (Тг — это окончательный порог для текущей проверки). Потомками узла иг называются узлы, для которых иi является предшествующим узлом, т. е. узлы, расположенные направо от иг. Непосредственными потомками иг называются 2х потомков, отстоящих от и г на одно ребро. Путь из узла u i к потомку иг лежит выше порога Т, если цены в узлах пути удовлетворяют неравенству Г;- ^ Т при t ^ j ^ I.
Следующая теорема, которая доказывается в приложении 6А, описывает работу алгоритма. С точки зрения последующего анализа наиболее важными пунктами теоремы являются пункты (б) и (б); эти пункты лучше всего понять, связав чтение теоремы с последующим обсуждением.
Теорема 6.9.1.
а) Путь порогов Т0, ..., Ti и путь цен Г0, ..., Гь связанные с проверкой узла ии удовлетворяют следующим соотношениям при 0< i < I — 1:
б) Для каждого узла, относительно которого когда-либо проводилась ^-проверка, окончательный порог Т при первой ^-проверке связан с ценой Г этого узла соотношением
ri(
Ti+i>Tt,
Ti+i^ Т1~\-+ Тг+1>Тг + А^Г;+1>Гг.
(6.9.5)
(6.9.6)
(6.9.7)
(6.9.8)
Т<Г<Т + Д.
(6.9.9)
1 ^ Зак. 210
289
Окончательный порог при каждой последующей F-проверке этого узла лежит на А ниже, чем при предшествующей F-проверке этого узла.
в) Пусть относительно узла и проведена F-проверка с окончательным значением порога, равным Т. Тогда, прежде чем узел и сможет быть проверен вновь, должны быть проведены F-проверки с окончательным порогом Т в каждом из потомков узла и, для которых путь, ведущий из и, лежит выше Т. Кроме того, в течение времени между данной проверкой узла и и его первой перепроверкой порог не может быть сделан ниже Т.
Рис. 6.9.6. Траектория порогов, связанная с проверкой последовательности и12.
Обсуждение. Пусть заданы бесконечные*) передаваемая и принятая последовательности символов; назовем правильным путем последовательность цен Г0, rit ... в узлах, соответствующих переданной информационной последовательности. Предположим, что этот правильный путь флуктуирует с положительным смещением, а каждый другой путь в дереве принятых цен флуктуирует с отрицательным смещением. Обозначим через Тг окончательный порог при первой F-проверке узла игде иг — произвольный узел правильного пути. Согласно пункту б) теоремы Г, ^ Г; < ТА. Назовем узел и г правильного пути прорвавшимся, если Г; ^ Г г для всех i > I. Из пункта в) теоремы вытекает, что если узел и? прорвался, то он не будет перепроверяться до тех пор, пока не будет проверен каждый последующий узел правильного пути, т. е., иными словами, вообще не будет перепроверяться. Так как все неправильные пути флуктуируют вниз, то декодер в результате движется вперед от одного прорвавшегося узла к следующему; поэтому использование алгоритма приведет в конце концов к декодированию каждого символа правильного пути. Отметим, однако, что декодер никогда не может быть вполне уверен, что он «декоди-
*> Если последовательности имеют конечную длину, но декодирование заканчивается, когда относительно конечного символа последовательности произведена F-проверка, то можно использовать те же рассуждения.
290
ровал» узел, так как всегда не исключена возможность, что последующие узлы упадут ниже данного порога. В дальнейшем мы подробнее обсудим этот момент.
На рис. 6.9.6 представлена типичная последовательность узлов вдоль правильного пути. Предположим, что Гг^Г12 для всех lz> 12; тогда прорвавшимися узлами будут u0, ub u7, u9, u10, и и12.
