混合基时间抽取FFT算法基2时间抽取FFT算法序列的长度N必需满足N=2M基3时间抽取FFT算法序列的长度N必需满足N=3M基4时间抽取FFT算法序列的长度N必需满足N=4M如果N不满足此要求，则需对序列进行补零FFT算法的计算复杂度与序列的长度成正比，因此，大量补零将降低FFT算法的实际效果
基2时间抽取FFT算法序列的长度N必需满足N=2M 基3时间抽取FFT算法序列的长度N必需满足N=3M 如果N不满足此要求，则需对序列进行补零。 FFT算法的计算复杂度与序列的长度成正比， 因此，大量补零将降低FFT算法的实际效果。 混合基时间抽取FFT算法 基4时间抽取FFT算法序列的长度N必需满足N=4M
混合基时间抽取FFT算法例如，某序列的长度N=96，若利用FFT计算其DFT，利用基2-FFT计算，则需要补零到128个点（增加32个0）利用基3-FFT计算，则需要补零到243个点（增加147个0）利用基4-FFT计算，则需要补零到256个点（增加160个0）混合基FFT如何减少补零个数，提高FFT的计算效率？
如何减少补零个数，提高FFT的计算效率？ 混合基时间抽取FFT算法 例如，某序列的长度N=96，若利用FFT计算其DFT， 利用基2-FFT计算，则需要补零到128个点（增加32个0） 利用基3-FFT计算，则需要补零到243个点（增加147个0） 利用基4-FFT计算，则需要补零到256个点（增加160个0） 混合基FFT
混合基时间抽取FFT算法先将96点的序列分解为3组32点的子序列，即96=3×32由基2-FFT计算此三组32点的子序列的DFT。按基3-FFT的规则将三组32点的DFT进行合成，构成96点序列的DFT0X[m]=X,[m]+W"X,[m]+W"X,[m]X[m+N /3] = X,[m]+W,WmX,[m]+W,WmX,[m]X[m+2N /3] = X,[m]+W,W"X,[m]+W,W"X,[m]由于此计算过程利用了不同基的FFT，因而称混合基FFT
混合基时间抽取FFT算法 先将96点的序列分解为3组32点的子序列，即96=3×32 由基2-FFT计算此三组32点的子序列的DFT， 按基3-FFT的规则将三组32点的DFT进行合成，构成96点序列的DFT 。 由于此计算过程利用了不同基的FFT，因而称混合基FFT
混合基时间抽取FFT算法序列x[k]的长度可表示为N=pxq，将序列x[k]按时间抽取方式分解为p组q点序列x[k],x,[k],×xp[k]，则根据时间抽取FFT算法原理可得基p时间抽取FFT算法基本表示式为m=0, 1,.., q-1X[m] =X,[m]+WwX,[m]+L +W/p-1)mX,[m]X[m +gl = X,[m] + W(m+g)X,[ml +L + W(p-1(m+g)X,[m]MX[m + (p- 1)g] = X,[m) + Wm+pg-9)X,[ml +L + W(p-1(m+pg-9)X,[m)
序列 x[k]的长度可表示为N=p×q，将序列x[k]按时间抽取方式分 解为p组q点序列 ，则根据时间抽取FFT算法原理可得 基p时间抽取FFT算法基本表示式为 m=0, 1,., q-1 混合基时间抽取FFT算法
例：利用混合基FFT算法计算N=12点序列的DFT，并画出其算法流图。N=12可表示为N=3×4，将序列x[kl按时间抽取分解为3组4点序列，即对序列x[k]按基3方式抽取，构成三组子序列x[k],x,[k],x,[k]X[K]x[0]x[0] x[3] x[6], x[9]+x[kX,[m]x[1]Xi2[k]x2,[k]x[2]x[1] x[4] x[7], x[10]x,[k]X[m]X,[m]x,[k]x[3][k]x,[k]X,[m]...x[2] x[5] x[8], x[11]132[k]基3合成基3分解x[11]基2分解与合成
例：利用混合基FFT算法计算N=12点序列的DFT， 并画出其算法流图。 N=12可表示为N=3×4，将序列x[k]按时间抽取分解为3组4点序 列，即对序列x[k]按基3方式抽取，构成三组子序列 4点DFT 4点DFT 4点DFT 基3分解 基2分解与合成 基3合成