数字信号处理（第3版）ch3-3FFT应用

电子信息工程学院信号处理课程组数字信号处理DigitalSignalProcessing快速傅里叶变换引论基2时间抽取FFT算法基2频率抽取FFT算法快速傅里叶变换应用其他基时间抽取FFT混合基时间抽取FFTFFT算法对称性分析离散傅里叶变换快速算法利用N点复序列FFT，计算2个N点实序列FFT利用N点复序列FFT，计算2N点实序列的FFT利用N点复序列FFT，计算N点复序列的IFFTFFT算法的应用利用N点复序列FFT算法，计算2个N点实序列FFTx1[k]和

x2[k]分别是N点实序列，构建N点复序列所以利用N点复序列FFT算法得到y[k]的DFT。因为y[0]=1+2jy[2]=jy[1]=2+2jy[3]=1+j例:已知两个4点的序列x[k]={1,2,0,1},h[k]={2,2,1,1}试用一次4点FFT流图,计算两个序列的DFT。1+3j1+j3+3j1+j4+6j-222j解：构造复序列

y[k]=x[k]+

jh[k]={1+2j,2+2j,j,1+j}

例:已知两个4点的序列x[k]={1,2,0,1},h[k]={2,2,1,1}试用一次4点FFT流图,计算两个序列的DFT。Y[m]={4+6j,2,-2,2j}Y*[(4-m)4]={4-6j,-2j,-2,2}m=0,1,2,3m=0,1,2,3x[k]是一个长度为2N的实序列利用N点复序列FFT算法，计算2N点实序列的FFT构建复序列y[k]计算N点复序列y[k]对应的Y[m]，并由Y[m]计算出X1[m]和X2[m]由X1[m]和X2[m]按基2合成X[m]例：试利用4点基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,-1,1,-1}的DFT。解：

根据基2时间抽取FFT算法原理，8点序列DFT可由两个4点序列的DFT表达。序列x[k]按照奇偶分解为x1[k]和x2[k]，则存在

其中x1[k]={1,1,2,1}x2[k]={-1,-1,-1,-1}由x1[k]和x2[k]构建复序列y[k]，通过4点FFT计算y[k]对应的Y[m]，并由Y[m]计算出X1[m]和X2[m]。解得X[m]={1,-1,1,-1,9,-1,1,-1}例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,-1,1,-1}的DFT。X1[0]=5X1[1]=-1X1[2]=1X1[3]=-1X2[0]=-4X2[1]=0X2[2]=0X2[3]=01-11-19-1-1-1-1-11-1X1[m]={5,-1,1,-1}

X2[m]={-4,0,0,0}定义：利用DFT与IDFT定义的对称性利用N点复序列FFT，计算N点复序列的IFFT

步骤：(1)将X[m]选取共轭(3)对(2)中结果取共轭并除以N(2)用FFT流图计算

利用N点序列的FFT，计算N点序列的IFFT{4,8,12,16}10-2-2-2j-2+2j481216812-4-4j例：已知X[m]=DFT{x[k]}={10,-2+2j，-2,-2-2j}利用基2时间抽取FFT流图，计算x[k]。

{1,2,3,4}FFT算法的应用MATLAB提供了多个函数用于快速计算DFT和IDFT，即

fft(x)，fft(x,N)，ifft(X)，ifft(X,N)fft(x)

计算L点的DFT，L是序列x的长度，即L=length(x)；fft(x,N)

计算N点的DFT，若L<N，则将原序列补零至N点，

然后计算其N点DFT；ifft(X)

计算L点的IDFT，L是序列X的长度；ifft(X,N