5.2. Коды БЧХ

Коды БЧХ [39—41] представляют собой важный класс циклических кодов, исправляющих кратные ошибки. Оставшаяся часть этой главы посвящена исследованию параметров этих кодов и описанию методов их реализации. В подразд. 2.3.1 коды БЧХ были определены через корни порождающего многочлена степени Каждое кодовое слово этого кода имеет вид где многочлен данных степени Умножение многочленов эквивалентно свертке во временной области, так что

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

Определение. Примитивным кодом БЧХ над полем GF (q) с длиной блока исправляющим ошибок, является множество всех слов над для которых последовательных компонентов спектра с номерами равны 0.

Тот факт, что последовательных степеней а — корни (или что спектр содержит последовательных нулевых компонентов), является важным свойством кодов БЧХ, позволяющим исправлять ошибок. Это вытекает из следующей теоремы.

Теорема (Граница БЧХ). Пусть спектр С ненулевого вектора с содержит последовательных нулевых компонентов для Тогда с содержит по крайней мере ненулевых компонентов.

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

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

Однако степень не превышает так что (5.7) превращается в равенство

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

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

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

Коды БЧХ образуют подкласс циклических кодов. При заданном порождающем многочлене кодирование можно осуществлять с помощью регистра сдвига с обратными связями, показанного на рис. 2.4. Этот подход излагался в гл. 2, и здесь возвращаться к нему не будем. Кодирование можно проводить, используя также метод преобразований, как это описано в статье [37]. Хотя этот подход является интересным, он, скорее всего, не имеет практического значения.

Важный подкласс кодов БЧХ составляют коды Рида — Соломона [42], рассмотренные в подразд. 2.3.1. Для этих кодов компоненты кодовых слов и их преобразований лежат в Порождающий многочлен имеет вид

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