4.3.1. Комментарий к алгоритмам декодирования

В отличие от БМА алгоритм Евклида (ЕА) использует все синдромы уже на первом шаге процедуры. Однако, по числу операций в конечном поле алгоритм Берлекэмпа-Мэсси (БМА) обычно эффективнее ЕА. С другой стороны, каждый шаг ЕА имеет идентичную структуру, что приводит к более эффективной аппаратной (микросхемной) реализации. Кроме того, три рассмотренных метода декодирования для (двоичных и недвоичных) кодов БЧХ являются неполными, так как исправляют ограниченное число ошибок — декодирование с ограниченным расстоянием. Вследствие этого рассмотренные алгоритмы способны обнаруживать ситуации, которые превышают их корректирующую способность.

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

Известны также и другие подходы к декодированию кодов БЧХ, из которых наиболее значительным является использование быстрых алгоритмов дискретного преобразования Фурье над полем GF(2^m). Этот подход к созданию быстрых алгоритмов декодирования исследуется в [Blah], где читатель найдет необходимые подробности.

Рассмотренные выше алгоритмы принято называть декодированием в частотной области, учитывая эквивалентность между вычислением синдрома и преобразованием Фурье над конечным полем. В [Blah, Blah 1*} рассматриваются и другой подход к построению декодеров — декодирование во временной области. Этот вариант декодеров PC кодов требует большего количества операций в поле, но считается более удобным для аппаратной (микросхемной) реализации.

Сравнительно недавно Судан [Sud] предложил (алгебраический) алгоритм, исправляющий ошибки за границей минимального расстояния кода. Этот алгоритм применяется к декодированию PC и, главным образом, АГ кодов. Выходом этого алгоритма является список (ближайших в некоторой метрике) кодовых слов. Алгоритм {декодирования в список) основан на процедурах интерполяции и факторизации многочленов от двух переменных над GF(2^m) и его расширением. Оригинальный алгоритм Судана был позднее улучшен в работе [Gur] и других. Важно, что на основе алгоритма Судана создан алгебраический алгоритм мягкого декодирования кодов PC и близких к ним АГ кодов.

4.3.2. Исправление ошибок и стираний

Для исправления стираний необходимое изменение в процедуре декодирования кодов PC, рассмотренной выше, состоит во введении многочлена локаторов стираний τ(х),

где у_iℓ = а^iℓ, локаторы стираний, 1 ≤ ℓ ≤μ.

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

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

(4.10)

Алгоритм БМ применяется для определения многочлена локаторов ошибок с учетом следующих изменений:

1. Рассогласование определяется теперь как

(4.11)

где d₀=T_μ+1

2. Условие остановки алгоритма заменяется следующим:

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

(4.12)

Кроме того, вычисляется следующий многочлен локаторов искажений,

(4.13)

С помощью модифицированного алгоритма Форни получаем для значений ошибок:

(4.14)

и для значений стираний:

(4.15)

Алгоритм Евклида также может быть применен к модифицированному синдрому T(х) для исправления стираний и ошибок. Для этого в алгоритме исправления только ошибок многочлен S(x) заменяется многочленом 1 + Т(х), а в начальных условиях r₀(x) =x^d,d = 2t_d+1, и r₁(x) = 1 + Т(х). Алгоритм останавливается на j-ом шаге, если deg[r_j(x)] ≤ |_(d - 1 +μ)/2_|, и выдает как решение w(х) = r_j(х) и σ(х) = b_j(x).

Пример 43. Пусть С это (15,9,7) код PC над GF(2⁴) с нулями в точках {а, а², ..., а⁶}, где примитивный элемент поля удовлетворяет равенству р(а) =а⁴ + а³ + 1 = 0. Для удобства ниже представлена таблица элементов GF(2^m) , упорядоченная по степеням примитивного элемента а , а⁴ + а³ + 1 = 0. Таблица элементов GF(2^m), p(x) = x⁴+x³+1.

Порождающий многочлен кода С равен

Положим, что ассоциированный с кодовым словом полином равен

Пусть принятое слово представлено полиномом

Предположим, что приемник располагает дополнительной информацией о том, что позиции с локаторами а⁰ и а⁵ ненадежны и заявлены как стирания.

Заметим, что многочлен искажений имеет вид е(х) = а¹⁴ + а⁸x³ + а⁵х⁵ + ах¹².

Таким образом, кроме принятого слова r(х) декодеру известны локаторы μ = 2 двух стираний, а⁰ и а⁵. Это позволяет вычислить многочлен локаторов стираний

(4.16)

Синдромы для принятого слова равны:

Соответственно, синдромный многочлен равен:

(4.17)

Модифицированный синдром (4.10) равен

Алгоритм Берлекэмпа-Мэсси для исправления ошибок и стираний

• Итерация 0: Начальные установки.

• Итерация 1:

• Итерация 2:

• Итерация 3:

• Итерация 4

Таким образом, получаем многочлен локаторов ошибок

Напомним, что в последнем равенстве с помощью процедуры Ченя найдены обратные величины локаторов ошибок в поле GF(2^m). Действительно, проверка дает σ(а¹²) = 0 и о(а³) = 0. Следовательно, локаторами ошибок являются а^-12 = а³ и a^-3 = а¹².

Из определения (4.12) находим модифицированный многочлен значений искажений

(4.18)

Многочлен локаторов искажений равен

и, следовательно, ф'(х) = 1.

Значения ошибок и стираний могут быть вычислены по формулам (4.14) и (4.15), соответственно,

Отсюда следует, что многочлен искажений равен

Результат декодирования v(x) = г(х) + е(х) совпадает с переданным словом v(x). Исправлены две ошибки и два стирания.

Прямое вычисление значений искажений

Для кодов PC с малым кодовым расстоянием значения стираний можно получить как решение системы линейных уравнений. Пусть е(х) полином ошибок, ассоциированный с комбинацией v ошибок и μ стираний,

(4.19)

Тогда справедлива следующая система линейных уравнений, аналогичная (4.8), связывающая синдромы и значения искажений:

(4.20)

где 1 ≤i≤ 2t_d. Как и раньше, может быть использовано любое подмножество v +μ≤t_d уравнений для определения значений всех стираний и ошибок.

Пример 44. Рассмотрим прямое вычисление значений искажений из предыдущего примера. После выполнения алгоритма Берлекэмпа-Мэсси и процедуры Ченя декодеру известны локаторы искажений и многочлен ошибок в виде

Значения искажений могут быть найдены из системы линейных уравнений (4.20), которая в матричной форме имеет

следующий вид

(4.21)

Легко проверить, что решением (4.21) являются f₀ = а¹⁴, е₃ = а⁸,f₅ = а⁵, e₁₂ = а. Эти значения совпадают со значениями искажений, вычисленными модифицированным алгоритмом Форни.