8.2. ОГРАНИЧЕНИЯ СОПРЯЖЕННОСТИ И ИДЕМПОТЕНТЫ

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

Ограничения такого рода знакомы по полю комплексных чисел. Напомним, что в ноле комплексных чисел спектр имеет вещественное обратное преобразование Фурье тогда и только когда Следующая теорема описывает множество ограничении, которые называются ограничениями (или условиями) сопряженности и устанавливают аналогичное условие для конечного поля.

Теорема 8.2.1. Пусть V есть -мерный вектор с компонентами из где делит Тогда обратное преобразование Фурье является вектором с компонентами из тогда и только тогда, когда выполняются следующие равенства:

Доказательство. По определению

В ноле характеристики для любого целого справедливо равенство Далее, если элемент поля то при всех Следовательно,

Обратно, предположим, что для всех Тогда

Пусть Так как взаимно просто с то, когда принимает все значения от 0 до число также принимает все значения от 0 до Следовательно,

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

Чтобы применить данную теорему, следующим образом разобьем числа по на подмножества, известные под названием классов сопряженных элементов:

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

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

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

Определение -ичным следом элемента поля называется сумма

Согласно теореме степень -ичного следа элемента равна ичному следу элемента следовательно, -ичный след является элементом поля Если класс сопряженных элементов, которому принадлежит содержит элементов, то равен сумме всех элементов этого класса сопряженных элементов. В противном случае число элементов в классе сопряженных делит и кратность, с которой каждый элемент входит в след.

Рис. 8.1. (см. скан) Классы сопряженных элементов.

равна получающемуся частному. Из определения следа и теоремы 4.6.10 следует, что

и что все сопряженные элементы имеют один и тот же след.

Теорема 8.2.3. Над q-ичный след принимает в каче стве своего значения каждое из чисел поля одинаково часто, а именно раз.

Доказательство. Пусть у — элемент поля элемент из след которого равен -у. Тогда является корнем многочлена

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

Одно из полезных свойств следа устанавливает следующая теорема.

Теорема 8.2.4. Квадратное уравнение

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

Доказательство. Пусть корень этого квадратного уравнения. Вычисленный в точке двоичный след соответствующего квадратичного трехчлена равен

По отношению к сложению след дистрибутивен, а следы элементов являются одним и тем же элементом поля GF (2). Следовательно,

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

Предположим теперь, что мы выбрали хорду и определили спектр

Согласно теореме 8.2.1, обратное преобразование Фурье для этого спектра является вектором над который можно представить многочленом Так как в частотной области свертка преобразуется в произведение то

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

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

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

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

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

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

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

Тогда является идемпонентом. Его корни совпадают с корнями следовательно, он является кодовым словом. Кроме того, для всех и поэтому Далее, многочлен с является кодовым словом тогда и только тогда, когда для некоторого выполняется равенство с откуда следует, что

это и доказывает теорему.