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

7.3. БПФ ПРИ ИСПОЛЬЗОВАНИИ БИТОВЫХ ОПЕРАЦИИ

ются степенями числа 2, можно вычислять свертки в кольце вычетов по модулю (й"/2 с помощью преобразования Фурье, покомпонентного умножения и обратного преобразования. Сначала установим два предварительных результата - леммы 7.4 и 7.5. В них мы будем предполагать, что R={S, +, •, О, 1) - коммутативное кольцо и п=2*, kl.

Лемма 7.4. Для всякого aS

п-1 fe-l

2а = П(1+а).

{=0 1 = 0

Доказательство. Доказательство проводится индукцией по k. Базис, т. е. случай k=l, тривиален. Теперь заметим, что

п-1 n/2-l

2а = (1+а) 2 {аУ. (7.6)

1=0 i = 0

Предположение индукции и подстановка а? вместо а дают

л/2-1 к-2 к-1

2 (аГи [1 + (a)j = II [I (7.7)

(=0 i=0 i=\

Подставляя (7.7) в правую часть равенства (7.6), получаем требуемое. □

Лемма 7.5. Пусть т=(а"/+1,где ш б S, афО. Тогда для 1<р<п

co> = 0(mod т).

Доказательство. В силу леммы 7.4 достаточно показать, что l + oipO (mod т) для некоторого /, 0<у<А:. Пусть р=2р, где р нечетно. Очевидно, что 0<.k. Выберем / так, чтобы /-(-s== =k-l. Тогда l-b(u2P=H-(u2*-P=l-f(m-1)Р. Но т-1 =-1 (mod т) и р нечетно, так что (т-1)"-1 (mod т). Отсюда следует, что Ц-сй2-=0 (mod т) для jk-l-s. □

Теорема 7.5. Пусть п и (л - положительные степени числа 2 и т=(й"/2 -f 1. Пусть R„- кольцо вычетов по модулю т. Тогда в кольце R„ элемент п имеет обратный (по модулю т) и а - примитивный корень п-й степени из единицы.

Доказательство. Так как п - степень числа 2, а ffi нечетно, то m и п взаимно просты. Поэтому п имеет обратный по модулю т). Так как а)ф1, то а)=(а" (-\)(-1)=

) Это утверждение составляет одну из основных теорем теории чисел. В разд. 8.8 будет показано, что если а и b взаимно просты, то существуют такие целые числа х и у, что ах-\-Ьу=1. Тогда ах=1 (mod b). Полагая b=m и а=п, получаем наше утверждение.



= 1 (mod(cu/2+l)). Тогда из леммы 7.5 следует, что ш - примитивный корень п-й степени из единицы в R„. □

Теорема 7.5 важна потому, что теорема о свертке верна для кольца целых чисел по модулю 2"/2+1. Если надо вычислить свертку двух п-мерных векторов с целыми компонентами, причем компоненты свертки заключены между О и 2"/, мы можем быть уверены, что ответ будет точным. Если же компоненты свертки не заключены между О и 2"/2, то они точны по модулю 2"/ +1.

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

Пусть т=а)Р+1 для некоторого целого числа р. Для вычисления а по модулю т применим обобщение приема "отбрасывания девяток" (нахождения вычета по модулю 9). Если число а разложено по основанию (оР, т. е. записано в виде последовательности из / блоков по р цифр в каждом, то а по модулю т можно сосчитать, попеременно складывая и вычитая эти / блоков из р цифр.

Лемма 7.6. Пусть пг=сй+1 и а=аг(й", где 0<аг<сй для каждого i. Тогда

а = 2а,(-l)(modm). <=о

Доказательство. Достаточно увидеть, что шр s =-1 (mod т). □

Заметим, что если число блоков / в лемме 7.6 фиксировано, то вычет числа а по модулю т можно найти за Об (р log ш) битовых операций.

Пример 7.3. Пусть п=4, (0=2 и т=2»+1. Тогда, применяя лемму 7.6, положим р=2. Рассмотрлм число а, запись которого по основанию 2 имеет вид 101100. В нашем случае ai=00, ai=ll и аа=10. Вычисляем Со-ai+aj=-1, а затем, прибавляя т, находим, что a=4(mod 5). Так как а==44, то результат верен. □

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

Теорема 7.6. Пусть (о и п - степени числа 2 и пг=(о"/2+1. Пусть [со, Ci, . . ., On-iV- вектор с целочисленньши компонентами, где 0ai<:m для каждого i. Тогда дискретное преобразование Фурье



7.3. бпф при использовании битовых операции

для [flo, fli, . . ., On-iV и обратное к нему можно вычислить по модулю тзаОъ (п* log п log (о) ишгов.

Д о к а 3 а т е л ь с т в о. Применить алгоритм 7.1 или 7.2. Для обратного преобразования подставить вместо и и умножить каждый результат на п-*. Целое число по модулю т можно представить цепочкой из Ь= ((п/2) log (о)+1 символов О и 1. Так как m=2*-i-fl, то вычеты по модулю т можно представить в виде двоичных чисел от 00.. .0 до 100. . .0.

В алгоритме 7.1 участвует сложение целых чисел по модулю т и умножение по модулю т целого числа на степень числа©. Эти операции выполняются за время 0(п log п). В силу леммы 7.6 сложение по модулю т занимает ОъФ) шагов, где &=((п/2) log (о)-М. Умножение на (ор, 0р<.п, эквивалентно сдвигу влево на р log ш разрядов, поскольку (о - степень числа 2. Получающееся целое число содержит не более ЗЬ-2 разрядов, так что по лемме 7.6 сдвиг и последующее вычисление вычета занимают Об(Ь) шагов. Таким образом, прямое преобразование Фурье можно найти за время Об фп log п), или Об (п* log п log (о).

В обратном преобразовании участвует умножение на (ц-р и п~*. Так как (х>Р(о"~р1 (mod т), то (о"~р=(о~р (mod т). Следовательно, вместо умножения на (о-р можно умножать на со"-, что эквивалентно сдвигу влево на (п-р) log © разрядов, причем получающееся целое число содержит не более ЗЬ-2 разрядов. Снова по лемме 7.6 вычеты можно найти за Овф) шагов. Наконец, рассмотрим умножение на п-Ч Если п=2*, то оно сводится к сдвигу влево на п log ю-k разрядов (в результате получается число не более чем с ЗЬ-2 двоичными разрядами) и вычислению вычета по лемме 7.6. Таким образом, нахождение обратного преобразования Фурье также требует Об (п log п log ю) шагов. □

Пример 7.4. Пусть и=2, п=4 и т=5. Вычислим преобразование Фурье вектора [оо, ai, Ог, Оз, где fli=t. Так как а;<5 для каждого i, то можно ожидать, что этот вектор можно будет восстановить, проведя вычисления по модулю т. Для представления чисел мы используем три бита, но в действительности у нас будут лишь ООО.....100, если не считать промежуточных результатов.

В соответствии с алгоритмом 7.1 мы должны вычислить коэффициенты, указанные на рис. 7.6, где вместо (о подставлено число 2.

«2

<Г,+4<75

l7o+/72+4(ei+<7j) = 2

ei,+4aj+2(<7,+4ej)

eb+4(rj-t-8(fli+4ej) -во-1-8в1+4й2+2вэ

Рис. 7.6. Вычисление быстрого преобразования Фурье для л=4.





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