Быстрое дискретное преобразование Фурье
89 та n = 0, ±1, ± 2,.... Будем полагать, что f (n) - периодическая функция с пе- риодом N, т.е. f (n ± N) = f (n) для ∀ n. (8.1) Дискретное преобразование Фурье от функции f (n) определяется известной формулой ~ N −1 n=0 F[ f ] = f (k) = ∑ exp(i N kn) f (n); 2π k = 0, N −1 , (8.2) ~ ~ где, очевидно, Фурье-трансформанта f (k) - также периодическая функция с периодом N. Если мы знаем Фурье-трансформанту f (k) , то мы можем восстановить f (n), используя обратное дискретное преобразование исходную функцию Фурье −1 ~ exp(− 1 ~ N −1 k =0 N ∑ F [ f ] = f (n) = 2π i kn) f (k); n = 0, N −1 . N (8.3) В общем случае, число арифметических операций, которое требуется для вычисления дискретного преобразования Фурье, без затрат на вычисление N функций вида exp(i 2π kn) , оценивается формулой TF ~ N 2 . (8.4) Для уменьшения числа операций, необходимых для вычисления преобра- зования Фурье, опишем алгоритм быстрого дискретного преобразования Фурье (БПФ). Положим N = N1 N2 , где N1 и N2 - целые числа. Представим k и n в выражении (2) в виде k = k2 + k1N2 и n = n1 + n2 N1, где k1, n1 = 0, N1 −1; ~ ~ k2 , n2 = 0, N2 −1. Тогда из (2) получим f (k) = f (k1, k2 ) == ⎠ ∑ N1 −1 N 2 −1 n1 =0 n2 =0 ⎝ 1 2 ∑ exp ⎜i N N (k2 + k1N2 ) (n1 + n2 N1)⎟ f (n1,n2 ) = ⎛ 2π ⎞ ⎠ ⎞ 1 2 1 1 N1−1 ∑ n1=0 ⎝ 1 ⎞ N2 −1 ⎠ n2 =0 ⎝ 2 N N N exp ⎜i k n + i ⎛ 2π 2π ⎛ 2π k2 n1 ⎟ ∑ exp ⎜i N k2 n2 )⎟ f (n1,n2 ).(8.5) 90 Пусть N1 - простое число. Из (5) очевидно, что число арифметических операций, которое требуется для вычисления дискретного преобразования Фурье, без затрат на вычисление функций exp(i 2π N kn) , оценивается форму- лой TF (N ) ~ N2 N 2 + N T (N ) . 1 1 F 2 (8.6) Перепишем (6) в следующем виде 1 N TF (N ) ~ N + TF (N2 ) . (8.7) N2 как произведение простых сомножителей числа Представим N N1, N2 ,..., Nm , т.е. 1 2 m N = Nl1 Nl2 ...N lm . (8.8) Введем понятие целочисленного логарифма целого числа, как сумму всех про- стых сомножителей с учетом их кратности, т.е. m (8.9) LOG(N ) = ∑lk Nk . k =1 Отметим, что если N – простое число, то LOG(N ) = N . Тогда из (7)-(9), получим, что число арифметических операций для вы- числения Фурье-преобразования (5) с использованием «быстрых» алгоритмов оценивается формулой TFF ~ N LOG(N ) . (8.10) Если число N – представляется степенью двойки, то получаем хорошо извест- ную оценку для БПФ ~ N log 2 (N ) . (8.11) TFF Рассмотрим матрицу следующего вида
Slaidy.com
