Преобразование Фурье: математика, стоящая за сигналами и спектральным анализом

Вы когда-нибудь задумывались, как устройства умеют убирать шум и менять высоту звука в аудио? Или как ваш телефон сжимает изображение высокого разрешения? С помощью математического инструмента такие задачи решаются так: сигнал раскладывают на «чистые» синусоиды и косинусоиды. В этом и заключается сила преобразования Фурье — идеи, которая радикально изменила использование компьютеров в областях вроде сжатия изображений, гидроакустики, медицинской визуализации и многих других.

Предыстория
Основную идею преобразования Фурье предложил французский математик и физик Жозеф Фурье в 1822 году, когда решал уравнение теплопроводности. Он показал, что любую функцию можно представить в виде суммы синусов и косинусов. Сначала это вызвало споры, но позже математики — такие как Дирихле, Коши и Риман — развили и формализовали эту теорию. Первое крупное практическое применение появилось в телеграфии в конце XIX века.

Краткое объяснение
Преобразование Фурье раскладывает сложный (составной) сигнал на синусоидальные компоненты и представляет его как функцию частоты.

Уравнение преобразования выглядит так:

где верхний предел интегрирования — +∞, а нижний — −∞

Здесь f(t) — заданная функция сложной волны: область определения — время, а значения — амплитуда или интенсивность. Чтобы выполнить преобразование, предполагают синусоидальные волны разных частот. Затем нужна модель, которая сравнивает эти частоты с частотами, присутствующими в исходном сигнале, и тем самым показывает, какой вклад синусоида конкретной частоты вносит в сигнал.

Синусоидой называют волну с гладкими периодическими колебаниями — как синус и косинус. Ряд Фурье — известный инструмент, который переводит периодические сигналы в сумму синусоид. Но он плохо работает с непериодическими волнами. Тогда используется преобразование Фурье: оно «встраивает» семейство синусоид с переменной частотой в базисную функцию e^−jωt и связывает временную область с частотной.

Эта комплексная экспонента (формула Эйлера) состоит из косинусной (действительной) и синусной (мнимой) частей. В каждый момент времени (t) она соответствует точке на единичной окружности с углом −ωt в комплексной плоскости. Её вращение во времени «согласует» f(t) с синусоидальными компонентами на частоте ω, позволяя выделить, какая часть f(t) относится к этой частоте.

Чтобы найти проекцию f(t) на базисную функцию, две функции перемножают (аналогично проекции одного вектора на другой) и интегрируют по времени. Чем ближе «проверяемая» частота к реально присутствующим в сигнале, тем больше значение интеграла. При бесконечных пределах интегрирования вклад несоответствующих частот обнуляется из-за взаимной компенсации и ортогональности. А совпадающие частоты после интегрирования дают ненулевое значение. В конце строят график «амплитуда — частота», где для каждой частоты откладывают модуль интеграла. Этот график и показывает вклад разных частот в исходный сигнал.

Применения
У этой количественной модели есть несколько разновидностей, и они используются во множестве областей. Обратное преобразование Фурье помогает восстанавливать сигналы в МРТ и в радиоастрономии. Дискретное преобразование Фурье (DFT) важно для цифровой обработки сигналов — например, в распознавании речи и в сейсмическом анализе. Быстрое преобразование Фурье (FFT) ускоряет вычисления и делает возможной обработку аудио в реальном времени и сжатие изображений, например JPEG.

Этот метод также позволяет разлагать данные МРТ и КТ. Он помогает анализировать спектры света от далёких звёзд. Его применяют для оценки структурной целостности, а также для работы с волновыми функциями в квантовой механике. Многие теоремы комплексного анализа опираются на основы преобразования Фурье. И так далее — возможностей у этого подхода бесчисленное множество.

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

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

В 1965 году Кули и Тьюки опубликовали ставший знаменитым алгоритм, который снизил стоимость вычисления дискретного преобразования Фурье с O(n²) до $O (n log n)$.

Этот скачок сделал реальными обработку сигналов в реальном времени и цифровое сжатие медиа.

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