Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Движение вбок. Пусть Т0...... Ti — путь порогов при проверках узла щ
и предположим, что из щ производится движение вбок или назад. Тогда к щ должно быть применимо правило 3 или бив обоих случаях согласно этим правилам Тi < Г;_!- Мы видим, что движения вбок или назад могут быть произведены лишь при / > 0. В силу предположений индукции к щ применимо (6А.З) и, следовательно, (6А.4). Из (6А.4) вытекает, что Ti > Ti-i + Д => <= Ti > Гг-хпри! = I — 1. Поскольку, как было уже показано, Ti < Гг_1, то должно выполняться неравенство Ti < Ti~t + Д. Так как согласно (6А.2) Ti > Ti-i и так как Т может изменяться, лишь принимая приращения Д, то выводим, что при L и В движениях из иг имеет место равенство
Гг = Тг-!.
(6 А. 5)
325
При движении вбок из узла и; в узел и/ путь порогов Т0, • ••, 7^-1 не изменяется. Первоначальный порог при проверках в ui равен и согласно (6А.5| Ti = Ti-i. Пусть Ti — конечный порог для проверок в и/. Так как в узле и/ должны применяться правила 1, 2 или 3, то порог не может понижаться и потому Ti > Ti-lt что доказывает (6А.2). Если Ti > + Д, то порог в и/ дол-
жен быть повышен, применяется правило 1 и Г;_х < Ti-1 + Д, что доказывает (6А.З).
Движение назад. Вновь допустим, что Т0, ..., Ti является путем порогов при проверках и;, и предположим, что было совершено движение назад к u;_i. Согласно (6А.5) первоначальный порог при проверке u;_x равен Г/ =
Так как из и; было совершено движение назад, то в иг—i применяется либо правило 5, либо правило 4. Если применяется правило 5 ,то конечный порог Ti—i при новых проверках u;_i равен первоначальному порогу, который, как указано выше, равен Ti-t. Поэтому, так как для uj выполняются соотношения (6А.2) и (6А.З), то они также выполняются и для новой проверки u;_!. Если применяется правило 4, то согласно рис. 6А.1 (учитывая, что T;_i—первоначальный порог), Г;_2 < Ti-i- Согласно (6А.1) Ti-2 < Г[_2 и в силу того, что пороги могут изменяться лишь на приращения Д, то < ^/-i — Д- Окончательный порог T[—i при новой проверке равен — Д, так что Ti-% ^ Ti—i,
что доказывает (6А.2) для и;_х. Наконец, если Ti—\ > Ti-2 + Д, то >
> 7'г_2+Д, и из справедливости соотношения (6А.З) для щ следует его справедливость для u/_i, что завершает доказательство пункта (а).
Следующее следствие из пункта (а) теоремы будет необходимо при доказательстве пунктов (б) и (в).
Следствие. Если в узле и проведена F-проверка с окончательным порогом Т, то Т является начальным порогом при первых последующих проверках каждого из непосредственных потомков узла и и при первой последующей проверке узла и.
Доказательство. Для проверки первого непосредственного потомка узла и это утверждение очевидно. Первая проверка каждого из других непосредственных потомков должна производиться при движении вбок из ранее просмотренных непосредственных потомков узла и. Но согласно (6А.5) такое движение вбок может выполняться лишь тогда, когда окончательный порог, установленный до выполнения движения, равен Т. Аналогично, первое движение назад к и совершается из последнего среди непосредственных потомков и порог вновь равен Т. |
Доказательство теоремы 6.9.1 (пункт б). Мы хотим показать, что окончательный порог Т при первой F-проверке каждого узла связан с ценой узла Г соотношением
Т < Г < Т + Д, (6А.6)
а также что каждая из последующих F-проверок этого узла проводится с окончательным порогом на Д ниже, чем предыдущее значение.
Воспользуемся индукцией вдоль пути узлов, сначала доказав справедливость теоремы для начального узла, а затем показав, что если теорема верна для какого-либо данного узла, то она справедлива для любого из непосредственных потомков этого узла. Начальные проверки и0 являются F-проверками и удовлетворяют (6А.6) в силу начальных условий, накладываемых на декодер. Согласно следствию из пункта (а) первоначальный порог для каждой последующей проверки начального узла равен окончательному порогу при предыдущей проверке. Так какГ_1= —оо, то к каждой такой проверке применимо правило 4; причем эта /•'-проверка производится с окончательным порогом, сниженным на Д. Теперь предположим, что утверждение пункта (б) теоремы справедливо для узла U[_! с ценой, равной Г/_2, и пусть и/ — его непосредственный потомок с ценой Г/. По предположению окончательный порог Т при первой /•'-проверке узла ui-i удовлетворяет неравенствам:
326
7’<Г/_1<Г + Д.
(6А.7)
Согласно следствию, Т есть первоначальный порог при первой проверке и;. Теперь рассмотрим отдельно случаи Г; > Т и Г; < Т.
Если Г; > Т, первая проверка и; удовлетворяет условиям правила 1, и окончательный порог Т установлен таким образом, что он удовлетворяет условию (6А.6) для U;. Согласно следствию первоначальный порог при следующем возвращении к щ равен Г;. Если Ti > Т + Д (т. е. если порог повышен при первоначальной проверке uj), то согласно (6А.7) Ti > Гг_1, применяется правило 4 и при возвращении совершается F-проверка с окончательным порогом Т\ — Д. Рассуждая таким же образом, находим, что окончательный порог уменьшается на Д при каждом последующем возвращении к и; до тех пор, пока окончательный порог не будет равен Т. При следующем возвращении к и; первоначальный порог меньше или равен Г;_1, применяется правило 5 и совершается движение вбок или назад. Прежде чем можно будет совершить следующую F-проверку иг, по предположению должна быть совершена другая F-проверка при окончательном пороге Т — Д. Поэтому первоначальный и окончательный пороги при следующих F-проверках и; также равны Т — Д. Аналогично, последовательные F-проверки и; чередуются с F-проверками иг-i, каждый раз с величиной порога на Д ниже,чем при предыдущей проверке.
