3.5.2. Алгоритм Берлекемпа-Мэсси (вма)
Алгоритм Берлекемпа-Мэсси лучше всего рассматривать как итеративный процесс построения минимального линейного
Рис. 23. ЛРОС с отводами σ1, σ 2,..., σ v и выходом S1, S2,..., S2v.
регистра (сдвига) с обратной связью (ЛРОС), аналогичного показанному на Рисунке 23, который генерирует известную последовательность синдромов S1 S2,...S2td.
Целью ВМА является построение многочлена (обратной связи) σ (i+1)(х) наименьшей степени, удовлетворяющего следующему уравнению, выведенному из (3.16):
(3.18)
Решение этой задачи эквивалентно условию, что многочлен
является многочленом обратной связи ЛРОС, который генерирует ограниченную последовательность синдромов.
Несовместность (рассогласование, расхождение, различие) на i-ой итерации, определенная как
является мерой соответствия синдромной последовательности и генерируемой ЛРОС и содержит корректирующий множитель для вычисления σ (i+1) на следующей итерации. Возможны два случая:
(3.19)
• Если di = 0, то уравнение (3.18) удовлетворяется с равенством
• Если di ≠ 0, то решение на следующей итерации имеет вид
(3.20)
где является
решением на m-ой
итерации такое, что —1 < т≤
1,
максимальна.
Итеративное
вычисление σ(i+1)(.х)
продолжается, пока не удовлетворятся
одно или оба условия: либо i
≥
i+1,+td-1
либо i
= 2td-
1.
Начальными условиями алгоритма являются:
(3.21)
Заметим также, что в Алгоритме Берлекэмпа-Мэсси используются программные инструкции (если — то). По этой причине ВМА не слишком удобен для аппаратной реализации. Тем не менее, по числу операций в конечном поле GF(2W) этот алгоритм весьма эффективен.
Пример 34. Пусть С двоичный (15,5,7) код БЧХ, исправляющий три ошибки из Примера 33. Для проверки вычислений и просто для справки приводится степенное и векторное представление элементов поля GF(16), порожденное примитивным многочленом р(х) = 1 + х + х4:
Таблица элементов поля GF(24), р(х) = 1 + х + х4:
Порождающий
многочлен кода С равен g(x) = х10
+ х8
+ х5
+ х4
+ х2
+ х + 1 . Предположим, что информационный
полином равен u(х)
= х + х2
+ х4
. Тогда соответствующее ему кодовое
слово равно
Пусть принятое слово равно r(x) = 1+х + х2+х3 + х4 + х6 + х8 + х11 + x14, соответствующее вектору r(х) =v(х)+e(х), полученному в результате передачи слова v по ДСК. (Вектору е соответствует многочлен ошибок е(х) = 1 + х6 + х12. Хотя декодеру этот вектор ошибок неизвестен, он используется здесь для упрощения вычисления синдромов.)
Синдромы равны:
Алгоритм Берлекемпа-Мэсси (ВМА):
• Итерация 0: Инициализация.
• Итерация 1:
• Итерация 2:
• Итерация 3:
• Итерация 4:
• Итерация 5:
• Итерация 6:
Таким образом,
То, что на нечетных шагах алгоритма di= 0 в предыдущем примере не случайность. Для двоичных кодов БЧХ это закономерность. С тем же результатом можно было выполнять только четные шаги алгоритма. Единственное изменение состоит в замене правила остановки на следующее
В результате снижается сложность декодирования. Читателю предлагается найти σ(х) в Примере 34, используя только три итерации.