Составители:
Рубрика:
Ввиду соотношений (8.22) – (8.24) общее число мультипликатив-
ных операций M = D + M
1
+ M
2
имеет оценку
M ≤ n(2 log
2
n + 1). (8.25)
Число аддитивных операций оценивается аналогично.
11
Замечание 5. Оценка (8.25) может быть уточнена.
12
Замечание 6. Логические операции и пересылки обычно делают-
ся быстрее арифметических действий на ЭВМ, однако, большое их
число может повлиять на производительность алгоритма. В случае
БПФ это влияние несущественно.
13
Замечание 7. Весьма важным является объём необходимой памя-
ти для реализации алгоритма. Как видно БПФ позволяет ограни-
читься небольшим увеличением памяти, необходимой для исходных
данных.
14
9. Быстрое преобразование Фурье с использованием би-
товых операций
В ряде случаев при применении преобразования Фурье нужен
точный результат. Если же в качестве кольца K брать кольцо ком-
плексных чисел, то при использовании вычислений на ЭВМ это
может привести к ошибкам округления, связанным со спецификой
разрядной сетки. Д ля точных вычислений удобно использовать ко-
нечное поле (например, поле вычетов по модулю m, где m доста-
точно велико).
В дальнейшем будет показано, что если n и ω – степени числа
2, то можно вычислять свёртки по модулю ω
n/2
+ 1 с помощью
преобразования Фурье, покомпонентного умножения и обратного
преобразования.
Итак, пусть K = {S, +, ·, 0, 1} – коммутативное кольцо,
n = 2
k
, k ≥ 1. (9.1)
Лемма 5. Для всякого a ∈ S
2
k
−1
X
i=0
a
i
=
k−1
Y
i=0
(1 + a
2
i
). (9.2)
11
Подсчитать число аддитивных операций в алгоритме БПФ.
12
Уточнить оценку (8.25).
13
Оценить число логических операций и число пересылок в алгоритме БПФ.
14
Дать оценку необходимой памяти дл я алгоритма БПФ.
28
Страницы
- « первая
- ‹ предыдущая
- …
- 25
- 26
- 27
- 28
- 29
- …
- следующая ›
- последняя »
