4.4.2. Варианты алгоритма Чейза

Некоторые простые варианты алгоритма Чейза были исследованы Бойдом [30] при попытке найти наименее сложную реализацию мягкого декодера для укороченного -кода Хемминга. Декодер представлял собой часть каскадной схемы, и при его построении было важно добиться почти оптимальных характеристик при относительно большой вероятности ошибки слова.

Рис. 4.9. Стандартный жесткий декодер для -кода

Простейшая рассмотренная Бойдом схема называлась жестким декодером с помощником. Хотя этот алгоритм и не является вариантом алгоритма Чейза, он служит основой одного из простых вариантов, и мы обсудим его первым. Жесткий декодер для -кода показан на рис. 4.9. Он представляет собой, по существу, декодер с поиском в таблице синдромов и содержит в памяти наиболее вероятную комбинацию ошибок для каждого синдрома. Из 31 синдрома 13 служат для исправления одиночных ошибок, а остальные — для исправления двойных и тройных ошибок. При возникновении двойных или тройных ошибок существует несколько возможных кандидатов, и при жестком решении все они одинаково хороши. Однако при мягком решении один из этих кандидатов будет, очевидно, лучше других. Метод Бойда состоит в нахождении наименее достоверного символа для определения того, какую из комбинаций ошибок веса 2 или 3 следует выбрать. Выбор делается таким образом, чтобы положение наименее достоверного символа совпадало с одной из ошибок в комбинации веса 2 или 3. Схема, реализующая такой декодер, показана на рис. 4.10.

Объединение этого метода с алгоритмом Чейза приводит к построению декодера, который Бойд назвал многокомбинационным декодером Чейза с помощником. Простейшим является случай, когда известны положения двух наименее надежных символов. В этом случае процедура Бойда состоит в следующем.

1. Образуем синдром и используем положение предпоследнего по достоверности символа в качестве помощника для поиска комбинации ошибок в таблице.

Рис. 4.10. Жесткий декодер с помощником для -кода

2. Заменяем наименее достоверный символ на противоположный и повторяем шаг 1.

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

Способ действий в случае равенства расстояний, предложенный на шаге 3, основан на наблюдении, согласно которому число жестких ошибок, введенных на шаге 2, всегда не меньше, чем на шаге 1. При обычном методе квантования в канале это будет соответствовать несколько более вероятному событию. Используя, например, переходные вероятности, приведенные в подразд. 4.1.3, находим

Таким образом, при прочих равных условиях три мягкие ошибки веса 4 каждая более вероятны, чем две мягкие ошибки веса 6 каждая.

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

1. Образуем синдром и используем положение третьего с конца по достоверности символа в качестве помощника при поиске комбинации ошибок в таблице.

2. Заменяем наименее достоверный символ на обратный, вычисляем синдром и используем предпоследний по достоверности символ в качестве помощника при поиске комбинации ошибок в таблице.

3. Заменяем предпоследний по достоверности символ на обратный, вычисляем синдром и используем третий с конца по достоверности символ в качестве помощника при поиске комбинации ошибок в таблице.

4. Выбираем кодовое слово, ближайшее к принятой последовательности; при равенстве некоторых расстояний выбираем кодовое слово, соответствующее комбинации ошибок, имеющей больший вес.

Относительные

Рис. 4.11. Относительные характеристики алгоритмов Чейза с помощником и стандартного алгоритма Чейза для -кода

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