离散傅立叶变换的运算特点

《离散傅立叶变换的运算特点》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、快速傅立叶变换快速傅立叶变换21§7-1离散傅立叶变换的运算特点2§7-2按时间抽取的FFT算法3§7-3按频率抽取的FFT算法4§7-4几种特殊的FFT算法2021/7/23引言有限长序列通过离散傅里叶变换(DFT)将其频域离散化成有限长序列。但其计算量太大，很难实时地处理问题，因此引出了快速傅里叶变换(FFT)。FFT并不是一种新的变换形式，它只是DFT的一种快速算法。并且根据对序列分解与选取方法的不同而产生了FFT的多种算法。FFT:FastFourierTransform1965年，Cooley,Turkey《机

2、器计算傅里叶级数的一种算法》32021/7/23直接计算DFT的问题及改进途径离散傅立叶变换（DFT）的定义为：4k＝0，1，2，…，N－1n＝0，1，2，…，N－12021/7/23DFT运算量2021/7/235复数乘法复数加法一个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)由此看出：直接计算DFT时，乘法次数与加法次数都是和N的平方成比例的。当N很大时，所需工作量非常

3、可观。当N=1024点时，直接计DFT需要：次，即四百多万次的实数乘法运算。这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有十分苛刻的要求。可利用DFT运算的系数的固有对称性和周期性，改善DFT的运算效率2021/7/2362021/7/23782021/7/2392021/7/23FFT算法分类:时间抽选法DIT:Decimation-In-Time频率抽选法DIF:Decimation-In-Frequency§7-2按时间抽取的FFT算法§7-2按时间抽取的FFT算法一、按时间抽取的算法原理二、按时间

4、抽取的算法特点三、按时间抽取FFT算法的其他形式112021/7/23一、按时间抽取的算法原理设序列点数N=2L，L为整数。若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组：122021/7/2313则x(n)的DFT:2021/7/2314再利用周期性求X(k)的后半部分2021/7/2315一个“蝶形运算”包含1次乘法，2次加法2021/7/23162021/7/23复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2–1)两个N/2点DFTN2/2N(N/2–1

5、)一个蝶形12N/2个蝶形N/2N总计17分解后的运算量：运算量减少了近一半2021/7/23N/2仍为偶数，进一步分解：N/2N/4182021/7/2319同理：其中：这样逐级分解，直到2点DFT基2时间抽取FFT算法流图20N=2x[k]={x[0],x[1]}2021/7/234点基2时间抽取FFT算法流图21x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2点DFT2点DFT-1-1-1-1X[0]X[1]X[2]X[3]2021/7/23222021/7/234点基2时间抽取FFT算法

6、流图8点基2时间抽取FFT算法流图234点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]-1-1-1-12021/7/23244点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x[5]x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]X[0]X[1]X[2]X[3]X[4]X[5]X[6]X

7、[7]-1-1-1-18点基2时间抽取FFT算法流图2021/7/23基2时间抽取FFT算法25第一级第二级第三级2021/7/23二、按时间抽取的算法特点261.计算速度当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法：复数加法：比较DFT2021/7/23272021/7/23算法的计算复杂度28复乘次数NN22021/7/23例.如果一台通用计算机的速度为平均每次复乘，每次复加，用它来计算512点的，问直接计算需要多少时间，用运算需要多少时间。解：(1)直接利用计算：复乘次

8、数为，复加次数为。复乘所需时间复加所需时间所以直接利用DFT计算所需时间：2021/7/2329复乘所需时间复加所需时间所以用FFT计算所需时间(2)利用计算：复乘次数为，复加次数为。2021/7/23302.倒序排列n0n1n200011011001101倒位序自然序000000001004100101022010