Ответ 1
Вы правы, "быстрое преобразование Фурье - это просто имя для любого алгоритма, который вычисляет дискретное преобразование Фурье в O (n log n) времени, и существует несколько таких алгоритмов.
Вот простейшее объяснение ДПФ и БПФ, как я их думаю, а также примеры для малых N, которые могут помочь. (Обратите внимание, что существуют альтернативные интерпретации и другие алгоритмы.)
Дискретное преобразование Фурье
Учитывая N числа f 0, f 1, f 2,..., f N-1, ДПФ дает другой набор чисел N.
В частности: Let & omega; - примитивный N -й корень из 1 (либо в комплексных числах, либо в некотором конечном поле), что означает, что & omega; N= 1, но не меньшая мощность равна 1. Вы можете представить f k как коэффициенты многочлена P (x) = & sum; f k x k. N новых чисел F 0, F 1,..., F N-1, которые DFT дает, являются результатами оценки полином по степеням & omega;. То есть для каждого n от 0 до N-1 новым числом F n является P (& omega; n) = & sum; 0≤k≤N -1 f k & omega; nk.
[Причина выбора & omega; что обратный ДПФ имеет приятную форму, очень похожую на сам ДПФ.]
Заметим, что поиск этих F наивно принимает операции O (N 2). Но мы можем использовать специальную структуру, которая исходит от & omega; мы выбрали, и это позволяет нам делать это в O (N log N). Любой такой алгоритм называется быстрым преобразованием Фурье.
Быстрое преобразование Фурье
Итак, вот один из способов сделать БПФ. Я заменил N на 2N, чтобы упростить обозначение. У нас есть f 0, f 1, f 2,..., f 2N-1, и мы хотим вычислить P (& omega; 0), P (& omega; 1),... P (& omega; 2N-1), где мы можем написать
P (x) = Q (x) + & omega; 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
Теперь вот красота вещи. Заметим, что значение 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; 0 до & omega; N-1 - достаточно.
Это означает, что ваша первоначальная задача - оценить многочлен 2N-терма P в точках 2N & omega; 0 to & omega; 2N-1 - была сведена к две задачи оценки N-термов полиномов Q и R в N точках & omega; 0 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ω 2 a + bω 2 + cω). (Так как ω 4= ω.)
При 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), не очень освещая, возможно.