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

混合基时间抽取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合成

例：利用混合基FFT算法计算N=12点序列的DFT，并画出其算法流图。N=12可表示为N=3×4，将序列x[k]按时间抽取分解为3组4点序列，即对序列x[k]按基3方式抽取，构成三组子序列x[k],x,[k],x,[k]x,[k] =x[3k] = (x[0], x[3], x[6], x[9]}x,[k] = x[3k+1] = (x[1], x[4], x[7], x[10])k =0. 1. 2, 3x,[k] = x[3k +2] = (x[2], x[5], x[8], x[11]其对应的DFT变换为X,[m],X[m],X,[m]，则长序列的DFT为1 +W"X,[mlX[m] =X,[m] + WX,[m]X[m+4] =X,[ml + W(m+4)X,[ml + W2(m+4)X,[m]m=0, 1, 2, 31212X[m+8 - )[ml + w(g*) ,[ml + wg0m-) ,[ml12

其对应的DFT变换为X1 [m], X2 [m], X3 [m]，则长序列的DFT为 例：利用混合基FFT算法计算N=12点序列的DFT， 并画出其算法流图。 N=12可表示为N=3×4，将序列x[k]按时间抽取分解为3组4点序 列，即对序列x[k]按基3方式抽取，构成三组子序列

例：利用混合基FFT算法计算N=12点序列的DFT，并画出其算法流图。+ W"X,[mX[ml =X[m + W2X,[mlV2mX[m+4] =X[m) + W(m+4)X,[ml + W2(m+4)X,[m]m=0, 1, 2, 3X[m+8] =X,[ml + W(m+8)X,[m) + W2(m+8)x,[ml1212化简得到：+ W2mX,[m]X[m] = X[ml + W1X,[m]12m=0, 1, 2, 3X[m+4] =X[ml + W2 WX,[ml + wg w2"X,[ml12X[m+8] =X[m + W2W2X,[m + WsW"X,[ml;2元82元441+iv3b=W8a=W4 =W16 :.12e'12e3-121212J22

例：利用混合基FFT算法计算N=12点序列的DFT， 并画出其算法流图。 化简得到：

例：利用混合基FFT算法计算N=12点序列的DFT，并画出其算法流图。 + W2"X,[m]X[m] = X,[m] + WmX,[m] X[m+4] = X[m] + aWmX,[m] + bW2"X,[m]m=0, 1. 2. 31.2X[m+8] = X[m] + bW12X,[m] + aW2"X,[m]luewo0él10üéX,[m] üX[m] üé12bue1exImeXIm+41-9WI200ue0W2"eX,[m] 0at@X[m +8] αlb

例：利用混合基FFT算法计算N=12点序列的DFT， 并画出其算法流图。 1

Xi[0]XTO]x[0].Xi[]]x[1]x[3] 04点xi[k]X[m]Xi[2]DFTx[6]。X[2]X[3]x[9][3]X[0]Wi2x[1].X[4]W?x[4] :oX[5]4点X[2] W3x2[K]X[m+4]DFTx[7] .X[6]x[3]WOX17]x10]X[0] W?x[2] 。oX[8]lw2x[5] .oX[9]4点X[m+8]x3[k]X[2] WDFTx[8] .x[10]X[3] W2X[1 1]x[11]0基3合成基3分解

基3分解 基3合成

总结习题：1．为什么提出混合基FFT算法？2．计算N=80点序列的DFT，可以采用哪种混合基方式？(A)基3-基2(B)基4-基5(C)基3-基5(D)基2-基4

总结 习题： 1. 为什么提出混合基FFT算法？ 2. 计算N=80点序列的DFT，可以采用哪种混合基方式？ (A) 基3-基2 (B) 基4-基5 (C)基3-基5 (D) 基2-基4