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

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

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

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

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

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

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

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

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

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

В частности: Пусть ω - примитивный N-й корень из 1 (либо в комплексных числах, либо в некотором конечном поле), что означает, что ω^N=1, но никакая меньшая степень не равна 1. Можно представить f_k как коэффициенты многочлена P(x) = ∑f_kx^k. N новых чисел F₀, F₁, ..., F_N-1, которые дает ДПФ, являются результатами оценки многочлена на мощностях ω. То есть для каждого n от 0 до N-1 новое число F_n равно P(ωⁿ) = ∑_0≤k≤N-1 f_kω^nk.

[Причина выбора ω в том, что обратное ДПФ имеет красивую форму, очень похожую на само ДПФ.]

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

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

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

P(x) = Q(x) + ω^NR(x) с

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

R(x) = f_N + f_N+1x + ... + f_2N-1x^2N-1

Теперь вот в чем прелесть. Обратите внимание, что значение ω^k+N очень просто связано со значением ω^k:
P(ω^k+N) = ω^N(Q(ω^k) + ω^NR(ω^k)) = R(ω^k) + ω^NQ(ω^k). Поэтому достаточно оценок Q и R при ω⁰ - ω^N-1.

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

Примеры ДПФ

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

Для N=2, ω=-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+c-d, a-bi-c+di). В частности, пример из вашего вопроса: ДПФ на (1,0,0,0,0) дает (1,1,1,1), не очень, наверное, поучительный.

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

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

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