第3章_FFT(1)

1、3.1 引言：引言： 1. DFT运算量的估计运算量的估计 设x(n)为复序列，则计算每一X(k)需1010)(1)()()(NknkNNnnkNWkXNnxWnxkX N次复乘（N-1）次复加完成一次DFT计算需（k=0,1,2N-1）若用实数乘法统计：复乘运算：(a+jb)(c+jd)=(ac-bd)+j(ad+bc) =(a-b)d+a(c-d)+j(a-b)d+b(c+d)完成一次DFT计算运算量为： 2. 提高提高DFT运算效率途径运算效率途径 利用 的性质：周期性、可约性、共轭对称性周期性、可约性、共轭对称性 把长序列化解成短序列进行计算，通过叠代运算来减少 DFT的运算量。N2次

2、复乘N（N-1）次复加 N2实乘：4N2实加：2N(N-1)+2N2=4N2-2NnkNW(3次实乘，5次实加)3. 基（基（Radix）的定义：）的定义：在FFT运算中最小DFT单元序列的长 度称为基基；4. FFT按分解方法不同可分为：按分解方法不同可分为： Radix2 (N=2m) 时间抽选(DIT)Decimation In Time频率抽选(DIF) Decimation In Frequency) 1 () 0() 1 () 0() 1 () 0(1111) 1 () 0() 1 () 0() 1 , 0() 1 () 0()()(1202020222102xxxxxxxxWWW

3、WXXkWxWxWnxkXkknnk实质性乘法：指除去(1), (j)之外所需的乘法； 例：3点DFT（用于Radix3） )2(x) 1 (x)0(xWWWWWWWWW)2(x) 1 (x)0(xWWWWWWWWW)2(X) 1 (X)0(X13230323130303030343230323130303030313232313WWWW13232313WWWW(Butterfly Computation)2 , 1 , 0()2() 1 ()0()()(23303203kWxWxWxWnxkXkknnk) 1 ( x)0( x)0(X1) 1 (X三点信号流图： x(0) X(0) x(1)

4、 X(1) x(2) X(2) 13W23W23W43W 5.高效算法标准：高效算法标准： 乘、加次数最少； 算法结构的简单程度；（取指方便） 算法占用的存储量少；3。2 时间抽选时间抽选FFT算法算法(Radix 2DITFFT) N=2m 1.算法原理：算法原理：时间抽选是把n序号按奇、偶分解 例：N=8=23 x(n)= （ 也称为信号的多相分解）0, 2, 4, 6=x(2r)=e(r) E(k)N/21, 3, 5, 7=x(2r+1)=f(r) F(k)N/2(0rN/2) )k(FW)k(E)2Nk(X)k(FW)k(E)k(X)k(FW)k(EW)1r2(xW)r2(x)k(X

5、kNkN2/NkN2/Nk)1r2(N12N0rrk2N12N0r(0kN-1)12Nk0 其流图如教材图3.2.2 先做二个N/2点的DFT需2(N/2)2次乘法； 再做(N/2)个2点的DFT勿需任何乘法； 级间需(N/2)个旋转因子旋转因子(TwiddleFactor FFT Algorithm)； 经第一次分解后，总共需复乘次数：mc= 2(N/2)2+N/2=N/2(N+1)E(0)E(1)E(2)E(3)F(0)F(1)F(2)F(3)再次分解如图3.2.3完整的8点流图如3.2.4x0 x1 x2 x3 2. Radix 2DITFFT算法特点算法特点: (1)分解级数： FFT

6、点数为：N=2m, 则总共有m级； 每级共有（N/2）个蝶形运算 xL-1(i) xL(i) xL-1 (j) xL (j) xL(i)= xL-1(i)+ xL-1 (j) xL(j)= xL-1(i) xL-1 (j) 1rNWrNWrNW (2)运算量估计： 每个蝶形运算需：复乘次数 1 次；复加次数 2 次 总共所需复乘和复加次数： 如果考虑去除 ，则复乘次数可减至 如果再去除 ，则复乘次数可减至 与直接计算相比较 (图3.2.5)N(logN)2(logNNma)N(log2N)2(log2N2Nmm2m2c2m2c0NW) 1N()N(log2Nm2c4NNW)2N23(Nlog2

7、Nm2cNlogN2Nlog2NNK222 (3)原位运算（In place） 利用同一存储单元存储蝶形输入、输出数据的方法； (4)序列的倒位序排列 目的：满足同址运算的要求； 表示方法： 实现：表3.2.2变址处理：IJ，不做处理 I=J不做交换；IJ已经交换完了，不再交换； IJ , 进行交换； 软件编程实现：图3.2.8, 虚框表示逆记数；21020122nn2n2nnn2n2n0ni1i=0, 1, 2 3.3 N=8=222, Radix 2DITFFT的数学表示式及其对应的数学表示式及其对应 的流图的流图 1。运算表示式及几点说明 设置变量及其维数；0n01 0k01 0n11

8、0k11 0n21 0k21 列写输入输出 n、k的表达式： 列出运算表示式，并对n分解（DI T），分别化简：01222102kk2k2knn2n2n互为倒序表示：)0k1k22k22)(2n1n20n22(8102n2102101n100nW)nn2n2(x)k(X )W)nn2n2(x(WWW)nn2n2(x002100122201221210012202kn210n10n10n01220)kk2k2(n8)kk2k2(n2810n10n10n)kk2k2(n280122001kn28W()W11kn48)kk2(n8012W()W22kn4810n10n0122121)kn2n2(x(

9、01kn28W)W11kn2)kk2(n8012W()W22kn4801kn28W()kk2(n8012W(01kn28W)kk2(n8012W(10n012222)kk2n2(x)kk2(n8012W22kn2W)k(X)kk2k2(x01223说明：(1) n、k 互为倒序排列（与要求的流图排序无关）； (2) FFT运算是一逐级叠代过程，每次求和消去一个ni 代之以ki； (3) 求和运算时，若DI T，则按n做分解；若DI F，则 按k做分解，对表示式进行化简； (4) n表示式中的最高位，表示流图的第一级，不管n k如何表示，求和总是从n表示式中最高位开始； (5) 同一表示式可以有

10、多个流图与之对应； 2. 根据表示式画出相应的流图： 输入倒序输出正序形式)nnn(nnn2n2n2, 1,02102 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1 )k,k,k(kkk2k2k0120122 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 101kn28W)kk2(n8012W3.组的概念：流图中的每一组有相同的结构和相同的 分布 结构包括：蝶形运算类型；运算结点的间距rNWL=1L=2L=3 组的计算：第L级有： 组，每组内有 种蝶形， 每个蝶形的间距 ； 旋转因子的分布： 例：

11、设FFT的点数为N=256=28，输入为倒位序排列，问第 L=5级，有几组蝶形，每组有几种蝶形，每个蝶形的间距 是几点，旋转因子共有几个，具体值是什么？ 解： 有23=8组蝶形，每组内有256/(82) =16 种蝶形， 每个蝶形的间距是16点，Lm21L21L2i2N2i22i2LmLmLmLLWWW) 12(1Li=(0, 1, 2, 3 )76524334251607nn2n2n2n2n2n2n2n旋转因子分布： (0i15)具体蝶形运算形式： xL-1(i) xL(i) xL-1 (j) xL (j) j=i+ 3.4 Radix-2 DITFFT的其他流图形式：的其他流图形式： 其他

12、流图形式的获取原则：保持各结点所连的支路及 其传输系数不变，只是数据的提取和存放次序的不 同。（见图3.4.1 3.4.2） i82562i256i32i2WWWW3Li2NLmW1L2)nnn(nnn2n2n2, 1,02102)k,k,k(kkk2k2k0120122 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 101kn28W 0 0 0 1 0 0 0 1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 1)kk2(n8012W输入正序输出倒位序排列的流图：级间几何图形相同的DI TFFT流图（图3.4.2） 3。2 频率抽选

13、频率抽选FFT算法算法(Radix 2DIFFFT) N=2m 1. 基本原理：基本原理：DIF是把X(k)分解成短序列(对k分解) 12N0nnr2NnN12N0nnr2N12N0nnkNk12N0nk)2Nn(N12N0nnkN1N2NnnkN12N0nnkNWW)2Nn(x)n(x)1r2(X1r2kW)2Nn(x)n(x)r2(Xr2kW)1)(2Nn(x)n(xW)2Nn(xW)n(xW)n(xW)n(x)k(X逐次分解流图表示：nNW N=23=8点DI FFFT完整流图： 基本蝶形运算： xL-1(i)o o o oxL(i) xL-1(j)o o o oxL(j)1rNW xL

14、(i)=xL-1(i)+xL-1(j) xL(j)=xL-1(i) xL-1(j)rNW 2. N=8=222, Radix 2DIFFFT的数学表示式及其对应 的流图 1) Radix 2DIFFFT的数学表示式： 设置变量及其维数； 0n01 0k01 0n11 0k11 0n21 0k21 列写输入输出 n、k的表达式： 互为倒序表示： 列出运算表示式，并对k分解（DI F），分别化简：21020122kk2k2knn2n2n)kk2k2)(nn2n2(810n012210n10n21020122012W)nn2n2(x)k(X000111010001110122201201222012

15、21012012202nk2nk28nk210n10n01221nk2nk28nk2)nn2(k8kn210n10n10n0122)nn2n2(k8)nn2n2(k2810n10n10n)nn2n2(k280122WW)W)nn2k2(x()W)(WW()W)(W)nn2n2(x(WWW)nn2n2(x)nn2(k8012W01nk28W01nk28W)kk2k2(xWW)nk2k2(x01223nk2nk2810n012220001001nk28W)nnn(nnn2n2n0, 1,20122)k,k,k(kkk2k2k2102102 =X(k) 2) 流图表示： 0 0 0 1 0 0 0

16、1 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 10 0 00 0 10 1 00 1 11 0 01 0 1 1 1 01 1 101nk28W)nn2(k8012W 3) DI T与DI F的关系： 相同点： 分解级数都是m级； 乘法次数都是 ； 都是同址运算； 都有不同流图对应相同的表达式； 区别：蝶形运算结构不同： DI TFFTNlog2N2DI FFFT由DI TFFT碟形解出： xL-1(i)= （xL(i)+xL(j)） xL-1(j)= xL-1(i) xL-1(j)若去除 ，并把 改为 ，即为DI F蝶形流图， DI T和DI F在流图形式上互为转置关系。r

17、NW2121rNWrNW21 4) 用DI T与DI F的组合来过滤x(n)DI TFFTDI FIFFTx(n) 正 y(n)正倒倒H(k) 5) 如何用DFT（FFT）模块做I FFT？ 3.6 高组合数的高组合数的FFT算法算法旋转因子算法旋转因子算法 （混合基FFT，多基多进制算法） 1。N为组合数时，DI TFFT算法原理： N=N0N1N2Nm-1=M0 Nm-1 物理概念见教材(p.139)M0设：0m05，0n22； 0 5，0k22 n=3m0+n2 k=6 k2+ 2222202022222020222020kn3n18m620n2050m)k6(n18)k6(m31820

18、n2050m)k6)(nm3(1820n2050mWW)W)nm3(x(WW)nm3(xW)nm3(x)k(X22n18W 对应流图见教材图3.6.1； 经第一次分解后乘法次数的估算： mc=3 62+18+6 32=18022互为倒序排列 2。N=18=233分解的DI TFFT运算表示式及其流图 （见教材p.141和图3.6.3） 3。算法特点： 1)混合基FFT： 定义； DI T、DIF的物理概念及其具体做法； 2) 广义倒序： 定义； 广义倒序排序方法：式(3.6.7) 、(3.6.8) 3) 旋转因子算法概念 （与之对应的是素因子算法：p.148） 4）旋转因子算法运算量估计n0n

19、1n2012210kkkknnnn 3 9 26oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo210nn3n9nn(n0, n1, n2) 0 0 0 x(0) 1 0 0 x(9) 0 1 0 x(3) 1 1 0 x(12) 0 2 0 x(6) 1 2 0 x(15) 0 0 1 x(1) 1 0 1 x(10) 0 1 1 x(4) 1 1 1 x(13) 0 2 1 x(7) 1 2 1 x(16) 0 0 2 x(

20、2) 1 0 2 x(11) 0 1 2 x(5) 1 1 2 x(14) 0 2 2 x(8) 1 2 2 x(17)k,k,k(kkk2k6k012012X(0) 0 0 0X(1) 0 0 1X(2) 0 1 0X(3) 0 1 1X(4) 0 2 0X(5) 0 2 1X(6) 1 0 0X(7) 1 0 1X(8) 1 1 0X(9) 1 1 1X(10) 1 2 0X(11) 1 2 1X(12) 2 0 0X(13) 2 0 1X(14) 2 1 0X(15) 2 1 1X(16) 2 2 0X(17) 2 2 111111111101kn318W)kk2(n18012W318W018W618W018W018W018W018W018W318W318W618W618W018W118W218W318W418W518W018W218W4