Преобразование Фурье онлайн (FFT)

Принцип преобразования Фурье

Преобразование Фурье — математическая операция, представляющая сигнал во временной области как сумму синусоид (косинусов и синусов) разных частот. Жан-Батист Фурье в 1822 г. в работе «Аналитическая теория тепла» показал, что любая периодическая функция может быть разложена в ряд синусоид.

Прямое DFT: X[k] = Σ x[n] * e^(-2πi*kn/N), n=0..N-1 Обратное: x[n] = (1/N) * Σ X[k] * e^(2πi*kn/N), k=0..N-1

FFT vs DFT

• DFT: прямое вычисление по формуле. Сложность O(N²).
• FFT: алгоритм Кули-Тьюки (1965). Сложность O(N log N).

Идея FFT: разложить N-точечное преобразование на два (N/2)-точечных + объединение. Рекурсивно. Работает идеально для N = 2^k. Для других N используются варианты FFT (Bluestein, Rader).

Сравнение для разных N:

• N=1024: DFT 10⁶ оп, FFT 10⁴ оп → выигрыш ×100.
• N=10⁶: DFT 10¹² оп, FFT 2·10⁷ оп → выигрыш ×50 000.

Применение FFT

• Аудио: спектральный анализ, эквалайзер, сжатие MP3 (через MDCT — родственник DFT), AAC, FLAC.
• Изображения: JPEG использует DCT (Discrete Cosine Transform — родственник DFT). Сжатие 5-20× при потере качества 5-10%.
• Радио: OFDM (Orthogonal Frequency Division Multiplexing) — основа Wi-Fi, 4G LTE, 5G. Каждая поднесущая — отдельная частота, FFT-обработка.
• Медицина: МРТ (k-space → image), УЗИ-Doppler, ЭКГ анализ ритма.
• Сейсмология: анализ землетрясений, поиск нефти.
• GPS и спутники: декодирование сигналов.
• Криптография: умножение больших чисел (Шёнхаге-Штрассен) — для RSA, факторизации.

Оконные функции

При FFT конечного фрагмента сигнала появляется «спектральная утечка» — энергия размывается на соседние частоты. Решение — окна:

• Прямоугольное: w[n] = 1. Лучшее разрешение, плохое подавление утечек.
• Hann: w[n] = 0,5·(1 − cos(2πn/(N−1))). Стандарт для общего использования.
• Hamming: похоже на Hann, лучше подавляет первый боковой лепесток.
• Blackman: ещё лучше подавление, но шире главный лепесток.
• Гаусс: для очень узких пиков.
• Tukey: гибрид прямоугольного и Hann.