快速傅里叶变换ppt课件.ppt

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

1、一、直接计算DFT的问题及改进途径1运算量复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)N2N(N–1)实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)4N22N(2N–1)2改善DFT运算效率的基本途径：利用DFT运算的系数的固有对称性和周期性，改善DFT的运算效率。1.合并法：合并DFT运算中的某些项。2.分解法：将长序列DFT利用对称性和周期性，分解为短序列DFT。34把N点数据分成二半：其运算量为：再分二半

2、：+=+++=这样一直分下去，剩下两点的变换。5FFT算法分类:时间抽选法DIT:Decimation-In-Time频率抽选法DIF:Decimation-In-Frequency6二、按时间抽选的基-2FFT算法1、算法原理设序列点数N=2L，L为整数。若不满足，则补零将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。7则x(n)的DFT:8再利用周期性求X(k)的后半部分910分解后的运算量：复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2–1)两

3、个N/2点DFTN2/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计运算量减少了近一半11N/2仍为偶数，进一步分解：N/2N/412同理：其中：1314这样逐级分解，直到2点DFT当N=8时，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,115m=1m=2m=316FFT算法中一些概念（1）“级”概念将N点DFT先分成两个N/2点DFT，再是四个N/4点DFT…直至N/2个两点DFT.每分一次称为“一”级运算。因为N=2L所以N点DFT可分成L级如上图所示依次m=1,

4、m=2….L共L级17（2）“组”概念每一级都有N/2个蝶形单元，例如：N=8,则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组具有相同的结构，相同的因子分布，第m级的组数为：例：N=8=23，分3级。m=1级,分成四组,每组系数为m=2级,分成二组,每组系数为m=3级,分成一组,每组系数为182、运算量当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法：复数加法：比较DFT19m=1m=2m=3203、算法特点1）原位计算m表示第m

5、级迭代，k，j表示数据所在的行数212）倒位序倒位序自然序000000001004100101022010110630110011410010155101011361101117711122233）蝶形运算对N=2L点FFT，输入倒位序，输出自然序，第m级运算每个蝶形的两节点距离为2m–1第m级运算：24m=1m=2m=325因子的确定方法结论：每由后向前（m由L-->1级）推进一级，则此系数为后级系数中偶数序号的那一半。26蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移L–m位，把

6、右边空出的位置补零，结果为r的二进制数。方法二：274）存储单元输入序列x(n):N个存储单元系数：N/2个存储单元284、DIT算法的其他形式流图输入倒位序输出自然序输入自然序输出倒位序输入输出均自然序相同几何形状输入倒位序输出自然序输入自然序输出倒位序293031323334三、按频率抽选的基-2FFT算法1、算法原理设序列点数N=2L，L为整数。将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半：3536按k的奇偶将X(k)分成两部分：37令则X(2r)和X(2r+1)分别

7、是x1(n)和x2(n)的N/2点DFT，记为X1(k)和X2(k)38x1(0)x1(1)-1x1(2)x1(3)-1x2(0)x2(1)-1x2(2)x2(3)-1N/2点DFTN/2点DFTx(0)x(7)x(1)x(2)x(3)x(4)x(5)x(6)X1(0)=X(0)X2(0)=X(1)X1(1)=X(2)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)39N/2仍为偶数，进一步分解：N/2N/440x3(0)x3(1)-1-1x4

8、(0)x4(1)N/4点DFTN/4点DFTx1(0)x1(1)x1(2)x1(3)X3(0)=X1(0)=X(0)X4(0)=X1(1)=X(2)X3(1)=X1(2)=X(4)X4(1)=X1(3)=X(6)41同理：其中：4243逐级分解，直到2点DFT当N=8时，即分解到x3(n)，x4(n)，x5(n)，x6(n)，n=0,144452、算法特点1）原位计算-1L级蝶形运算，每级N/2个蝶形，每个蝶形结构：m表示第m级迭代，k，j表示数据所在的行数462）蝶形运算对N=2L点FFT，输