Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
3. Декодирование по нескольким критериямРассмотрим теперь декодирующее устройство, использующее несколько критериев, которое исследует древовидное множество сообщений 5 в соответствии со следующими правилами. 1. Вычислительное устройство начинает с наименьшего критерия 2. Как только вычислительное устройство обнаружит какую-нибудь последовательность из 3. Если отброшено все множество 4. Вычислительное устройство продолжает эту процедуру до тех пор, пока некоторая последовательность не останется в 5 для всех длин вплоть до Если принять эти правила, то вычислительное устройство будет использовать критерий Грубо говоря, нам понадобится много критериев, прежде чем будет принята некоторая последовательность из Пусть представляет собой значение
Критерий
Удобно положить
тогда мы можем написать
Подставляя соотнсшения (3.15) и (3.26) в неравенство (3.23), получаем
где мы использовали обозначение Для того чтобы пояснить вывод границы для
где величина является при
Для этих значений
Функция Итак, мы нашли, что
При помощи некоторых алгебраических преобразований можно показать, что
Мы увидим вскоре, что при Рис. 11. (см. скан) Это следует из того факта, что для каждого от С вместе с графиком зависимости Мы хотим теперь найти границу для
где
а величина
Итак, мы можем переписать соотношение (3.15) в следующем виде:
Далее, при
и неравенство
В силу того, что от
Если
то (см. рис. 12)
то этот же рисунок показывает, что Мы примем для
После некоторых преобразований можно показать, что
Далее, определим
Подставляя значение (3.36) в (3.37), получаем
Неравенство
Наконец, мы определим
Рис. 12. (см. скан) Кусочно линейное приближение к Тогда, решая уравнение (3.396), мы находим
Нужные нам границы для
Подставляя значения (3.39а) и (3.41) в неравенство (3.156), находим
Неравенство (3.42) верно, так как из Далее
Из неравенства (3.38) следует, что
Учитывая это неравенство, из соотношения (3.43) получаем
где
Аналогично, для
В силу неравенства (3.38), имеем
Подставляя это неравенство в соотношение (3.47), получаем
Подстановка неравенств (3.45) и (3.49) в (3.42) дает, наконец, искомую границу для
где
Мы будем теперь искать границу для
Подставив далее (3.25) в (3.52), заметив, что
Мы хотим выбрать
Подстановка этих величин в соотношение (3.53) дает окончательный результат
Формула (3.56) позволяет показать, что средний объем вычислений, необходимых для выделения неправильного подмножества, меняется медленнее, чем что
Далее, для
и, таким образом,
Используя соотношения (3.57) и (3.59) для того, чтобы ограничить сверху правую часть неравенства (3.56), получаем окончательный результат:
Мы видим, что эта граница бесконечно увеличивается при
|
1 |
Оглавление
|