5.3. Вероятностное декодирование

Рассмотрим А-ичный -код и допустим, что все кодовые слова равновероятны. Как и в гл. 4, мы хотим, используя обозначения рис. 4.1, найти вероятность того, что переданный символ в позиции равен при условии,

что известны принятые символы в ярусах проверочного дерева с корнем Найдем сначала

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

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

где

В равенстве (5.26) а берется по модулю А, а умножение в соотношении (5.27) выполняется по модулю

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

Лемма 5.1. Рассмотрим последовательность независимых А-ичных символов, в которой символ имеет распределение вероятностей Вероятность

того, что сумма символов по модулю А примет значение а, равна в разложении

где произведение в соотношении (5.28) берется по модулю

Доказательство леммы. Заметим, что правая часть соотношения (5.28) при использовании обычного умножения оказывается просто -преобразованием суммы букв. Другими словами, коэффициент при в разложении (5.28) равен вероятности того, что сумма символов равна а. Изменения, связанные с тем, что мы берем произведение по модулю сводятся просто к тому, что коэффициенты при степенях с показателями, равными по модулю А, складываются, что и доказывает лемму.

Доказательство теоремы. После некоторых преобразований условных вероятностей из венства (5.25) получим

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

где задается в уравнении (5.27). Подставляя выражение (5.30) в равенство (5.29), получаем утверждение теоремы. Ч.Т.Д.

Выражение (5.26) можно сразу же использовать для построения итерационного процесса, воспользовавшись рассуждениями гл. 4. При последовательных итерациях следует писать вместо для каждого символа вычисляются различных вероятностей, каждая из которых не учитывает одно проверочное множество.