Дискретное преобразование Фурье
Для возможности компьютерных вычислений переведём задачу в дис- кретную форму. Для этого выберем дискретные моменты времени по форму- ле 11:
где ∆t — период дискретизации.tn = n · ∆t, (11)
Затем выберем дискретные значения функции в эти моменты по форму- ле 12:
xn = f (n · ∆t), (12)
так, что на полном периоде функции оказывается N точек:
N · ∆t = T. (13)
Полученные выражения можно подставить в формулу для коэффициен- тов ck. Так интеграл заменяется интегральной суммой, получаем формулу 14:
Σ
N −1
— (14)
c = ∆t xk N ∆t n n=0
2πin∆tk
e N ∆t , k = 0, ..., N − 1.
Обозначим относительную величину коэффициента ck через X(k) и по- лучим формулу 15 для дискретного преобразования Фурье:
Σ
2πink
N −1X(k) = xn
n=0
e− N , k = 0, ..., N − 1. (15)
Быстрое преобразование Фурье
2
БПФ отличается от ДПФ только уменьшенным количеством операций. На самом деле это одни и те же алгоритмы. БПФ — это алгоритм быстрого вычисления ДПФ с трудоёмкостью O(N log2 N ).Основные концепции бпф
2πi
Пусть WN = e− N — комплексный поворачивающий множитель, тогда выражение для X(k) можно представить формулой 16:
N
N −1
X(k) = Σ xnWnk, k = 0, ..., N − 1. (16)n=0
2
Основной его смысл в том, что мы делим исходную последовательность прореживанием по времени. Оно заключается в разделении ДПФ длиной N на две ДПФ длиной N : одно состоит из компонентов с чётными индексами x0, x2, ..., а другое — из компонентов с нечётными индексами x1, x3, Полу-чим формулу 17:
−12
N
N
2
N
X(k) = Σ x2nWnk + Wk
N
−12
N
2
Σ x2n+1Wnk
(17)
4
Аналогично каждую из них можно разделить на две ДПФ длиной N и такдалее до тех пор, пока в каждой сумме не останется по одному элементу. Для удачного разделения размер входных данных должен быть степенью двойки: N = 2q, q ∈ N .
Процедура объединения
В результате математических преобразований получили, что два ДПФ четных и нечетных временных отсчетов входного сигнала можно объединить в ДПФ полной длины, если просуммировать отсчеты четной последователь- ности с произведением отсчетов нечетной последовательности входных сиг- налов на поворачивающий множитель. Количество операций умножения при этом значительно уменьшается по сравнению с прямым вычислением ДПФ.
2
Поворачивающие множители симметричны относительно N . Покажем
2
это. Рассмотрим отсчёт X(k + N ):
−12
N
2
X(k + N ) = Σ x
N
−12
N
2
2
N
2
2n
Wn(k+ N ) +W (k+ N ) Σ x
Wn(k+ N ), k = 0, ..., N −1 (18)
N
2
2
2
2n+1
Попробуем упростить поворачивающие множители под знаками сумм:
Wn(k+ N ) = WnkWn N
= Wnke−2πin = Wnk, (19)
2 2
N N N N N
2 2 2 2 2
так как e−2πin = 1 по формуле Эйлера. Теперь попробуем упростить множитель перед второй суммой:
N
2
N
2
N
W (k+ N ) = Wk W N= Wk e−πi = −Wk , (20)
N
N
так как e−πi = −1 по формуле Эйлера. Окончательно получим:
−12
N
N
2
N
X(k) = Σ x2nWnk + Wk
N
−12
N
2
Σ x2n+1Wnk
(21)
−12
N
2
X(k + N ) = Σ x
N
−12
N
2
N
2n
Wnk − Wk Σ x
Wnk, (22)
N
2
2n+1
то есть отличие только в знаке перед вторым слагаемым.