Алгоритм быстрого преобразования Фурье

[vadv55]

На сайте http://www.dsplib.ru/content/thintime/thintime.html производится анализ алгоритма быстрого преобразования Фурье (БПФ) как эффективного метода расчёта дискретного преобразования Фурье (ДПФ). Если оставить в стороне вычислительную сложность преобразования Фурье и способы уменьшения количества производимых операций, а остановиться на сравнении выражений для вычисления ДПФ и БПФ с прореживанием по времени, то можно прийти к следующему выводу: в обоих выражениях выходная последовательность отсчётов спектра представляется через сумму всех отсчётов сигнала входной последовательности, различие между ними состоит в значениях поворотных коэффициентов. В отличие от ДПФ, в выражении для БПФ никак не представлен множитель n - порядковый номер отсчёта исходного сигнала, а множитель k - порядковый номер отсчёта спектра - частично видоизменяется. В конечном итоге результаты вычисления этих выражений не совпадают. Для того, чтобы окончательно в этом убедиться, достаточно взглянуть на поворотные коэффициенты для приведенного количества отсчётов сигнала $N=8$: уже во втором элементе выходной последовательности отсутствуют коэффициенты с экспоненциальными показателями $-\pi$, $\frac{-5 \pi}{4}$, $\frac{-3 \pi}{2}$, $\frac{-7 \pi}{4}$. Почему же между ними наблюдается такое расхождение, ведь БПФ используется только для ускорения вычислений при расчёте ДПФ, а на выходе должно получиться ДПФ входной последовательности?

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

vadv55
Наберите все формулы и термы $\TeX$ом.
Ссылку можете оформить с помощью тега url или хотя бы без подчеркивания.
Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
вернул

[Xaositect]

Если у Вас что-то не сошлось, значит, Вы где-то что-то забыли. Должно получаться одно и то же.

Давайте разберем $N = 4$. У нас есть массив $a_0,\dots,a_3$ и нужно вычислить коэффициенты Фурье $f_{k} = \sum\limits_{i = 0}^3 a_i w^{ik}$, где $w = e^{\frac{i\pi}{2}} = i$, т.е. $f_0 = a_0 + a_1 + a_2 + a_3$, $f_1 = a_0 + i a_1 -- a_2 - i a_3$, $f_2 = a_0 - a_1 + a_3 - a_4$, $f_3 = a_0 - i a_1 - a_2 + i a_3$.

Для этого мы разбиваем этот массив на два, с четными и нечетными индексами: $a_0, a_2$ и $a_1, a_3$. Для них мы вычисляем преобразования Фурье $a_0 + a_2, a_0 - a_2$ и $a_1 + a_3, a_1 - a_3$. Потом мы собираем результаты, не забывая домножать на поворачивающие множители: $f_0 = (a_0 + a_2) + w^0(a_1 + a_3)$, $f_1 = (a_0 + a_2) + w^1(a_1 + a_3)$, $f_2 = (a_0 + a_2) - w^0(a_1 + a_3)$, $f_3 = (a_0 + a_2) - w^1(a_1 + a_3)$, все сходится.

[vadv55]

Большое спасибо за ответ. Я не учёл, что эти коэффициенты можно привести к существующим, использовав свойства функций синуса и косинуса. Ваши выражения для N=4 в целом правильны, единственное замечание - показатель экспоненты в поворотных коэффициентах имеет отрицательный знак.