4.2.2. Другая форма алгоритма Хартмана-Рудольфа
Лучшее понимание природы алгоритма ХР можно получить, записав (4.19) несколько иначе. Прежде всего, подставляя (47) в (4.18), получаем
Осуществляя жесткое решение для каждого принятого символа
имеем
Отсюда вытекает, что абсолютное значение
так что
Сделаем теперь следующие замечания. Прежде всего, каждое из произведений в (4.19) содержит лишь те значения
для которых
Далее, проверочное уравнение, соответствующее каждому кодовому слову
дуального слова, определяется по ненулевым элементам этого слова. Так, если для каждого
образовать сумму по модулю 2 величин
для тех
для которых
то каждая из этих сумм будет задавать оценку В величины
Каждая оценка имеет вид
ошибка, соответствующая члену, для которого
Наконец, обозначив через
вероятность того, что
можно переписать в виде
С учетом приведенных замечаний (4.19) переписывается в виде
или
Напомним, что вероятность появления нечетного числа ошибок определяется как
так что
Поэтому
задается формулой
Равенство (4.21) позволяет сформулировать алгоритм ХР следующим образом.
1. С помощью проверочной матрицы вычисляем все возможные оценки для
через
2. Умножаем каждую оценку на вес, равный разности вероятностей того, что данная оценка верна и неверна.
3. Суммируем все взвешенные оценки и выбираем
сравнивая полученную сумму с нулем.
Из формы алгоритма ХР, задаваемой (4.21), очевидно, что он является обобщением АРР-алгоритма порогового декодирования, в котором вместо множества проверок, ортогональных по данному символу, используются все возможные проверочные уравнения. Кроме гого, веса вычисляются несколько другим способом.
Поскольку в АРР-алгоритме проводится существенно меньшее число проверок, возникла точка зрения [28], что, изменив весовые множители, можно существенно уменьшить число проверок для произвольного
-кода. Однако в настоящее время положительные результаты в этом направлении получены только для кодов с
-шаговой ортогонализацией. Интересно отметить, что если декодировать код с одношаговой ортогонализацией, осуществляя только ортогональные проверки на четность и вычисляя веса с помощью алгоритма ХР, то полученная решающая функция будет совпадать с (4.14). Таким образом, в этом частном случае привлечение небольшой части всех проверочных уравнений приводит к превосходному правилу декодирования.
Независимо от того, используются ли все кодовые слова дуального кода или лишь некоторая их часть, все модификации и методы реализации, рассмотренные для алгоритма декодирования АРР, применимы и к алгоритму ХР. Так, можно вычислять веса, основываясь на наименее достоверном символе в каждой проверке (аналогично алгоритму Форни и Дэвиса), или повторять декодирование несколько раз, заменяя первоначальные мягкие решения на вновь вычисленные (и нормированные) значения