《离散傅立叶变换的运算特点.ppt》由会员分享，可在线阅读，更多相关《离散傅立叶变换的运算特点.ppt（69页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、快速傅立叶变换2 217-1 离散傅立叶变换的运算特点离散傅立叶变换的运算特点27-2 按时间抽取的按时间抽取的FFT算法算法37-3 按频率抽取的按频率抽取的FFT算法算法47-4 几种特殊的几种特殊的FFT算法算法2023/2/202023/2/20引言 有限长序列通过离散傅里叶变换(DFT)将其频域离散化成有限长序列。但其计算量太大，很难实时地处理问题，因此引出了快速傅里叶变换(FFT)。FFT 并不是一种新的变换形式，它只是DFT 的一种快速算法。并且根据对序列分解与选取方法的不同而产生了FFT 的多种算法。FFTFFT:Fast Fourier Transform1965年，Cool
2、ey,Turkey 机器计算傅里叶级数的一种算法3 32023/2/202023/2/20直接计算DFT的问题及改进途径离散傅立叶变换（DFT）的定义为：4 4 k0，1，2，N1 n0，1，2，N12023/2/202023/2/20DFT运算量2023/2/202023/2/205 5复数乘法复数乘法复数加法复数加法一个X(k)N N 1N个X(k)（N点DFT）N2N(N 1)实数乘法实数乘法实数加法实数加法一次复乘42一次复加2一次X(k)4N2N+2(N 1)=2(2N 1)N个X(k)(N点DFT)4N 22N(2N 1)由此看出：直接计算DFT时，乘法次数与加法次数都是和N的平方
3、成比例的。当N很大时，所需工作量非常可观。当N=1024点时，直接计DFT需要：次，即四百多万次的实数乘法运算。这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有十分苛刻的要求。可利用可利用DFTDFT运算的系数运算的系数 的固有对称性和周期性，改善的固有对称性和周期性，改善DFTDFT的运算效率的运算效率2023/2/202023/2/2062023/2/202023/2/2078 82023/2/202023/2/209 92023/2/202023/2/20FFTFFT算法分类算法分类:时间抽选法时间抽选法DIT:Decimation-In-Time频率抽选法频率抽选法DIF
4、:Decimation-In-Frequency7-2 按按时间抽取的FFT算法一、按时间抽取的算法原理二、按时间抽取的算法特点三、按时间抽取FFT算法的其他形式11 112023/2/202023/2/20一、按时间抽取的算法原理设序列点数 N=2L，L 为整数。若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。将序列x(n)按n的奇偶分成两组：12122023/2/202023/2/201313则则x(n)的的DFT:2023/2/202023/2/201414再利用周期性求再利用周期性求X(k)的后半部分的后半部分2023/2/202023/2/201515一个一个“蝶形运算
5、蝶形运算”包含包含1次乘法，次乘法，2次加法次加法2023/2/202023/2/2016162023/2/202023/2/20复数乘法复数乘法复数加法复数加法一个一个N/2点点DFT(N/2)2N/2(N/2 1)两个两个N/2点点DFTN 2/2N(N/2 1)一个蝶形一个蝶形12N/2个蝶形个蝶形N/2N总计总计1717分解后的运算量：分解后的运算量：运算量减少了近一半运算量减少了近一半2023/2/202023/2/20N/2仍为偶数，进一步分解：N/2 N/418182023/2/202023/2/20191919同理同理：其中：其中：这样逐级分解，直到这样逐级分解，直到2点点DF
6、T2020N=2xk=x0,x12023/2/202023/2/202121x0 x2x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0X 1X 2X 32023/2/202023/2/2022222023/2/202023/2/204点基2时间抽取FFT算法流图23234点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-12023/2/202023/2/2024244点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X2
7、2X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基2时间抽取FFT算法流图2023/2/202023/2/202525第一级第一级第二级第二级第三级第三级2023/2/202023/2/2026261.计算速度 当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法复数乘法：复数加法复数加法：比较比较DFT 2023/2/202023/2/2027272023/2/202023/2/202828复乘次数NN 22023/2/202023/2/20例.如果一台通用计算机的速度为平均每次复乘 ，每次复加 ，用它来计算512点的 ，问直
8、接计算需要多少时间，用 运算需要多少时间。解：(1)直接利用 计算：复乘次数为 ，复加次数为 。复乘所需时间 复加所需时间 所以直接利用DFT 计算所需时间：2023/2/202023/2/202929复乘所需时间 复加所需时间 所以用 FFT 计算所需时间(2)利用 计算：复乘次数为 ，复加次数为 。2023/2/202023/2/2030302.倒序排列n0n1n200011011001101倒位序倒位序 自然序自然序000000001004100101022010110630110011410010155101011361101117711131313232倒序倒序k0k1k2xk2 k
9、1k0 x00 0 x10 0 x01 00101112 xk k0 xk2 k101x11 0 x001 x101 x01 1x111 010101012023/2/202023/2/20 3.同址运算 在同一级蝶形运算中，两信号只参与一次运算。4.蝶距规律3333三、按时间抽取FFT算法的其它形式34342023/2/202023/2/2035352023/2/202023/2/2036362023/2/202023/2/2037372023/2/202023/2/20一、按频率抽取的算法原理二、按频率抽取的算法特点三、与按时间抽取算法的对称性3838一、按频率抽取的算法原理设序列点数 N
10、=2L，L 为整数。若不满足，则补零将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半39394040则则x(n)的的DFT:4141 按按k的奇偶将的奇偶将X(k)分成两部分：分成两部分：令4242 则则X(2r)和和X(2r+1)分别是分别是x1(n)和和x2(n)的的 N/2点点DFT，记为，记为X1(k)和和X2(k)4343x1(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)
11、X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X(7)N/2仍为偶数，进一步分解：N/2 N/444444545x3(0)x3(1)-1-1x4(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)逐级分解，直到2点DFT4646同理：同理：其中：其中：3NW-1-12NW-1-11NW-1-10NW-1-1x0 x4x1x5x2x6x3x74点点DFTX0X6X2X44点点DFTX1X3X5
12、X74848X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2点点DFT-1-1-1-12NW0NW-1-1-1-12点点DFT2点点DFT2点点DFT49490NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1时间抽取和频率抽取FFT算法：50501.计算速度 当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法
13、2次复数加法。复数乘法复数乘法：复数加法复数加法：无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率抽取算法这两种抽取算法这两种FFTFFT算法是完全等价的。算法是完全等价的。2.排序规则输入序列x（n）是自然顺序的，输出序列X（k是倒置顺序的。其整序规则与按时间抽取算法是完全一致的。5151 3.同址运算该算法和按时间抽取算法一样也是进行同址运算的。4.蝶距规律其蝶形系数的分布规律与按时间抽取算法是完全对称的。5252三、与按时间抽取算法的对称性二者具有完全对称的蝶距规律蝶形结构和运算流图也都是完全对称的需要的复乘和复加次数也
14、相同频率抽取法运算流图是时间抽取法运算流图的转置，若知道其中一个，应用转置关系就可以得到另一个。5353一、按频率抽取的算法原理二、按频率抽取的算法特点三、与按时间抽取算法的对称性5454一、按频率抽取的算法原理设序列点数 N=2L，L 为整数。若不满足，则补零将X(k)按k的奇偶分组前，先将输入x(n)按n的顺序分成前后两半55555656则则x(n)的的DFT:5757 按按k的奇偶将的奇偶将X(k)分成两部分：分成两部分：令5858 则则X(2r)和和X(2r+1)分别是分别是x1(n)和和x2(n)的的 N/2点点DFT，记为，记为X1(k)和和X2(k)5959x1(0)x1(1)-
15、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)N/2仍为偶数，进一步分解：N/2 N/460606161x3(0)x3(1)-1-1x4(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
16、(1)=X1(3)=X(6)逐级分解，直到2点DFT6262同理：同理：其中：其中：3NW-1-12NW-1-11NW-1-10NW-1-1x0 x4x1x5x2x6x3x74点点DFTX0X6X2X44点点DFTX1X3X5X76464X0X6X4X2X1X5X3X70NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2点点DFT-1-1-1-12NW0NW-1-1-1-12点点DFT2点点DFT2点点DFT65650NW1NW2NW3NW-1-1-1-1-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X
17、2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1-1时间抽取和频率抽取FFT算法：66661.计算速度 当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法复数乘法：复数加法复数加法：无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率抽取算法这两种抽取算法这两种FFTFFT算法是完全等价的。算法是完全等价的。2.排序规则输入序列x（n）是自然顺序的，输出序列X（k是倒置顺序的。其整序规则与按时间抽取算法是完全一致的。6767 3.同址运算该算法和按时间抽取算法一样也是进行同址运算的。4.蝶距规律其蝶形系数的分布规律与按时间抽取算法是完全对称的。6868三、与按时间抽取算法的对称性二者具有完全对称的蝶距规律蝶形结构和运算流图也都是完全对称的需要的复乘和复加次数也相同频率抽取法运算流图是时间抽取法运算流图的转置，若知道其中一个，应用转置关系就可以得到另一个。6969