Дискретное преобразование Фурье (FFT): Математика медиа и связи

Суть преобразования Фурье заключается в разложении любого сложного сигнала (например, звука голоса) на сумму простых синусоидальных волн (гармоник) различных частот и амплитуд. Формула DFT берет массив N дискретных отсчетов сигнала во времени и переводит его в массив из N комплексных чисел, представляющих спектр частот. Проблема в том, что прямое вычисление этой математической формулы требует O(N^2) операций комплексного умножения. Для обработки качественного аудио (44100 отсчетов в секунду) процессоры прошлого века просто захлебнулись бы.

Триумф случился в 1965 году, когда Джеймс Кули и Джон Тьюки переоткрыли алгоритм Быстрого преобразования Фурье (FFT — Fast Fourier Transform) (впервые описанный Гауссом еще в 1805 году). Алгоритм использует парадигму «разделяй и властвуй».

FFT эксплуатирует уникальные симметричные свойства комплексных корней из единицы на окружности. Алгоритм разделяет исходный массив сигнала на элементы с четными и нечетными индексами, решает задачу Фурье для двух половин в два раза меньшего размера, а затем комбинирует результаты за линейное время с помощью умножения на так называемые «поворачивающие множители» (Twiddle factors). Этот рекурсивный трюк снижает вычислительную сложность с астрономических O(N^2) до невероятно быстрых O(N log N).

Ускорение, даруемое FFT, настолько грандиозно, что оно перевернуло не только медиаиндустрию (сжатие аудио отсекает те гармоники Фурье-спектра, которые не слышит ухо человека). Алгоритм FFT стал краеугольным камнем самой вычислительной алгебры. Если вам нужно перемножить два колоссальных числа (размером в миллионы цифр), стандартный метод "в столбик" займет слишком много времени. Математики используют Алгоритм Шёнхаге — Штрассена: они рассматривают длинные числа как многочлены, переводят их коэффициенты в частотную область с помощью FFT, мгновенно перемножают спектры покомпонентно, а затем применяют обратное FFT, чтобы вернуться к числам. Это позволяет современным компьютерам искать миллионные знаки числа Пи и генерировать огромные криптографические ключи.