ПРИЛОЖЕНИЕ 6А

Прежде чем приступить к доказательству теоремы 6.9.1, полезно переписать правила алгоритма декодирования так, как представлено на рис. Заметим, что условия, указанные на рис. содержат все условия, представленные на рис. 6.9.4, а также некоторые дополнительные условия. Поэтому, если применяется некоторое правило из описания алгоритма на рис. 6А. 1, то оно должно совпадать с правилом, указанным на рис. 6.9.4. Чтобы показать, что некоторое правило применимо к каждой проверке на рис. 6А.1, можно воспользоваться индукцией по последовательным проверкам. Рассмотрим каждое из правил на рис. предположим, что данное правило применимо, и рассмотрим условия, которые возникают при следующей проверке. Например, если применяется правило 1, то для следующих проверок и это является новым условием, добавляемым к правилам 1, 2 и 3.

Рис. 6А.1. Множество правил, эквивалентное множеству правил, указанному на рис. 6.9 4.

Доказательство теоремы 6.9.1 (пункт а). Мы хотим показать, что пути порогов и цен, связанных с проверками узла удовлетворяют соотношениям (для :

Последней проверкой для любого узла предшественника текущего узла должна быть -проверка, поскольку может быть достигнуто лишь при движении вперед из Поэтому к и; должно быть применено одно из правил 1, 2 или 4, и в каждом случае должно выполняться Далее заметим, что является прямым следствием соотношение является соединением неравенств в Теперь докажем используя индукцию по последовательности узлов, просмотренных декодером. Для первой проверки в начальном узле справедливость и тривиальна, поскольку множество пусто при Теперь предположим, что и выполняются при проверках в произвольном узле с последовательностью порогов Рассматривая сначала движение вперед, затем вбок и затем назад из непосредственными, но утомительными рассуждениями показывается, что соотношения и всегда выполняются в следующем проверяемом узле.

Движение вперед. После движения из вперед в узел пороги не изменяются, но к этой последовательности добавляется новый порог как движение в было движением вперед, к применимы правила 1,

2 или 3 и окончательный порог больше или равен первоначальному порогу что доказывает для Если то порог был повышен и должно применяться правило 1. Так как первоначальный порог равен и предшествующая цена равна то крайне левое условие в правиле 1 принимает вид что устанавливает справедливость

Движение вбок. Пусть порогов при проверках узла и предположим, что из и; производится движение вбок или назад. Тогда к должно быть применимо правило 3 или обоих случаях согласно этим правилам Мы видим, что движения вбок или назад могут быть произведены лишь при В силу предположений индукции к применимо следовательно, Из вытекает, что . Поскольку, как было уже показано, то должно выполняться неравенство Так как согласно так как Т может изменяться, лишь принимая приращения А, то выводим, что при движениях из имеет место равенство

При движении вбок из узла и; в узел путь порогов не изменяется Первоначальный порог при проверках в и; равен и согласно Пусть конечный порог для проверок в и; Так как в узле должны применяться правила 1, 2 или 3, то порог не может понижаться и потому что доказывает Если то порог в должен быть повышен, применяется правило что доказывает

Движение назад Вновь допу стнм, что является путем порогов при проверках и предположим, что было совершено движение назад к Согласно (6 5) первоначачьньщ порог при проверке равен Так как было совершено движение назад, то в применяется либо правило 5, либо правило 4. Если применяется правило 5 до конечный порог при новых проверках равен первоначальному порогу, который, как указано выше, равен Поэтому, так как для и; выполняются соотношения то они также выпочняются и Для новой проверки Если применяется правню 4, то согласно рис (учитывая, что -первоначальный порог) Согласно и в силу того, что пороги могут изменяться лишь на приращения А, то Окончательный порог при новой проверке равен — А, так что что доказывает для Наконец, если и из справедливости соотношения для следует его справедливость для что завершает доказательство пункта

Следующее следствие из пункта теоремы будет необходимо при доказательстве пунктов и

Следствие Если в узле и проведена проверка с окончательным порогом то Т явпяется начальным порогом при первых последующих проверках каждого из непосредственных потомков узла и при первой последующей проверке узла

Доказательство Для проверки первого непосредственного потомка узла и это утверждение очевидно Первая проверка каждого из других непосредственных потомков должна производиться при движении вбок ранее просмотренных непосредственных потомков узта и Но согласно такое движение вбок может выполняться лишь тогда, окончательный порог, установленный до выполнения движения, равен Т Аналогично, первое движение назад к и совершается из последнего среди непосредственных потомков и порог вновь равен

Доказательство теоремы (пункт б) Мы хотим показать, что окон чательный порог Т при первой проверке каждого узла связан с ценой узла соотношением

а также что каждая из последующих проверок этого узла проводится с окончательным порогом на А ниже, чем предыдущее значение.

Воспользуемся индукцией вдоль пути узлов, сначала доказав справедливость теоремы начального узла, а затем показав, что если теорема верна для какого либо данного узла, то она справедлива для любого из непосредственных потомков этого Начальные проверки являются проверками и удовлетворяют начальных условий, накладываемых на декодер. Согласно следствию первоначальный порог для каждой последующей проверки начального узла равен окончательному порогу при предыдущей про верке Так то к каждой такой проверке применимо правило 4, причем эта проверка производится с окончательным порогом, сниженным на Теперь предположим, что утверждение пункта теоремы справедливо для узла с ценой, равной и пусть и — его непосредственный потомок с ценой По предположению окончательный порог Т при первой -проверке узла удовлетворяет неравенствам

Согласно следствию, Т есть первоначальный порог при первой проверке Теперь рассмотрим отдельно случаи

Если первая проверка удовлетворяет условиям правила 1, и окончательный порог Т установлен таким образом, что он удовлетворяет условию для Согласно следствию первоначальный порог при следующем возвращении к равен Если А (т. е. если порог повышен при первоначальной проверке то согласно применяется правило 4 и при возвращении совершается -проверка с окончательным порогом Рассуждая таким же образом, находим, что окончательный порог уменьшается на при каждом последующем возвращении к и; до тех пор, пока окончательный порог не будет равен При следующем возвращении к первоначальный порог меньше или равен применяется правило 5 и совершается движение вбок или назад. Прежде чем можно будет совершить следующую -проверку по предположению должна быть совершена другая -проверка при окончательном пороге Поэтому первоначальный и окончательный пороги при следующих -проверках и; также равны Аналогично, последовательные -проверки чередуются с -проверками каждый раз с величиной порога на ниже,чем при предыдущей проверке.

Наконец, рассмотрим случай Тогда при первой проверке применяется правило 3, совершается движение вбок или назад и перепроверяется лишь после следующей -проверки на этот раз при окончательном пороге При каждой из последовательных проверок первоначальный порог понижается на до тех пор, пока порог не станет меньше или равен совершаемая в этот момент проверка — это -проверка и для выполняется Как и ранее, окончательные пороги при последовательных проверках уменьшаются по сравнению с предыдущим значением на величину

Доказательство теоремы 6.9.1 (пункт в). Пусть в узле производится -проверка с окончательным порогом Мы хотим показать, что прежде чем можно будет проверить вновь, каждый из потомков для которого путь из лежит выше должен будет пройти -проверку с окончательным порогом В процессе доказательства пункта для каждого из непосредственных потомков например для было показано, что если путь из лежит выше (т. е. если то прежде чем произвести первую перепроверку узла будет произведена -проверка узла окончательным порогом Теорема доказывается индукцией по длине пути потомков узла т. е. если потомок находящийся на глубине от узла проходит -проверку с окончательным порогом то каждый из непосредственных потомков узла и для которого проходит -проверку с окончательным порогом прежде чем следовательно, пройдет перепроверку. Из (6.9.3) следует, что этот порог не может быть сделан ниже до тех пор, пока не будет перепроверен. Это завершает доказательство.