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

Коротко: Преобразование Фурье раскладывает сигнал на колебания разных частот, из которых он состоит.

Подробнее: Вместо «насколько громко в каждый момент?» оно отвечает на вопрос «насколько сильно представлена каждая частота?». Компьютеры используют дискретный вариант (ДПФ), который алгоритм БПФ (FFT) вычисляет за O(n log n) вместо O(n²).

Подробности

• Идея: Любой сигнал можно записать как сумму синусоидальных и косинусоидальных волн.
• Результат: Спектр из амплитуды (сила) и фазы (сдвиг) на каждую частоту.
• Теорема отсчётов: Чтобы уловить частоту f, нужно дискретизировать как минимум с 2·f (Найквист). Иначе возникают ошибки наложения спектров (алиасинг).
• Применение: Эквалайзеры и индикаторы спектра в аудиопрограммах, сжатие (MP3 и JPEG используют родственные преобразования), фильтры шума, быстрое умножение больших чисел, радио и Wi-Fi (OFDM).
• Предел: Спектр не говорит, когда возникла частота. Это покрывает оконное преобразование Фурье (спектрограмма).

См. также: O-нотация