Быстрое преобразование Фурье (БПФ / FFT)

Раскладываем мир на синусоиды

Преобразование Фурье утверждает, что любой сложный сигнал (например, звук вашего голоса или изображение) можно разложить в сумму простых синусоидальных волн разной частоты и амплитуды.

Комплексные числа и Формула Эйлера

Формула Эйлера связывает экспоненту и тригонометрию:

Комплексные корни из единицы \omega_n^k = e^{i \frac{2\pi k}{n}} используются в алгоритме БПФ для быстрого вычисления значений многочлена в точках.

Почему FFT — один из важнейших алгоритмов XX века?

Прямое перемножение двух многочленов степени N требует O(N^2) операций. С помощью БПФ мы переводим многочлены в частотное представление, перемножаем значения за O(N) и возвращаемся обратно — итоговая сложность всего O(N \log N)!

Это позволило создать сжатие MP3, JPEG, компьютерную томографию и быструю обработку сигналов в 5G связи.