3. Декодирование по нескольким критериям

Рассмотрим теперь декодирующее устройство, использующее несколько критериев, которое исследует древовидное множество сообщений 5 в соответствии со следующими правилами.

1. Вычислительное устройство начинает с наименьшего критерия и порождает последовательно все множество При этом устройство отбрасывает любую последовательность длины которая отличается от полученной последовательности (также длины или больше местах.

2. Как только вычислительное устройство обнаружит какую-нибудь последовательность из которая сохраняется при всех длинах вплоть до оно печатает соответствующий первый информационный символ.

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

4. Вычислительное устройство продолжает эту процедуру до тех пор, пока некоторая последовательность не останется в 5 для всех длин вплоть до тогда оно печатает соответствующий первый информационный символ.

Если принять эти правила, то вычислительное устройство будет использовать критерий только в том случае, когда правильное подмножество следовательно, правильная последовательность исключено по критерию Вероятность такого события зависит только от шумов в канале. Осреднением по всем шумовым последовательностям в канале мы можем найти границу для среднего объема вычислений, требуемых для того, чтобы исключить неправильное подмножество

Грубо говоря, нам понадобится много критериев, прежде чем будет принята некоторая последовательность из только тогда, когда в канале имеется слишком сильный шум. Чаще всего мы сможем принять некоторый элемент из , и в частности при помощи небольшого числа критериев.

Пусть представляет собой значение при и пусть вероятность того, что декодирующее устройство будет использовать критерий. Если средний объем вычислений, требуемых для прослеживания множества тот

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

Удобно положить

тогда мы можем написать

Подставляя соотнсшения (3.15) и (3.26) в неравенство (3.23), получаем

где мы использовали обозначение для

Для того чтобы пояснить вывод границы для , который будет дан дальше, мы прежде всего рассмотрим экспоненту под знаком двойной суммы, входящей в неравенство (3.27). Соотношение (3.9) утверждает, что для каждого существует область значений в которой

где величина является при решением уравнения

Для этих значений интересующая нас экспонента принимает вид

Функция достигает минимума при определенном уравнением (2.35). Далее, при фиксированном является монотонно убывающей функцией от Отсюда вытекает, что при заданном существует некоторое такое, что с очень большой точностью равно

Итак, мы нашли, что

При помощи некоторых алгебраических преобразований можно показать, что

Мы увидим вскоре, что при величина ограничена сверху числом, которое медленно меняется при изменении При эта граница быстро растет.

Рис. 11. (см. скан) как функции от для двоичного симметричного канала.

Это следует из того факта, что для каждого в первой сумме в правой части неравенства (3.27) существует слагаемое, которое не меньше, чем На рис. 11 изображена зависимость отношения

от С вместе с графиком зависимости от С, приведенным для сравнения.

Мы хотим теперь найти границу для при Сначала мы получим границу для среднего объема вычислений, необходимых для того, чтобы проследить за неправильным подмножеством при фиксированном критерии Мы уже заметили, что

где

а величина была определена соотношением

Итак, мы можем переписать соотношение (3.15) в следующем виде:

Далее, при

и неравенство можно переписать так:

В силу того, что является трансцендентной функцией от явное вычисление правой части равенства (3.15) кажется неосуществимым. Однако в рассуждении, проведенном после неравенства (3.27), мы уже отмечали, что большой вклад в дает Так как с ростом монотонно возрастает, то из равенства (3.156) следует, что мы можем оценить сверху оценив для этого сверху любой величиной зависящей

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

Если определено как решение уравнения

то (см. рис. 12) . С другой стороны, если определить как решение уравнения

то этот же рисунок показывает, что

Мы примем для наименьшее из двух значений, даваемых уравнениями (3.33) и (3.34). В соответствии с этим, мы определим как такое [значение для которого

После некоторых преобразований можно показать, что

Далее, определим так, чтобы выполнялись неравенства

Подставляя значение (3.36) в (3.37), получаем

Неравенство вытекает (после значительного количества алгебраических преобразований) из уравнения, определяющего и из соотношения

Наконец, мы определим как

Рис. 12. (см. скан) Кусочно линейное приближение к и оценка сверху при помощи

Тогда, решая уравнение (3.396), мы находим

Нужные нам границы для определяются теперь последовательными подстановками: выражение (3.40) нужно подставить в соотношение (3.33) и далее воспользоваться равенствами (3.31) и (3.32). Мы получим

Подставляя значения (3.39а) и (3.41) в неравенство (3.156), находим

Неравенство (3.42) верно, так как из следует, что

Далее

Из неравенства (3.38) следует, что

Учитывая это неравенство, из соотношения (3.43) получаем

где

Аналогично, для

В силу неравенства (3.38), имеем

Подставляя это неравенство в соотношение (3.47), получаем

Подстановка неравенств (3.45) и (3.49) в (3.42) дает, наконец, искомую границу для а именно

где

Мы будем теперь искать границу для Подставляя соотношения (3.26) и (3.50) в (3.23), получаем

Подставив далее (3.25) в (3.52), заметив, что для и ограничив результат суммирования суммой геометрической прогрессии, мы получим

Мы хотим выбрать и так, чтобы граница для была минимальной. Дифференцируя по этим переменным и полагая результат равным нулю, получим

Подстановка этих величин в соотношение (3.53) дает окончательный результат

Формула (3.56) позволяет показать, что средний объем вычислений, необходимых для выделения неправильного подмножества, меняется медленнее, чем Для того чтобы выявить зависимость от В, заметим прежде всего,

что

Далее, для

и, таким образом,

Используя соотношения (3.57) и (3.59) для того, чтобы ограничить сверху правую часть неравенства (3.56), получаем окончательный результат:

Мы видим, что эта граница бесконечно увеличивается при и с ростом растет медленнее, чем линейная функция (при ).