1、1n直接计算直接计算DFT的问题及改进的途径的问题及改进的途径 2 3 设复序列设复序列x(n)长度为长度为N点，其点，其DFT为为10()()NnkNnX kx n Wk=0，N-1（1）计算一个）计算一个X(k)值的运算量值的运算量复数乘法次数：复数乘法次数：N复数加法次数：复数加法次数：N14（2）计算全部）计算全部N个个X(k)值的运算量值的运算量复数乘法次数：复数乘法次数：N2复数加法次数：复数加法次数：N(N1)（3）对应的实数运算量）对应的实数运算量1100()()Re()Im()ReImNNnknknkNNNnnX kx n Wx njx nWjW10Re()ReIm()ImN
2、nknkNNnx nWx nWRe()ImIm()RenknkNNjx nWx nW5一次复数乘法一次复数乘法：4次实数乘法次实数乘法 2次实数加法次实数加法 一个一个X(k)：4N次实数乘法次实数乘法2N+2(N-1)=2(2N-1)次实数加法次实数加法 所以所以 整个整个N点点DFT运算共需要：运算共需要：N2(2N-1)=2N(2N-1)实数乘法次数：实数乘法次数：4 N2实数加法次数：实数加法次数：1100()()Re()Im()ReImNNnknknkNNNnnX kx n Wx njx nWjW10Re()ReIm()ImNnknkNNnx nWx nWRe()ImIm()Renk
3、nkNNjx nWx nW6N点点DFT的复数乘法次数举例的复数乘法次数举例NN2NN22464404941612816384864256 65 536 16256512 262 144 3210281024 1 048 576 结论结论：当：当N很大时，其运算量很大，对实时性很强的信号很大时，其运算量很大，对实时性很强的信号处理来说，要求计算速度快，因此需要改进处理来说，要求计算速度快，因此需要改进DFT的计算的计算方法，以大大减少运算次数。方法，以大大减少运算次数。7 nkNW()k N nNWjWNN2主要原理是利用系数主要原理是利用系数 的以下特性对的以下特性对DFT进行分解：进行分解
4、：nkNW（1）对称性）对称性()nkNW（2）周期性）周期性()()n N kn kNnkNNNWWW（3）可约性）可约性 mnknkmNNWW/nknk mNN mWW另外，另外，12/NNWkNNkNWW)2/(10NWkkNNW12891()(2)x rxr设设N2L，将，将x(n)按按 n 的奇偶分为两组：的奇偶分为两组：2()(21)x rxrr=0，1，12N10()()()NnkNnX kDFT x nx n W则则1010)()(NnnnkNNnnnkNWnxWnx为奇数为偶数10120)12(1202)12()2(NrkrNNrrkNWrxWrx1202212021)()(
5、NrrkNkNNrrkNWrxWWrx)()(21kXWkXkN1010)()(NnnnkNNnnnkNWnxWnx为奇数为偶数式中，式中，X1(k)和和X2(k)分别是分别是x1(n)和和x2(n)的的N/2的的DFT。另外，式中另外，式中k的取值范围是：的取值范围是：0，1，N/21。22jj222/2eekrkrkrkrNNNNWW11因此，因此，只能计算出只能计算出X(k)的前一半值。的前一半值。12()()()kNX kX kW Xk后一半后一半X(k)值，值，N/2，N/2 1，N？rkNW2(2)2r NkNW利用利用可得到可得到 1()2NXk2 1(2)120()Nr NkN
6、rx r W2 1120()NrkNrx r W)(1kX同理可得同理可得22()()2NXkXk12考虑到考虑到 kNkNNNkNNWWWW2)2(因此可得后半部分因此可得后半部分X(k)2()2()2(221NkXWNkXNkXNkN12()()()kNX kX kW Xk及前半部分及前半部分X(k)()(21kXWkXkNk=0，1，N/21k=0，1，N/211312()()()kNX kX kW Xk蝶形运算式蝶形运算式蝶形运算信蝶形运算信号流图符号号流图符号 因此，只要求出因此，只要求出2个个N/2点的点的DFT，即，即X1(k)和和X2(k)，再，再经过蝶形运算就可求出全部经过蝶
7、形运算就可求出全部X(k)的值，运算量大大减少。的值，运算量大大减少。蝶形运算符号蝶形运算符号)()()2(21kXWkXNkXkN14图图4.2.2 8点点DFT一次时域抽取分解运算流图一次时域抽取分解运算流图以以N=8为例，分解为为例，分解为2个个4点的点的DFT，然后做，然后做8/2=4次蝶形运次蝶形运算即可求出所有算即可求出所有8点点X(k)的值。的值。15复数乘法次数：复数乘法次数：N2复数加法次数：复数加法次数：N(N1)复数乘法次数：复数乘法次数：2*(N/2)2+N/2=N2/2+N/2复数加法次数：复数加法次数：2*(N/2)(N/21)+2*N/2=N2/2nN点点 16
8、由于由于N2L，因而，因而N/2仍是偶数仍是偶数，可以进一步把每个，可以进一步把每个N/2点点子序列再按其奇偶部分分解为两个子序列再按其奇偶部分分解为两个N/4点的子序列。点的子序列。以以N/2点序列点序列x1(r)为例为例 3141()(2)0,1,1()(21)4x lxlNlx lxl则有则有 rkNNrWrxkX212011)()(klNNllkNNlWlxWlx)12(21401221401)12()2(lkNNlkNlkNNlWlxWWlx41404241403)()()()(42/3kXWkXkNk=0,1,14N17且且13/24()()4kNNXkXkWXkk=0,1,14N
9、由此可见，一个由此可见，一个N/2点点DFT可分解成两个可分解成两个N/4点点DFT。同理，也可对同理，也可对x2(n)进行同样的分解，求出进行同样的分解，求出X2(k)。18图图4.2.3 84.2.3 8点点DFTDFT二次时域抽取分解运算流图二次时域抽取分解运算流图1913/40()lkNlx l W02(0)(4)xW x0(0)(4)NxW x 对此例对此例N=8，最后剩下的是，最后剩下的是4个个N/4=2点的点的DFT，2点点DFT也可以由蝶形运算来完成。以也可以由蝶形运算来完成。以X3(k)为例。为例。/4 133/40()()NlkNlXkx l Wk=0,1即即03323(0
10、)(0)(1)XxW x13323(1)(0)(1)XxW x12(0)(4)xW x0(0)(4)NxW x这说明，这说明，N=2M的的DFT可全部由蝶形运算来完成。可全部由蝶形运算来完成。/4/420图图4.2.4 8点点DIT-FFT运算流图运算流图21由按时间抽取法由按时间抽取法FFT的信号流图可知，当的信号流图可知，当N=2L时，共有时，共有 级级蝶形运算；每级都由蝶形运算；每级都由 个蝶形运算组成，而每个蝶形有个蝶形运算组成，而每个蝶形有 次复乘、次复乘、次复加，因此每级运算都需次复加，因此每级运算都需 次复乘和次复乘和 次复加。次复加。LN/2 N/2 12N22这样这样 级运算
11、总共需要：级运算总共需要：L复数乘法：NNLN2log22复数加法：NNLN2log直接直接DFT算法运算量算法运算量 复数乘法：复数加法：N2N(N1)直接计算直接计算DFT与与FFT算法的计算量之比为算法的计算量之比为MNNNNNM222log2log223NN2计算量之比M NN2计算量之比M 2414.012816 38444836.641644.025665 5361 02464.0864125.4512262 1442 304113.816256328.010241 048 5765 120204.83210288012.820484 194 30411 264372.464404
12、919221.4NN2log2NN2log224n算法原理算法原理 再把输出再把输出X(k)按按k的奇偶分组的奇偶分组先把输入按先把输入按n的顺序分成前后两半的顺序分成前后两半设序列长度为设序列长度为N=2L，L为整数为整数 前半子序列前半子序列x(n)后半子序列后半子序列)2(Nnx 0n12N0n12N2510()()NnkNnX kx n W由由DFT定义得定义得/2 110/2()()NNnknkNNnn Nx nWx nW12/0)2(12/0)2()(NnkNnNNnnkNWNnxWnx12/02)2()(NnnkNkNNWWNnxnxk=0，1，N26由于由于 1222jNNjN
13、NeeW/2 120()()()2NNknkNNnNX kx nx nWW所以所以kkNNW)1(2则则 12/0)2()1()()(NnnkNkWNnxnxkXk=0，1，N27然后按然后按k的奇偶可将的奇偶可将X(k)分为两部分分为两部分 2m21kkmr=0，1，12N则式则式/2 10()()(1)()2 NknkNnNX kx nx nW可转化为可转化为/2 120(2)()()2NnmNnNXmx nx nW/2 1/20()()2NnmNnNx nx nW/2 1(21)0(21)()()2NnmNnNXmx nx nW/2 120()()2NnnmNNnNx nx nWW28/
14、2 1/20(2m)()()2NnmNnNXx nx nW令令 nNWNnxnxnxNnxnxnx)2()()()2()()(21n=0，1，12N代入代入/2 120(21)()()2NnnmNNnNXmx nx nWW2 11202 1220(2)()(21)()NnmNnNnmNnmx n Wmx n Wr=0，1，12N可得可得为为2个个N/2点的点的DFT，合起来正好是，合起来正好是N点点X(k)的值。的值。29nNWNnxnxnxNnxnxnx)2()()()2()()(21将将称为蝶形运算称为蝶形运算与时间抽选基与时间抽选基2FFT算法中的蝶形运算符号略有不同。算法中的蝶形运算符
15、号略有不同。30例例 按频率抽取，将按频率抽取，将N点点DFT分解为两个分解为两个N/2点点DFT的组合的组合(N=8)31 与时间抽取法的推导过程一样，由于与时间抽取法的推导过程一样，由于 N=2L，N/2仍然是仍然是一个偶数，因而可以将每个一个偶数，因而可以将每个N/2点点DFT的输出再分解为偶数组的输出再分解为偶数组与奇数组，这就将与奇数组，这就将N/2点点DFT进一步分解为两个进一步分解为两个N/4点点DFT。N=8323310)(1)(NknkNWkXNkXIDFT10)(1NknkNWkXN10)(1NknkNWkXN1()()IFFT X kFFT XkN()X k 求共轭()X
16、kFFT 求()FFT Xk()FFT XkN 除以()x n 求共轭 在实际工作中，数据在实际工作中，数据x(n)x(n)常常是实数序列。如果直接按常常是实数序列。如果直接按FFTFFT运算流图计算，就是把运算流图计算，就是把x(n)x(n)看成一个虚部为零的复序列进行计看成一个虚部为零的复序列进行计算，这就增加了存储量和运算时间。算，这就增加了存储量和运算时间。处理该问题的算法有三种：处理该问题的算法有三种：1.1.用一个用一个N N点点FFTFFT计算两个计算两个N N点实序列的点实序列的FFTFFT，一个实序列作为，一个实序列作为x(n)x(n)的实部，另一个作为虚部，计算的实部，另一个作为虚部，计算FFTFFT，根据，根据DFTDFT的共轭对称的共轭对称性，用例性，用例3.2.23.2.2所述方法输出所述方法输出X(k)X(k)分别得到两个实序列的分别得到两个实序列的N N点点DFTDFT；2.2.用用N/2N/2点点FFTFFT计算一个计算一个N N点实序列的点实序列的DFTDFT（自己练习）；（自己练习）；3.3.用离散哈特莱变换（用离散哈特莱变换（DHTDHT）。）。34
