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

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

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

Если кодовое расстояние кода равно и принятое слово содержит символов, соответствующих стираниям, то при декодировании «стертых» символов могут быть игнорированы. Однако даже если игнорировать эти символы, то два кодовых слова будут отличаться друг от друга по меньшей мере в оставшихся позициях, что позволяет в дополнение к стираниям исправлять по меньшей мере

ошибок в канале. Таким образом, код может исправлять все комбинации из стираний и в ошибок в канале, для которых

Ошибки и стирания исправляются с помощью двоичного кода БЧХ следующим образом. Предположим, что код БЧХ гарантирует исправление ошибок, а принятое слово содержит символов, соответствующих стираниям. Алгоритм декодирования очень прост. Вначале заменим стертых символов нулями и декодируем полученное слово, используя стандартный алгоритм декодирования БЧХ. Затем заменим стертых символов единицами и вновь проведем аналогичное декодирование. Наконец, выберем то из двух кодовых слов, в котором было исправлено меньшее число ошибок на нестертых позициях. Легко видеть, что при выполнении условия (5.57) по описанному алгоритму всегда осуществляется правильное декодирование. В самом деле, пусть при замене стертых символов нулями на этих в позициях возникло ошибок. Тогда общее число ошибок станет равным и их исправление гарантируется при . С другой стороны, если то при замене стертых символов единицами будет введено ошибок. В этом случае полученная комбинация состоит из ошибок и ее также можно исправить. Заметим, что этот алгоритм весьма близок к алгоритмму Чейза и не является чисто алгебраическим.

Труднее исправлять стирания в недвоичных кодах БЧХ. Аналогично (5.6) введем многочлен локаторов стираний

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

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

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

Заметим, что если стирание произошло на позиции и соответствующий подставленный символ не содержит ошибки, то и содержат множитель Вычисление ошибки по формуле (5.61) приведет к нулевому значению этого символа.

Решить ключевое уравнение можно с помощью алгоритма либо Евклида, либо Берлекэмпа. При использовании алгоритма Евклида для кода БЧХ, исправляющего ошибок, следует применять видоизмененный многочлен синдрома, введенный Форни [48]:

Алгоритм решения следующий:

1) применить алгоритм Евклида к

2) использовать начальные условия

3) остановиться, когда четно) или нечетно), где

4) положить

Легко показать, что начальные условия, указанные на шаге 2, дают последовательность решений (5.59) и что каждый многочлен содержит в качестве множителя. Таким образом,

Кроме того, этот алгоритм обладает некоторыми свойствами, аналогичными (5.39):

Требуемым решением является многочлен степень которого не превышает где

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

Рассмотрим случай четного Если так что то Поэтому решение после итерации является нужным решением ключевого уравнения. Аналогично рассматривается случай нечетного При этом оказывается, что в качестве порога для остановки можно использовать либо либо поскольку степень требуемого многочлена превышает степень предыдущего многочлена по крайней мере на 2.

Пример. Вновь рассмотрим код PC длиной 15, исправляющий тройные ошибки, с заданным формулой

причем символы на позициях, соответствующих считаются стертыми. Заметим, что многочлен (5.60) совпадает с многочленом (5.42), однако в данном случае учтены стирания. Тогда

Поскольку выполнение алгоритма Евклида должно закончиться при Применение алгоритма Евклида для решения ключевого уравнения (5.59) показано в табл. 5.8. Полученный многочлен локаторов ошибок совпадает с многочленом, найденным ранее.

Таблица 5.8. (см. скан) Решение ключевого уравнения для вадаваемого уравнением (5.69)

Поэтому корнями являются а корнями многочлена локаторов стираний

Многочлен значений ошибок имеет вид

а производная определяется как

Используя (5.61), получаем многочлен ошибок в виде и на выходе декодера имеем

Декодирование с исправлением ошибок и стираний можно осуществить также с использованием алгоритма Берлекэмпа. Один из методов применения алгоритма Берлекэмпа, в котором используется модифицированный многочлен синдрома был предложен Берлекэмпом [2]. Однако можно обойтись без вычисления

многочлена Единственным изменением, которое нужно внести в алгоритм, приведенный на рис. 5.8, является измнение начальных условий. Решение ключевого уравнения с применением алгоритма Берлекэмпа осуществляется следующим образом:

1) вычислить

2) использовать структурную схему на рис. 5.8, заменив

3) в качестве начальных условий принять

4) вычислить как ранее.

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

Однако описанная процедура не дает многочлена значений ошибок Данный многочлен должен быть вычислен по формуле (5.59) на основе После этого значения ошибок вычисляются по формуле (5.61).

Пример. Вновь рассмотрим кол PC из предыдущего примера при и заданных равенствами (5.67) и (5.68). Использование алгоритма Берлекэмпа для решения ключевого уравнения показано в табл. 5.9.

Таблица 5.9. (см. скан) Решение ключевого уравнения для задаваемых уравнениями (5.67) и (5.68), с помощью алгоритма Берлекэмпа

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