北京交通大学：《数字信号处理》课程教学课件（讲稿）第3章 快速傅里叶算法FFT 3.4.其他基时间抽取FFT算法

其他基时间抽取FFT算法基4时间抽取FFT算法原理1基4时间抽取FFT算法流图1u基3时间抽取FFT算法原理基3时间抽取FFT算法流图11

u 基4时间抽取FFT算法原理 u 基4时间抽取FFT算法流图 u 基3时间抽取FFT算法原理 u 基3时间抽取FFT算法流图 其他基时间抽取FFT算法

基4时间抽取FFT算法原理基4时间抽取FFT算法是将长度为N的序列x[k分解为4组短序列N=4Mx[k]=x[4k]k=0,1,L ,N/4- 1x2[k]=x[4k +1]k=0,1,L ,N /4- 1x,[k]=x[4k+2]k=0.1L,N/4- 1x4[k]=x[4k+3]k=0,1,L ,N/4- 1分别计算4组短序列的DFT，再由其合成长序列的DFT

基4时间抽取FFT算法是将长度为N的序列x[k]分解为4组短序列 基4时间抽取FFT算法原理 分别计算4组短序列的DFT，再由其合成长序列的DFT。 N=4 M

基4时间抽取FFT算法原理4组短序列DFT合成长序列DFTX[m] = X,[m] +W"X,[m]+W2" X,[m] +W" X[m]X[m+N / 4] = X[m] +W,W"X,[m] +WW2"X,[m]+WWs"X[m]X[m+2N / 4] = X[m] +WW"X,[m]+WW2" X,[m]+W'W" X[m]X[m+3N / 4] = X,[m] +W"W"X,[m] +WW2" X,[m] +W"w3" X[m]

基4时间抽取FFT算法原理 4组短序列DFT合成长序列DFT

基4时间抽取FFT算法原理4组短序列DFT合成长序列DFTew!010X[m]el10éiueX[m]uHeetetiex,[ml)X[m+ N / 4]WW0-j-100Jete2ien1eWan-11-lteo0eX[m+2N/4]uelueX,[m]ii0tedW3mlieX[m+3N /4]10-100"aeX.[m]ajie1

基4时间抽取FFT算法原理 1 j -1 -j 4组短序列DFT合成长序列DFT

基4时间抽取FFT算法原理4点序列DFT--时域到频域111éx[o]u?ex[olu1D0<ePuX[1-j-11eu111éx[2]u-1- 1uex[2]<eueuUj-1x[3]ajuex[3]a

基4时间抽取FFT算法原理 1 j -1 -j 4点序列DFT-时域到频域

基4时间抽取FFT算法原理eX[olue1 tex[oluexmu时域到频域eX[2]uel- luex[2]ueex[3]juex[3]1iewoX[m]el1100é0ueX,[mlu2Neeaue1exlm!X[m+ N / 4]W- 10-j00tieO频域合成Wu-11-lue0ueX,[mjueXm+2N/4ju00etieSX(m+3N /41wnex m11- 1000lte

基4时间抽取FFT算法原理 频域合成 时域到频域 1 j -1 -j

基4时间抽取FFT算法流图基4FFT算法中的基本蝶形Wo X[mlX [m]o()W"X,[m]oX|m+N/4]11m2mW2m31X,[mpoX[m+2N /4]WX[mpX[m+3N /4]

基4 FFT算法中的基本蝶形 基4时间抽取FFT算法流图

基4时间抽取FFT算法流图X,[ml.oX[0]x[0]ex[4]X[1]OX[2]x[8] x[12]eXT31X,[m]x[1] 0X[4]MS]x[5] X[6]x[9]0x[13]eA[7]X,[m]1x[2] X[8]x[6]X19]x[10]eX1O]x[14]X[11]X,[m]0x[3]X[12]x[7]eX[13]6x[11]e16点基4-FFT算法流图X[14]福9x[15]0XT15]

基4时间抽取FFT算法流图 16点基4-FFT算法流图

基3时间抽取FFT算法原理基3时间抽取FFT算法是将长度为N的序列x[k]分解为3组短序列N=3Mk=0,1L ,N/3- 1x[k]= x[3k]x2[k]=x[3k +1]k=0,1L ,N/3- 1k=0,1L ,N/3- 1x,[k]=x[3k +2]分别计算3组短序列的DFT，再由其合成长序列的DFT。？自行推导基3时间抽取FFT算法

基3时间抽取FFT算法是将长度为N的序列x[k]分解为3组短序列 基3时间抽取FFT算法原理 分别计算3组短序列的DFT，再由其合成长序列的DFT。 N=3 M 自行推导基3时间抽取FFT算法

基3时间抽取FFT算法原理3组短序列DFT合成长序列DFTX[m] = X,[m]+W"X,[m]+W"X,[m]X[m +N /3] = X[m]+W,W"X,[m]+W,W"X,[m]X[m+2N /3] =X,[m]+W,W"X,[m]+W,W"X,[m]ewo10éllueX[m]O uéX,[m]uuMelee<0ix.mD1Wm60福[m+Na6deNObW2mj001X[m+2N /3]iHeX,[m]O2

基3时间抽取FFT算法原理 3组短序列DFT合成长序列DFT 1 a b