1、一、直接用DFT计算的运算量与用FFT计算的运算量比较，减少运算量的途径2221log N,log212DFTNN NFFTNN直接用计算的运算量：复乘次，复加（）次。用计算的运算量：复乘次 复加N次。减少运算量的途径：（）合并法（）分解法按时间抽取法解过程的规律。n1.原位运算（in-place)n2.码位倒读规则，乱序输入，顺序输出（1）“级级”概念概念n将N 点DFT先分成两个N/2点DFT，再是四个N/4点DFT直至N/2个两点DFT.每分一次称为“一”级运算。n因为N=2M所以N点DFT可分成M级依次m=0,m=1.M-1共M级 每一级都有N/2个蝶形单元，例如：N=8,则每级都有4
2、个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组具有相同的结构，相同的 因子分布，第m级的组数为：rNW12mN例：N=8=23，分3级。m=0级,分成四组,每组系数为m=1级,分成二组,每组系数为m=2级,分成一组,每组系数为080204/WWWN28082012/02/,WWWWWWNNNN382818083210,WWWWWWWWNNNNrNW121,0,3,2,102101001238281808828081404408022mkkkkkWmWWWWkWmWWWWkWmWWkWmm级的系数为看出：第，级，级，级，由上可知：结论：每由后向前（结论：每由后向前（m由由M-1-0级
3、）推进一级）推进一级，则此系数为后级系数中偶数序号的那一半。级，则此系数为后级系数中偶数序号的那一半。x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)12/0NNNWW 其中旋转因子，共有m=0m=1m=2x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)12/0NNNWW 其中旋转因子，共有m=
4、0m=1m=210*10*10*10)()()(1()(1)()(1)()(1)(NnnkNnkNNknkNNknkNNkWnxkXkXDFTNWkXNnxWkXNnxWkXNnx比较与取共轭再取共轭）对它取共轭：可知：只须将频域成份一个求共轭变换，即（1）将X(k)的虚部乘以-1，即先取X(k)的共轭，得X*(k)。(2)将X*(k)直接送入FFT程序即可得出Nx*(n)。(3)最后再对运算结果取一次共轭变换，并乘以常数1/N，即可以求出IFFT变换的x(n)的值。此为DFT可用FFT程序)(kzX)(nx22nnA22k22)(nWnh)(ng)(kG，表示在园内通常正可负，为角频率）：为
5、起始样点相角（可：为起始样点半径，1,00000AAeAAj（2）zk是z平面一段螺线上的等分角上某一采样点。上的一部分。，这段园弧则是单位园若的一段园弧，：表示半径弯曲（向原点盘旋）围线（螺线）盘旋向内的增加，随着盘旋向外弯曲的增加，围线（螺线）随着弯曲。旋是向内弯曲还是向外它的大小控制着围线盘：为螺线的伸展率。其中11:1:1000000)(0000AAkkeAzkjkk的路径是逆时针旋转。为正时，表示当的路径是顺时针旋转。为负时，表示当它可以是正值或负值。（即之间角频率差。：表示两相邻kkkzzzzzzz0021100),)3(。变换求出该序列即由，为均匀分布在单位园上此时等分）时，（。
6、即即（当满足下面特殊条件：DFTCZTzNNMeecAeAAbNMakNjjj221,)(01,1)(:)4(002000000当M、N足够小时，直接算法运算量少。但M、N值比较大时（大于50），CZT算法比直接算法的运算量少得多。例M=50，N=50，N*M=2500次而CZT1600次。235log2()kCZTNLLLMX zNM共需复乘次数为：直接计算需要次复数乘法）点重叠。相邻两段输出序列有（点，长度为点，而长度为重叠部分相加起来：将各段点计算相乘：点计算点）计算（11)()()()()()4()()()3()()()()2()()(),()(1010)()(1)1(01)1()()
7、(10MmpnypnxnynynykYIFFTnyIFFTLkXkHkYnhDFTkHnxDFTkXDFTLLnMMnnhnhLnpipinipnxnxDFTLiiiiiiiiiiii)()()()3()()()()(211)1()()(1kXkHkYnxDFTkXnhDFTkHFFTNMMNLLMMNnxnxiiiii相乘点）计算（个零值点。则需要在它前边填充前一段保留信号，而对第一段，由于没有，准备进行圆卷积。点短序列组成个输入序列值，的再补上前一段保留下来段的前边这样分段后，应在每一为短序列的长度；点，每段长度为，分成几个短序列）先将（)1()()1()5()()()4(MLinynyM
8、kYIDFTnyIFFTNiii出。就构成了最后的正确输来的序列衔接起来，再把各相邻输出段留下必须舍去。不等于线性卷积的值，个点的前由于每段圆周卷积结果点计算)(nx10102)()()()(NnnkNNnnkNjWnxenxnxDFSkX2110011()()()()NNjnknkNNkkx nIDFS X kX k eX k WNNNjNeW210102)()()()(NnnkNNnnkNjWnxenxnxDFTkX10102)()(1)()(NknkNNknkNjWkxekXNkXIDFTnxn时移特性时移特性已知已知 DFTx(n)=X(k)则则 DFTx(n+m)NRN(n)=WN-
9、mkX(k)n频移特性设频域N点，有限长序列X(k)则)()(nxkXIDFTln()()()NNNIDFT XklRkW x n121212111LNNLNNLL NN线性卷积长度时，点圆周卷积能代表线性卷积时，n=0到n=N-L-1处混叠，即圆周卷积和线性卷积不同的点n=N-L到n=L-1为圆周卷积和线性圆周卷积长度，卷积相同的点)()()()()()(nxnRrNnxnRnxnxNrNNN()jX ennjjenxnxFeX)()()(x(n)的傅立叶变换定义如下:可见 还是 w的周期函数，周期为2比较后可见：序列的傅立叶变换是序列的傅立叶变换是Z Z变换在变换在 时时的的Z Z变换，即变换，即Z Z变换在的单位圆上变换在的单位圆上 的特殊情况。的特殊情况。jez 1zjezjzXeX)()(22shshff 即理想抽样输出：()()()()()aaTamx tx ttx mTtmT()()at nTx nx t祝您成功！
