4. Вероятность ошибки

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

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

нашей процедуре поиска последовательность из удовлетворяющую условию

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

отсюда следует, что

Далее, из случайного метода построения древовидного кода следует (с помощью тех же аргументов, что и в гл. 2), что

Рассмотрим теперь вероятность того, что действительно используется критерий. Мы уже установили, что

Если и выбраны так же, как в равенствах (3.54) и (3.55), то

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

В соответствии с определением наших исключающих функций [см. соотношение (3.2)]

где, по определению, для Таким образом,

Средняя вероятность ошибки задается соотношением

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

где решение уравнения Тогда

Последнее неравенство в соотношении (3.70) вытекает из того факта, что при выбранном в соответствии с равенством (3.54).

Более того, при

Это неравенство следует из соотношений (3.11) и Подставляя неравенства (3.64), (3.67), (3.70) и (3.71) в соотношение (3.68), мы получаем, что

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

неравенству (3.72), находим, что

В гл. 2 мы показали, что для случайных блоковых кодов длины вероятность ошибки ограничена сверху следующим образом:

где

Очевидно, что сумма, входящая в неравенство (2.33), мажорирует сумму, входящую в неравенство (3.73). Это верно в силу того, что индекс в неравенстве (2.33) пробегает все целые значения между и в то время как область изменения индекса в неравенстве (3.73) может быть только некоторым подмножеством этой совокупности целых чисел.

Итак, используя предыдущие результаты [неравенства (2.36) и (2.37)] и выбирая в качестве его минимизирующее значение, задаваемое равенством (3.54), мы получаем, что для первых символов в случайном древовидном коде

и

Экспоненциальное поведение осредненной по ансамблю вероятности ошибки для последовательного декодирования совпадает с ее поведением для блоковых кодов.