4.4. Алгоритм Чейза

Алгоритм Чейза [26] представляет собой способ приблизиться к работе декодера, дающего оценку максимального правдоподобия для последовательности. Аналогично алгоритму Велдона, в методе Чейза используется несколько жестких декодеров, однако совершенно иначе. Декодеры Чейза порождают набор возможных кодовых слов, и наиболее вероятное из них выбирается в качестве выходного слова.

4.4.1. Стандартные алгоритмы Чейза

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

1. Принимаем жесткое решение по каждому символу принятой последовательности и получаем вектор

2. Намеренно вводим различные комбинации ошибок порождая пробные последовательности Декодируем каждую из полученных пробных последовательностей с помощью декодера с жестким решением.

3. Вычисляем расстояние между каждым кодовым словом и принятой последовательностью (при мягком решении) и выбираем ближайшее кодовое слово.

Три предложенных Чейзом варианта отличаются методом порождения пробных последовательностей. Метод 1 приводит к наибольшему числу пробных последовательностей и имеет наилучшие характеристики. В методах 2 и 3 используется меньшее число

пробных последовательностей, и соответственно их характеристики несколько хуже.

Метод 1: взять в качестве векторов нулевой вектор и все комбинации ошибок веса

Метод 2: взять в качестве векторов множество из векторов, имеющих всевозможные символы на наименее достоверных позициях и нулевые символы на остальных.

Метод 3: определить наименее достоверных символов; векторы имеют единичные символы на наименее достоверных позициях и нулевые символы на остальных для нечетного для четного

Основная идея алгоритма Чейза состоит в порождении списка кодовых слов, который почти всегда будет содержать слово, ближайшее к принятой последовательности. Этот алгоритм основан на том, что в случаях, когда кодовое слово, декодированное с помощью обычного жесткого решения, не совпадает с переданным словом, одно из ближайших к нему кодовых слов обычно совпадает с переданным. Три алгоритма, предложенные Чейзом, представляют собой, по существу, три метода порождения различных множеств этих ближайших соседей. Напомним, что любой код с кодовым расстоянием всегда позволяет исправлять все комбинации ошибок мягкого решения, вес которых не превышает Таким образом, жесткое декодирование принятой последовательности часто будет содержать ошибок. Если удалить из них с помощью какой-нибудь последовательности веса жесткий декодер сможет исправить оставшиеся ошибок. Следовательно, при четном пробная последовательность будет содержать ошибок, а при нечетном ошибок. Метод 1 является, очевидно, избыточным, поскольку дает требуемую пробную последовательность раз. Он будет давать также большое число других, маловероятных наборов, изменяя высокодостоверные символы. Следует отметить, что при наличии более жестких ошибок весьма вероятно соответствие некоторых из них очень малодостоверным символам. Таким образом, ограничиваясь векторами содержащими единичные символы лишь на наименее достоверных позициях, в большинстве

Рис. 4.8. Характеристики -кода Голея в гауссовском канале

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

Применение метода 2 рассмотрим на примерах, которые приводились ранее для иллюстрации алгоритма Велдона. Предположим, что при использовании кода длиной 15 с расстоянием 5 была передана нулевая последовательность, а принята последовательность . При методе 2 в качестве пробных последовательностей берется жесткое решение с произвольными символами в двух наименее достоверных позициях (позиции 8 и 9). Таким образом, четыре пробные последовательности имеют вид

Жесткий декодер переведет, очевидно, в нулевое кодовое слово, которое находится на расстоянии 17 от Любая другая пробная последовательность, которая не декодируется в нулевое слово, должна декодироваться в кодовое слово, вес которого не меньше 5. В любом случае такое кодовое слово будет находиться на расстоянии не меньше 18 от Таким образом, декодер дает правильное решение.

Аналогично можно декодировать принятую последовательность Применение метода 2 дает те же четыре пробные последовательности Пробная последовательность вновь декодируется в нулевое слово, которое находится на расстоянии 19 от Однако любое ненулевое кодовое слово, полученное из последовательностей должно иметь вес, не меньший 5, и его расстояние до должно быть не менее 20. Таким образом, декодер Чейза исправляет комбинацию ошибок, которая не исправляется при декодировании по алгоритму Велдона. Обычно характеристики метода 2 существенно ближе к характеристикам декодера максимального правдоподобия, чем у алгоритма Велдона, поскольку первый может исправлять большое число комбинаций, вес которых больше