6.3.3. Верхняя граница для среднего числа операций

В этом разделе оценку среднего числа операций, задаваемую формулой (6.15), усредним по ансамблю кодов, обладающих указанными выше свойствами. Для этого нам понадобится следующее неравенство Чернова, которое позволяет оценить сверху ступенчатую функцию с помощью экспоненциальной функции (фиг. 6.11)

Здесь докажем следующую теорему.

Теорема 6.1. (Сэвадж.) В дискретном канале без памяти при использовании алгоритма Фано среднее по ансамблю кодов число операций при декодировании (приходящееся на одно

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

Доказательство. Подставим (6.18) в (6.15). Тогда

Фиг. 6.11. и

Так как каждому ребру кодового дерева соответствует символов канала, то в данном случае

Из формул (6.20) — (6.22) имеем

где

Суммируя по в правой части последнего неравенства, получаем

где

Далее зафиксируем правильный путь и усредним (6.23) по принимаемым последовательностям Так как среднее значение суммы равно сумме средних значений и, кроме того, входит только в два последних сомножителя правой части последнего неравенства, то усреднение (6.23) сводится к нахождению среднего значения произведения Имеет место следующее равенство:

Так как канал является дискретным каналом без памяти, то при всех

где через обозначены соответственно последние ребер путей

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

где

Следовательно,

Правую часть (6.28) оценим сверху, воспользовавшись неравенством Шварца:

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

Выше был рассмотрен случай, когда . В действительности аналогичные оценки имеют место и при . В силу этого а следовательно, и можно оценить сверху с помощью правых частей (6.30).

Чтобы получить по возможности более точную границу, правые части (6.30) необходимо минимизировать по и распределению вероятностей Однако здесь минимизацию по мы проводить не будем, положим просто и минимизируем правые части (6.30) только по Пусть

Тогда

Отсюда и из неравенств

получаем

Из этого неравенства, в частности, следует справедливость теоремы 6.1.