Объяснение кода алгоритма FFT

Question

http://www.tech.dmu.ac.uk/~eg/tensiometer/fft/fft.c

http://www.tech.dmu.ac.uk/~eg/tensiometer/fft/fft_test.c

Я нашел хороший рабочий код C для алгоритма FFT для преобразования временной области в частотную область и наоборот в приведенных выше ссылках. Но я хотел знать блок-схему или пошаговый процесс работы этого кода. Я пытаюсь проанализировать код методом бабочки во времени для БПФ, но я сталкиваюсь с трудностями в понимании кода. Код работает очень хорошо и дает мне правильные результаты, но мне было бы очень полезно, если бы кто-то мог дать краткое или подробное объяснение того, как работает этот код.

Я запутался с массивом и указателями, используемыми в коде fft.c. Также я не понимаю, что переменные смещение и дельта означают в коде. Как считать / использовать прямоугольную матрицу действительных и мнимых терминов в коде? Пожалуйста, ведите меня.

Спасибо, псбк

Answer 1

Я настоятельно рекомендую прочитать это: /questions/42346658/kak-vyichislit-diskretnoe-preobrazovanie-fure/42346680#42346680

Теперь с первого взгляда смещение и дельта используются для:

• сделать перестановку бабочки в случайном порядке
• вы начинаете с шага 1 и половины интервала
• и по рекурсии вы получите log2(N) шаг и интервал 1 элемент...
• +/- один уровень рекурсии
• Я обычно делаю бабочку в обратном порядке

XX массив

• буфер для хранения подрезультата или входных данных
• Вы не можете легко выполнить БПФ на месте (если вообще)
• так что вместо этого вы вычисляете в / из временного буфера
• и в каждой рекурсии просто меняйте местами данные и временные буферы (физически или их значение)