快速傅里叶变换fft－金锄头文库

2、DFT的特点及减少运算量的基本途径长度为N的有限长序列x(n)的DFT为考虑x(n)为复数序列的一般情况，对某一个k值，直接按(4.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。 (4.2.1) 第4章快速傅里叶变换(FFT) 如前所述，N点DFT的复乘次数等于N2。显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。另外，旋转因子WmN具有明显的周期性和对称性。其周期性表现为(4.2.2) 其对称性表现为或者第4章快速傅里叶变换(FFT) 4.2.2 时域抽取法基2FFT基本原理 FFT算法基本上分为两大类：时域抽取法FFT(Decimation In

3、Time FFT,简称DIT-FFT)和频域抽取法FFT(Decimation In Frequency FFT,简称DIFFFT)。下面先介绍DITFFT算法。设序列x(n)的长度为N，且满足为自然数按n的奇偶把x(n)分解为两个N/2点的子序列第4章快速傅里叶变换(FFT) 则x(n)的DFT为由于所以第4章快速傅里叶变换(FFT) 其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即 (4.2.5) (4.2.6) 由于X1(k)和X2(k)均以N/2为周期，且，所以X(k)又可表示为(4.2.7) (4.2.8) 第4章快速傅里叶变换(FFT) 图4.2

4、.1 蝶形运算符号第4章快速傅里叶变换(FFT) 图4.2.2 N点DFT的一次时域抽取分解图(N=8) 第4章快速傅里叶变换(FFT) 与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即那么，X1(k)又可表示为 (4.2.9) 第4章快速傅里叶变换(FFT) 式中同理，由X3(k)和X4(k)的周期性和Wm N/2的对称性 Wk+N/4 N/2=-Wk N/2 最后得到： (4.2.10) 第4章快速傅里叶变换(FFT) 用同样的方法可计算出(4.2.11)其中第4章快速傅里叶变换(FFT) 图4.2.3 N点DFT的第二次时域抽取分解

5、图(N=8) 第4章快速傅里叶变换(FFT) 图4.2.4 N点DITFFT运算流图(N=8) 第4章快速傅里叶变换(FFT) 4.2.3 DITFFT算法与直接计算DFT运算量的比较每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为复数加次数为例如，N=210=1024时第4章快速傅里叶变换(FFT) 图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线第4章快速傅里叶变换(FFT) 4.2.4 DITFFT的运算规律及编程思想1.原位计算由图4.2.4可以看出，DITFFT的运算过程很有规律。N=2M点的FFT

6、共进行M级运算，每级由N/2个蝶形运算组成。2.旋转因子的变化规律如上所述，N点DITFFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子WpN，称其为旋转因子，p称为旋转因子的指数。第4章快速傅里叶变换(FFT) 观察图4.2.4不难发现，第L级共有2 L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下：L=1时，WpN=WJ N/4=WJ2L， J=0L=2时， WpN =WJ N/2=WJ2L， J=0，1L=3时， WpN =WJN=WJ2L， J=0，1，2，3对N=2M的一般情况，第L级的旋转因子为(4.2.12 ) (4.2.13) 第4章快速傅里叶变换(

7、FFT) 3. 蝶形运算规律设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式：X (J) XL-1(J)+X L-1(J+B)WpNXL(J+B) XL-1(J)-X L-1(J+B)WpN式中 p=J2 M-L；J=0,1,，2 L-1-1；L=1,2,，M第4章快速傅里叶变换(FFT) 下标L表示第L级运算，XL(J)则表示第L级运算后数组元素X(J)的值。如果要用实数运算完成上述蝶形运算，可按下面的算法进行。设T=X L-1(J+B)WpN=TR+jTIX L-1(J)=XR(J)+jXI(J) 式中下标R

8、表示取实部，I表示取虚部，第4章快速傅里叶变换(FFT) 则第4章快速傅里叶变换(FFT) 4. 编程思想及程序框图图4.2.6 DITFFT运算和程序框图第4章快速傅里叶变换(FFT) 5. 序列的倒序DITFFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于 N=2M，所以顺序数可用M位二进制数(nM-1nM-2n1n0)表示。图4.2.7 形成倒序的树状图(N=23) 第4章快速傅里叶变换(FFT) 表4.2.1 顺序和倒序二进制数对照表第4章快速傅里叶变换(FFT) 图4.2.8 倒序规律第4章快速傅里叶变换(FFT) 图4.2.

9、9 倒序程序框图第4章快速傅里叶变换(FFT) 4.2.5 频域抽取法FFT(DIFFFT) 在基2快速算法中，频域抽取法FFT也是一种常用的快速算法，简称DIFFFT。设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：第4章快速傅里叶变换(FFT) 偶数奇数将X(k)分解成偶数组与奇数组，当k取偶数(k=2r,r=0,1,N/2-1)时 (4.2.14)第4章快速傅里叶变换(FFT) 当k取奇数(k=2r+1,r=0,1,N/2-1)时(4.2.15)将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式，可得(4.

10、2.16) 第4章快速傅里叶变换(FFT) 图4.2.10 DIFFFT蝶形运算流图符号第4章快速傅里叶变换(FFT) 图4.2.11 DIFFFT一次分解运算流图(N=8) 第4章快速傅里叶变换(FFT) 图4.2.12 DIFFFT二次分解运算流图(N=8) 第4章快速傅里叶变换(FFT) 图4.2.13 DIFFFT运算流图(N=8) 第4章快速傅里叶变换(FFT) 图4.2.14 DITFFT的一种变形运算流图第4章快速傅里叶变换(FFT) 图4.2.15 DITFFT的一种变形运算流图第4章快速傅里叶变换(FFT) 4.2.6 IDFT的高效算法上述FFT算法流图也

11、可以用于离散傅里叶逆变换(Inverse Discrete Fourier Transform，简称IDFT)。比较DFT和IDFT的运算公式：第4章快速傅里叶变换(FFT) 图4.2.16 DITIFFT运算流图第4章快速傅里叶变换(FFT) 图4.2.17 DITIFFT运算流图(防止溢出) 第4章快速傅里叶变换(FFT) 如果希望直接调用FFT子程序计算IFFT，则可用下面的方法：由于对上式两边同时取共轭，得第4章快速傅里叶变换(FFT) 4.3 进一步减少运算量的措施4.3.1 多类蝶形单元运算由DITFFT运算流图已得出结论，N=2M点FFT共需要MN/2次复数乘法。由

12、(4.2.12)式，当L=1时，只有一种旋转因子W0N=1，所以，第一级不需要乘法运算。第4章快速傅里叶变换(FFT) 综上所述，先除去第一、二两级后，所需复数乘法次数应是从L=3至L=M共减少复数乘法次数为(4.3.1) (4.3.2) 因此， DITFFT的复乘次数降至 (4.3.3 ) 第4章快速傅里叶变换(FFT) 第4章快速傅里叶变换(FFT) 从实数运算考虑，计算N=2M点DITFFT所需实数乘法次数为(4.3.4)第4章快速傅里叶变换(FFT) 4.3.2 旋转因子的生成在FFT运算中，旋转因子WmN=cos(2m/N)-jsin(2m/N)，求正弦和余弦函数值的计算量

13、是很大的。第4章快速傅里叶变换(FFT) 4.3.3 实序列的FFT算法设x(n)为N点实序列，取x(n)的偶数点和奇数点分别作为新构造序列y(n)的实部和虚部，即对y(n)进行N/2点FFT，输出Y(k)，则根据DITFFT的思想及式(4.2.7)和(4.2.8)，可得到第4章快速傅里叶变换(FFT) 由于x(n)为实序列，所以X(k)具有共轭对称性，X(k)的另外N/2点的值为第4章快速傅里叶变换(FFT) 4.4 分裂基FFT算法 4.4.1 分裂基FFT算法原理当n=pq，且p=N/4，q=4时，n可表示为并有第4章快速傅里叶变换(FFT) 再将上式中的k表示为第4

14、章快速傅里叶变换(FFT) 可得对k0=0，1,2,3,并用k表示k1，用n表示n0，可以写出第4章快速傅里叶变换(FFT) (4.4.1) 第4章快速傅里叶变换(FFT) (4.4.2) 第4章快速傅里叶变换(FFT) (4.4.3) 令第4章快速傅里叶变换(FFT) 则(4.4.2)式可写成如下更简明的形式：(4.4.4) 第4章快速傅里叶变换(FFT) 图4.4.1 分裂基第一次分解L形流图第4章快速傅里叶变换(FFT) 例如，N=16，第一次抽选分解时，由式(4.4.3)得x2(n)=x(n)+x(n+8), 0n7x14(n)=x(n)-x(n+8)-jx(n+4

15、)-x(n+12)Wn16, 0n3x24(n)=x(n)-x(n+8)+jx(n+4)-x(n+12)W3n16, 0n3把上式代入式(4.4.4)，可得X(2k)=DFTx2(n), 0k7 X(4k+1)=DFTx14(n), 0k3 X(4k+3)=DFTx24(n), 0k3 第4章快速傅里叶变换(FFT) 图4.4.2 分裂基FFT算法L形排列示意图与结构示意图(a)分裂基FFT算法L形排列示意图；(b)分裂基FFT算法运算流图结构示意图第4章快速傅里叶变换(FFT) 图4.4.3 16点分裂基第一次分解L形流图(图中省去箭头) 第4章快速傅里叶变换(FFT) 第二次分解：先对图4.4.3中N/2点DFT进行分解。令X1(l)=X(2l)，则有X1(2l)=DFTy2(n), 0l3 X1(4l+1)=DFTy14(n), 0l1 X1(4l+3)=DFT

展开阅读全文