Для вычисления

s(x) = g (х) d (х) (mod х

заменим многочлен d {х) = Х1 diX от одной переменной много-членом от двух переменных, полагая п = пп :

d{y, z)= £ di+ntyz.

,- =0 г=о

Исходный многочлен получается из этого многочлена подстановкой - л: и г = jc . Аналогично определим g{y, г) и положим 5 {у, 2) = g{y,z)d {у, Z) (mod г +1).

Искомый многочлен s (л) получается из этого многочлена по правилу

S (х) = S {X, х ) (mod + 1),

не требующему никаких умножений. Следовательно, наша задача свелась к вычислению многочлена s {у, г).

Рассмотрим линейную свертку s [у) = g (у) d (у), в которой коэффициенты многочленов s (у), g (у) d {у) в свою очередь представляют собой многочлены от г и умножение этих многочленов от г понимается как умножение по модулю г + 1.

Возможно, эту процедуру легче понять, если выбрать л = 2 и заменить z на /. Тогда проделанный шаг обозначает замену произведения вещественных многочленов по модулю х + 1 произведением комплексных многочленов по модулю х -)- 1. Преимущество, даваемое таким шагом, состоит в возможности применения алгоритма Кука-Тоома с корнями в точках ±/. В общем случае можно г понимать как корень степени п из -1.

Воспользуемся алгоритмом Кука-Тоома, допуская в качестве корней степени формальной переменной г. (Формальное утверждение состоит в том, что мы выбираем корни в расширении поля, получаемом присоединением г.) Тогда при приведении по модулю - 2 коэффициенты многочленов g (у) и d {у) становятся многочленами от г. Так как они уже являются многочленами от г, то проделанный шаг не приводит к какому бы то нн было усложнению, если позаботиться о том, чтобы степень этих многочленов от Z не начинала превышать свою первоначальную границу. Это приводит к некоторому неравенству, связывающему делители п и п числа п.

Алгоритм Кука-Тоома можно использовать для вычисления линейной свертки, если корни выбранного многочлена расположены в точках ztz при I меньших п . Степень многочлена

т(у) = у{у- оо) п (у - г) {у + г)

равна 2п + 2, так что его можно использовать для вычисления свертки S {у) степени не более 2п + 1. Если степень многочлена S (у) меньше, то часть множителей можно из т (у) отбросить. Мы будем пользоваться многочленом т (у), удовлетворяющим условию deg m (у) = deg s (у) + 1 = 2/j - I.

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

Итеративный алгоритм применим, если 2л - 1 < 2л -г 1. Если это условие выполнено, то вычисление произведения многочленов по модулю + 1 разбивается на вычисления 2л - 1 произведений многочленов по модулю л -f 1. В свою очередь, это произведение повторением описанной процедуры может быть разбито на еще более мелкие подзадачи так, как это показано на рис. 7.6. (На диаграмме выпущены детали, связанные с критерием выбора разложения лл = л и с общими правилами предсложений и постсложений.) Число необходимых в алгоритме умножений и сложений описывается рекуррентными равенствами

М (л) = (2л - 1) М (л ),

Л (л) - (2л - 1) Л (п ) + Al (л) + Ла (л).

где Al (rt) обозначает число предсложений, связанных с приведением d (у) по модулю множителей многочлена т (у), а Ai (п) обозначает число сложений, необходимых для восстановления многочлена S (у) по его вычетам. Истинные значения величин Ai (л) и Аг (л) зависят от выбора 2п - 1 множителей разложения многочлена т {у).

Например, вычисление произведения многочленов по модулю х + 1 можно свести к вычислению трех произведений многочленов по модулю х -f- I, каждое из которых требует трех умножений; это дает алгоритм, содержащий девять умножений. Аналогично, вычисление произведения по модулю + 1 можно свести к вычислению семи произведений многочленов по модулю л: + 1, что приведет к алгоритму с полным числом умножений, равным 63 или 49 в зависимости от выбора алгоритма вычисления произведения многочленов по модулю + 1. Характеристики описанного итеративного алгоритма в зависимости от выбора составляющих подалгоритмов приведены на рис. 7.7. Варианты определяются способом разложения длины л на множители л и л ; п можно разложить далее. Все они выписаны в последнем столбце таблицы.

Вход

в процедуру mod хЛ + 1

Нет \ Да п - \

Приведение по mod (у ±2)

Вызов

процедуры mod лг + 1 2п - 1

Вызов алеоритма

Интерполяция по Лагранжу

Выход из процедуры mod л: + 1 Рис. 7.6. Принципиальная схема итеративного алгоритма.

Несколько видоизмененная версия алгоритма получается, если выбрать

mix) = П (х 2)(х + г) =

п\х-г) (modz + l).

Теперь степень основного модуля m (х) равна 2п , хотя достаточной является степень 2п - \. Следовательно, такой выбор многочлена т (х) приводит к одному дополнительному (по сравне-

Рве. 7.7. Характеристики некоторых алгоритмов вычисления произведения многочленов по модулю -f- 1.

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

7.5. Полиномиальное

представление расширений полей

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

Преобразование Фурье длины п отображает вектор длины п с рациональными компонентами в вектор длины п, компоненты

которого принадлежат некоторому подмножеству комплексных чисел, на самом деле счетному подмножеству. Обычно в исследованиях преобразования Фурье в качестве значений компонент выходного вектора допускаются произвольные комплексные числа, которые в практических вычислениях ограничиваются конечным множеством путем фиксации разрядности допустимых чисел. Это можно сделать до некоторой степени произвольно; условность представления проявляется в выборе необходимой длины слова с учетом допустимой погрешности округления. Даже тогда, когда областью определения преобразования Фурье является множество целых чисел, для точного вычисления преобразования необхо -димо, чтобы разрядность двоичного представления числа была бесконечной.

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

Пусть V представляет собой вектор длины п с рациональными компонентами и пусть m = е- . Тогда задаваемый преобразованием Фурье вектор

V = £ fe = 0.....п-\.

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

Пусть над полем рациональных чисел разложение многочлена X - 1 на простые множители дается равенством

х - 1 = р (x)pi {х)...р, (X). Простые делители являются круговыми многочленами, и для малых п их коэффициенты равны -1, О, 1. Так как элемент со является корнем многочлена х - 1, то он должен быть корнем одного из круговых многочленов, скажем, корнем многочлена р (х) степени пг со старшим коэффициентом, равным единице:

р (х) = х + р , ,х -1 + ... + р,х + рс. Так как р (ш) = О, то

а, = -Рт.! - - . . - PiO) - р .

Следовательно, (о может быть выражен в виде линейной комбинации меньших степеней элемента щ. Для меньших степеней

элемента ш такое представление невозможно, так как в противном случае ш <1ыл бы корнем многочлена степени меньше, чем степень многочлена р (х).

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

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

<J = Om-iX - + a .jX -2 + ... + а,х + а

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

(х-- 1) = (х + 1)(х /* + 1)...(х+1)(х- 1).

Круговой многочлен х / + 1 приводит к расширению поля Q, все элементы которого представляют собой многочлены с рациональными коэффициентами степени меньше, чем п/2. Сложением в поле является сложение многочленов, а умножением - умножение многочленов по модулю х + 1.

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

в поле дается равенством х--+ {х - I) = х- х -

2i- i X--1---X--g-x* + -X - X--.

Полиномиальное представление расширения полей относится не только к полю рациональных чисел. Его можно использовать и для расширений поля комплексных чисел. Например, поле комплексных рациональных чисел - это множество комплексных чисел вида а = а + /6, где а и Ь - рациональные числа. Это подмножество является подполем поля комплексных чисел, которое иногда обозначается через С (/). Во многих приложениях цифровой обработки сигналов компоненты обрабатываемых век-