The FFT

Từ vựng

English

Split, twiddle, recurse

The FFT factors an $N$-point DFT into two $N/2$-point DFTs plus $N$ combining multiplies — and recurses. Each butterfly is one multiply-and-add with a twiddle factor $W_N = e^{-j2\pi/N}$; $\log_2 N$ stages of $N/2$ butterflies.

Example

At $N = 1024$: direct $N^2 = 1\,048\,576$ operations, FFT $N\log_2 N = 10\,240$ — 102× fewer ✓ (N = 4096: 341×).

{exercise:uni-ee1203-count}

Luyện tập

Counting complex operations, the N = 1024 FFT beats the direct DFT by —

Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay

English

1 Hz bins at $f_s = 1$ kHz: $N = 1024$ gives $0.977$ Hz ✓. At 10 ns per operation the transform takes about 100 µs — real time against a 1.024 s record. Bin 100 is $100 \times 0.977 = 97.66$ Hz: the bin-to-hertz map is $k f_s/N$.

{exercise:uni-ee1203-bin} {exercise:uni-ee1203-stages}

Luyện tập

fs = 1 kHz and N = 1024: bin 100 sits at —

Độ khó 1/5 · 100 xu + phần thưởng nhỏ khi hoàn thành lần đầu tiên hôm nay