Реналь Гариев

В этом месяце исполняется 60 лет с тех пор, как в 1965 году Кули и Тьюки представили быстрое преобразование Фурье (БПФ) — один из важнейших алгоритмов в обработке сигналов и анализе данных.

В 1805 году Гаусс, изучая орбиты астероидов Паллада и Юнона, придумал метод интерполяции их траекторий по дискретным образцам. То, что он придумал, было математически очень близко к современному БПФ, но Гаусс никогда не публиковал эту работу и не анализировал ее вычислительную сложность. Она предшествовала даже работе Фурье 1822 года о диффузии тепла — но без обрамления или обобщения, которые Кули и Тьюки внесут 160 лет спустя.

В 1965 году Кули и Тьюки опубликовали свой ныне знаменитый алгоритм, который снизил стоимость вычисления дискретного преобразования Фурье с 𝑂 ( 𝑛 ²) до 𝑂 ( 𝑛 log ⁡𝑛 ). Этот скачок сделал возможными обработку сигналов в реальном времени и сжатие цифровых медиаданных.

От радиотелескопов до JPEG, от аудиокодеков до квантовой механики — БПФ повсюду. Это один из самых важных (и элегантных) алгоритмов 20-го века — уходящий корнями в гений Гаусса, но воплощенный в жизнь в компьютерную эпоху.