Перетворення Фурʼє
Перетворення Фурʼє часто зустрічається у фізиці та математиці, а тому має чимало застосувань і в повсякденному житті.
Коротко кажучи, перетворення Фурʼє бере вхідний сигнал, часто заданий у часовій або просторовій області, і перетворює його в частотну область.
А якщо конкретніше, то для вхідного сигналу, який є сумішшю (тобто суперпозицією) різних частот, перетворення розділить окремі частоти й покаже їхні відносні сили.
Це робить перетворення ключовим інструментом в обробці сигналів (наприклад, фільтрування, стиснення тощо) і в багатьох застосунках науки про дані.
Тому, мабуть, його використовують ширше, ніж можна уявити на перший погляд, і саме тому воно є яскравим прикладом того, де уявні числа стають незамінними, адже результат перетворення Фурʼє загалом є комплексним числом.
Хоча перетворення Фурʼє має інтегральну форму, ми працюємо в цифровому світі, тому нас цікавить дискретна версія.
Виведення цього перетворення виходить за межі цієї вправи, але пряме дискретне перетворення (у частотну область) має такий вигляд:
Xₖ = Σ xₙ * ℯ^(-2iπk * n/N)
Тут сума береться за n, N - кількість відліків, k - частота, i - уявна одиниця, а xₙ - окремий відлік.
Швидке перетворення Фурʼє
Попри те що перетворення Фурʼє надзвичайно корисне, у наївній реалізації воно працює трохи повільно (O(n²)).
Швидке перетворення Фурʼє (FFT) - це алгоритм, який різко це прискорює.
Зазвичай це роблять за допомогою стратегії «розділяй і володарюй», яка використовує деякі симетрії у формулюванні й дає асимптотичну складність O(Nlog(N)).
Це прискорення значно покращує практичність і розширює коло застосувань, для яких придатне перетворення.
