ft = о,..., га - I,

его преобразования Фурье принадлежат полю Q (ш); в более общем случае, если компоненты v принадлежат Q (ш), то компоненты его преобразования Фурье также принадлежат Q (ю).

Пусть степень кругового многочлена, корнем которого является (О, равна т. Тогда каждый элемент в Q (со) записывается

в виде многочлена над Q степени, меньшей т. В полиномиальной записи преобразование Фурье имеет вид

Vft = £ х*а, (mod р (х)), А = О..... л - 1.

Эта формула вычисляется проще, так как умножение на х сводится к операциям над индексами, а приведение по модулю р (х) содержит не более т сложений. Можно воспользоваться любым БПФ-алгоритмом, например БПФ-алгоритмом Кули-Тьюки. но все умножения представляют собой умножения на х, и, следовательно, требуют для своего выполнения не более т вещественных сложений и не содержат вещественных умножений. Аналогично, ка.ждое сложение является сложением многочленов и выполняется с т вещественными сложениями.

Применительно ко, входу с рациональными компонентами преобразование Фурье можно рассматривать как отображение векторов из многочленов первой степени в векторы из многочленов степени m - 1. В более общем случае, преобразование Фурье в такой трактовке отображает векторы, компонентами которых служат многочлены степени ш - 1, в векторы из многочленов степени т - 1.

Справедливость теоремы о свертке не зависит от того, как именно представлены числа в данной арифметической системе. Она применима в равной степени как к векторам, компоненты которых записаны в полиномиальной форме, так и к векторам, компоненты которых записаны в обычном виде. Следовательно, для вычисления циклической свертки последовательностей с рациональными компонентами, St = g{i,i~k))dk, можно взять пре-

образование Фурье векторов g и d в поле Q , вычислить в частотной области покомпонентное произведение Sj = GDj и взять обратное преобразование Фурье. В полиномиальной записи поля Q оба преобразования Фурье при этом не содержат умножений. Покомпонентное спектральное произведение, однако, теперь является произведением многочленов по модулю р (х), и, следовательно, требует большого числа вещественных умножений. Сложность вычислений переместилась с одного этапа на другой. Усложнение вычисления спектрального произведения сводит на нет выигрыш, полученный в преобразованиях Фурье. Позже мы увидим, что при вычислении двумерной циклической свертки все же можно получить выигрыш от полиномиального представления.

Например, пусть п = 64; круговой многочлен равен р (х) = = х -f 1. Элементы поля Q (ш) представляют собой многочлены степени 31 и задаются списком из 32 рациональных чисел. Каждое

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

Поле комплексных рациональных чисел можно расширить, присоединив корень оз степени п из единицы. Это дает наименьшее расширение Q (в), в котором имеется преобразование Фурье длины п. Если Q (ш) содержит / (т. е. содержит корень многочлена х + 1), то такое расширение Q (ш) содержит все комплексные рациональные числа. Это именно то расширение, которое нам нужно. Если круговой многочлен равен х + 1 для некоторого четного числа г, то это всегда так. В противном случае элемент ; надо присоединять.

Пусть п не равно степени двойки, ш обозначает корень степени п из единицы, а р (х) обозначает круговой многочлен степени т, корнем которого ш является. Тогда расширение Q (/, бТГ или, в более простых обозначениях, Q (/) , представляет собой) множество многочленов с коэффициентами из поля Q {/), степени которых не превосходят т - . Сложение в поле совпадает со сложением многочленов, а умножение - с умножением многочленой по модулю р (х). Коэффициенты этих многочленов складываются и вычитаются как комплексные числа.

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

7.6. Свертка в полиномиальных расширениях полей

Если V - вектор с рациональными компонентами, то компоненты

Vl, А = 0,..., п - 1,

где арифметика задается как полиномиальная арифметика поля С . Ядро преобразования теперь вместо х равно х . При таком определении преобразования Фурье, так же как и ранее, существует и обратное к нему преобразование и справедлива теорема о свертке.

7.7. Полиномиальное преобразование Нуссбаумера

Преобразования, построенные как преобразования Фурье в полиномиальных расширениях полей, заслуживают самостоятельного исследования. Мы определили их для поля рациональных чисел, так что коэффициенты всех многочленов рациональны. Так как построенное преобразование обратимо, то оно задает

некоторое множество тождеств для многочленов с рациональными коэффициентами. Тождества остаются справедливыми, даже если в качестве коэффициентов многочленов допустить вещественные (или комплексные) числа.

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

В кольце многочленов по модулю р (х) полиномиальное преобразование определяется равенством

Vx () = > (X) о, (X), ft = О..... п-\,

где (В (х) представляет собой элемент порядка п и умножение, конечно, является кольцевым умножением многочленов по модулю р (х). Наше рассмотрение будет ограничено случаем, когда ш (х) = X и многочлен р (х) делит х - 1. Как представляется, никакие другие случаи не имеют какого-либо реального практического интереса.

Определение 7.7.1. Пусть р (х) - некоторый многочлен степени т и пусть многочлены Vi (х), i = О..... п - 1, над полем F

имеют степени не более т - 1 и представляют собой компоненты полиномиального вектора. Полиномиальным преобразованием этого вектора называется вектор с компонентами

Vfc (х) = Б x t)j (х) (mod р (х)), k = 0..... п-1.

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

Ценность полиномиального преобразования обуславливается двумя теоремами: теоремой о существовании обратного преобразования и теоремой о свертке. Оба эти утверждения, конечно, сразу вытекают из возможности интерпретации полиномиального преобразования как преобразования Фурье, подобно тому, как это делалось в предыдущем разделе. Тем не менее поучительно дать более прямое доказательство.

Пусть п обозначает наименьшее целое число, для которого р (х) делит х - 1. В доказательстве следующей теоремы используется тот факт, что если многочлен а (х) делит х - 1, то

произведение Si, = GDt, является произведением многочленов по модулю + 1. Этот многочлен неприводцм, так что для каждого такого произведения необходимо по меньшей мере 2-32- 1 вещественное умножение. На самом деле число умножений существенно больше 63; практически используемый 32-точечный алгоритм, приведенный на рис. 7.7, содержит 147 умножений.

Таким образом, каждая из 64 компонент преобразования Фурье требует 147 вещественных умножений. Эго существенно больше, чем число вещественных умножений, необходимых при использовании общепринятого для этого случая БПФ-алгоритма.

На самом деле величины 5 не являются произвольными, а должны удовлетворять некоторым ограничениям, связанным с тем, что обратное преобразование Фурье должно иметь рациональные компоненты. 64 компоненты Sj обратного преобразования Фурье представляют собой 64 многочлена, каждый из которых задается 32 рациональными числами. На самом деле, 31 из этих чисел равны нулю, так как каждый из многочленов является многочленом нулевой степени. Это позволяет выписать ограничения, которым должны удовлетворять величины S, и окажется, что 64 из 147 этих величин нет надобности вычислять. Детальное выписывание этой процедуры, однако, приводит к алгоритму, очень похожему на алгоритм, основанный на китайской теореме об остатках, который проще выписать непосредственно. Поэтому мы не будет продолжать рассмотрение этой процедуры.

В полиномиальном расширении поля, Q , можно определить и более короткие преобразования Фурье. Предположим, что число п является составным: п = пп . Тогда и-точечное преобразование Фурье определяется равенством

250 Гл. 7. Быстрые алгоритмы и многомерные свертки .ДЛЯ произвольного многочлена / (д:) выполняется равенство

( ) If W1 = ш [/ (Щ.

Начнем с простейшего случая, когда число п просто.

Теорема 7.7.2. Предположим, что многочлен р (х) над полем F степени т делит многочлен х - 1, причем число п является простым. Тогда полиномиальный вектор v (х) длины п, компонентами которого являются многочлены степени т - I, и его полиномиальное преобразование V (д:) связаны соотношениями

Vu (х) = S x Vt (х) (mod р (х)), k = 0,... п - I,

W =4-2 () (mod(p(x)), < = 0..., n-I.

Доказательство. Исключая тривиальный случай, можно полагать, что степень многочлена р (х) равна по меньшей мере двум. Вычислим правую часть второго равенства:

=4-2 .w2 +

(mod p (x)) =

(mod p (x)).

Вычислим внутреннюю сумму. Если i равно /, то так как р (х) делит х - \, имеем:

п-1 п-I п-1

L 2 =4-2 =4- 2 -1)=

кО к=0 fe-0

= 1 (mQd р (х)).

hpn i, не равном I, воспользуемся тождеством, справедливым в кольце:

Так как г = 1 ni - i не кратно п, то

\ - X фО (mod х - 1),

в то время, как

I -X- =0 (mod X - 1).

Так как р (х) делит х - 1, то отсюда вытекает, что х =0 (mod р (х)).

Итак, мы доказали, что

1, если I = i (mod р (х)), О, если 1ф1 {mod р (х)).

ft=0

Следовательно,

±. 2 х<-) У, (X) = у, (X) (mod (х)).

что и завершает доказательство. □

Так как л: = 1, то обратное полиномиальное преобразование может быть записано в более простом виде

W = 4-2 *W (modp(x)),

хотя формально х * не является многочленом. Точно так же, как умножение на х выполняется с помощью переиндексации коэффициентов и приведения х по модулю р (х), умножение на,х также можно выполнить с помощью переиндексации коэф-фициентов и приведения по модулю р (х), причем для исключения х надо воспользоваться тем, что px + Pm-iX - Н-----h

+ р (х) + Ро = 0> так что

x- = Ро [рх - + р-.х - +...-[- р,].

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

Теорема 7.7.3 (теорема о свертке). Если в кольце многочленов по модулю р (х) вектор .чногочленов с компонентами s, (х), i = = 0, п - 1, связи с векторами многочленов, имеющи.чи компоненты gi (х) и di (х); i = О, л - 1, соотношением циклической свертки многочленов

Si{x)= gi.,(x)d,(x) (modp(x)),

то полиномиальный спектр (х) связи со спектрами (х) и (х) покомпонентным произведением многочленов

Sh (х) = Gj (х) Dj (х) (mod р (х)), * = О.....л - 1.