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

1. Основна інтуїція

Уявіть, що ви обертаєте сигнал навколо кола з різними швидкостями. За більшості швидкостей додатні та від'ємні частини сигналу взаємно знищуються, і центр мас залишається біля початку координат. Але коли ви обертаєте точно з частотою компонента в сигналі, піки завжди потрапляють на той самий бік — центр мас зміщується від початку координат. Перетворення Фур'є вимірює, наскільки далеко зміщується центр мас на кожній частоті.

Цю прекрасну геометричну інтерпретацію популяризував Грант Сандерсон (3Blue1Brown), і вона прямо відповідає інтегральному означенню: ми множимо сигнал на обертову комплексну експоненту та інтегруємо за часом.

2. Ряди Фур'є

Для періодичних функцій Жозеф Фур'є (1822) показав, що будь-яку достатньо «добру» функцію f(t) з періодом T можна записати як нескінченну суму синусоїд:

Кожен коефіцієнт cₙ — комплексне число, модуль якого є амплітудою n-ї гармоніки, а аргумент — її фазою. Цей ряд збігається до f(t) майже всюди.

Приклад — прямокутна хвиля: Прямокутна хвиля, що коливається між ±1, є сумою непарних гармонік: f(t) = (4/π)(sin t + sin(3t)/3 + sin(5t)/5 + …). Додавання більшої кількості членів робить кути різкішими.

3. Перетворення Фур'є

Для неперіодичних сигналів скінченної енергії ряд стає інтегралом — перетворенням Фур'є:

F(ξ) — це представлення f(t) в частотній області. Модуль |F(ξ)| показує, скільки частоти ξ присутньо; аргумент F(ξ) дає фазу цього компонента.

Ключові властивості

• Лінійність: FT(af + bg) = a·FT(f) + b·FT(g)
• Теорема про згортку: множення в часі = згортка в частоті (і навпаки). Це робить фільтрацію тривіально швидкою.
• Теорема Парсеваля: повна енергія зберігається: ∫|f|² dt = ∫|F|² dξ.
• Принцип невизначеності: вузький сплеск у часі має широкий частотний спектр; чистий тон (вузький у частоті) триває вічно в часі.

4. Дискретне перетворення Фур'є (DFT)

Комп'ютери працюють із дискретизованими даними — N відліків зі швидкістю f_s (Гц). Дискретне перетворення Фур'є бере N відліків у часовій області та повертає N коефіцієнтів частотної області:

Частотна роздільна здатність становить Δf = f_s / N Гц на бін. За теоремою Найквіста найвища представна частота становить f_s / 2 — потрібно дискретизувати з подвоєною найвищою частотою, що цікавить.

5. Швидке перетворення Фур'є (FFT)

Наївне DFT потребує O(N²) операцій — для N = 1 000 000 це 10¹² операцій. Непридатно. Алгоритм FFT Кулі–Тьюкі (1965) використовує рекурсивну структуру DFT, щоб звести це до O(N log N):

Ключова ідея: якщо N парне, DFT розміру N можна розбити на два DFT розміру N/2 — одне для відліків з парними індексами, одне для непарних. Цей підхід «розділяй і володарюй» застосовується рекурсивно до досягнення перетворень розміру 1.

Для N = 1 000 000 FFT потребує ~20 мільйонів операцій замість 10¹². FFT — один із найважливіших алгоритмів, які будь-коли було відкрито. Джеймс Кулі та Джон Тьюкі опублікували його в 1965 році, хоча Гаусс використовував еквівалентний метод ще в 1805 році.

6. Де воно трапляється

7. Реалізація DFT на JavaScript

Ось наївне O(N²) DFT на JavaScript — правильне, але повільне. Корисне для розуміння, не для продакшну.

// Наївне DFT — O(N²). Для N ≤ 1024 цього достатньо швидко для демо.
function dft(signal) {
  const N = signal.length;
  const result = [];

  for (let k = 0; k < N; k++) {
    let re = 0, im = 0;
    for (let n = 0; n < N; n++) {
      const angle = (2 * Math.PI * k * n) / N;
      re += signal[n] * Math.cos(angle);
      im -= signal[n] * Math.sin(angle);
    }
    result.push({ re, im,
      freq: k,
      amp: Math.sqrt(re*re + im*im) / N,
      phase: Math.atan2(im, re)
    });
  }
  return result;
}

// Відновити сигнал з перших `nTerms` компонентів DFT
function idft(freq, nTerms, N) {
  const out = new Float64Array(N);
  for (let i = 0; i < N; i++) {
    for (let k = 0; k < nTerms; k++) {
      const angle = (2 * Math.PI * freq[k].freq * i) / N;
      out[i] += freq[k].amp * Math.cos(angle - freq[k].phase) * N;
    }
  }
  return out;
}

AnalyserNode з Web Audio API використовує вбудоване FFT (розміри — степені двійки до 32 768) і повертає дані амплітуди в реальному часі.

8. Спробуйте симуляцію

Симуляція Фур'є дозволяє намалювати форму хвилі та спостерігати її частотний спектр у реальному часі. Ви можете додавати гармоніки одну за одною, щоб побачити, як вони будують прямокутну, пилкоподібну чи трикутну хвилю.