DSP_PC / Лабораторная работа #2
4.1. Быстрое преобразование Фурье
Для вычисления одного коэффициента ДПФ по формуле
необходимо выполнить N комплексных умножений и сложений. Таким образом, расчет всего ДПФ, содержащего N коэффициентов, потребует N2 пар операций «умножение-сложение». Число операций возрастает пропорционально квадрату размерности ДПФ. Однако, если N не является простым числом и может быть разложено на множители, процесс вычислений можно ускорить, разделив анализируемый набор отсчетов на части, вычислив их ДПФ и объединив результаты. Такие способы вычисления ДПФ называются быстрым преобразованием Фурье (БПФ; английский термин – Fast Fourier Transform, FFT) и повсеместно используется на практике.