fft运算电子版本.ppt

《fft运算电子版本.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、fft运算SectionI-1:按时间抽取FFT对于2的整数次幂点数的按时间抽取的FFT而言，其变换始于对序列x(n)按奇偶数项分组，表达式如下：在此基础上，DFT运算也相应分为两组，表达式如下：SectionI-1:按时间抽取FFTSectionI-1:按时间抽取FFT这样，一个N点的DFT被分解为两个N/2点的DFT了，这两个N/2点的DFT再按照(6-3)合成一个N点的DFT，同时利用W的周期特性，就可将X(k)表达为前后两部分：SectionI-1:按时间抽取FFT根据以上X(k)的组成方式，就可做出如

2、下的“蝶形结”运算结构（请注意该结构的组合方式及系数的标记位置）：这种方法，由于每一步分解都是按输入序列在时域上的次序是属于偶数还是奇数来抽取的，所以称为“按时间抽取法”.SectionI-2:按频率抽取FFT按频率抽取法将输入序列按前后对半分开，即将N点DFT写成前后两部分：此处我们可将X(k)进一步分解为偶数组和奇数组：SectionI-2:按频率抽取FFT以上两式表示的正是两个N/2点的DFT运算：其中，我们令SectionI-2:按频率抽取FFT这样同样是将一个N点的DFT分解为两个N/2点的DFT了。

3、式(6-13)所述运算关系可表示为如下的“蝶形结”运算结构（请注意该结构的组成方式及系数的标记位置）：这种分组方式由于每一次都是按输出X(k)在频域的顺序上是属于偶数还是奇数从而分解为两组的，故称为“按频率抽取法”。SectionI-3:IDFT(IFFT)IDFT的运算式为：将其与DFT的运算式相比较：可见，只要把DFT运算中的每一个系数改为，并且最后再乘以常数1/N，那么所有以上所讨论的时间抽取或频率抽取SectionI-3:IDFT(IFFT)的FFT算法都可以直接拿来运算IDFT。但是在命名上要颠倒一下

4、。当把FFT的时间抽取法用于IDFT运算时，由于输入变量由时间序列x(n)改变为频率序列X(k)，因此原来按x(n)的奇偶次序分组的时间抽取法FFT，现在就成了按X(k)的奇偶次序抽取了，因此应该称其为频率抽取IFFT运算。SectionI-3:IDFT(IFFT)同样，频率抽取的FFT运算用于IDFT时，也应该称为时间抽取的IFFT运算。另外，在IFFT的运算中，经常也将常数1/N分解为，并且在M级运算中，每级运算都分别乘一个1/2因子，这样就可以得到IFFT的以下两种基本蝶形结运算结构：SectionI-3

5、:IDFT(IFFT)若将上页左图所示蝶形运算代替FFT时间抽取法中的蝶形运算，就可以得到IFFT的频率抽取法运算；而将上页右图所示的蝶形运算代替FFT频率抽取法中的蝶形运算，就可以得到IFFT的时间抽取法运算。SectionI-4:任意基数FFT在此，我们只着重提出将点数N分解为几个整数的乘积，然后利用类似于前面所讨论的对序列分组处理然后依一定规则合并的方法，达到简化DFT运算的目的，其核心思想就是要将DFT的运算尽量分小(DivideandConquer)。SectionI-4:任意基数FFT以可被分解为两

6、个整数p和q的乘积的N点DFT为例。我们可以首先将x(n)分成p组，这p组序列每一组都是一个长度为q的有限长序列，然后将N点DFT运算也相应分解为p组，即有如下表示式：SectionI-4:任意基数FFT其中就是第l组序列的q点DFT：这样，式(6-19)就表明了一个N＝p*q点的DFT可以用p组的q点DFT来组成。同时，这种分解的原则对于任意基数的任何更加复杂的情况都是适用的。SectionI-4:任意基数FFT例如当N如果可以分解为m个质数因子p1，p2，…，pm时，即N=p1*p2*…*pm，那么我们第一

7、步可先把N分解为两个因子N=p1*q1，其中q1=p2*p3*…*pm，并用以上所讨论的方法将DFT分解为p1个q1点的DFT，SectionI-4:任意基数FFT然后第二步再将q1分解为q1=p2*q2，其中q2=p3*p4*…*pm，将每一个q1点DFT再分解为p2个q2点DFT，这样可以通过m次分解一直分到最少点数的DFT运算，从而使运算获得较高效率。SectionII:习题(第一部分)本节包括习题5，6，7，9和10，所涉均为我们在第一节里回顾到的各项内容。SectionII:习题(第一部分)55.试证

8、实以下流图是一个N=8的FFT流图.其输入是自然顺序的,而输出是码位倒置顺序的,试问这个流图是属与时间抽取法还是频率抽取法?并比较与书中哪一个流图等效。SectionII:习题(第一部分)5SectionII:习题(第一部分)5SectionII:习题(第一部分)5SectionII:习题(第一部分)5SectionII:习题(第一部分)5SectionII:习题(第一部分)66.试设