1.1. 离散傅里叶变换

• 傅里叶级数$f(t)$

$f(t) = \frac{a_{0}}{2} + \sum^{\infty}_{n=1}\biggr(a_{n}\cos n\omega t + b_{n}\sin n\omega t\biggr)$

• 其中：

$\omega=\frac{2 \pi}{T}$

$a_{n} = \frac{2}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}f(t) \cos n \omega t dt$

$b_{n} = \frac{2}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}f(t) \sin n \omega t dt$

• 欧拉公式：

$e^{j\theta}=\cos \theta + j\sin\theta$

$\cos n\omega t = \frac{e^{jn \omega t}+e^{-j n \omega t}}{2}$

$\sin n\omega t = -j\frac{e^{jn\omega t} - e^{-j n\omega t}}{2}$

$f(t) = \frac{a_{0}}{2}+\sum_{n=1}^{\infty}\biggr(a_{n}\cos n\omega t + b_{n}sin n\omega t\biggr)$

$f(t)= \frac{a_{0}}{2}+\sum_{n=1}^{\infty}\biggr[a_{n}\times \frac{e^{jn \omega t}+e^{-j n \omega t}}{2} -b_{n}\times j\frac{e^{jn\omega t} - e^{-j n\omega t}}{2}\biggr]$

$f(t)=\frac{a_{0}}{2}+\sum_{n=1}^{\infty}\biggr[\frac{a_{n}-j b_{n} }{2} e^{jn\omega t} + \frac{a_{n}+jb_{n}}{2} e^{-jn \omega t}\biggr ]$

$c_{0}=\frac{a_{0}}{2} \quad c_{n}=\frac{a_{n} - jb_{n}}{2} \quad d_{n}=\frac{a_{n}+jb_{n}}{2}$

$f(t)= c_{0} + \sum_{n=1}^{\infty}\biggr(c_{n} e^{jn \omega t} + d_{n} e^{-jn\omega t}\biggr)$

$c_{0}= \frac{1}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}f(t)dt$

$c_{n}=\frac{1}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}f(t)\biggr(\cos n \omega t - j\sin n\omega t\biggr)dt =\frac{1}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}f(t)e^{-jn\omega t}dt$

$d_{n}=\frac{1}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}f(t)\biggr(\cos n \omega t + j \sin n\omega t \biggr)dt = \frac{1}{T}\int_{-\frac{T}{2}}^{\frac{T}{2}}f(t)e^{jn \omega t}dt$

$d_{n} = c_{-n}$

$\sum_{n=1}^{\infty}d_{n}e^{jn\omega t} = \sum_{n=1}^{\infty}c_{-n}e^{-jn\omega t}=\sum_{n=-\infty}^{-1}c_{n}e^{jn\omega t}$

$f(t)= c_{0} + \sum_{n=1}^{\infty}\biggr(c_{n}\times e^{jn \omega t} + d_{n}\times e^{-jn\omega t}\biggr)=c_{0}e^{j0\omega t}+ \sum_{n=1}^{\infty}\biggr(c_{n}\times e^{jn \omega t} + c_{-n}\times e^{-jn\omega t}\biggr)$

$f(t)=c_{0}e^{j0\omega t}+ \sum_{n=1}^{\infty}\biggr(c_{n}\times e^{jn \omega t} + c_{-n}\times e^{-jn\omega t}\biggr)= c_{0}e^{j0\omega t}+ \sum_{n=1}^{\infty}\biggr(c_{n}\times e^{jn \omega t}) + \sum_{n=-\infty}^{-1} c_{n}\times e^{jn\omega t}\biggr)$

• 最终可得：

$f(t)= \sum_{n=-\infty}^{+\infty}c_{n}e^{jn\omega t}$

1.1.1. 快速傅里叶变换FFT

一维傅里叶变换DFT

DFT表示为： $F(u)=\sum_{x=0}^{N-1}f(x)e^{\frac{-j2\pi ux}{N}},u=0,...,N-1$ IDFT表示为： $f(x) = \frac{1}{N}\sum_{u=0}^{N-1}F(u)e^{\frac{j2\pi ux}{N}},x=0,...,N-1$ 令 $W=e^{\frac{-j2\pi}{N}}$

则： $F(u)=\sum_{x=0}^{N-1}f(x)W^{ux},u=0,...,N-1$

$f(x) = \frac{1}{N}\sum_{u=0}^{N-1}F(u)W^{-ux},x=0,...,N-1$

因为W因子具有周期性和对称性 $W^{u\pm rN}=e^{-j2\pi\frac{u\pm rN}{N}} =e^{-j\frac{2\pi}{N}u}\times e^{\mp j2\pi r}=e^{-j\frac{2 \pi}{N}u} = W^{u}$

$W^{u\pm \frac{N}{2}}=e^{-j\frac{2\pi}{N}(u \pm \frac{N}{2})} =e^{-j\frac{2\pi}{N}u}\times e^{\mp j\pi}=-e^{-j\frac{2 \pi}{N}u} = -W^{u}$

所以，合理安排重复出现的相乘运算，减少计算工作量

• 一个长为4的数字序列，求其离散傅里叶变换DFT

$F(u)=\sum_{x=0}^{3}f(x)W^{ux}=f(0)W^{0}+f(1)W^{1}+f(2)W^{2}+f(3)W^{3}$

$\left[\begin{matrix}F(0) \\ F(1) \\ F(2) \\ F(3)\end{matrix}\right]= \left[\begin{matrix}W^{0} & W^{0} & W^{0} & W^{0}\\ W^{0} & W^{1} & W^{2} & W^{3}\\W^{0} & W^{2} & W^{4} & W^{6}\\W^{0} & W^{3} & W^{6} & W^{9} \end{matrix}\right]=\left[\begin{matrix}f(0)\\f(1)\\f(2)\\f(3)\end{matrix}\right]$

1. W的对称性 $W^{2}=-W^{0}$

   $W^{3} = -W^{1}$

2. W的周期性 $W^{4}=-W^{0}$

   $W^{6}=-W^{2}$

   $W^{9}=-W^{1}$

   $\left[\begin{matrix}F(0)\\F(1)\\F(2)\\F(3)\end{matrix}\right]= \left[\begin{matrix} W^{0} & W^{0} & W^{0} & W^{0}\\ W^{0} & W^{1} & W^{2} & W^{3}\\W^{0} & W^{2} & W^{4} & W^{6}\\W^{0} & W^{3} & W^{6} & W^{9}\end{matrix}\right] \left[\begin{matrix}f(0)\\f(1)\\f(2)\\f(3)\end{matrix}\right]$

   $=\left[\begin{matrix}1 & 1 & 1 &1 \\ 1 & W^{1}& -1 & -W^{1}\\1 & -1 &1 &-1 \\ 1 & -W^{1}& -1 & W^{1}\\ \end{matrix}\right]\left[\begin{matrix}f(0)\\f(1)\\f(2)\\f(3)\end{matrix}\right]$

   $=\left[\begin{matrix} f(0)+f(2)+(f(1)+f(3))\\f(0)-f(2)+[f(1)-f(3)]W^{1}\\f(0)+f(2)-[f(1)+f(3)]\\f(0)-f(2)-[f(1)-f(3)]W^{1} \end{matrix} \right]$

   $F(u)=\sum_{x=0}^{N-1}f(x)e^{\frac{-j2\pi ux}{N}}=\sum_{x=0}^{N-1}f(x)W^{ux}_{N}=\sum_{x=0}^{N/2-1}f(2x)W^{2ux}_{N}+ \sum_{x=0}^{N/2-1}f(2x+1)W^{u(2x+1)}_{N}$

   令 $M=\frac{N}{2}$ 则： $F(u)=\sum_{x=0}^{M-1}f(2x)W^{ux}_{M}+ \sum_{x=0}^{M-1}f(2x+1)W^{ux}_{M}W^{u}_{N}$

   $F(u) = F_{e}(u) + W_{N}^{u}F_{o}(u) \quad 0 \le u \le M$

   **分成奇数项和偶数项之和**

1.1.2. 总结

• 将原函数分为奇数项和偶数项，通过不断的一个奇数一个偶数的相加（减），最终得到需要的结果

• FFT是将复杂的运算变成两个数相加（减）的简单运算的重复。 $F(u) = F_{e}(u) + W^{u+M}_{N}F_{0}(u)$

  $F(u+M) = F_{e}(u) - W^{u}_{N}F_{0}(u)$

  例子：

  一个长为8的数字序列，利用FFT算法求其DFT。

  

  

1.1.3. 二维离散傅里叶变换

$F(u,v) = \sum_{x=0}^{M-1}\sum_{y=0}^{N-1}f(x,y)e^{-j2\pi (\frac{xu}{M}+\frac{yv}{N})} \quad x,u =0,1,....,M-1 \quad y,v= 0,1,2...N-1$

$f(u,v) = \frac{1}{MN}\sum_{x=0}^{M-1}\sum_{y=0}^{N-1}F(u,v)e^{j2\pi (\frac{xu}{M}+\frac{yv}{N})} \quad x,u =0,1,....,M-1 \quad y,v= 0,1,2...N-1$

例：

先按列变换(也可以先按行变换)

1.1.4. 卷积定理

如果 $\quad F(f(t)) = F(\mu) \quad F(h(t))=H(\mu) \quad \Rightarrow \quad F[f(t)\star h(t) ] = F(\mu) \cdot H(\mu)$