Dari DFT ke FFT

Rekaman suara, getaran mesin, sampai data harga harian punya bentuk yang sama: deretan angka yang diukur berurutan sepanjang waktu. Cara pandang ini disebut domain waktu. Masalahnya, sebagian pertanyaan sulit dijawab dari deretan itu: dari rekaman getaran mesin yang berisik, telinga kita sulit menunjuk frekuensi mana yang paling kuat. Transformasi Fourier Diskrit (Discrete Fourier Transform, DFT) menawarkan cara pandang lain: sinyal diskrit sepanjang N sampel dapat dinyatakan sebagai jumlah komponen sinus, dan DFT menghitung kuat serta fase tiap komponen.

Menghitung DFT secara langsung memerlukan sekitar N² operasi. Algoritma Fast Fourier Transform (FFT) menghasilkan nilai yang persis sama hanya dengan O(N log N) operasi, dan di NumPy tersedia lewat np.fft.fft. Pada chapter ini kita menghitung FFT pertama pada sinus kecil yang bersih, membaca anatomi output complex128 yang sudah dikenalkan di Bilangan Kompleks, lalu menyusun kembali sinyal aslinya dengan np.fft.ifft. Pemahaman perioda dari Fungsi Trigonometri terus terpakai di sini.

Yang kita bedah pada chapter ini:

DFT sebagai dekomposisi sinyal menjadi komponen sinus
Lompatan efisiensi dari O(N²) ke O(N log N)
Rekonstruksi sinyal dari spektrum dengan np.fft.ifft

DFT: Sinyal sebagai Jumlah Komponen Sinus #

Contoh terkecil yang bisa kita periksa satu per satu adalah sinyal 8 sampel: 8 titik waktu yang menjangkau tepat satu detik, diisi sinus murni 1 Hz tanpa derau. Karena isi sinyalnya sudah kita ketahui, hasil DFT-nya mudah dinilai benar atau salah.

python
import numpy as np

t = np.arange(8) / 8                 # 8 titik waktu, jarak 0.125 detik
sinyal = np.sin(2 * np.pi * 1 * t)   # sinus murni 1 Hz
spec = np.fft.fft(sinyal)
print("dtype    :", spec.dtype)
print("bentuk   :", spec.shape)
print("spec[:4] :", np.round(spec[:4], 3))
print("magnitude:", np.abs(spec).round(4))

Output yang Dihasilkan:

text
dtype    : complex128
bentuk   : (8,)
spec[:4] : [ 0.+0.j -0.-4.j  0.-0.j  0.-0.j]
magnitude: [0. 4. 0. 0. 0. 0. 0. 4.]

Mari kita telaah baris demi baris:

Baris 3 (t = np.arange(8) / 8): t berisi 8 titik waktu dari 0 sampai 0.875 detik, sehingga 8 sampel mencakup satu periode penuh sinus.
Baris 4 (sinyal = np.sin(...)): sinus beramplitudo 1 pada 1 Hz; faktor 2 * np.pi mengubah frekuensi ke radian per detik, konvensi dari Fungsi Trigonometri.
Baris 5 (spec = np.fft.fft(sinyal)): np.fft.fft menerima sinyal 1-D dan mengembalikan array complex128 berpanjang sama, berisi koefisien DFT.
Baris 8 (np.round(spec[:4], 3)): empat koefisien pertama dibulatkan ke 3 desimal agar mudah dibaca; hanya bin indeks 1 yang berisi nilai besar, berupa -4j.
Baris 9 (np.abs(spec).round(4)): np.abs pada array kompleks menghitung magnitude — jarak tiap koefisien dari titik nol pada bidang kompleks.

Dari magnitude terlihat hanya dua bin yang hidup: bin 1 dan bin 7, keduanya bernilai 4. Nilai 4 itu persis (N/2) × amplitudo = 4 × 1, jadi DFT melaporkan amplitudo lewat skala tetap ini. Bin 1 adalah komponen +1 Hz; bin 7 cerminnya pada -1 Hz, kebiasaan yang kita bongkar pada chapter fftfreq dan Spektrum Frekuensi. Koefisien pada bin lain tidak persis nol — residunya sekitar 10⁻¹⁶ — sehingga setelah dibulatkan tampil sebagai -0. atau 0.-0.j.

Dari O(N²) ke O(N log N) #

Definisi DFT menimbang seluruh N sampel untuk setiap koefisien dengan faktor fase berbeda-beda; total biayanya sekitar N² perkalian kompleks. Algoritma FFT — diperkenalkan luas oleh Cooley dan Tukey pada 1965 — memecah sinyal menjadi sampel berindeks genap dan ganjil, mengulang pembagian itu secara rekursif, lalu menggabungkan hasilnya; total biayanya tinggal sekitar N log₂ N.

python
import numpy as np

for n in [8, 1024, 65536]:
    op_dft = n * n
    op_fft = int(n * np.log2(n))
    print(f"N={n:>6}: DFT ~{op_dft:>12,} op | FFT ~{op_fft:>9,} op")

Output yang Dihasilkan:

text
N=     8: DFT ~          64 op | FFT ~       24 op
N=  1024: DFT ~   1,048,576 op | FFT ~   10,240 op
N= 65536: DFT ~4,294,967,296 op | FFT ~1,048,576 op

Penjelasan blok di atas:

Baris 4 (op_dft = n * n): perkiraan jumlah operasi DFT yang dihitung langsung.
Baris 5 (op_fft = int(n * np.log2(n))): perkiraan jumlah operasi FFT; np.log2 memberi logaritma basis 2, lalu int membulatkannya ke bilangan bulat.
Baris 6: format :>12, meratakan angka ke kanan dan menyisipkan pemisah ribuan agar mudah dibaca.

Angka di atas hitungan operasi, bukan pengukuran waktu, tetapi skala lompatannya nyata:

N	DFT ~ N²	FFT ~ N log₂ N	Rasio
8	64	24	≈ 2.7×
1.024	1.048.576	10.240	≈ 102×
65.536	4.294.967.296	1.048.576	4.096×

Pada N = 65.536, FFT bekerja sekitar empat ribu kali lebih ringan — inilah yang membuat analisis spektrum sinyal panjang layak dilakukan. Implementasi FFT di NumPy bernama pocketfft dan menangani panjang berapa pun; panjang berfaktor kecil (misalnya pangkat dua) paling lancar, tetapi zero-padding tidak wajib.

Mengembalikan Sinyal dengan np.fft.ifft #

DFT punya invers: dari spektrum, sinyal di domain waktu dapat disusun kembali. np.fft.ifft menerima array spektrum dan mengembalikan sinyal waktunya. Pasangan fft lalu ifft pada spektrum yang tidak diubah mengembalikan sinyal semula hingga residu floating-point.

python
import numpy as np

t = np.arange(8) / 8
sinyal = np.sin(2 * np.pi * 1 * t)
hasil = np.fft.ifft(np.fft.fft(sinyal))
print("dtype hasil :", hasil.dtype)
print("sinyal asli :", sinyal.round(4))
print("riil ifft   :", np.real(hasil).round(4))
print("selisih maks:", np.abs(hasil - sinyal).max())

Output yang Dihasilkan:

text
dtype hasil : complex128
sinyal asli : [ 0.      0.7071  1.      0.7071  0.     -0.7071 -1.     -0.7071]
riil ifft   : [ 0.      0.7071  1.      0.7071  0.     -0.7071 -1.     -0.7071]
selisih maks: 1.1102230246251565e-16

Uraian baris-per-barisnya:

Baris 5 (hasil = np.fft.ifft(np.fft.fft(sinyal))): output np.fft.fft(sinyal) langsung menjadi argumen np.fft.ifft — pola round-trip yang lazim.
Baris 6: dtype hasil tetap complex128; np.fft.ifft tidak pernah mengembalikan array riil walaupun sinyal aslinya riil.
Baris 8 (np.real(hasil).round(4)): bagian riil diambil dengan np.real lalu dibulatkan; cocok dengan baris sinyal asli nilai demi nilai.
Baris 9: selisih terbesar dengan sinyal asli adalah 1.1102230246251565e-16 — bukan nol eksak, hanya satu-dua langkah di atas nol pada skala float64.

Dengan np.fft.fft dan np.fft.ifft, gerbang bolak-balik antara domain waktu dan domain frekuensi sudah kita miliki. Pertanyaan berikutnya praktis: bin ke-k mewakili berapa hertz? Jawabannya ada pada np.fft.fftfreq.