8.3. СПЕКТРАЛЬНОЕ ОПИСАНИЕ 247

И, следовательно, многочлен w (х) обладает следующим специальным свойством:

(х) = W (х) (mod X" - 1).

Произвольный многочлен w (х), удовлетворяющий условию

(х) = W {х) (mod х" - 1), называется идемпотентом.

Каждый идемпотент может быть получен следующим образом. Выберем несколько хорд и положим Wj = О, если / -принадлежит одной из них, и Wj- - 1 в противном случае. Обратное преобразование Фурье дает во временной области многочлен, который является идемпотентом, и каждый идемпотент можно построить таким способом.

Завершим этот параграф применением полученных результатов к циклическим кодам.

Теорема 8.2.5. Каждый циклический код содержит в качестве кодового слова единственный многочлен w (х), такой, что многочлен с (х) является кодовым словом тогда и только тогда, когда

с (х) W (х) с (х) (mod л:" - 1).

Многочлен w (х) является идемпотентом.

Доказательство. Пусть g (х) - порождающий многочлен, и пусть

(О, если g(ai) = О, ~ 1 1, если g{a) ф 0.

Тогда W (х) является идемпонентом. Его корни совпадают с корнями g (х), и, следовательно, он является кодовым словом. Кроме того, WjGj --= Gj для всех /, и поэтому w (х) g (х) = g (х). Далее, многочлен с (х) является кодовым словом тогда и только тогда, когда для некоторого а {х) выполняется равенство с (х) = а{х) g (х), откуда следует, что

с (х) W [х) = а{х) W (х) g{x) = а {х) g{x) = с {х) (mod х"- - 1); это и доказывает теорему. □

8.3. СПЕКТРАЛЬНОЕ ОПИСАНИЕ ЦИКЛИЧЕСКИХ КОДОВ

Каждое слово с {х) циклического кода задается многочленом степени п - 1. В несистематическом виде оно может быть записано как с{х) = g {х) d {х), где d {х) - информационный многочлен

степени й - 1. Во временной области это дает (циклическую) свертку:

Ci = 1]> gw-k))dk.

ft=0

Следовательно, в частотной области операция кодирования может быть записана в виде произведения

Cj = GjDj.

Любой удовлетворяющий этому равенству спектр задает в частотной области кодовое слово при условии, что во временной области все компоненты являются GF (д)-значными. В силу произвольности информационного спектра единственная существенная роль компонент Gj состоит в том, чтобы определить частоты, в которых стоят нулевые компоненты Cj спектра кодового слова. Таким образом, можно дать следующее альтернативное определение циклического кода. Циклическим кодом называется множество таких слов HajkGF (q), у которых все спектральные компоненты, принадлежащие заданному множеству так называемых проверочных частот j\, /„„и, равны нулю.

Хотя каждое слово циклического кода является вектором над GF (q), спектр кодового слова является вектором над GF (д™). Следовательно, циклический код может быть определен как множество GF (д)-значных обратных преобразований Фурье множества всех спектральных векторов, компоненты которых в заданном множестве частот равны нулю. Нельзя выбирать произвольный спектральный вектор, у которого стоят нули в заданном множестве частот; обратные преобразования некоторых из таких векторов могут иметь компоненты, не принадлежащие полю GF (q). Для того чтобы кодовое слово принадлежало полю GF (q), выбирать нужно только спектр, который удовлетворяет условиям сопряженности, приведенным в теореме 8.2.1.

Коды БЧХ являются такими циклическими кодами, в которых проверочные частоты выбираются последовательно. Исправляющий t ошибок код БЧХ длиной п = q" - 1 определяется как множество всех кодовых слов над GF (q), спектр которых равен нулю в заданном блоке из 2t последовательных частот.

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

Теорема 8.3.1 (граница БЧХ). Пусть п делит q" - I при некотором т. Единственным вектором из GF" (q) веса не более d - 1, имеющим d - 1 последовательных нулевых компонент спектра, является нулевой вектор.

Л (X) = П (1 - A-a-ft) = Аух + Л, 1Х- + •.. + + Л,

/г=1

Вектор А представляет собой частотный спектр, разумное определение которого сводится к тому, что его обратное преобразование = {Kj] равно нулю для каждого момента времени i, для которого Ci Ф 0. Выписанное выше произведение во временной области равно нулю == О для i = О, п- 1); следовательно, в частотной области циклическая свертка равна нулю:

Л*С = 0.

Так как Aq = 1 и = О при й > d - 1, то свертка может быть записана в виде

С] = - S Л/,С((; /е)).

Но на блоке длины d - 1 вектор С равен нулю. Следовательно, по рекурсии вектор С всюду равен нулю, так что и с должен быть нулевым вектором. □

Если п = g - 1 (или п делит q - 1), то код БЧХ является кодом Рида-Соломона; кодовое слово и его спектр лежат в одном и том же поле. Используя для вычисления спектральных компонент информационные символы, можно осуществлять кодирование непосредственно в частотной области. Каждый спектр, у которого 21 последовательных компонент равны нулю, является кодовым словом. Кодирование осуществляется следующим образом. Какие-либо 21 последовательных частот (например, первые 21) выбираются для обеспечения необходимого ограничения: символы в этих частотах полагаются равными нулю. Остальные п - 2t координат спектра заполняются информационными символами из GF {q). Тогда обратное преобразование Фурье дает (несистематическое) кодовое слово, как показано на рис. 8.2. Поскольку имеется п - 2t частот, в которых записываются информационные символы, то получается (п, п - 2)-код Рида--Соломона.

Для более общего случая кодов БЧХ кодирование является более сложным. Теперь мы имеем два поля: поле символов GF (q) и поле локаторов GF (д™), используемое для спектра. Опять 2t последовательных компонент спектра выбираются для того, чтобы

Доказательство. Обозначим через i, iy индексы v ненулевых компонент вектора с, v <. d - 1. Определим в частотной области вектор, обратное преобразование Фурье которого содержит нулевые компоненты для всех частот i, для которых Cj =ф 0. Такой вектор может быть выбран многими способами. Один из возможных выборов основывается на многочлене локаторов Л (х):