Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Пра Условия в узле Действия, которые следует
вило выполнить
Предыдущее Сравнение и Г; с перво Окончательный порог Движение
движение начальным порогом
1 F или L Г,_1<Г + Д. Vi>T Повышается* F+
2 F или L Г;_1>7’+Д, Г i>T Не изменяется F+
3 F или L любое Гг_1, Гi<T Не изменяется +
L или В +
4 В Г;_1<7’, любое Г; Понижается на Д F+
5 В любое Г; Не изменяется L или В +
* Прибавить к порогу /Д где / выбрано таким образом, что Г; — Д<Г7’ + /Л Г,.
+ Движение вперед (Forward) в первый из 2^ узлов, исходящих из текущего узла (предполагается предварительное упорядочение 2^ узлов).
+ Движение вбок (Lateral) в следующий узел, отличающийся от текущего узла лишь в последнем ребре (предполагается то же предварительное упорядочение, что и выше); если текущий узел является последним среди этих 2^ узлов, то совершается движение назад (Backward).
Рис. 6.9.4. Правила движения декодера.
сдвига вправо. Новое значение цены вычисляется из старого, вычитанием последнего слагаемого из суммы по л в (6.9.2). Поэтому для каждого возможного движения изменение цены при переходе от старого узла к новому зависит лишь от последних v гипотетических входных символов канала.
Алгоритм, использующий движение от одного узла к другому, является модификацией алгоритма Фано и представлен на рис. 6.9.4. В формулировку правила входит цеиа Гг текущего узла, который проверяется в данный момент, цена Г;_1 узла, находящегося на одно ребро слева от текущего узла, и порог Т. На порог Т наложено ограничение, состоящее в том, что при увеличении он изменяется на некоторое фиксированное число А, величина которого определяется алгоритмом.
В начале декодирования устанавливается следующие начальные условия: проверяется исходный узел и0, что соответствует тому, что регистр сдвига содержит лишь нули, причем ни один информационный
287
иг Окончатель Движение vi Окончатель Движение
ный порог ный порог
_ 0 F 010 ---3 L
0 0 L 011 ---3 F
1 0 В оно ---3 L
--- --- 1,5 F 0111 ---3 В
0 -1.5 F 011 ---3 В
00 ---1,5 L 01 ---3 В
01 --- 1,5 В 0 ---3 L
0 ---1,5 L 1 ---3 F
1 ---1,5 В 10 ---3 L
--- ---3 F И ---3 F
0 ---3 F 110 ---1,5 F
00 ---3 L 1100 0 F
01 ---3 F
Рис. 6.9.5. Запись поиска декодера, изображенного на рис. 6.9.3 (Л = 1,5).
символ еще не проверялся. Значение Г0 выбирается равным 0 и по определению Г_1 — — оо. Начальное значение порога не определено, но условимся считать, что декодер при начальной проверке следует правилу 1 с конечным порогом, равным 0.
Легко видеть, что движение вперед может быть предпринято в любой из 2^ узлов, отстоящих на одно ребро вправо от текущего. Предполагается, что узлы предварительно упорядочены и движение вперед всегда совершается в первый по порядку узел, а движение вбок — в следующий по порядку после текущего. Эта упорядоченность несущественна для исследования, но здесь мы будем предполагать лексикографическую упорядоченность гипотетических информационных подпоследовательностей длины X, считая 00...0 первой, 0...01 следующей и 11... 1 последней последовательностью*).
В дальнейшем мы увидим, что правило 1 алгоритма декодирования является правилом, обычно используемым при проверке декодером узлов, соответствующих действительно переданной последовательности, когда действие шума не слишком велико. В этих условиях порог будет подниматься таким образом, чтобы разность между ценой узла и величиной порога не была бы больше А. После движения вперед цена этого прежнего узла будет появляться как Гг_г, то обстоятельство, что Г/_1 < Т + А, вновь обеспечивает нам возможность применения правила 1 и нового повышения порога, если только новая цена Гг выше,
чем*старая^цена Г/__i. Если первоначально проверялся ложный узел,
то скорее всего цена узла будет меньше порога и декодер будет совершать движения вбок до тех пор, пока не перейдет к проверке правильного узла, а порог будет повышен вновь.
*> В первоначальном алгоритме Фано (1963) упорядочение узлов производилось в порядке убывания величины Г. Вообще говоря, это уменьшает число узлов, которое должно быть проверено, но увеличивает количество вычислений, необходимых на проверку, из-за дополнительных вычислений, затрачиваемых на упорядочение узлов.
