Вы правы, "быстрое преобразование Фурье - это просто имя для любого алгоритма, который вычисляет дискретное преобразование Фурье за O (n log n) времени, и существует несколько таких алгоритмов.
Вот простейшее объяснение ДПФ и БПФ, как мне кажется, а также примеры для малого N, которые могут помочь.(Обратите внимание, что существуют альтернативные интерпретации и другие алгоритмы.)
Дискретное преобразование Фурье
Дано N чисел f 0 , f 1 , f 2 ,…, f N-1 , ДПФ дает другой набор N чисел.
В частности: пусть ω будет примитивом N -го корня из 1 (либо в комплексных числах, либо в некотором конечном поле), что означает, что ω N = 1но не меньшая степень равна 1. Вы можете думать о f k как о коэффициентах многочлена P (x) = ∑f k x k , N новые числа F 0 , F 1 ,…, F N-1 , которые дает DFT, являются результатами оценивая полином при степенях ω.То есть для каждого n от 0 до N-1 новый номер F n равен P (ω n ) = ∑ 0≤k≤N-1 f k ω nk .
[Причина выбора ω заключается в том, что обратное ДПФимеет приятную форму, очень похожую на сам ДПФ.]
Обратите внимание, что нахождение этих F наивно требует операций O (N 2 ).Но мы можем использовать специальную структуру, которая исходит из выбранных нами ω, и это позволяет нам делать это в O (N log N).Любой такой алгоритм называется быстрым преобразованием Фурье.
Быстрое преобразование Фурье
Так что вот один из способов сделать БПФ.Я заменим N на 2N, чтобы упростить обозначения.У нас есть f 0 , f 1 , f 2 ,…, f 2N-1 , и мы хотим вычислить P (ω 0 ), P (ω 1 ),… P (ω 2N-1 ), где мы можем написать
P (x) = Q (x) + ω N R (x) с
Q (x) = f 0 + f 1 x+… + F N-1 x N-1
R (x) = f N + f N + 1 x +… + f 2N-1 x 2N-1
Теперь в этом вся прелесть.Заметьте, что значение в ω k + N очень просто связано со значением в ω k :
P (ω k + N ) = ω N (Q (ω k ) + ω N R (ω k )) = R (ω k ) + ω N Q (ω k ).Таким образом, оценки Q и R от ω 0 до ω N-1 достаточно.
Это означает, что ваша первоначальная задача - оценить 2N-членный многочленP в 2N точках ω 0 до ω 2N-1 - сводится к двум задачам оценки N-членных полиномов Q и R в N точках ω 0 до ω N-1 .Так что время работы T (2N) = 2T (N) + O (N) и все то, что дает T (N) = O (N log N).
Примеры DFT
Обратите внимание, что в других определениях коэффициенты 1 / N или 1 / √N.
Для N = 2 ω = -1, а преобразование Фурье (a, b) равно (a + b, ab).).
Для N = 3 ω - комплексный корень куба из 1, а преобразование Фурье (a, b, c) - (a + b + c, a + bω + cω 2 , a + bω 2 + cω).(Поскольку ω 4 = ω.)
Для N = 4 и ω = i, а преобразование Фурье для (a, b, c, d) равно (a + b + c)+ d, a + bi-c-di, a-b + cd, a-bi-c + di).В частности, пример в вашем вопросе: DFT на (1,0,0,0) дает (1,1,1,1), возможно, не очень освещающее.