Главная Промышленная автоматика. Доказательство. Каждое выполнение строк 6 и 7 занимает Од (2") шагов. При фиксированном т цикл в строках 3-7 повторяется n/2"+ раз, занимая в целом время Од (п), не зависящее от т. Внешний цикл, начинающийся в строке 2, выполняется log п раз, занимая в целом время Од(п log п). Цикл в строке 8 не требует выполнения арифметических операций. □ В теореме 7.4 мы предполагали, что число п фиксировано. Поэтому степени элемента со, а также значения s и rev (I), получаемые из I в строках 5 и 8, можно вычислять заранее и использовать как постоянные в неветвящейся программе. Если же надо, чтобы п было параметром, можно вычислить степени элемента ш и запомнить их в виде таблицы за О (п) шагов работы РАМ. Более того, хотя на вычисление s и rev(/) в строках 5 и 8 тратится О (log п) шагов, всего производится не более Зп таких вычислений, так что весь алгоритм при реализации на РАМ имеет временную сложность О(п logn). Следствие 1. Свертку а©Ь, где а и Ъ - векторы размерности п, можно вычислить за Од (п log п) ишгов. Доказательство. В силу теорем 7.1, 7.3 и 7.4. □ Следствие 2. Положительно и отрицательно обернутые свертки векторов аиЬ можно вычислить за Оа(п log п) ишгов. Алгоритм 7.1 был изложен для того, чтобы пояснить интуитивные соображения, лежащие в основе его конструкции. На самом деле при вычислении БПФ можно работать лишь с коэффициентами и тем самым упростить алгоритм. Это реализовано в алгоритме 7.2. Алгоритм 7.2. Упрощенный БПФ-алгоритм Вход. Вектор а=[ао, aj, . . ., a„-il, где п=2* для некоторого целого числа k. Выход. Вектор F(a)=[bo. Ьи • . ., bn-iV, где btajd) при 0<i<n. Метод. Применяем программу на рис. 7.4. Для облегчения понимания вводим временный массив S, чтобы хранить результаты предыдущего шага. На практике эти вычисления можно осуществлять на том же месте. □ Когда строка 3 выполняется первый раз, коэффициенты полинома p{x)=yaiX хранятся в массиве S. Во время первого выполнения строки 6 полином р (х) делится на х"-1 и д:"-(й"/2. Получаются остатки я/2-1 n/2-l 2 {ai+ai+n/i)x и 2 (ai + (i>"ai+„/a)x. begin 1. for iO until 2*-1 do R[q*-ai; 2. for /*-0 until k-l do begin 3. for i*-0 until 2*-1 do S[t]-i?[t]; 4. for i*-0 until 2*-1 do begin 5. пусть [doi-. .d.j]-двоичное представление целого числа i; 6. R[[d,.. .d. ,]]5[[d,.. .d, M-M- • + + . .</.o.. .o]5[fdo.. .d, ,ld,,,.. .d, JJ end; 7. for t-O until 2*-1 do end Рис. 7.4. Упрощенный БПФ-алгоритм. ««0+*4 "l+b *2+*e *3+77 Й5+(11*<74 (7,+<yVj а+ШОщ U+WO ao+Oi a*-as ao+ a,+as /7(1 +i72 Рис. 7.5. Иллюстрация вычисления БПФ с помощью алгоритма 7.2. Некоторые полиномы-остатки опущены за недостатком места. Их коэффициенты хранятся в массиве S при втором выполнении строки 3. Коэффициенты первого остатка занимают первую половину массива S, а второго остатка - вторую половину S. При втором выполнении строки 6 каждый из этих двух полиномов-остатков делится на два полинома вида х"/*-ш*. Это дает четыре остатка, каждый степени п/4-1. Их коэффициенты при третьем выполнении строки 3 запоминаются в S и т. д. Строка 7 реорган зует компоненты ответа так, чтобы они шли в правильном порядке. Она нужна потому, что корни из единицы были переставлены, чтобы устранить члены, получающиеся от перекрестных умножений при вычислении произведений полиномов д:-со. Этот процесс при п=8 частично проиллюстрирован на рис. 7.5. 7.3. БПФ ПРИ ИСПОЛЬЗОВАНИИ БИТОВЫХ ОПЕРАЦИЙ В тех приложениях, где преобразование Фурье проводится для упрощения вычисления свертки, часто нужен точный результат. Если элементы берутся из кольца вещественных чисел, их надо аппроксимировать с помощью конечного числа разрядов, и это порождает ошибки. Избежать этих ошибок можно, если производить вычисления в конечном поле ). Например, чтобы свернуть а=[ао, at, а». О, 01 и Ь=[&о, Ьи bt. О, 01 можно взять 2 в качестве корня пятой степени из единицы и вычислять по модулю 31. Тогда преобразование векторов а и Ь, попарные умножения и нахождение обратного преобразования дают точное значение а©Ь по модулю 31 При использовании конечного поля часто бывает трудно выбрать подходящее поле с подходящим корнем тг-й степени из единицы. Поэтому мы будем пользоваться кольцом R„ целых чисел по модулю т, где m будет таким, чтобы в R„ был примитивный корень п-й степени из единицы »). Сразу не очевидно, что поданному п можно найти такие шит что со - примитивный корень тг-й степени из единицы в кольце вычетов по модулю т. Кроме того, не годятся слишком большие т, поскольку тогда вычисления по модулю т будут громоздкими. К счастью, если п - степень числа 2, то подходящее число т существует всегда, и оно равно примерно 2". В частности, мы покажем (теорема 7.5), что когда п и сй>1 явля- ) Определение поля дано в разд. 12.1. *) Разумеется, компоненты ответа должны быть заключены между О и 30, ибо иначе нельзя будет восстановить их. В общем случае надо выбирать модули достаточно большими, чтобы можно было восстановить ответ. *) До сих пор вы могли бы считать ш комплексным числом е""/", а арифметические операции - операциями в поле комплексных чисел. Но начиная отсюда, нужно считать ш целым числом, а все арифметические операции - операциями в конечном кольце вычетов по модулю т. 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.0021 |