6.3. Среднее число операций при декодировании

6.3.1. Среднее число операций

При последовательном декодировании с помощью алгоритма Фано среднее число операций при декодировании является случайной величиной, зависящей от принятой последовательности, подвергшейся воздействию шумов в канале, переданной информационной последовательности и сверточного кода. В силу этого определение среднего числа операций для некоторого заданного кода является очень трудной задачей. Однако с помощью границы случайного кодирования Сэваджу [9, 10] удалось получить границу для среднего по некоторому ансамблю кодов числа операций при декодировании,

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

Фиг. 6.10. Неправильное подмножество

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

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

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

(равенство принято для удобства).

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

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

2) Допустим, что двоичная переменная алгоритма Фано равна 1 и декодер при поиске когда-то возвращается к пути . В силу того что декодер не может вторично выбрать ребро, указанное в п. 1, и пытается найти какое-либо другое ребро, чтобы пройти вперед. Если этот поиск оканчивается неудачно, то декодер возвращается в узел, предшествующий началу Следовательно, при значении порога и условии, что на пути декодер может выполнить самое большое операций.

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

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

Действительно:

1) в случае путь может быть достигнут при значении порога

2) если то и путь может быть достигнут при значении порога

3) так как при то и путь может быть достигнут при значении порога

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

Величины определяющие путь могут принимать значения соответственно от 0 до и от 1 до Таким образом, вводя ступенчатую функцию

число операций с можно оценить сверху следующим образом:

Далее оценим сверху правую часть (6.13). Величина согласно формуле (6.10), определяется равенством

т. е. является значением при некотором Так как является ступенчатой функцией, принимающей значения 0 и 1, то среди значений содержится и Таким образом, для с получаем следующую оценку;

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