Що таке перетворення Фур'є?
У 1822 році французький математик Жозеф Фур'є досліджував, як тепло поширюється через тверді об'єкти. Щоб розв'язати своє рівняння теплопровідності, йому знадобився математичний трюк: представлення будь-якої функції як суми синусоїдальних хвиль. Те, що почалося як інженерна зручність, виявилося однією з найглибших ідей в усій математиці.
Основне твердження Фур'є-аналізу є всеохопним: будь-який періодичний сигнал — незалежно від того, наскільки складна чи неправильна його форма — можна виразити як суму чистих синусів і косинусів різних частот та амплітуд. Прямокутну хвилю, пилкоподібну хвилю, навіть серцевий ритм можна записати як:
f(t) = A₁sin(2πf₁t) + A₂sin(2πf₂t) + A₃sin(2πf₃t) + …
Перетворення Фур'є бере сигнал у часовій області — амплітуду, побудовану відносно часу, — і перетворює його на частотну область — показуючи, скільки кожної частоти присутньо. Ці два представлення містять точно ту саму інформацію; це просто два різні способи дивитися на один і той самий сигнал. Обернене перетворення Фур'є повертає назад із бездоганною точністю.
Чуючи частоти
Ваші вуха виконують біологічний Фур'є-аналіз кожної миті, коли ви слухаєте. Базилярна мембрана в равлику фізично резонує в різних позиціях для різних частот, розбиваючи вхідний звук на частотні складові, перш ніж надіслати сигнали до мозку.
Розгляньмо клавішу піаніно. Коли ви натискаєте ноту ля першої октави (A4), ви чуєте ноту частотою 440 Гц — але струна насправді вібрує на частотах 440 Гц (основний тон), 880 Гц (друга гармоніка), 1320 Гц (третя гармоніка) і багатьох вищих гармоніках одночасно. Тембр — різниця між піаніно, скрипкою й трубою, що грають ту саму ноту ля — цілком визначається відносними амплітудами цих гармонік. Спектр Фур'є — це відбиток пальця звуку.
Спектрограма розширює цю ідею, показуючи, як частотний вміст сигналу змінюється в часі — амплітуда, частота й час в одному зображенні. Спектрограми використовуються в розпізнаванні мовлення (голосні звуки мають характерні формантні частоти), у розпізнаванні пташиних співів і в застосунку Shazam, який ідентифікує пісні, зіставляючи відбиток спектрограми фрагмента з базою даних мільйонів пісень.
Швидке перетворення Фур'є
Обчислення перетворення Фур'є для сигналу з n відліків наївним способом вимагає порядку n² арифметичних операцій — це дискретне перетворення Фур'є (ДПФ). Для однієї секунди аудіо, дискретизованого на частоті 44 100 Гц, це майже два мільярди операцій на секунду звуку. Абсолютно непрактично в реальному часі.
У 1965 році Джеймс Кулі та Джон Тьюкі опублікували знаковий алгоритм, який скоротив це до O(n log n) операцій — швидке перетворення Фур'є (ШПФ). Ключова ідея елегантна: ДПФ розміру n можна рекурсивно розбити на два ДПФ розміру n/2, результати яких можна об'єднати за O(n) додаткової роботи. Застосована рекурсивно, ця схема дає множник log n.
ШПФ мало настільки величезний вплив, що Гілберт Стренг назвав його «найважливішим чисельним алгоритмом нашого життя». Воно зробило обробку сигналів у реальному часі практично можливою. Сьогодні ШПФ працює всередині кожного аудіокодека смартфона, кожного чипа Wi-Fi та 4G-радіо (які використовують OFDM — ортогональне частотне мультиплексування, по суті масштабне ШПФ), кожного цифрового осцилографа й кожної радарної системи. Це невидима інфраструктура сучасної цивілізації.
Стиснення зображень і JPEG
Ідея Фур'є природно поширюється на два виміри. Зображення можна розглядати як сигнал, що змінюється в просторі, а не в часі, і його можна розкласти на просторові частотні складові. Високі просторові частоти відповідають дрібним деталям і різким краям; низькі частоти відповідають широким, поступовим тональним ділянкам.
Стиснення JPEG використовує близького родича перетворення Фур'є — дискретне косинусне перетворення (ДКП). Зображення ділиться на блоки пікселів 8×8, кожен блок піддається ДКП, а отримані коефіцієнти квантуються — високочастотні коефіцієнти, до яких людське око менш чутливе, округлюються агресивно або відкидаються повністю. Решта коефіцієнтів потім стискається за допомогою кодування без втрат.
Саме тому сильно стиснені зображення JPEG набувають характерних блокових артефактів: сітка обробки 8×8 стає видимою, коли відкидається забагато коефіцієнтів ДКП. Межі блоків, де незалежні частотні розкладання не збігаються, з'являються як видимі шви. Розуміння Фур'є-аналізу точно пояснює, чому так відбувається і як цього уникнути.
Візуалізуйте суперпозицію хвиль наживо: наш симулятор хвиль дозволяє додавати синусоїдальні хвилі різних частот, амплітуд і фаз та спостерігати, як вони поєднуються, — пряма, практична демонстрація синтезу Фур'є в дії.
Перетворення Фур'є в квантовій механіці
У квантовій механіці стан частинки можна описати або через її положення, або через її імпульс. Ці два описи не є незалежними — вони пов'язані перетворенням Фур'є. Хвильова функція в просторі положень та хвильова функція в просторі імпульсів є парою перетворень Фур'є.
Це математичне співвідношення має глибокий фізичний наслідок: принцип невизначеності Гейзенберга. Базова властивість Фур'є-аналізу полягає в тому, що функція, різко локалізована в одній області, обов'язково розмита в іншій. Сплеск у часі відповідає плаского спектру частот; чистий тон у частоті відповідає нескінченно розтягнутій хвилі в часі.
Застосовано до квантової механіки: частинка, положення якої точно відоме (вузька хвильова функція в просторі положень), має цілком невизначений імпульс (широкий розкид у просторі імпульсів), і навпаки. Принцип невизначеності — це не твердження про збурення вимірюванням, а математична теорема про пари перетворень Фур'є, що відображає щось глибоке про структуру Всесвіту.
Дискретне перетворення Фур'є на практиці
Працюючи з реальними цифровими сигналами, ми завжди маємо справу з дискретними відліками, а не з неперервними функціями. Теорема вибірки — доведена незалежно Гаррі Найквістом і Клодом Шенноном — повідомляє фундаментальне обмеження: щоб достовірно захопити всі частоти до fmax, необхідно вибирати з частотою не менше 2 × fmax відліків за секунду.
Аудіо CD дискретизується з частотою 44 100 Гц, захоплюючи частоти до 22 050 Гц — трохи вище верхньої межі людського слуху, що становить приблизно 20 000 Гц. Коли частота дискретизації надто низька для наявних частот, виникає ефект накладання спектрів (аліасинг): високочастотні складові «згортаються назад» і з'являються як хибні низькочастотні артефакти. Саме тому на кіноплівці лопаті гвинтокрила, що обертаються, іноді здаються такими, що обертаються назад, — частота кадрів занадто повільна, щоб достовірно захопити частоту обертання лопатей.
Перетворення Фур'є з'єднує неперервне й дискретне, нескінченне й скінченне, часову область і частотну область. Це лінза, що дозволяє науковцям та інженерам бачити те саме явище з двох взаємодоповнюючих перспектив — і в цьому подвоєному баченні задачі, нерозв'язні в одній області, часто стають елементарними в іншій.