FFT простими словами: як працює швидке перетворення Фур'є

3D Simulations

📐 Алгоритм · Обробка сигналів

📅 Березень 2026 ⏱ 15 хв 🎓 Середній–просунутий · Останнє оновлення: 5 липня 2026 р.

FFT простими словами: чому швидке перетворення Фур'є змінило світ

Алгоритм FFT Кулі-Тьюкі знижує дискретне перетворення Фур'є з O(N²) множень до O(N log N) — прискорення, яке зробило обчислювально можливими обробку аудіо в реальному часі, стиснення JPEG, бездротову модуляцію та аналіз радарних сигналів. Алгоритму вже 60 років, але розуміння того, чому він працює, досі лишається одним із найелегантніших осяянь у комп'ютерній науці.

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

1. Дискретне перетворення Фур'є

DFT перетворює послідовність із N відліків у часовій області на N коефіцієнтів у частотній області. Кожен вихід X[k] вимірює, скільки частоти f_k = k/N (у циклах на відлік) присутньо у вхідному сигналі.

Означення DFT: X[k] = Σ_{n=0}^{N−1} x[n] · e^{−j 2π k n / N} k = 0, 1, ..., N−1 Обернене DFT: x[n] = (1/N) · Σ_{k=0}^{N−1} X[k] · e^{+j 2π k n / N} Комплексна експонента: e^{−j θ} = cos θ − j sin θ Тлумачення X[k]: амплітуда |X[k]| на частоті k/N циклів/відлік фаза arg(X[k]) = зсув фази цієї частотної складової

DFT застосовується всюди: аналіз спектра аудіо, фільтрація шуму, стиснення зображень (DCT), згортка, кореляція та схеми модуляції. Проблема в тому, щоб обчислити його швидко.

2. Чому DFT має складність O(N²)

Щоб обчислити кожне X[k], ви підсумовуєте N доданків. Існує N значень k. Тож загальна кількість комплексних множень дорівнює N × N = N².

Наївне DFT

O(N²)

N = 1024 → ~1 млн операцій

FFT Кулі-Тьюкі

O(N log N)

N = 1024 → ~10 тис. операцій

N (відліків)	Операції DFT (N²)	Операції FFT (N log₂N)	Прискорення
64	4 096	384	~10×
1 024	1 048 576	10 240	~100×
65 536	4 294 967 296	1 048 576	~4 000×
1 048 576 (1 млн)	10¹²	20 971 520	~50 000×

Історичний вплив: До FFT обчислення 1024-точкового DFT на апаратурі 1960-х займало кілька хвилин. Після праці Кулі та Тьюкі 1965 року воно стало займати секунди. Це єдине алгоритмічне покращення уможливило сейсмічний аналіз, обробку телевізійних зображень і, зрештою, увесь сучасний цифровий зв'язок.

3. Розділяй і володарюй: парно-непарний поділ

Ключове осяяння (Кулі-Тьюкі, 1965; раніше відкрите Гауссом близько 1805 року): розбити N-точкове DFT на два N/2-точкові DFT — одне для відліків із парними індексами, друге — з непарними.

X[k] = Σ_{n=0}^{N−1} x[n] · W_N^{kn} де W_N = e^{−j2π/N} (повертальний множник) Розбиваємо на парні (n = 2m) та непарні (n = 2m+1) індекси: X[k] = Σ_{m=0}^{N/2−1} x[2m] · W_N^{2km} + Σ_{m=0}^{N/2−1} x[2m+1] · W_N^{k(2m+1)} = Σ_{m=0}^{N/2−1} x[2m] · W_{N/2}^{km} + W_N^k · Σ_{m=0}^{N/2−1} x[2m+1] · W_{N/2}^{km} = E[k] + W_N^k · O[k] де E[k] = DFT парних відліків (N/2-точкове DFT) O[k] = DFT непарних відліків (N/2-точкове DFT) використовуючи W_N² = W_{N/2}

Це вдвічі зменшує розмір задачі. Оскільки E[k] та O[k] періодичні з періодом N/2, нам потрібно обчислити їх лише раз і повторно використати для k та k + N/2:

Оновлення метеликом: X[k] = E[k] + W_N^k · O[k] X[k + N/2] = E[k] − W_N^k · O[k] (бо W_N^{k+N/2} = −W_N^k за періодичністю) Рекурсія: T(N) = 2·T(N/2) + O(N) Розв'язок: T(N) = O(N log N)

4. Діаграма-метелик

Метелик — це фундаментальна одиниця FFT: два входи дають два виходи за один крок. У FFT з N=8 три стадії по N/2 = 4 метелики обчислюють повне перетворення.

Кожне перехрестя «X» — це операція-метелик. У N-точковому FFT є log₂N стадій, кожна з N/2 метеликами — що дає загалом N/2 × log₂N операцій-метеликів.

5. Повертальні множники та періодичність

Член W_N^k = e^{−j2πk/N} називають повертальним множником (twiddle factor, або множником повороту). Ключова симетрія, що робить FFT ефективним:

Періодичність: W_N^{k+N} = W_N^k (поворот на повне коло → те саме значення) Спряжена симетрія: W_N^{k+N/2} = −W_N^k (поворот на 180° → зміна знака) Зведення: W_N^{2k} = W_{N/2}^k (множник удвічі меншого розміру) Перші 4 множники (N=8): W₈⁰ = 1 (без повороту) W₈¹ = (√2/2)(1−j) ≈ 0.707 − 0.707j (−45°) W₈² = −j = (0−1j) (−90°) W₈³ ≈ −0.707 − 0.707j (−135°) Симетрія −W_N^k = W_N^{k+N/2} означає, що кожен метелик повторно використовує той самий множник для двох виходів — знову вдвічі зменшуючи кількість множень.

Попереднє обчислення множників: В оптимізованому FFT усі повертальні множники обчислюються раз і зберігаються в таблиці пошуку. Головний цикл лише переміщує дані (додавання/віднімання метелика) плюс одне комплексне множення на метелик. Множення — це 4 дійсні множення та 2 додавання (можна звести до 3 множень трюком Карацуби).

6. Перестановка бітовою інверсією

Алгоритм Кулі-Тьюкі природно видає вихід у перемішаному порядку. Для обчислення «на місці» вхід спершу треба переупорядкувати за допомогою перестановки бітовою інверсією: індекс n замінюється на його двійкові цифри, записані у зворотному порядку.

Бітова інверсія для N=8 (3 біти): Індекс Двійковий Обернений Новий індекс 0 000 000 0 1 001 100 4 2 010 010 2 3 011 110 6 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7 Обмін: (0\leftrightarrow0), (1\leftrightarrow4), (2\leftrightarrow2), (3\leftrightarrow6), (4\leftrightarrow1)*, (5\leftrightarrow5), (6\leftrightarrow3)*, (7\leftrightarrow7) (* уже опрацьовано зворотним обміном — міняти лише коли rev > i, щоб уникнути подвійного обміну)

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

Чистий ітеративний (на місці) FFT Кулі-Тьюкі за основою 2 на JavaScript:

// FFT розміру N (має бути степенем 2)
// Вхід: масиви re[] та im[] (дійсна/уявна частини)
// Вихід: re[] та im[] змінюються на місці
function fft(re, im) {
  const N = re.length;

  // 1. Перестановка бітовою інверсією
  let j = 0;
  for (let i = 1; i < N; i++) {
    let bit = N >> 1;
    for (; j & bit; bit >>= 1) j ^= bit;
    j ^= bit;
    if (i < j) {
      [re[i], re[j]] = [re[j], re[i]];
      [im[i], im[j]] = [im[j], im[i]];
    }
  }

  // 2. Стадії метеликів
  for (let len = 2; len <= N; len <<= 1) {
    const halfLen = len >> 1;
    const ang = -2 * Math.PI / len;     // приберіть мінус для оберненого FFT
    const wRe = Math.cos(ang);
    const wIm = Math.sin(ang);

    for (let i = 0; i < N; i += len) {
      let curRe = 1, curIm = 0;         // починається з W^0 = 1

      for (let k = 0; k < halfLen; k++) {
        const uRe = re[i + k];
        const uIm = im[i + k];
        const vRe = re[i + k + halfLen] * curRe - im[i + k + halfLen] * curIm;
        const vIm = re[i + k + halfLen] * curIm + im[i + k + halfLen] * curRe;

        // Метелик: u + W·v  та  u - W·v
        re[i + k]          = uRe + vRe;
        im[i + k]          = uIm + vIm;
        re[i + k + halfLen] = uRe - vRe;
        im[i + k + halfLen] = uIm - vIm;

        // Повертаємо повертальний множник на W_len
        const newRe = curRe * wRe - curIm * wIm;
        curIm       = curRe * wIm + curIm * wRe;
        curRe       = newRe;
      }
    }
  }
}

// Використання: обчислити спектр дійсного сигналу
const N = 1024;
const re = new Float64Array(N);
const im = new Float64Array(N);  // нулі для дійсного входу
// ... заповнити re[] відліками ...
fft(re, im);
// re[k], im[k] = комплексний спектр на частоті k/N (циклів/відлік)
// |X[k]| = Math.hypot(re[k], im[k])
// фаза   = Math.atan2(im[k], re[k])

Зауваження щодо продуктивності: для аудіо (N=2048 на 44,1 kHz) це обробляє кадр за <1 ms у сучасному JS. Для N=1 млн відліків використовуйте типізовані масиви (Float32Array) та WASM для найкращої продуктивності. AnalyserNode з WebAudio API обгортає нативний FFT — використовуйте його для аудіовізуалізаторів у реальному часі.

8. Застосування: аудіо, зображення, OFDM

Аудіоспектр і фільтрація

Обробка аудіо безперервно використовує FFT: взяти N відліків (вікно), FFT → змінити частотні біни (еквалайзер, придушення шуму, визначення висоти тону) → IFFT → перекривання-додавання для відновлення. Аудіо в реальному часі на 44,1 kHz використовує FFT на N = 512–4096 точок, оновлюючи 10–100 разів на секунду.

Швидка згортка O(N log N)

Теорема про згортку: поточкове множення в частотній області = згортка в часовій області. Згортка двох N-точкових сигналів напряму: O(N²). Через FFT → множення → IFFT: O(N log N). Застосовується в: аудіореверберації (згорткова реверберація з імпульсними відгуками), розмитті зображень, множенні многочленів.

Теорема про згортку: (x * h)[n] = IFFT{ FFT{x} \cdot FFT{h} } Складність: 3 \times O(N log N) проти O(N²) напряму Точка перетину: FFT швидше при N > ~32 відліків

JPEG: двовимірне DCT

Стиснення JPEG використовує двовимірне дискретне косинусне перетворення (DCT-II) на блоках 8×8. DCT — це дійснозначна спеціалізація DFT (лише косинусний базис, без синуса). Більшість енергії концентрується в низькочастотних коефіцієнтах DCT → агресивно квантують високочастотні коефіцієнти. Двовимірне DCT 8×8 обчислюється через два одновимірні DCT (спочатку рядок, потім стовпець) — кожне O(8 log 8) ≈ O(24).

Бездротова модуляція OFDM

OFDM (мультиплексування з ортогональним частотним поділом) — використовується у Wi-Fi, 4G/5G, цифровому радіо DAB — кодує дані на N ортогональних піднесучих. IFFT перетворює символи частотної області (QAM) на часову форму сигналу для передавання. Приймач застосовує FFT до отриманого сигналу назад у частотну область. N = 64 (Wi-Fi 802.11a/g), 2048 (LTE), 4096 (5G NR).

Застосування	Типове N	Область
Відображення аудіоспектра	512–4096	1D FFT, дійсний вхід
Стиснення MP3 / AAC	512–2048 (MDCT)	Модифіковане DCT
Стиснення JPEG	блоки 8×8 (DCT)	2D DCT
Реконструкція зображень МРТ	256²–1024²	2D FFT (k-простір)
Стиснення радарного імпульсу	512–65536	1D FFT, узгоджений фільтр
OFDM 5G NR	128–4096	IFFT для модуляції
Множення многочленів	Будь-який степінь 2	1D FFT (NTT для точного)