Главная Промышленная автоматика.

7.2. АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

Очевидно, что преобразование Фурье вектора а из Л" и обратное к нему МОЖНО вычислить за время Од (и") в предположении, что каждая арифметическая операция над элементами кольца R выполняется за один шаг. Однако если п - степень числа 2, то можно сделать это быстрее: известен алгоритм сложности Од (и log «), вычисляющий преобразование Фурье или обратное к нему, и мы думаем, что эта оценка неулучшаема. Приведем только алгоритм прямого преобразования Фурье. Алгоритм обратного преобразования аналогичен и предоставляется читателю. Основная идея быстрого преобразования Фурье (БПФ) является по своей природе алгебраической; МЫ находим подобие между частями тех п сумм, которые порождаются умножением Аа. Во всем этом разделе мы считаем, что 71=2* для некоторого целого числа k.

Вспомним, что вычисление вектора Л а эквивалентно вычислению

полинома р{х)=У,а}Х в точках д:=сй«, со . . ., ш»-*. Но вычисле-/Го

ние р {х) в точке х=а равносильно нахождению остатка от деления р{х) на X-а. (Чтобы увидеть это, можно записать р(х) в виде (х-а) q{x)+c, где с - постоянная. Тогда р{а)=с.) Таким образом, вычисление преобразования Фурье сводится к нахождению остатка

от деления полинома р{х)-а]Х степени п-1 на каждый из

полиномов X-(0°, X-0)1, . . ., д;-(0"-.

Обычное последовательное деление р{х) на каждый из полиномов X-ш дает процесс сложности О (и*). Чтобы построить более быстрый алгоритм, перемножим попарно х-ш, затем перемножим попарно получившиеся п/2 полиномов и т. д., пока не останется два полинома qi и q, каждый из которых равен произведению половины полиномов X-ш. Далее делим р {х) на qi и q. Соответствующие остатки ri{x) и Га(х) имеют степень не более п/2-1 каждый. Для каждого корня со, для которого qi делится без остатка на д;-ш, нахождение остатка от деления р {х) на х-т равносильно нахождению остатка от деления ri{x) на х-ш. Аналогичное утверждение верно для каждого корня ш, для которого q делится без остатка на X-со. Поэтому вычисление остатков от деления р {х) на каждый из полиномов X-ш равносильно вычислению остатков от деления fiix) и Га(х) на каждый из п/2 подходящих полиномов д:-со. Рекурсивное применение этой тактики "разделяй и властвуй" гораздо эффективнее прямолинейного метода деления р {х) на каждый полином ж-со.

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



можно добиться, чтобы все произведения имели вид х-ш, и это еще уменьшит время, затрачиваемое на умножения и деления полиномов. Изложим все эти идеи точнее.

Пусть Со, Си . . ., Сп-1- перестановка элементов со", со*, . . . .. которую мы конкретизируем позже. Определим полиномы

/я, где От и/является целым кратным числа 2", 0</<2*-1:

;+2«-1

Таким образом, oft= (х-Со) (x-Ci) . . . (x-Cn-i), qio=x-Ci и в общем случае

Существует 2*"" полиномов со вторым нижним индексом т, и каждый полином x-Ci делит в точности один из них. Полиномы изображены на рис. 7.1. (См. также разд. 8.4 и 8.5.)

Наша цель - вычислить остаток от деления р (х) на (д:) для каждого /. Для этого вычислим остатки от деления р (х) на (х) для каждого qi„, начиная с m=k-1 и кончая т=0.

Допустим, что уже вычислены полиномы степени 2"-1, остающиеся от деления р(х) на qi„{x). (Можно считать, что гр{х).) Поскольку q,„=qq", где q=qi,„-i и (7"=(7j+2»-,m-i, мы утверждаем, что остаток от деления р (д;) на q (х) равен остатку от деления

на q (х) и аналогичное утверждение верно и для q" (х). Для до-

2*-1-1

П ix-cj) j-o


Рис. 7.1. Полиномы qi.



казательства положим

p(x) = hi{x) q(x) + r,,,n-i, где степень полинома r,,„ i не превосходит 2»-i-1. Так как p{x) = hi(x) qi„(x) + ri„,

h, {X) q {X) + г,. = Л, (X) qi„ {х) + r,„. (7.5)

Разделим обе части равенства (7.5) на q(х)\ так как hi(x) q{x) и Л,(д:) qin(x) делятся без остатка, то остаток от деления на (д:) равен г.„ 1.

Таким образом, можно получить остатки от деления р{х) на (д;) и р(х) на qix), разделив на q {х) и q" (х) полином г,„ степени 2*""-1, а не полином р(х) степени 2*-1. Этот метод выполнения делений сам по себе дает экономию времени. Но можно делать еще больше. Выбрав подходящий порядок элементов с, d, . . ., c„ i для степеней ш, можно добиться, чтобы каждый полином qi имел вид дг"-со* при некотором s. Деление на такие полиномы выполняется особенно просто.

Лемма 7.2. Пусть n=2* м ш - примитивный корень степени п из единицы. Пусть [dodi. . .dy-il - двоичное представление целого числа и где 0</<2* *), а rev О") - целое число с двоичным представле-

1 + 21П-1

нием [d-i d-f -do). Обозначим c=(u™vV) « q=. п (x-Cj). Тогда qi=x-(Si"W).

Доказательство. Доказательство проводится индукцией по т. Базис, т. е. случай т=0, тривиален, ибо по определению qia=x-Cf=x-(u"v<). Для проведения шага индукции заметим, что при т>0

Яш = Ql, m-lЧl*-. т-1 =

где 1/2"- - четное число между О и 2*-1. Тогда

поскольку сй2*"=(й"/2 =-1. Следовательно,

q = х"" со ( а"»-») = х*"*-со" (/2"*)

поскольку rev(20=Va rev(0- □

Пример 7.1. Если п=8, то список Со, Ci, .... с, есть со", со*, а, (О, ш», (05, (О», col. Полиномы qi„ иллюстрируются на рис. 7.2.

То есть 1=к-1-(2.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 [93] 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.002