от ДПФ к БПФ

Прежде чем начать разбираться в БПФ, введем понятия поворачивающего множителя W:

Важно запомнить, что комплексная экспонента со знаком минус, то есть в тригонометрическом виде будет присутствовать cos и -sin, которые будут храниться в памяти. 

Рассмотрим свойства W. Для примера возьмем N = 4. При этом m = 0..N-1.

Получили, что для расчета N коэффициентов W, достаточно посчитать первые N/2 коэффициентов. Это правило справедливо для любого N.

Теперь выведем формулу БПФ с использованием поворачивающего множителя W. Для этого на первом шаге разобьем сумму на две части, выделив четные и нечетные отчеты в две отдельные последовательности.

Получили, что для вычисления N точечного ДПФ достаточно посчитать два N/2 точечных ДПФ из четных и нечетных слагаемых и объединить их. Пользуясь свойствами поворачивающего множителя, можно показать, что для вычисление X(m+N/2) не нужно считать W для него:

Для вычисления X(m+N/2) не нужно ничего считать: достаточно поменять знак поворачивающего множителя  и использовать две суммы, полученные для X(m). 

Итого: для вычисления 8 точечного ДПФ нужно посчитать два 4 точечных ДПФ. Так же можно продолжить и вычислить 4 точечное ДПФ через два 2 точечных.

Далее будем переносить алгоритм на verilog и разбираться во всех тонкостях.