数字图像处理---快速傅里叶变换ppt课件.ppt

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

1、第五章快速傅里叶变换本章目录直接计算DFT的问题及改进的途径按时间抽取的基2-FFT算法按频率抽取的基2-FFT算法快速傅里叶逆变换(IFFT)算法Matlab实现25.1引言DFT在实际应用中很重要:可以计算信号的频谱、功率谱和线性卷积等。直接按DFT变换进行计算，当序列长度N很大时，计算量非常大，所需时间会很长。FFT并不是一种与DFT不同的变换，而是DFT的一种快速计算的算法。35.2直接计算DFT的问题及改进的途径DFT的运算量设复序列x(n)长度为N点，其DFT为k=0，，…，N-1（1）计算一个X(k)值的运算量复数乘法次数：N复数加法次数：N－

2、145.2.1DFT的运算量（2）计算全部N个X(k)值的运算量复数乘法次数：N2复数加法次数：N(N－1)（3）对应的实数运算量5一次复数乘法：4次实数乘法2次实数加法＋一个X(k)：4N次实数乘法＋2N+2(N-1)=2(2N-1)次实数加法所以整个N点DFT运算共需要：N×2(2N-1)=2N(2N-1)实数乘法次数：4N2实数加法次数：6DFT运算量的结论N点DFT的复数乘法次数举例NN2NN22464404941612816384864256655361625651226214432102810241048576结论：当N很大时，其运算量很大，对实时

3、性很强的信号处理来说，要求计算速度快，因此需要改进DFT的计算方法，以大大减少运算次数。75.2.2减少运算工作量的途径主要原理是利用系数的以下特性对DFT进行分解：（1）对称性（2）周期性（3）可约性另外，85.3按时间抽取的基2-FFT算法算法原理按时间抽取基-2FFT算法与直接计算DFT运算量的比较按时间抽取的FFT算法的特点按时间抽取FFT算法的其它形式流程图95.3.1算法原理设N＝2L，将x(n)按n的奇偶分为两组：r=0，1，…，则10式中，X1(k)和X2(k)分别是x1(n)和x2(n)的N/2的DFT。另外，式中k的取值范围是：0，1，…，

4、N/2－1。11因此，只能计算出X(k)的前一半值。后一半X(k)值，N/2，N/2＋1，…，N？利用可得到同理可得12考虑到因此可得后半部分X(k)及前半部分X(k)k=0，1，…，N/2－1k=0，1，…，N/2－113蝶形运算蝶形运算式蝶形运算信号流图符号因此，只要求出2个N/2点的DFT，即X1(k)和X2(k)，再经过蝶形运算就可求出全部X(k)的值，运算量大大减少。14以8点为例第一次按奇偶分解以N=8为例，分解为2个4点的DFT，然后做8/2=4次蝶形运算即可求出所有8点X(k)的值。15蝶形运算量比较复数乘法次数：N2复数加法次数：N(N－1)

5、复数乘法次数：2*(N/2)2+N/2=N2/2+N/2复数加法次数：2*(N/2)(N/2－1)+2*N/2=N2/2N点DFT的运算量分解一次后所需的运算量＝2个N/2的DFT＋N/2蝶形：因此通过一次分解后，运算工作量减少了差不多一半。16进一步按奇偶分解由于N＝2L，因而N/2仍是偶数，可以进一步把每个N/2点子序列再按其奇偶部分分解为两个N/4点的子序列。以N/2点序列x1(r)为例则有k=0,1,…,17且k=0,1,…,由此可见，一个N/2点DFT可分解成两个N/4点DFT。同理，也可对x2(n)进行同样的分解，求出X2(k)。18以8点为例第二

6、次按奇偶分解19算法原理对此例N=8，最后剩下的是4个N/4=2点的DFT，2点DFT也可以由蝶形运算来完成。以X3(k)为例。k=0,1即这说明，N=2M的DFT可全部由蝶形运算来完成。20以8点为例第三次按奇偶分解N=8按时间抽取法FFT信号流图215.3.2按时间抽取基2-FFT算法与直接计算DFT运算量的比较由按时间抽取法FFT的信号流图可知，当N=2L时，共有级蝶形运算；每级都由个蝶形运算组成，而每个蝶形有次复乘、次复加，因此每级运算都需次复乘和次复加。LN/2N/212N22这样级运算总共需要：L复数乘法：复数加法：直接DFT算法运算量复数乘法：复

7、数加法：N2N(N－1)直接计算DFT与FFT算法的计算量之比为M23FFT算法与直接DFT算法运算量的比较NN2计算量之比MNN2计算量之比M2414.01281638444836.641644.025665536102464.0864125.45122621442304113.816256328.0102410485765120204.83210288012.82048419430411264372.464404919221.4245.3.3按时间抽取的FFT算法的特点序列的逆序排列同址运算（原位运算）蝶形运算两节点间的距离的确定25序列的逆序排列由于x(

8、n)被反复地按奇、偶分组，所以流图输入