Перетворення Фур’є

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

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

Подробиці

• Ідея: Будь-який сигнал можна записати як суму синусоїдальних і косинусоїдальних хвиль.
• Результат: Спектр з амплітуди (сила) і фази (зсув) на кожну частоту.
• Теорема відліків: Щоб вловити частоту f, треба дискретизувати щонайменше з 2·f (Найквіст). Інакше виникають помилки накладання спектрів (аліасинг).
• Застосування: Еквалайзери та індикатори спектра в аудіопрограмах, стиснення (MP3 і JPEG використовують споріднені перетворення), фільтри шуму, швидке множення великих чисел, радіо та Wi-Fi (OFDM).
• Межа: Спектр не каже, коли виникла частота. Це покриває віконне перетворення Фур’є (спектрограма).

Див. також: O-нотація