Fourier, DFT và FFT trực quan

BÀI NÀY NỐI TỪ ĐÂU?

Ta đã có finite record $x[n]$ và muốn đổi representation sang các complex frequency coefficients. Ý tưởng cốt lõi không phải “FFT tìm tần số”, mà là đổi basis.

ONE IDEA · THREE NAMES

Fourier idea→DFT→FFT algorithm

Fourier là family of representations dựa trên sinusoid/complex exponential. DFT là một transform cụ thể cho $N$ samples. FFT là họ thuật toán tính DFT nhanh hơn, không phải một transform khác.

01 · FOURIER LÀ MỘT BÀI TOÁN ĐỔI BASIS

Thay vì hỏi “sample thứ $n$ bằng bao nhiêu?”, ta hỏi “mỗi complex sinusoid cần hệ số bao nhiêu để dựng lại record?”.

TIME COORDINATES $x[0],x[1],\ldots,x[N-1]$ một vector trong sample basis

→ change basis →

COMPLEX SINUSOID BASIS $e^{j2\pi kn/N}$ mỗi

k

là một direction dao động khác

→

FREQUENCY COORDINATES $X[k]$ complex coefficient của từng basis vector

02 · FOURIER TRANSFORM, DTFT VÀ DFT KHÔNG PHẢI CÙNG MỘT OBJECT

Chúng dùng cùng family of ideas nhưng khác signal model và frequency variable.

CONTINUOUS-TIME FOURIER TRANSFORM

$x(t)\leftrightarrow X(f)$

Time liên tục, frequency variable cũng liên tục.

DTFT

$x[n]\leftrightarrow X(e^{j\omega})$

Time rời rạc nhưng normalized frequency vẫn là biến liên tục và tuần hoàn.

DFT

$N$ samples ↔ $N$ coefficients

Một finite record cho một finite set frequency samples/bins.

Khi software receiver “chạy FFT trên một buffer”, về mặt toán học nó thường đang tính DFT của buffer đó. Vì vậy Bài 7 tập trung vào DFT, nhưng mental model vẫn nối về family Fourier rộng hơn.

03 · MỖI DFT BIN LÀ MỘT COMPLEX INNER PRODUCT

Một candidate bin được de-rotate khỏi record. Nếu phase progression khớp, các contribution cộng coherent.

X[k]=\sum_{n=0}^{N-1}x[n]e^{-j2\pi kn/N}

$N$ số samples trong finite record

$n$ sample index

$k$ basis / DFT-bin index

$X[k]$ complex projection coefficient

IF FREQUENCY MATCHESde-rotated vectors alignvector sum lớn

vs

IF INTEGER BIN MISMATCHESvectors rotate around the circlevector sum lý tưởng triệt tiêu

Đây là cách đọc rất hữu ích của dấu âm trong exponent. Ta nhân record với conjugate của candidate basis. Component đúng frequency bị “đứng yên” sau de-rotation, còn component khác tiếp tục quay.

04 · BIN INDEX KHÔNG TỰ NÓ LÀ HERTZ

Physical frequency của bin phụ thuộc sampling rate và FFT/DFT length.

BIN SPACING $\Delta f=f_s/N$ Hz giữa hai adjacent bins

OBSERVATION TIME $T_{\mathrm{obs}}=N/f_s$ duration của record

SAME RELATION $\Delta f=1/T_{\mathrm{obs}}$ bin spacing gắn trực tiếp với record duration

Với unshifted DFT ordering, index tăng từ zero tới $N-1$ . Nhưng physical frequencies ở nửa sau thường đại diện cho negative frequencies.

LOW INDEX $0\le k<N/2$

f_k=k\,f_s/N

→

NYQUIST BIN $k=N/2$ special even-

N

bin at the Nyquist boundary

→

UPPER INDEX $N/2<k<N$

f_k=(k-N)f_s/N

k=0

→

0\,\mathrm{Hz}

k=1

→

+1\,\mathrm{Hz}

k=31

→

+31\,\mathrm{Hz}

k=32

→ Nyquist bin

k=63

→

-1\,\mathrm{Hz}

05 · INTERACTIVE LAB

Trước tiên nhìn DFT như vector projection. Sau đó chuyển sang leakage/window để thấy finite-record effects.

Basis projection dùng complex tone đúng bin để cho thấy de-rotation và coherent sum. Leakage & window dùng real tone, thay $N$ , fractional-bin offset và window để thấy spectral spreading.

Input bin $k_0=7$ Candidate bin $k=7$

INPUT $k_0=7$

z[n]=e^{j2\pi k_0n/N}

CANDIDATE $k=7$

e^{-j2\pi kn/N}

RESIDUAL ROTATION $0\,\text{cycle/record}$

k_0-k

NORMALIZED SUM $1.000$ coherent addition

INPUT COMPLEX TONE $e^{j2\pi k_0n/N}$

×

CONJUGATE BASIS $e^{-j2\pi kn/N}$

→

PRODUCTS $e^{j2\pi(k_0-k)n/N}$

→ sum →

DFT RESPONSEvectors align

PRODUCT PHASORSmỗi sample đóng góp một unit vector trước khi cộng

Khi $k=k_0$ , mọi product có angle zero nên cộng coherent. Với một integer-bin mismatch, product phasors đi đủ vòng và tổng lý tưởng triệt tiêu.

06 · LEAKAGE ĐẾN TỪ FINITE RECORD

Một finite record tương đương signal bị nhân với một window theo time.

Rectangular window là trường hợp đơn giản nhất: giữ nguyên $N$ samples rồi bỏ mọi thứ bên ngoài record. Multiplication theo time tương ứng convolution theo frequency, nên một ideal spectral line bị “smear” theo spectrum của window.

BIN-CENTERED $7.0\,\mathrm{Hz}$ integer cycles trong observation interval

→

OFF-BIN $7.5\,\mathrm{Hz}$ basis grid không đi qua tone frequency

→

07 · WINDOW THAY LEAKAGE TRADE-OFF

Window không “sửa FFT”. Nó thay record trước khi DFT được tính.

RECTANGULAR

$w[n]=1$

Main lobe hẹp hơn nhưng sidelobes tương đối cao. Khi tone đúng bin và record được kiểm soát, đây có thể là lựa chọn rất sạch.

HANN

$w[n]=\frac12-\frac12\cos\!\left(\frac{2\pi n}{N-1}\right)$

Taper hai đầu, hạ sidelobes nhưng làm main lobe rộng hơn. Amplitude measurement cần xử lý coherent gain đúng.

Không có “window tốt nhất” độc lập với bài toán. Detect một weak tone cạnh strong tone, estimate amplitude và resolve hai close tones có thể ưu tiên các trade-off khác nhau.

08 · DFT CÓ THỂ ĐẢO NGƯỢC, FFT CHỈ LÀ CÁCH TÍNH NHANH

Frequency coefficients không làm mất information nếu transform pair và normalization được giữ đầy đủ.

x[n]=\frac1N\sum_{k=0}^{N-1}X[k]e^{+j2\pi kn/N}

Công thức trên là một common normalization convention: forward DFT không chia $N$ , inverse DFT chia $N$ . Libraries khác có thể chia ở forward, inverse hoặc chia đối xứng ở cả hai.

DIRECT DFT $\mathcal O(N^2)$

Mỗi output bin cộng contributions từ toàn bộ input record.

same transform
faster algorithm

FFT $\mathcal O(N\log N)$

Khai thác symmetry/factorization để reuse computation.

09 · ZERO-PADDING KHÔNG TẠO THÊM OBSERVATION TIME

FFT dài hơn sau khi append zeros cho nhiều frequency samples hơn, không cho thêm measured data.

MEASURED RECORD $N$ real samplesphysical observation duration đã cố định

→ append zeros →

LONGER DFT GRID $N_{\mathrm{FFT}}>N$ frequency sampling của same finite-record spectrum dày hơn

Zero-padding rất hữu ích để interpolate spectrum display hoặc estimate peak position mượt hơn. Nhưng nếu mục tiêu là có thêm independent information về hai components gần nhau, chỉ append zeros không thay được record dài hơn hoặc SNR tốt hơn.

10 · DỪNG Ở ĐÂU TRƯỚC KHI SANG MODULATION?

$X[k]$ là một complex coefficient. Nó chưa mặc định là một modulation symbol.

TRONG BÀI 7 $X[k]$

Coefficient sinh ra bởi transform của một finite record.

TRONG BÀI 8complex modulation symbol

Một deliberately chosen complex point đại diện cho bits.

LATER IN OFDMfrequency-domain input bins

Modulation symbols sẽ được đặt có chủ đích lên bins/subcarriers trước IFFT.

Ba objects có thể đều là complex numbers nhưng khác ý nghĩa vì chúng xuất hiện ở stage khác nhau. Bài 08 sẽ tập trung vào việc bits chọn complex point như thế nào.

11 · NỐI LẠI CÁC Ý

Fourier idea: đổi từ sample coordinates sang sinusoid/complex-exponential coordinates.
DFT: mỗi $X[k]$ là complex projection coefficient của một basis frequency.
Bin mapping: $\Delta f=f_s/N=1/T_{\mathrm{obs}}$ và upper DFT indexes thường map sang negative frequencies.
Leakage: finite observation/window làm spectral energy spread khi tone không align với DFT grid.
Window: đổi main-lobe/sidelobe trade-off, không tạo thêm information.
Inverse DFT: reconstruct record từ full complex coefficient set theo transform convention đã chọn.
FFT: algorithm nhanh để tính DFT; IFFT là algorithm nhanh cho inverse DFT.
Zero-padding: lấy frequency samples dày hơn nhưng không tăng physical observation time.