Что на самом деле показывает вам FFT — Объяснено преобразование Фурье (Русский)

Вопрос

Играть аккорд на пианино — скажем, С и Е вместе. Ухо слышит один звук. Но этот звук накладывается на две частоты: 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. Вот почему квадратные волны звучат «жужжащими» — они содержат высокочастотную энергию, которой не обладают чистые синусы.
Белый шум производит бары примерно одинаковой высоты повсюду. Каждая частота присутствует с одинаковой вероятностью.
Человеческий голос производит фундаментальный звук, который вы слышите, плюс форманты — резонансные пики от формы вашего голосового тракта, которые отличают гласные.

Первые три — ниже щелкните между ними. Высота – это формулы, не рисунок: синус равен 1 при фундаментальном, квадратная волна ровно 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. Переключитесь на шум — плоский спектр, каждая частота одинаково вероятна.

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

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

Ссылки

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

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

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