Преобразование Фурье
Любой периодический сигнал можно представить как сумму синусоид разных частот, амплитуд и фаз. Это знаменитая теорема Жозефа Фурье (1822). Даже сложный сигнал — речь, музыка, ЭКГ — раскладывается в этот «частотный портрет», который называется спектром. Преобразование Фурье — математическая операция, делающая это разложение.
Profound study of nature is the most fertile source of mathematical discoveries.— Joseph Fourier «Théorie analytique de la chaleur», 1822
Быстрое преобразование Фурье (Cooley-Tukey)
Прямой расчёт дискретного преобразования Фурье (DFT) для N точек требует O(N²) операций. Алгоритм Cooley-Tukey FFT (1965) использует приём «разделяй и властвуй»: рекурсивно разбивает сигнал на чётные и нечётные индексы, объединяя через twiddle factors. Это даёт O(N·log N).
N = 1 000 000: DFT — 10¹² операций, FFT — 2 · 10⁷ — разница в 50 000 раз
Теорема Найквиста-Котельникова-Шеннона
Чтобы корректно представить непрерывный сигнал в дискретной форме, надо сэмплировать его с частотой fs ≥ 2·fmax, где fmax — максимальная частота в сигнале. Это теорема Найквиста (или Котельникова в русской традиции; работа Котельникова 1933, Найквист 1928). Половина частоты сэмплирования (fs/2) — частота Найквиста — это потолок «видимых» частот в спектре. Что выше — складывается в нижнюю часть спектра как алиасинг.
Оконные функции
FFT неявно предполагает, что входной сигнал периодически повторяется. Реальный сигнал конечен — края резко обрываются, что в спектре проявляется как «растекание» энергии (spectral leakage). Чтобы смягчить это, сигнал умножают на оконную функцию:
- Прямоугольное — окна нет, сильное растекание, но узкие пики.
- Hann (1 − cos) / 2 — стандарт по умолчанию, баланс.
- Hamming 0.54 − 0.46·cos — лучшее подавление первого бокового лепестка.
- Blackman — наиболее чистое подавление, но шире главный лепесток.
Применения FFT
- MP3 / OGG / AAC — модифицированное DCT (родственник FFT) для сжатия аудио.
- JPEG / JPEG2000 — DCT и wavelet для сжатия изображений.
- Wi-Fi / 4G / 5G — OFDM-модуляция, базируется на IFFT/FFT.
- Whisper / нейросетевые ASR — мел-спектрограмма (FFT + мел-шкала) перед нейросетью.
- Эквалайзер в плеере — FFT-фильтрация в реальном времени.
- МРТ — обратное FFT 2D/3D данных k-пространства в изображение.
- Электроника — анализ цепей в частотной области (см. RC/LC-фильтр).
- Oppenheim A.V., Schafer R.W. «Discrete-Time Signal Processing», 3rd ed.. Oppenheim, Schafer. Pearson. 2010.
- An algorithm for the machine calculation of complex Fourier series. Cooley J.W., Tukey J.W.. Mathematics of Computation 19. 1965.
- Smith S.W. «The Scientist and Engineer's Guide to DSP» (бесплатно). Smith S.W.. dspguide.com. 1997. ↗ ссылка
- Котельников В.А. «О пропускной способности эфира и проволоки в электросвязи». Котельников В.А.. I Всесоюзный съезд по вопросам технической реконструкции связи. 1933.
