FFT — Transformasi Fourier Cepat Dijelaskan Sederhana

FFT, atau fast Fourier transform, adalah cara cepat untuk menghitung discrete Fourier transform (DFT). Jika Anda mulai dari sampel yang berjarak sama, DFT memberi tahu seberapa besar setiap pola frekuensi diskret muncul dalam sampel tersebut.

Poin pentingnya adalah FFT tidak mengubah hasil. FFT memberikan nilai DFT yang sama seperti rumus langsung, tetapi mencapainya dengan jauh lebih sedikit pekerjaan yang berulang.

FFT Dalam Satu Kalimat

FFT adalah algoritma yang lebih cepat untuk mendapatkan bilangan domain frekuensi yang sama yang sudah didefinisikan oleh DFT.

Apa yang Diukur DFT

Misalkan Anda memiliki sampel $x_0, x_1, \dots, x_{N-1}$. DFT menghasilkan bilangan $X_0, X_1, \dots, X_{N-1}$ yang didefinisikan oleh

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}$$

Setiap $X_k$ mengukur seberapa kuat data cocok dengan satu pola frekuensi diskret.

Jika sampel berjarak sama pada laju sampling $f_s$, maka jarak antar bin frekuensi yang berdekatan adalah

$$\frac{f_s}{N}$$

Kondisi itu penting. Tanpa laju sampling yang diketahui, Anda tetap memiliki bin DFT, tetapi Anda tidak dapat memberinya label sebagai frekuensi fisik seperti hertz.

Mengapa FFT Lebih Cepat

FFT adalah keluarga algoritma untuk menghitung DFT secara efisien. Trik utamanya adalah memanfaatkan kembali struktur pada faktor eksponensial kompleks alih-alih menghitung ulang penjumlahan yang hampir identik dari awal.

Versi yang paling mudah dibayangkan adalah FFT radix-2. Metode ini bekerja paling alami saat $N$ adalah pangkat dari $2$, dan membagi satu transformasi panjang-$N$ menjadi dua transformasi panjang-$N/2$ sebelum menggabungkan hasilnya.

Untuk DFT langsung, jumlah operasi aritmetika bertambah seorde $N^2$. Untuk metode FFT yang umum, jumlahnya turun menjadi sekitar $N \log N$.

Perbedaan itulah yang membuat FFT penting dalam praktik. Untuk masukan kecil, kedua metode mungkin sama-sama terasa memadai. Untuk masukan besar, FFT jauh lebih cepat.

Bagaimana FFT Membagi Pekerjaan

Alih-alih membandingkan setiap sampel dengan setiap pola frekuensi secara langsung, FFT memecah masalah menjadi transformasi-transformasi yang lebih kecil lalu menggabungkannya kembali dengan faktor fase.

Pembagian standar adalah:

1. Masukkan sampel berindeks genap ke dalam satu daftar.
2. Masukkan sampel berindeks ganjil ke dalam daftar lain.
3. Hitung transformasi yang lebih kecil pada daftar-daftar itu.
4. Gabungkan kedua bagiannya.

Ini adalah pendekatan divide-and-conquer yang diterapkan pada analisis frekuensi.

Contoh FFT 4 Titik

Ambil sinyal 4 titik

$$x = [1, 0, 1, 0]$$

Pola ini bergantian antara $1$ dan $0$, jadi kita mengharapkan adanya struktur frekuensi, bukan hasil yang benar-benar datar.

Bagi menjadi indeks genap dan ganjil:

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

DFT 2 titik dari bagian genap adalah

$$E = [2, 0]$$

dan DFT 2 titik dari bagian ganjil adalah

$$O = [0, 0]$$

Untuk FFT 4 titik, langkah penggabungannya adalah

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

dengan

$$W_4 = e^{-i 2 \pi / 4}$$

Karena $O_k = 0$, penggabungannya menjadi sangat sederhana:

$$X = [2, 0, 2, 0]$$

Sekarang tafsirkan hasilnya.

$X_0 = 2$ adalah suku frekuensi nol, jadi ini mencerminkan nilai rata-rata sampel yang tidak nol. Nilai tak nol pada $X_2$ menangkap bagian pola yang bergantian dalam kasus 4 titik ini. Jika Anda mengurangkan mean terlebih dahulu, suku $X_0$ akan hilang dan komponen yang bergantian akan terlihat lebih jelas.

Contoh ini kecil, tetapi idenya dapat diperluas: selesaikan transformasi-transformasi yang lebih kecil, lalu gabungkan, alih-alih membangun ulang seluruh penjumlahan setiap saat.

Kesalahan Umum tentang FFT

Menganggap FFT dan DFT Memberikan Hasil yang Berbeda

Tidak. FFT adalah metode yang lebih cepat untuk menghitung DFT.

Membaca Bin sebagai Frekuensi Fisik Terlalu Cepat

Lokasi bin baru menjadi frekuensi fisik ketika jarak antar sampel diketahui. Jika laju sampling adalah $f_s$, maka jarak antar bin adalah $f_s/N$ untuk sampel yang berjarak sama.

Menganggap Zero-Padding Menambah Informasi Baru

Zero-padding dapat membuat spektrum terlihat lebih halus karena ia mengambil sampel transformasi dasarnya dengan lebih rapat, tetapi tidak menambahkan data terukur yang baru.

Mengabaikan Persiapan Sinyal

Penghilangan mean, windowing, dan pilihan sampling yang cermat bisa sangat berpengaruh. Jika kondisi-kondisi itu diabaikan, keluaran FFT mungkin tetap benar secara matematis untuk sampel yang diberikan, tetapi menyesatkan saat ditafsirkan.

Di Mana FFT Digunakan

FFT muncul di mana pun Anda membutuhkan informasi domain frekuensi yang cepat dari data hasil sampling. Contoh umum meliputi analisis spektrum, filtering, pemrosesan citra, analisis getaran, penyelesaian persamaan diferensial secara numerik, serta komputasi polinomial atau konvolusi yang cepat.

Alasannya praktis: banyak operasi menjadi lebih mudah atau lebih cepat setelah berpindah dari domain sampel ke domain frekuensi.

Coba Kasus Serupa

Ambil $8$ sampel berjarak sama dari satu gelombang sinus selama satu periode penuh dan hitung DFT-nya dengan kalkulator atau skrip. Lalu tambahkan offset konstan dan bandingkan keluaran barunya. Nilai yang lebih kuat pada $X_0$ adalah cara sederhana untuk melihat apa yang dipisahkan oleh FFT.