傅里叶快速变换

《傅里叶快速变换》由会员分享，可在线阅读，更多相关《傅里叶快速变换（37页珍藏版）》请在金锄头文库上搜索。

1、第4章 快速傅里叶变换(FFT) 4.2 4.2 基基2FFT2FFT算法算法4.2.1 4.2.1 减少运算量的基本途径减少运算量的基本途径 1 1 旋转因子的周期性旋转因子的周期性2 2 旋转因子的对称性旋转因子的对称性（1 1 ） （2 2 ）3 3 旋转因子的约分性旋转因子的约分性第4章 快速傅里叶变换(FFT) FFTFFT的基本思想：把长序列的的基本思想：把长序列的DFTDFT分解为分解为n n个短序列的个短序列的 DFTDFT，根据旋转因子的特性，减少运算次数，主要减，根据旋转因子的特性，减少运算次数，主要减 少乘法的次数。少乘法的次数。2-FFT2-FFT分为两类分为两类时域抽

2、取法时域抽取法FFTFFT：DIT-FFTDIT-FFT频域抽取法频域抽取法FFTFFT：DIF-FFTDIF-FFT4.2.2 4.2.2 时域抽取法基时域抽取法基2FFT2FFT基本原理基本原理设序列设序列x(n)x(n)的长度为的长度为N N，且满足，且满足算法的思想：算法的思想：在时域进行在时域进行MM级奇偶抽取，利用旋转因子级奇偶抽取，利用旋转因子的对称性，将的对称性，将N N点点DFTDFT变成变成MM级蝶形运算级蝶形运算为自然数为自然数 第4章 快速傅里叶变换(FFT) 按按n n的奇偶把的奇偶把x(n)x(n)分解为两个分解为两个N/2N/2点的子序列点的子序列则则x(n)x(

3、n)的的DFTDFT为为第4章 快速傅里叶变换(FFT) 由于由于所以所以 X X1 1(k)(k)和和X X2 2(k)(k)分别为分别为x x1 1(r)(r)和和x x2 2(r)(r)的的N/2N/2点点DFTDFT而且而且X X1 1(k)(k)和和X X2 2(k) (k) 周期周期 为为N/2N/2第4章 快速傅里叶变换(FFT) 根据对称性根据对称性同理同理可得可得所以所以将将N N点点DFTDFT 分解为两个分解为两个 N/2N/2点的点的 DFTDFT第4章 快速傅里叶变换(FFT) A=XA=X1 1(k(k) )B=XB=X2 2(k(k) )C=WC=WN Nk k图

4、4.2.1 蝶形运算符号 一次复数乘，一次复数乘， 两次复数加两次复数加第4章 快速傅里叶变换(FFT) 经过一次分解，计算一个经过一次分解，计算一个N N点点DFTDFT变成计算两个变成计算两个 N/2N/2点点DFTDFT和和N/2N/2个蝶形运算。个蝶形运算。两个两个N/2N/2点点DFTDFT复数乘法次数复数乘法次数 ： 复数加法次数：复数加法次数：N/2N/2个蝶形运算所用的复数乘法个蝶形运算所用的复数乘法 ：复数加法次数：复数加法次数： N总共的复数加法：总共的复数加法：所以计算所以计算N N点点DFTDFT总的复数乘法：总的复数乘法：经过一次分解后运算经过一次分解后运算 量减少了

5、将近一倍量减少了将近一倍第4章 快速傅里叶变换(FFT) 与第一次分解相同，将与第一次分解相同，将x x1 1(r)(r)按奇偶分解成两个按奇偶分解成两个N/4N/4长的子序列长的子序列x x3 3( (l l) )和和x x4 4( (l l) )，即，即那么，那么，X X1 1(k)(k)又可表示为又可表示为 N=2N=2MM，N/2N/2仍然是偶数，可以对两个仍然是偶数，可以对两个N/2N/2点点DFTDFT进行分解进行分解第4章 快速傅里叶变换(FFT) 同理，由同理，由X X3 3(k)(k)和和X X4 4(k)(k)的周期性和的周期性和 WWN/2N/2k k的对称的对称性性 W

6、Wk+N/4k+N/4N/2N/2=-W=-Wk k N/2N/2 最后得到：最后得到： 式中式中 用同样的方法可计算出用同样的方法可计算出第4章 快速傅里叶变换(FFT) 其中其中 第4章 快速傅里叶变换(FFT) 图图4.2.4 N4.2.4 N点点DITFFTDITFFT运算流图运算流图(N=8) (N=8) 依次类推，经过依次类推，经过MM次分解，最后将次分解，最后将N N点点DFTDFT分解为分解为N/2N/2 个个2 2点的点的DFTDFT第4章 快速傅里叶变换(FFT) 4.2.3 2DITFFT4.2.3 2DITFFT算法与直接计算算法与直接计算DFTDFT运算量的比较运算量

7、的比较N=2N=2MM，流图中共有，流图中共有MM级蝶形，每一级有级蝶形，每一级有N/2N/2个蝶形，个蝶形，每个蝶形需要一次复数乘法和两次复数加法，所以每一每个蝶形需要一次复数乘法和两次复数加法，所以每一 级运算都需要级运算都需要N/2N/2次复数乘和次复数乘和N N次复数加法。次复数加法。所以，所以，MM级运算总共需要的复数乘次数为级运算总共需要的复数乘次数为复数加次数为复数加次数为 直接进行直接进行DFTDFT的复数乘法：的复数乘法：N N2 2复数加法：复数加法：N(N-1)N(N-1)第4章 快速傅里叶变换(FFT) 图图4.2.5 FFT4.2.5 FFT算法与直接计算算法与直接计

8、算DFTDFT所需乘法次数的比较所需乘法次数的比较第4章 快速傅里叶变换(FFT) 例如，例如，N=2N=21010=1024=1024时时运算效率提高运算效率提高200200多倍多倍372.42048204.81024113.851264.025636.912821.46412.8328.0165.484.044.02FFT算法与直接算法的运 算量比较第4章 快速傅里叶变换(FFT) 对于对于N=2N=2MM，FFTFFT分级的级数：分级的级数：M=logM=log2 2N N每级蝶形算子个数：每级蝶形算子个数：N/2N/2总的复数乘法：总的复数乘法：总的复数加法：总的复数加法：NlogNl

9、og2 2N N总结：总结：第4章 快速傅里叶变换(FFT) 4.2.4 DITFFT4.2.4 DITFFT的运算规律的运算规律1. 1.原位计算原位计算利用同一存储单元存储蝶形计算输入和输出的数据利用同一存储单元存储蝶形计算输入和输出的数据2. 2.旋转因子的变化规律旋转因子的变化规律每级都有每级都有N/2N/2个蝶形，每个蝶形都要乘以旋转因子个蝶形，每个蝶形都要乘以旋转因子WWp pN N，p p称为旋转因子的指数。称为旋转因子的指数。 第1级第2级第3级N=8=2N=8=23 3第4章 快速傅里叶变换(FFT) 第1级第2级第3级N=2N=23 3=8=8时的各级旋转因子表示如下：时的

10、各级旋转因子表示如下：L=1L=1时，时， ， J=0J=0L=2 L=2时，时， ， J=0J=0，1 1L=3 L=3时，时， ， J=0J=0，1 1，2 2，3 3对对N=2N=2MM的一般情况，第的一般情况，第L L级的旋转因子为级的旋转因子为第第L L级共有级共有2 2L-1L-1个不同的旋转因子个不同的旋转因子第4章 快速傅里叶变换(FFT) 4. 4. 序列的倒序序列的倒序对于对于N=2N=2MM，x(n)x(n)的序号可用的序号可用MM位二进制数表示。位二进制数表示。 DITFFTDITFFT算法的输入序列不是顺序输入的，是有规律算法的输入序列不是顺序输入的，是有规律的倒序。

11、的倒序。顺序顺序0000000010010100100110111001001011011101101111110 01 12 23 34 45 56 67 70000001001000100101101100010011011010110111111110 04 42 26 61 15 53 37 7高低位互换高低位互换第4章 快速傅里叶变换(FFT) 表4.2.1 顺序和倒序二进制数对照表 第4章 快速傅里叶变换(FFT) 图4.2.8 倒序规律 第4章 快速傅里叶变换(FFT) 图4.2.9 倒序程序框图 第4章 快速傅里叶变换(FFT) 4. 编程思想及程序框图图4.2.6 DITFF

12、T运算和程序框图 第4章 快速傅里叶变换(FFT) 4.2.5 4.2.5 频域抽取法频域抽取法FFT(DIFFFT) FFT(DIFFFT) 设序列设序列x(n)x(n)长度为长度为N=2N=2MM，首先将，首先将x(n)x(n)前后对半分前后对半分开，得到两个子序列，其开，得到两个子序列，其DFTDFT可表示为如下形式可表示为如下形式：偶数偶数 奇数奇数 第4章 快速傅里叶变换(FFT) 按按k k的奇偶性，的奇偶性， 将将X(k)X(k)分解成偶数组与奇数组分解成偶数组与奇数组当当k k取偶数取偶数(k=2r,r=0,1,N/2-1)(k=2r,r=0,1,N/2-1)时时 当k取奇数(

13、k=2r+1,r=0,1,N/2-1)时x x1 1(n)(n)x x2 2(n)(n)第4章 快速傅里叶变换(FFT) N N点点X(k)X(k)分解为两个分解为两个N/2N/2 点的点的DFTDFTA=x(n)A=x(n)B=x(n+N/2)B=x(n+N/2)C=WC=WN Nn n一次乘法， 两次加法第4章 快速傅里叶变换(FFT) 图图4.2.10 DIFFFT4.2.10 DIFFFT蝶形运算流图符号蝶形运算流图符号 第4章 快速傅里叶变换(FFT) 图图4.2.11 DIFFFT4.2.11 DIFFFT一次分解运算流图一次分解运算流图(N=8)(N=8) 一次抽取后， DIT-

14、FFT和DIF- FFT不同第4章 快速傅里叶变换(FFT) 图图4.2.12 DIFFFT4.2.12 DIFFFT二次分解运算流图二次分解运算流图(N=8) (N=8) 第4章 快速傅里叶变换(FFT) 图图4.2.13 DIFFFT4.2.13 DIFFFT运算流图运算流图(N=8) (N=8) 注：注：DIF-FFTDIF-FFT的输出需要经过倒序才能得到顺序的的输出需要经过倒序才能得到顺序的 输出，倒序的方法同前。输出，倒序的方法同前。第4章 快速傅里叶变换(FFT) 和和DIT-FFTDIT-FFT类似，对于类似，对于N=2N=2MM，共有，共有MM级蝶形运级蝶形运 算，每级共有算

15、，每级共有N/2N/2个蝶形，所以二者运算量是一样的个蝶形，所以二者运算量是一样的 。DIT-FFTDIT-FFT和和DIF-FFTDIF-FFT的不同点的不同点DIT-FFTDIT-FFT倒序倒序DIF-FFTDIF-FFT顺序顺序先相乘后加减先相乘后加减倒序倒序顺序顺序先加减后相乘先加减后相乘输入输入输出输出蝶形单元蝶形单元第4章 快速傅里叶变换(FFT) DIT-FFTDIT-FFT和和DIF-FFTDIF-FFT流图互为转置流图互为转置DIT-FFTDIT-FFT流图流图DIF-FFTDIF-FFT流图流图第4章 快速傅里叶变换(FFT) 图图4.2.14 DITFFT4.2.14 DITFFT的一种变形运算流图的一种变形运算流图输入顺序、输出倒序的输入顺序、输出倒序的DIT-FFTDIT-FFT第4章 快速傅里叶变换(FFT) 图图4.2.15