(Ⅲ)离散变换与FFT

下面主要目的是讨论工程应用中的Fourier变换,因此需要做出如下适配:

  • 把连续的、无穷多的时域变量换为离散的、有限多的N个;
  • 把角频率换为频率,也就是指数部分带上2\pi系数.

定义:离散Fourier变换(Discrete Fourier transform, DFT)对函数f在N个点0,1,\dots,{N-1}的变换为

\widehat{f\phantom{}}(u)=\sum _ {x=0}^{N-1} f(x)\, \mathrm{e}^{-\mathrm{i}\frac{2\pi}{N} ux}, \quad u=0,1,\dots,N-1.

不难验证逆变换(Inverse discrete Fourier transform, IDFT)成立(这里过程略去)

f(x)=\frac1N\sum _ {u=0}^{N-1}\widehat{f\phantom{}}(u)\, \mathrm{e}^{\mathrm{i}\frac{2\pi}{N}ux},\quad x=0,1,\dots,N-1.

一般把它们都看作N为周期的函数,从而在整数上都有定义.

经常需要考虑二维情形,2D DFT和IDFT分别为

\begin{gathered}
\widehat{f\phantom{}}(u,v)=\sum _ {x=0}^{M-1}\sum _ {y=0}^{N-1}f(x,y)\exp\Big\{{-\mathrm{i}2\pi\Big(\frac{ux}{M}+\frac{vy}{N}\Big)}\Big\},\\
f(x,y)=\frac{1}{MN}\sum _ {u=0}^{M-1}\sum _ {v=0}^{N-1}\widehat{f\phantom{}}(u,v)\exp\Big\{{\mathrm{i}2\pi\Big(\frac{ux}{M}+\frac{vy}{N}\Big)}\Big\}.
\end{gathered}

和连续版很多性质都类似,例如时域乘指数因子\exp(\mathrm{i}2\pi u _ 0x/M)等价于频域u右平移u _ 0,这样

f(x,y)(-1)^{x+y}\longleftrightarrow \widehat{f\phantom{}}(u-M/2,v-N/2).

离散卷积则定义为

\begin{gathered}
(f\ast g)(x)=\sum _ {n=0}^{N-1}f(n)g(x-n),\quad x=0,1,\dots,N-1,\\
(f\ast g)(x,y)=\sum _ {m=0}^{M-1}\sum _ {n=0}^{N-1}f(m,n)g(x-m,y-n).
\end{gathered}

卷积定理\widehat{f\ast g}=\widehat{f\phantom{}}\widehat{g\vphantom{f}}成立.

计算:用DFT算IDFT与2d DFT

如果DFT能算了,IDFT也能用同样方式得出.这是因为

\overline{f(x,y)}=\frac{1}{MN}\sum _ {u=0}^{M-1}\sum _ {v=0}^{N-1}\overline{\widehat{f\phantom{}}(u,v)}\exp\Big\{{-\mathrm{i}2\pi\Big(\frac{ux}{M}+\frac{vy}{N}\Big)}\Big\}.

所以有了\widehat{f\phantom{}},计算共轭后得到的函数进行DFT,得到的就是MN \overline{f(x,y)}了.

2D的DFT同样能用1D的得出.把DFT写为

\begin{aligned}
\widehat{f\phantom{}}(u,v)&=\sum _ {x=0}^{M-1}\exp\Big({-\mathrm{i}\frac{2\pi}{M}ux}\Big)\sum _ {y=0}^{N-1}f(x,y)\exp\Big({-\mathrm{i}\frac{2\pi}{N}vy}\Big)\\
&=\sum _ {x=0}^{M-1}F _ v(x)\exp\Big({-\mathrm{i}\frac{2\pi}{M}ux}\Big).
\end{aligned}

其中F _ v(x)=\sum _ y f(x,y)\mathrm{e}^{-\mathrm{i}2\pi vy/N}是一维的DFT.也就是说,二维的DFT可以通过先对每行计算一维的DFT,再将所有得到的结果按列的方向再算一维的DFT.

这样有一维的DFT算法就足够算其它的变换了.

计算:FFT

让Fourier变换能在工程应用中发挥作用,离不开20世纪最伟大的算法之一——快速Fourier变换(Fast Fourier Transform, FFT).后面将会看到,即使是离散版的Fourier变换,要直接计算的开销巨大,然而FFT能让计算量极大降低.实时的频域上信号处理也成为可能,工业界引发划时代的变革.

FFT现在有多种实现,下面来看最经典的一个.通常来说,实际中N的选取比较自由,以下假设N是2的幂(现代计算库对非2幂也有高效算法).把DFT的求和拆分为奇数部分和偶数部分,

\begin{aligned}
&\widehat{f\phantom{}}(u)=\sum _ {x=0}^{N-1}f(x)\, \mathrm{e}^{-\mathrm{i}\frac{2\pi}{N} ux}\\
={}&\sum _ {k=0}^{N/2-1}f(2k)\, \mathrm{e}^{-\mathrm{i}\frac{2\pi}{N}u(2k)}+\sum _ {k=0}^{N/2-1}f(2k+1)\, \mathrm{e}^{-\mathrm{i}\frac{2\pi}{N}u(2k+1)}\\
={}&\sum _ {k=0}^{N/2-1}f(2k)\, \mathrm{e}^{-\mathrm{i}\frac{2\pi}{N/2}uk}+\mathrm{e}^{-\mathrm{i}\frac{2\pi}{N}u}\sum _ {k=0}^{N/2-1}f(2k+1)\, \mathrm{e}^{-\mathrm{i}\frac{2\pi}{N/2}uk}\\
={}& E _ u+\mathrm{e}^{-\mathrm{i}\frac{2\pi}{N}u}O _ u.
\end{aligned}

恰好用奇数项的变换和偶数项的变换表示出来了,E _ u,O _ u分别是偶数项、奇数项的DFT:

E _ u=\sum _ {k=0}^{N/2-1}f(2k)\, \mathrm{e}^{-\mathrm{i}\frac{2\pi}{N/2}uk},\quad O _ u=\sum _ {k=0}^{N/2-1}f(2k+1)\, \mathrm{e}^{-\mathrm{i}\frac{2\pi}{N/2}uk}.

算法的要点是只需要用到前半的u=0,1,\dots,N/2-1,后半的可以用前半算出来.利用\mathrm{e}^{-\mathrm{i}\pi}=-1,

\begin{gathered}
E _ {u+N/2}=\sum _ {k=0}^{N/2-1}f(2k)\, \mathrm{e}^{-\mathrm{i}\frac{2\pi}{N/2}uk}\mathrm{e}^{-\mathrm{i}2\pi k}=E _ u,\\
O _ {u+N/2}=\dots=O _ u,\\
\widehat{f\phantom{}}(u+N/2)=E _ {u+N/2}+\mathrm{e}^{-\mathrm{i}\frac{2\pi}{N}(u+N/2)}O _ {u+N/2}=E _ u-\mathrm{e}^{-\mathrm{i}\frac{2\pi}{N}u}O _ u.
\end{gathered}

综合起来,

\begin{cases}
\widehat{f\phantom{}}(u)=E _ u+\mathrm{e}^{-\mathrm{i}\frac{2\pi}{N}u}O _ u,\\
\widehat{f\phantom{}}(u+N/2)=E _ u-\mathrm{e}^{-\mathrm{i}\frac{2\pi}{N}u}O _ u,
\end{cases}\quad u=0,1,\dots,N/2-1.

这样就归结为奇数项和偶数项的DFT,递归算下去即可.

在Python,NumPy和SciPy均提供FFT的计算(numpy.fft.fft或scipy.fft.fft).

FFT的复杂度优势

设N=2^p,进行一次长为N的FFT需要的加减法和乘法分别为A(p),M(p).

当p=0,DFT即为自身,无需运算.当p=1,E _ 0,O _ 0无需运算,\widehat{f\phantom{}}(0)要加法乘法各一次,\widehat{f\phantom{}}(1)需要减法乘法各一次,但注意到乘法和\widehat{f\phantom{}}(0)计算的是同一个,因此此时A(1)=2、M(1)=1.当p=2,要得到\widehat{f\phantom{}}(0),\widehat{f\phantom{}}(1):用2A(1),2M(1)次加法乘法算出E,O后,再用加法乘法各两次得到\widehat{f\phantom{}}(0),\widehat{f\phantom{}}(1).而\widehat{f\phantom{}}(0+2),\widehat{f\phantom{}}(1+2)则各需要一次减法,乘法已经算过无需再算.因此A(2)=2A(1)+4以及M(2)=2M(1)+2.

一般地,

\begin{gathered}
A(p)=2A(p-1)+2^p,\\
M(p)=2M(p-1)+2^{p-1},\\
A(0)=0,\, M(0)=0.
\end{gathered}

对于加法,A(p)/2^p=A(p-1)/2^{p-1}+1,于是A(p)/2^p=p,A(p)=p2^p=N\log _ 2N.同样M(p)/2^p=p/2,M(p)=p2^p/2=\frac N2\log _ 2N.

原始的DFT的复杂度是O(N^2),而FFT降低到了O(N\log N).复杂度优势大致是2^p/p,当p是十几就已经快了千倍.对于二维的变换,复杂度更是从O(N^4)降低到O(N^2\log N)(行列等长时).


评论

Leave a Reply

Your email address will not be published. Required fields are marked *