- fourier Series 定义:
- $F(f)(u)=\int_{-\infty}^{\infty} f(x)e^{-2\pi i x u} dx$
- 2维：$G(p,q)=F(g(x,y)) = \int\int^\infty_\infty g(x,y)e^{-i2\pi(px+qy)}dxdy$
- 2维的可以拆分成1维
- 离散形式: 信号$x$ 的FFT 信号$X$
- $X_k=\sum_{m=0}^{N-1}x_m\cdot e^{-i\cdot 2\pi km/N}=\sum_{m=0}^{N-1}x_m\cdot TW(N,k)^m$
- $N$ 是信号长度
- $k$ 是sample的位置
- $TW(N,k) = e^{-i*2k\pi/N}$ 是FFT 的twiddle factor(旋转因子)
- $TW(N,k)=\cos(-2k\pi/N)+i\cdot \sin(-2k\pi/N)=TW_r(N,k)+i\cdot TW_i(N,k)$
- $X_k=\sum_{m=0}^{N-1}x_m\cdot e^{-i\cdot 2\pi km/N}=\sum_{m=0}^{N-1}x_m\cdot TW(N,k)^m$
butterfly diagram
利用fft的对称性和周期性
$X(k)=X(k)$