2. Декодирование по единому критерию

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

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

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

Пусть средний объем вычислений на этапе, необходимых для того, чтобы проверить

все последовательности из которые были сохранены на этапе. Так как среднее число оставшихся последовательностей в то

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

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

где ограничено числом 2.

Из рис. 9 ясно, что в сумме, входящей в соотношение (3.15), есть максимальный член. Пусть — соответствующее ему значение Тогда из соотношений (3.9) и (2.14) получаем, что при

Рассматривая как непрерывную переменную и дифференцируя по ней, мы находим условие максимума:

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

Комбинируя соотношения (3.17) и (3.18), получаем

Явные выражения для и соответствующего ртах не могут быть получены из-за трансцендентной природы функции однако общий вид соотношения (3.19)

поучителен. При заданных значениях мы можем решить трансцендентные уравнения (3.19) и (3.2) совместно для птзх и ртах; если затем мы оставим постоянными и удвоим К, то решение для ртах останется неизменным, а решение для удвоится. Значение ртах определяется значением отношения Таким образом, в силу равенства (3.2) мы можем написать

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

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

Для процедуры декодирования по единому критерию вероятность ошибки практически совпадает с вероятностью того, что правильное подмножество будет отброшено так же, как и неправильное подмножество.

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

Наша цель состоит в том, чтобы не только уменьшить количество вычислений при декодировании, но и сохранить при этом характер убывания ошибки. Но если сделать наш вероятностный критерий К пропорциональным то граница для среднего количества вычислений [см. уравнение (3.21)] будет расти экспоненциально при растущем Этого роста можно избежать, используя возрастающую последовательность вероятностных критериев и соответствующую последовательность исключающих функций