2.2.7. Синдромные многочлены

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

Прежде всего синдромный многочлен можно определить как многочлен степени , являющийся остатком от деления принятой последовательности на порождающий многочлен, т. е.

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

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

Положим

Тот факт, что эти два представления синдрома содержат одну и ту же информацию, непосредственно следует из китайской теоремы об остатках для многочленов. Согласно этой теореме существует взаимно однозначное соответствие между многочленами и наборами многочленов (Эта точка зрения подробно развивается в гл. 2 книги Берлекэмпа [2], к которой мы отсылаем заинтересованного читателя.) Большинство читателей-инженеров могут убедиться в его справедливости, рассмотрев приводимый далее пример. Этот пример показывает также, как выглядит преобразование двух различных представлений друг в друга.

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

Если задавать синдром как ,

то соответствующая проверочная матрица имеет вид

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

Обратное преобразование можно получить, решив эту систему уравнений. Оно имеет вид

рис. 2.8 показана схема вычисления в которой для вычисления используется (2.17). На рис. 2.9 показана схема, согласно которой вначале вычисляются а

Рис. 2.8. Схема вычисления и последующего вычисления

Рис. 2.9. Схема вычисления и последующего вычисления

затем используется (2.18) для вычисления На практике это последнее преобразование применяется очень редко, и цель настоящего примера состоит лишь в том, чтобы указать на его существование.

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

где корень — корень Эта форма синдрома соответствует проверочной матрице в виде (2.15). В предыдущем примере проверочная матрица задается в виде

Легко показать, что можно вычислить по Н с помощью следующих формул:

Рис. 2.10. Схема вычисления по

Рис. 2.11. Схема вычисления непосредственно по

Схема, по которой производятся эти вычисления, показана на рис. 2.10. Матрицу можно вычислить и непосредственно, используя схему на рис. 2.11. Связи для схемы вычисления можно получить из второго множества столбцов в (2.19). Исследуя что множество, можно заметить, что при одном сдвиге содержимое ячейки 1 должно переходить в ячейки 1 и 2, содержимое ячейки 2 — в ячейки 2 и 3 и содержимое ячейки 3 — в ячейки 1, 2 и 3.