Что на самом деле показывает FFT

Вопрос

Играйте аккорд на фортепиано — скажем, C и E вместе. Ухо слышит один звук. Но этот звук накладывается на две частоты: 261,6 Гц и 329,6 Гц. Ваша улитка физически разделяет их — различные волосковые клетки резонируют на разных частотах, посылая различные сигналы в ваш мозг.

Быстрое преобразование Фурье делает то же самое, но с числами вместо волосковых клеток. Дайте ему сигнал (последовательность образцов амплитуды с течением времени), и он вернет список частот и их сильных сторон. Ответ: ** Какие частоты присутствуют и сколько из них? **

Что на самом деле происходит

Сигнал, отобранный с течением времени, представляет собой список чисел: амплитуду в каждой точке выборки. 1-секундная запись с частотой 44 100 Гц составляет 44 100 номеров. Эти числа описывают сигнал в ** временной области ** — амплитуде как функцию времени.

FFT преобразует это в **частотный домен ** — амплитуду как функцию частоты. Одна и та же информация, разное представление. Как переключение между декартовыми и полярными координатами: ничего не создается и не уничтожается, только перевыражено.

Математическое ядро: каждый периодический сигнал может быть записан как сумма синусовых и косинусных волн на разных частотах. Это теорема Фурье (1807). FFT вычисляет коэффициенты этой суммы — сколько каждой частоты находится в сигнале.

Почему «быстро»

Наивный способ вычисления преобразования Фурье требует Операции N2 для N образцов. Для 1024 образцов это около 1 миллиона операций. Алгоритм Кули-Туки (1965) сводит это к N·log2(N) — около 10 000 операций для одного и того же ввода. 100-кратное ускорение. Для миллиона образцов ускорение составляет 50 000x.

Трюк: разделить преобразование N-точки на два преобразования N/2-точки, рекурсивно. Это требует, чтобы N был мощностью 2 (или вы pad с нулями). Каждый раскол наполовину решает проблему. Операция «бабочка» объединяет половинки:

X[k]     = Even[k] + W · Odd[k]
X[k+N/2] = Even[k] - W · Odd[k]

Где W — комплекс экспоненциальный (вращение в комплексной плоскости). Те же два подрезультата дают вам два выходных пункта. Вот почему алгоритм «быстрый» — он повторно использует каждое вычисление дважды.

Реализация PinePaper представляет собой учебник Cooley-Tukey radix-2 DIT (вычисление во времени). 40 строк JavaScript. Мы писали его с нуля, а не импортировали библиотеку, потому что хотели, чтобы студенты могли читать источник и понимать каждую строку.

Что означают эти бары

Когда вы видите анализатор спектра (бары, прыгающие под музыку), каждый бар представляет собой частотную корзину. Высота - величина (сила) этой частоты в текущем сигнале.

• Чистая синусоидальная волна производит один высокий бар на своей частоте и ничего больше.
• ** Квадратная волна** производит бары на фундаментальной и каждой нечетной гармонике (3-я, 5-я, 7-я...), уменьшаясь как 1/n. Вот почему квадратные волны звучат «жужжащими» — они содержат высокочастотную энергию, которой нет у чистых синусов.
• Белый шум производит бары примерно одинаковой высоты повсюду. Каждая частота присутствует с одинаковой вероятностью.
• ** Человеческий голос** производит фундаментальный (подарок, который вы слышите) плюс форманты — резонансные пики из формы вашего голосового тракта, которые отличают гласные.

Оригинальное название: Why the Edges Matter

Есть уловка. FFT предполагает, что сигнал повторяется вечно. Но наша выборка конечна — она начинается и останавливается. Если сигнал не находится на нуле в обеих конечных точках, резкое отключение создает искусственное высокочастотное содержимое. Это называется спектральной утечкой.

Фиксация: умножьте сигнал на ** функцию окна **, которая плавно сужается до нуля по краям. Общие окна:

• Ханн (козиновый колокол): хорошее общее назначение, теряет некоторое разрешение частоты
• Хамминг: похож на Ханна, но не достигает нуля по краям, немного лучше подавление боковой стороны
• Черный человек: более узкая основная доля, лучшее подавление боковой области, теряет больше частотного разрешения

Выбор всегда является компромиссом между частотным разрешением (как точно вы можете определить частоту) и спектральной утечкой (сколько энергии истекает в соседние банки). Не существует идеального окна. Это следствие принципа неопределенности — вы не можете иметь произвольно точное знание как времени, так и частоты одновременно.

Где живет FFT

Вы постоянно взаимодействуете с результатами FFT:

• MP3 и AAC-сжатие: преобразование аудио в частотный домен, отбрасывание частот ниже порога слышимости, сжатие того, что осталось. Преобразование является основой сжатия аудио с потерями.
• Сжатие JPEG: 2D-версия (DCT) преобразует 8×8 пиксельных блоков в частотный домен, квантовает высокочастотные компоненты. Вот почему артефакты JPEG выглядят как блоки.
• WiFi и 5G: кодирование OFDM разделяет данные по многим частотным поднесущим. FFT преобразует символы передачи данных во временной области и частотной области.
• ** МРТ-изображение**: необработанный сигнал от МРТ-сканера находится в частотном пространстве. Обратный FFT реконструирует пространственное изображение. Буквально: каждая МРТ, которую вы когда-либо видели, является обратным преобразованием Фурье.
• Шазам: вычисляет спектрограмму (FFT по раздвижным окнам), извлекает пики, сопоставляет рисунок с базой данных. FFT — это первый шаг к признанию каждой песни.

В вашем кармане 60-летний алгоритм, работающий миллиарды раз в день.

Попробуйте

Откройте PinePaper, выберите генератор анализатора спектра. Создайте квадратную волну. Посмотрите на бары — вы увидите, что нечетные гармоники падают как 1/n. Переключитесь на пиломатериал — теперь присутствуют все гармоники, отпадающие как 1/n. Переключитесь на шум — плоский спектр, каждая частота одинаково вероятна.

Измените функцию окна. Посмотрите, как Ханн сглаживает спектр ценой более широких пиков. Переключитесь на Блэкмана — более узкие пики, но более низкие боковые панели.

Ты не читаешь о ФФТ. Вы измеряете сигналы и наблюдаете за трансформацией. В этом разница между знанием и пониманием.

Ссылки

• Бригам, Э.О. (1988). Быстрое преобразование Фурье и его применение. Прентис Холл.
• Cooley, J.W. & Tukey, J.W. (1965). Алгоритм для машинного расчета комплексной серии Фурье. Математика вычислений, 19(90), 297-301.
• Фурье, Дж. (1822). Теория аналитики де ла Шалер. Париж: Фирмин Дидо.
• Харрис, Ф.Дж. (1978). Использование Windows для гармонического анализа с дискретным преобразованием Фурье. Труды IEEE, 66(1), 51-83.
• Oppenheim, A.V. & Schafer, R.W. (2009). * Обработка сигналов в дискретное время* (3-е изд.). Прентис Холл.
• Шеннон, C.E. (1949). Коммуникация в присутствии шума. Труды IRE, 37(1), 10-21.
• Смит, S.W. (1997). Руководство для ученых и инженеров по цифровой обработке сигналов. Калифорнийское техническое издательство.
• Wang, A. et al. (2003). Алгоритм промышленного поиска аудио. Труды ISMIR 2003. (Алгоритм отпечатков пальцев Shazam.)
• Уоллес, Г.К. (1991). Стандарт сжатия изображений JPEG. Связь АСМ, 34(4), 30-44.

---

PinePaper's FFT - это реализация Cooley-Tukey radix-2 с окном Hann, Hamming и Blackman, а также фильтрами с низким и высоким пропусками. Попробуйте бесплатно на [pinepaper.studio/editor] (/editor)