Декодирование РС–кодов в частотной области

 

При декодировании РС–кодов в качестве синдрома может быть использовано «пустое» для всех слов РС–кода спектральное окно шириной s. Действительно, если наблюдение свободно от ошибок, то внутри окна будут отсутствовать ненулевые спектральные компоненты. Следовательно, появление ненулевых компонент ДПФ вектора указывает на то, что некоторые символы переданного слова РС–кода были искажены, так что конкретный образец этих компонент может быть использован для исправления ошибок.

В дальнейшем будем полагать, что , так что

и «нулевое окно» охватывает частоты . Тогда спектральные компоненты наблюдения (в полиномиальной форме ) внутри нулевого окна определяются вектором ошибки (или, что эквивалентно, полиномом ошибки ):

.

Таким образом, первой операцией, выполняемой при декодировании в частотной области, является вычисление компонент синдрома в виде прямого ДПФ компонент наблюдения на частотах, лежащих внутри нулевого окна:

. (9.8)

Все последующие шаги направлены на экстраполяцию спектра ошибок, определенного в пределах нулевого окна, на всю частотную область. Это оказывается возможным, если только фактическое число ошибочных символов n не превосходит исправляющей способности РС–кода: .

Пусть обозначают позиции ненулевых символов в векторе ошибок:

.

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

. (9.9)

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

.

Поскольку для любого i, при котором , то при всех , тогда на основании теоремы о свертке 9.2.1

,

или, учитывая, что , получаем

, (9.10)

в котором знак «минус» может быть опущен в случае полей . Полученный результат имеет чрезвычайную важность, показывая, что компоненты ДПФ вектора ошибок образуют линейную рекуррентную последовательность памяти n, величина которой в точности равна числу ошибочных символов. Следовательно, как только значения n и коэффициентов полинома локаторов ошибок станут известными, а память n не превысит исправляющей способности t, т.е. половины ширины нулевого окна, то из значения синдрома может быть восстановлен весь спектр ошибок.

Теорема 9.4.1. Величина памяти n рекурсии спектральных компонент вектора ошибок, где n – истинное число ошибочных символов, как минимум, равна единице.

В зависимости от кратности исправляемых ошибок используются различные алгоритмы определения коэффициентов многочлена локаторов . В том случае, когда РС–код ориентирован на исправление ошибок большой кратности, эффективным оказывается метод Берлекэмпа–Месси. Суть его состоит в сведении данной задачи к нахождению коэффициентов многочлена, который задает линейный регистр сдвига минимальной длины с обратной связью, генерирующий известную последовательность компонентов синдрома. Если же БЧХ–код рассчитан на исправление ошибок малой кратности, то используется метод Питерсона–Горенстейна–Цирлера, основу которого составляет следующая теорема.

Составим матрицу размерности вида

.

Теорема 9.4.2. Матрица является вырожденной, если ее порядок , и невырожденной, если , где n – фактическое число ошибочных символов.

На основании приведенных результатов приходим к следующей процедуре декодирования:

1. Вычисление компонентов синдрома с помощью прямого ДПФ (9.8) вектора наблюдений в пределах нулевого окна;

2. Составление матрицы , начиная с и уменьшая значение m на единицу всякий раз, когда оказывается вырожденной. Если же – не вырождена, то становится известным величина n.

3. При известном значении n с помощью рекурсии (9.10) составляется линейная система из n уравнений с неизвестными:

(9.11)

в которой используются вычисленные на первом этапе компоненты синдрома , где , и которая в матричной форме представляется как

,

где и . Решение системы уравнений (9.11)

,

дает коэффициенты полинома локаторов ошибок, т.е. коэффициенты рекурсии спектра ошибок.

4. С помощью рекурсии (9.10) восстанавливается весь спектр ошибок

.

5. Осуществляется обратное ДПФ

,

для получения оценки вектора ошибок .

6. Вычитание (суммирование в случае ) оценки из вектора наблюдений дает оценку принятого кодового слова: .

С практической точки рациональный путь нахождения значений памяти и коэффициентов рекурсии предоставляет алгоритм Берлекэмпа–Месси, основой которого служит структура обычного регистра сдвига с линейной обратной связью (LFSR), генерирующего линейную рекуррентную последовательность , представленная на рис. 9.2. При начальной загрузке данная схема формирует на выходе остальные элементы согласно соотношению

.

Алгоритм Берлекэмпа–Месси представляет собой итеративную процедуру, начинающуюся со значения и начальной загрузки . На j –м шаге итераций алгоритм берет следующий по порядку компонент синдрома и строит LFSR минимальной длины, генерирующий последовательность . Если регистр, построенный на предыдущем шаге итераций, способен сформировать указанную последовательность, алгоритм прямо переходит к следующему шагу итераций. В противном случае, перед переходом осуществляется пересчет коэффициентов и, если необходимо, увеличивается значение памяти.

Процедура декодирования завершается одним из трех возможных исходов:

· если фактическое число ошибок не превышает исправляющей способности кода , то процедура завершается правильным декодированием;

· если фактическое число ошибок превосходит исправляющую способность кода t (), а наблюдение расположено на расстоянии меньшем t от некоторого другого кодового слова , то принимается решение о приеме этого ошибочного слова без возможности установления этой ситуации (неправильное декодирование);

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

Геометрическая интерпретация указанных трех ситуаций представлена на рис. 9.3, на котором вектора и отвечают истинному и ложному кодовым словам соответственно, а индексация вектора наблюдений произведена в соответствии с порядком приведенных выше исходов декодирования.

Пример 9.4.1. Рассмотрим (7,3) РС–код из примера 9.1.1, использующий конструкцию поля , которое строится на основе примитивного полинома (см. примет 8.2.5), т.е. с помощью примитивного элемента, удовлетворяющего соотношению . Расстояние кода и, значит, код исправляет любые ошибки кратности один и два. Пусть вектор наблюдения задан в виде , так что .

Первоначально вычислим значения компонентов синдрома с помощью прямого ДПФ (9.8) вектора наблюдений в пределах нулевого окна, т.е. на частотах , где :

,

.

Составим матрицу размерности (2´2):

,

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

Таким образом, линейная система состоит только из одного уравнения вида: , так что , откуда . В итоге приходим к рекурсии вида , которая начинается с , т.е. . Восстановив с помощью рекурсии весь спектр ошибки, первые четыре компонента которого совпадают с компонентами синдрома, осуществляем обратное ДПФ, которое приводит к следующему результату

Так, например:

.

Таким образом, оценка вектора ошибки содержит единственный ненулевой элемент z на четвертой позиции (при начале индексации с нуля) и нулевые элементы на всех остальных. Так что на выходе декодера появится решение о приеме сигнала или в виде полинома . Не составляет труда убедиться, что полученный вектор является словом РС–кода (например, проверить, что его синдром равен нулю):

,

.

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

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