《离散傅立叶变换的运算特点》由会员分享，可在线阅读，更多相关《离散傅立叶变换的运算特点（69页珍藏版）》请在金锄头文库上搜索。
1、 快速傅立叶变换2 217-1 离散傅立叶变换的运算特点27-2 按时间抽取的FFT算法37-3 按频率抽取的FFT算法47-4 几种特殊的FFT算法* *引言有限长序列通过离散傅里叶变换(DFT)将其频域 离散化成有限长序列。但其计算量太大，很难实时 地处理问题，因此引出了快速傅里叶变换(FFT)。 FFT 并不是一种新的变换形式，它只是DFT 的一种 快速算法。并且根据对序列分解与选取方法的不同 而产生了FFT 的多种算法。FFT: Fast Fourier Transform 1965年，Cooley, Turkey机器计算傅里叶级数的一种算法3 3* *直接计算DFT的问题及改进途径离
2、散傅立叶变换（DFT）的定义为：4 4k0，1，2，N1n0，1，2，N1* *DFT运算量* *5 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的平方成比例的。当N很大时，所需工作量非常可观。当N=1024点时，直接计DFT需要：次，即四百多万次的实数乘法运算。这对实时性很强的信号处理 (如雷达信号处理)来讲，它对计算速度有十分苛刻的要求。可
3、利用DFT运算的系数 的固有对称性和周期性，改善 DFT的运算效率* *6* *78 8* *9 9* *FFTFFT算法分类算法分类: :时间抽选法 DIT: Decimation-In-Time频率抽选法 DIF: Decimation-In-Frequency7-2 按时间抽取的FFT算法一、按时间抽取的算法原理二、按时间抽取的算法特点三、按时间抽取FFT算法的其他形式11 11* *一、按时间抽取的算法原理设序列点数 N = 2L，L 为整数。 若不满足，则补零N为2的整数幂的FFT算法称基-2FFT算法。 将序列x(n)按n的奇偶分成两组：1212* *1313则x(n)的DFT:*
4、 *1414再利用周期性求X(k)的后半部分* *1515一个“蝶形运算”包含1次乘法，2次加法* *1616* *复数乘法复数加法一个N / 2点DFT(N / 2)2N / 2 (N / 2 1)两个N / 2点DFTN 2 / 2N (N / 2 1)一个蝶形12N / 2个蝶形N / 2N总计1717分解后的运算量：运算量减少了近一半* *N / 2仍为偶数，进一步分解：N / 2 N / 41818* *19 1919同理：其中：这样逐级分解，直到2点DFT2020N=2xk=x0, x1* *2121x0x2x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0
5、X 1X 2X 3* *2222* *23234点DFT4点DFTx0x2x4x6x1x3 x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-1* *24244点DFT4点DFTx0x2x4x6x1x3 x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基2时间抽取FFT算法流图* *2525第一级第二级第三级* *26261.计算速度当N = 2L时，共有L级蝶形，每级N / 2个蝶形，每 个蝶形有1次复数乘法2次复数加法。复数乘法：复数加法：比较DF
6、T * *2727* *2828复乘次数NN 2* *例 .如果一台通用计算机的速度为平均每次复乘 ， 每次复加 ，用它来计算512点的 ，问 直接计算需要多少时间，用 运算需要多少时间。 解：(1)直接利用 计算：复乘次数为 ，复加次数为 。 复乘所需时间 复加所需时间 所以直接利用DFT 计算所需时间： * *2929复乘所需时间 复加所需时间 所以用 FFT 计算所需时间 (2) 利用 计算：复乘次数为 ，复加次数为 。 * *30302.倒序排列n0n1n2 000 1 10 1 100 1 10 1倒位序 自然序000000001004100101022010110630110011
7、410010155101011361101117711131313232倒序k0k1k2xk2 k1k0x00 0x10 0x01 00101112 xk k0xk2 k101x11 0x001 x101 x01 1x111 01010101* * 3.同址运算在同一级蝶形运算中，两信号只参与一次运算。 4.蝶距规律3333三、按时间抽取FFT算法的其它形式3434* *3535* *3636* *3737* *一、按频率抽取的算法原理二、按频率抽取的算法特点三、与按时间抽取算法的对称性3838一、按频率抽取的算法原理设序列点数 N = 2L，L 为整数。 若不满足，则补零将X(k)按k的奇偶
8、分组前，先将输入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)X1(2)=X(4)X1(3)=X(6)X2(1)=X(3)X2(2)=X(5)X2(3)=X
9、(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同理：其中：3 NW -12 NW -11 NW -10 NW -1x0x4x1x5x2x6x3x74点 DFTX0X6X2X44点 DFTX1X3X5X74848X0X6X4X2X1X5X3X70 NW1 NW2 NW3 NW -1-1-1-1x0
10、x3x1x2x4x5x6x70 NW2 NW2点 DFT-1-12 NW0 NW -1-12点 DFT2点 DFT2点 DFT49490 NW1 NW2 NW3 NW -1-1-1-1x0x3x1x2x4x5x6x70 NW2 NW2 NW0 NWX0X6X4X2X1X5X3X70 NW0 NW0 NW0 NW-1-1-1-1-1-1-1-1时间抽取和频率 抽取FFT算法：50501.计算速度当N = 2L时，共有L级蝶形，每级N / 2个蝶形 ，每个蝶形有1次复数乘法2次复数加法。复数乘法：复数加法：无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率无论从流图结构，还是从计算速度来看
11、，按时间抽取算法和按频率 抽取算法这两种抽取算法这两种FFTFFT算法是完全等价的。算法是完全等价的。2.排序规则输入序列x（n）是自然顺序的，输出序列X（k是倒 置顺序的。 其整序规则与按时间抽取算法是完全一致的。51513.同址运算 该算法和按时间抽取算法一样也是进行同址运算的。4.蝶距规律 其蝶形系数的分布规律与按时间抽取算法是完全对称的 。5252三、与按时间抽取算法的对称性二者具有完全对称的蝶距规律蝶形结构和运算流图也都是完全对称的需要的复乘和复加次数也相同频率抽取法运算流图是时间抽取法运算流图的转置，若知道其中一个，应用转置关系就可以得到另一个。5353一、按频率抽取的算法原理二、
12、按频率抽取的算法特点三、与按时间抽取算法的对称性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)-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
13、)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(1)=X1(3)=X(6)逐级分解，直到2点DFT6262同理：其中：3 NW -12 NW -11 NW -10 NW -1x0x4x1x5x2x6x
14、3x74点 DFTX0X6X2X44点 DFTX1X3X5X76464X0X6X4X2X1X5X3X70 NW1 NW2 NW3 NW -1-1-1-1x0x3x1x2x4x5x6x70 NW2 NW2点 DFT-1-12 NW0 NW -1-12点 DFT2点 DFT2点 DFT65650 NW1 NW2 NW3 NW -1-1-1-1x0x3x1x2x4x5x6x70 NW2 NW2 NW0 NWX0X6X4X2X1X5X3X70 NW0 NW0 NW0 NW-1-1-1-1-1-1-1-1时间抽取和频率 抽取FFT算法：66661.计算速度当N = 2L时，共有L级蝶形，每级N / 2个蝶形 ，每个蝶形有1次复数乘法2次复数加法。复数乘法：复数加法：无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率无论从流图结构，还是从计算速度来看，按时间抽取算法和按频率 抽取算法这两种抽取算法这两种FFTFFT算法是完全等价的。算法是完全等价的。2.排序规则输入序列x（n）是自然顺序的，输出序列X（k是倒 置顺序的。 其整序规则与按时间抽取算法是完全一致的。67673.同址运算 该算法和按时间抽取算法一样也是进行同址运算的。4.蝶距规律 其蝶形系数的分布规律与按时间抽取算法是完全对称的 。6868三、
