и в силу однозначности преобразования Фурье гЯ = Vc для всех i. Таким образом, Vi являются корнями многочлена - х при всех i, и этими корнями исчерпывается все поле GF (q). □

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

Ajlhjq, .... Г-}, где mj - наименьшее целое положительное число, удовлетворяющее равенству fq"i = j (mod n). В силу конечности поля такое mj всегда существует. Например, если (/ = 2 и я = 7, то классы сопряженных «элементов имеют вид

Ло={0}, Л1=1, 2, 4}, Л, = 3, 6, 5Ь

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

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

Определение 8.2.2. q-ичным следом элемента Р поля GF {q") называется сумма

tr(P)= 1]р.

Согласно теореме 4.6.10, q-я степень (/-ичного следа элемента Р равна (/-ичному следу элемента р, и, следовательно, (/-ичный след является элементом поля GF (q). Если класс сопряженных элементов, которому принадлежит р, содержит т элементов, то tr (Р) равен сумме всех элементов этого класса сопряженных элементов. В противном случае число элементов в классе сопряженных делит т, и кратность, с которой каждый элемент входит в след.

По мобулю 7

По мойулю 63

По мойулю 31

По мо5улю 12,7

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

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

tr ф+у) = tr (Р) + tr (у)

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

Согласно теореме 8.2.1, обратное преобразование Фурье для этого спектра является вектором над GF (q), который можно представить многочленом w (х). Так как в частотной области свертка (х) преобразуется в произведение W}, то W) = Wj,

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

Доказательство. Пусть у - элемент поля GF (q), а Р - элемент из GF ((/"), след которого равен у. Тогда Р является корнем многочлена

XQ-"- + -I-----хЧ-\~Х-у.

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

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

Теорема 8.2.4. Квадратное уравнение х + X + а О,

где а - элеменЬг поля GF (2"), имеет корни в поле GF (2") тогда и только тогда, когда двоичный след элемента а равен ну.т.

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

tr (Р + р + а) = tr (0) = 0.

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

tr (а) = 0.

Обратно, каждое Р является корнем многочлена х + х + а для некоторого а, а именно для а, равного -(Р -- Р). Всего имеется 2"- таких а, для которых след равен нулю, и этого в точности хватает, чтобы составить 2™" уравнений с двумя корнями каждое. Доказательство закончено. □

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

О, jAu, 1. УЛ-