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

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

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

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

Пользуясь этим ансамблем и введенными обозначениями, мы можем доказать следующую теорему:

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

Для доказательства нам потребуется следующая лемма.

Лемма 4.1. Рассмотрим последовательность независимых двоичных символов, причем вероятность того, что символ последовательности равен 1, есть Тогда вероятность четного числа единиц равна

Доказательство леммы. Рассмотрим функцию

Заметим, что в разложении этого выражения по степеням коэффициент при равен вероятности появления единиц. Функция

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

что и доказывает лемму.

Доказательство теоремы.

По определению условных вероятностей имеем

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

Аналогично

Подставляя выражения (4.3) и (4.4) в равенство (4.2), получим утверждение теоремы. Ч.Т.Д.

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

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

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

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

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

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

Для практического вычисления вероятностей в теореме 4.1 оказывается удобнее преобразовать равенство (4.1) с помощью логарифмических отношений правдоподобий. Пусть

где а — знак, абсолютная величина логарифмического отношения правдоподобий. После некоторых преобразований выражения (4.1) получим

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

Рис. 4.2. Декодирующее устройство.

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

Пусть на вход декодера подается логарифмическое отношение правдоподобий; первый ряд блоков на рис. 4.2 вычисляет для каждого символа т. е. выполняет самую правую операцию в равенстве (4.6). На выходе сумматоров во втором ряду получается величина соответствующая двум правым операциям в равенстве (4.6). Аналогично последовательные ряды блоков соответствуют операциям в равенстве (4.6), выполняемым последовательно, справа налево. На рис. 4.2, разумеется, опущены некоторые

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

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