北京交通大学：《数字信号处理》课程教学课件（讲稿）第3章 快速傅里叶算法FFT 3.7 FFT算法的应用

FFT算法的应用※利用N点复序列FFT，计算2个N点实序列FFT※利用N点复序列FFT，计算2N点实序列的FFT※利用N点复序列FFT，计算N点复序列的IFFT

※利用N点复序列FFT，计算2个N点实序列FFT ※利用N点复序列FFT，计算2N点实序列的FFT ※利用N点复序列FFT，计算N点复序列的IFFT FFT算法的应用

利用N点复序列FFT算法，计算2个N点实序列FFTx[k]和x>[k]分别是N点实序列，，如何调用一次N点复序列FFT算法得到X[m]和X[m]?构建N点复序列Jy[k]=x,[k]+ jx?[k]利用N点复序列FFT算法得到y[K|的DFT。y[k] = x,[k] + jx,[k]- ? Y[m]因为y'[k]= x,[k]- jx?[k]- R Y*[(N - m)]所以 X[ml=[m)+Y[(N- m)}} X,[m]=[m]-Y[(N- m)]

利用N点复序列FFT算法，计算2个N点实序列FFT x1 [k]和x2 [k]分别是N点实序列，如何调用一次N点复序列FFT算法得到 X1 [m]和X2 [m]？ 构建N点复序列 所以 利用N点复序列FFT算法得到y[k]的DFT。 因为

例：已知两个4点的序列x[k]=[1,2,0，1}，h[k]=[2，2,1,1}试用一次4点FFT流图,计算两个序列的DFT。解：构造复序列y[k]= x[k]+ jh[k]={1+2j, 2+2, j, 1+j]4+6jy[0]-1+2j1+3i21+y[2]-j-23+31[1]-2+2j 2jy[3]-1+j+

y[0]=1+2j y[2]=j y[1]=2+2j y[3]=1+j 例: 已知两个4点的序列x[k]={1, 2, 0, 1}, h[k]={2, 2, 1, 1} 试用一次4点FFT流图,计算两个序列的DFT。 1+3j 1+j 3+3j 1+j 4+6j -2 2 2j 解：构造复序列 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)m=0,1,2,3业Y*[(4- m)4] = {4-6j, -2j, -2, 2)m=0,1,2,3Y[m]+Y*[(4 - m)4]}={ 4, 1- j, - 2, 1+j 21(Y[m]- Y*[(4 - m)4]} =( 6, 1- j, 0, 1+j HIm2j

例: 已知两个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,3 m=0,1,2,3

利用N点复序列FFT算法，计算2N点实序列的FFTx[k是长度为2N的实序列，如何调用一次N点复序列FFT算法得到XIm?i x,[k] = x[2k]x[k]?k =0,1,L ,N- 1i x,[k]= x[2k +1]构建复序列y[k]：J[k]=x,[k] + jx,[k]计算N点复序列y[k]对应的Y[m]，并由Y[m]计算出X,[m]和X[m]。由X,[m]和X,[m]按基2合成X[m]X[m] = X,[m] +W"X,[m]m = 0,1.,L .N - 1X[m +N] = X,[m]- W"X,[m]

x[k]是长度为2N的实序列，如何调用一次N点复序列FFT算法得到X[m] ？ 利用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。解：序列x[K]按照奇偶分解为x,[]和x[]，则存在X[m] = X,[m]+W"X,[m]m = 0,1,2,3X[m + 4] = X,[m] - W."X,[m]其中x[k]=(1, 1, 2, 1]x2[k]=(-1, -1, - 1, - 1}由x,[k]和x?[k]构建复序列y[K]，通过4点FFT计算y[k]对应的Y[m]，并由Ym]计算出X[m|和X[m]

例：试利用4点基2时间抽取的FFT流图计算8点序列 x[k]={1, -1, 1, -1, 2, -1, 1,-1}的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]

例：试利用4点基2时间抽取的FFT流图计算8点序列x[k]=1, -1, 1, -1, 2, -1, 1,-1的DFT。X,[0]=5X,[1]=-1e.1X[m]=(5, -1, 1, -1}X,[2]-1X2[m]={-4, 0, 0, 0]/X,[3]=-1W解得X[0]=-49WX[m]= (1,-1,1, -1, 9, -1, 1,-1-1X2[1]=0W1X2[2]=0W-1X2[3]=0

解得 X[m]= {1,-1,1, -1, 9, -1, 1,-1} X1 [0]=5 X1 [1]=-1 X1 [2]=1 X1 [3]=-1 X2 [0]=-4 X2 [1]=0 X2 [2]=0 X2 [3]=0 1 -1 1 -1 9 -1 -1 -1 -1 -1 1 -1 X1 [m]={5, -1, 1, -1} X2 [m]={-4, 0, 0, 0} 例：试利用4点基2时间抽取的FFT流图计算8点序列 x[k]={1, -1, 1, -1, 2, -1, 1,-1}的DFT

利用N点复序列FFT，计算N点复序列的IFFTN-1X[m]= DFT (x[k]}=a x[k]WADFT与IDFT:k=0N-1mkx[k]= IDFT {X[m]}=一a X[m]WNm-0利用DFT与IDFT定义的对称性akmkoa(DFT(X[ml))x[k]NN0

DFT与IDFT： 利用DFT与IDFT定义的对称性 利用N点复序列FFT，计算N点复序列的IFFT

利用N点复序列FFT，计算N点复序列的IFFTw.ooamk(DFT(X"[ml))X*[m]Wx[k]:中ceNNN0m=0Nx[k]X[m]0009X[m]FFTx[k]N步:(1）将Xml选取共轭(2)用FFT流图计算 DFT(X*[ml)(3）对(2)中结果取共轭并除以N

步骤： (1) 将X[m]选取共轭 (3) 对(2)中结果取共轭并除以 N (2) 用FFT流图计算 利用N点复序列FFT，计算N点复序列的IFFT

例:已知X[m]-DFT(x[K]}={10, -2+2j，-2,-2-2j)利用基2时间抽取FFT流图，计算x[k]。X*[m] =(10,-2 - 2j,- 2,- 2 +2j)DFT (x*[m]}= {4, 8, 12, 16]10-28-2-2j12-2+2j16DFT x'[mk(1, 2, 3, 4)

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