Chap4快速傅立叶变换(FFT)课件.ppt

《Chap4快速傅立叶变换(FFT)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chap4快速傅立叶变换（FFT）本章主要内容按时间抽取（DIT）的FFT算法按频率抽取（DIF）的FFT算法线性调频z变换实序列FFT算法FFT应用§4.1引言一、DFT的计算工作量两者的差别仅在指数的符号和因子1/N§4.1引言（续）分析计算一个X(k)的值的工作量:如X(1)考虑一般情况：都是复数一个X(k)：N次复数乘法，（N-1）次复数加法所有X(k)：N2次复数乘法，N（N-1）次复数加法运算量与N2（序列长度）成正比！当N很大时，如N=1024,则要完成1048576次（一百多万次）运算，这样，难以做到实时处理。§4.1引言（续）二、算法改进1.的

2、对称性和周期性对称性：周期性：得到：§4.1引言（续）利用上述特性，可以将有些项合并，并将DFT分解为短序列，从而降低运算次数，提高运算速度。1965年，库利（cooley）和图基（Tukey）首先提出FFT算法，对于N点DFT，仅需次复数乘法运算。例如：§4.1引言（续）例如：将第n项和第N-n项合并，其中实部部分得：乘法次数减少一半！其它项同样。§4.2按时间抽取的FFT算法——库利－图基算法一、算法原理（基-2FFT）1.先将x(n)按n的奇偶分为两组做DFT，设不足时可在序列末尾补零，这样有：n为偶数时：n为奇数时：因此：§4.2按时间抽取的FFT算法

3、（续）其中：§4.2按时间抽取的FFT算法（续）均为N/2点DFT只能确定出的前N/2，即：的后N/2点的确定§4.2按时间抽取的FFT算法（续）的后一半也完全由的前一半所确定。结论：一个N点序列的DFT可由两个N/2点的DFT来确定。§4.2按时间抽取的FFT算法（续）2.蝶形运算由表示的运算是一种特殊的运算实现上式运算的流图称作蝶形运算（N/2个蝶形）11-1§4.2按时间抽取的FFT算法（续）3.计算量分析：按奇偶分组后的计算量一个N/2点的DFT运算量：复乘次数：复加次数：两个N/2点的DFT运算量：复乘次数：复加次数：一个蝶形运算量：复乘次数：1复加次

4、数：2N/2个蝶形运算量：复乘次数：N/2复加次数：N总运算量：复乘：复加：直接运算量：运算量减少近一半！§4.2按时间抽取的FFT算法（续）例：N=8可以分解为两个N/2＝4点的DFTN为偶数时，记N为奇数时，记分别计算N/2＝4点的DFT，得（k=0,1,2,3）§4.2按时间抽取的FFT算法（续）得：蝶形图如下：§4.2按时间抽取的FFT算法（续）同理：仍为偶数，可进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4得子序列。分别进行N/4点的DFT，得§4.2按时间抽取的FFT算法（续）这样，做相同的分解，并分别做傅立叶变换§4.2按时间抽取的FFT

5、算法（续）由进行蝶形运算，得：流图如下：§4.2按时间抽取的FFT算法（续）继续分解，直至两个一点为止。N＝8完整流图如下：§4.2按时间抽取的FFT算法（续）二、DITDFT算法小结：计算一个的FFT时，需经过级分解，最终得到N/2个两点DFT。由两点DFT逐级合成4点，8点，…，N点。每级中都有N/2个蝶形。每次分解都是根据序列序号的奇偶进行的，故称为按时间抽取的算法。DITDFT属于原位运算。流图中输入“乱序”，输出“顺序”。§4.2按时间抽取的FFT算法（续）“乱序”原因01010101x(000)x(100)x(010)x(110)x(001)x(10

6、1)x(011)x(111)04261537§4.2按时间抽取的FFT算法（续）“整序”规律将输入序号按自然顺序排序后，用相应位数的二进制码表示，再进行反序，即可实现输入端的整序。自然顺序n二进制反序二进制倒位顺序n0000000010011004201001023011110641000011510110156110011371111117§4.2按时间抽取的FFT算法（续）蝶形图的规律第级：蝶形运算有N/2个传输系数，为共N/2个。第三级：蝶形运算类型有四个第二级：蝶形运算类型有二个第一级：蝶形运算类型有一个每向前一级，W因子取偶数序号。参加蝶形运算两点间的

7、距离规律：最后一级的间距最大，每向前推一级，间距减小一半。§4.2按时间抽取的FFT算法（续）DITDFT算法与直接计算的DFT运算量的比较因为在级运算中，每一级都有N/2个蝶形，每一级运算中运算有都有N/2次复乘和N次复加（见前面）因而，级运算中，共需要复加次数：复乘次数：只考虑乘法计算量时，直接计算与FFT方法运算量相比：N足够大时，FFT有明显优势。§4.2按时间抽取的FFT算法（续）直接计算与FFT方法，乘法运算比较曲线§4.3按频率抽取（DIF）的FFT算法——桑德－图基算法一、算法原理设不足时，可在末尾补零。将x(n)按n的自然顺序分为前后两组，即

8、则：§4.3按频率抽取（