Как именно вы вычисляете быстрое преобразование Фурье?

Ответ 1

Вы правы, "быстрое преобразование Фурье - это просто имя для любого алгоритма, который вычисляет дискретное преобразование Фурье в O (n log n) времени, и существует несколько таких алгоритмов.

Вот простейшее объяснение ДПФ и БПФ, как я их думаю, а также примеры для малых N, которые могут помочь. (Обратите внимание, что существуют альтернативные интерпретации и другие алгоритмы.)

Дискретное преобразование Фурье

Учитывая N числа f ₀, f ₁, f ₂,..., f _N-1, ДПФ дает другой набор чисел N.

В частности: Let & omega; - примитивный N -й корень из 1 (либо в комплексных числах, либо в некотором конечном поле), что означает, что & omega; ^N= 1, но не меньшая мощность равна 1. Вы можете представить f _k как коэффициенты многочлена P (x) = & sum; f _k x ^k. N новых чисел F ₀, F ₁,..., F _N-1, которые DFT дает, являются результатами оценки полином по степеням & omega;. То есть для каждого n от 0 до N-1 новым числом F _n является P (& omega; ⁿ) = & sum; _{0≤k≤N -1} f _k & omega; ^nk.

[Причина выбора & omega; что обратный ДПФ имеет приятную форму, очень похожую на сам ДПФ.]

Заметим, что поиск этих F наивно принимает операции O (N ²). Но мы можем использовать специальную структуру, которая исходит от & omega; мы выбрали, и это позволяет нам делать это в O (N log N). Любой такой алгоритм называется быстрым преобразованием Фурье.

Быстрое преобразование Фурье

Итак, вот один из способов сделать БПФ. Я заменил N на 2N, чтобы упростить обозначение. У нас есть f ₀, f ₁, f ₂,..., f _2N-1, и мы хотим вычислить P (& omega; ⁰), P (& omega; ¹),... P (& omega; ^2N-1), где мы можем написать

P (x) = Q (x) + & omega; ^N R (x) с

Q (x) = f ₀ + f ₁ x +... + f _N-1 x ^N-1

R (x) = f _N + f _{N + 1} x +... + f _2N-1 x ^{2N- 1}

Теперь вот красота вещи. Заметим, что значение at & omega; ^{k + N} очень просто связано со значением в & omega; ^k:
P (& omega; ^{k + N}) = & omega; ^N (Q (& omega; ^k) + & omega; ^N R (& omega; ^k)) = R (& omega; ^k) + & omega; ^N Q (& omega; ^k). Таким образом, оценки Q и R при & omega; ⁰ до & omega; ^N-1 - достаточно.

Это означает, что ваша первоначальная задача - оценить многочлен 2N-терма P в точках 2N & omega; ⁰ to & omega; ^2N-1 - была сведена к две задачи оценки N-термов полиномов Q и R в N точках & omega; ⁰ to & omega; ^N-1. Таким образом, время работы T (2N) = 2T (N) + O (N) и все, что дает T (N) = O (N log N).

Примеры DFT

Обратите внимание, что в других определениях указаны коэффициенты 1/N или 1/√N.

При N = 2, & omega; = - 1, а преобразование Фурье (a, b) - (a + b, a-b).

При N = 3 ω - комплексный кубический корень из 1, а преобразование Фурье (a, b, c) - (a + b + c, a + bω + cω ² a + bω ² + cω). (Так как ω ⁴= ω.)

При N = 4 и ω = i, а преобразование Фурье (a, b, c, d) является (a + b + c + d, a + bi-c-di, a-b + cd, а-би-си + ди). В частности, пример в вашем вопросе: ДПФ на (1,0,0,0) дает (1,1,1,1), не очень освещая, возможно.

Ответ 2

БПФ - это просто эффективная реализация ДПФ. Результаты должны быть одинаковыми для обоих, но в целом FFT будет намного быстрее. Удостоверьтесь, что вы понимаете, как работает DFT в первую очередь, так как это намного проще и гораздо легче понять.

Когда вы понимаете DFT, переходите к БПФ. Обратите внимание, что, хотя общий принцип одинаков, существует множество различных реализаций и вариантов БПФ, например. прореживание во времени v прореживание в частоте, радикс 2 v в других радиусах и смешанный радиус, комплекс-комплексный v real-to-complex и т.д.

Хорошая практическая книга для чтения по теме Быстрое преобразование Фурье и ее приложения Э. Бригама.

Ответ 3

Да, FFT - это просто эффективный алгоритм DFT. Понимание самого БПФ может занять некоторое время, если вы уже не изучили сложные числа и непрерывное преобразование Фурье; но в основном это базовое изменение базы, основанной на периодических функциях.

(Если вы хотите узнать больше о Фурье-анализе, я рекомендую книгу "Анализ Фурье и его приложения" Джеральда Б. Фолланда)

Ответ 4

Я также новичок в преобразованиях Фурье, и я нашел эту онлайн-книгу очень полезной:

Руководство для инженеров и инженеров по цифровой обработке сигналов

Ссылка приведет вас к главе о дискретном преобразовании Фурье. В этой главе объясняется разница между всеми преобразованиями Фурье, а также где вы будете использовать тот, который и псевдокод, который показывает, как вы собираетесь вычислять дискретное преобразование Фурье.

Ответ 5

Если вы ищете простое английское объяснение ДПФ и немного БПФ, а вместо академического goggledeegoo, то вы должны читать следующее: http://blogs.zynaptiq.com/bernsee/dft-a-pied/

Я не мог бы лучше объяснить это.