信号分析与处理 ：第六章_快速傅里叶变换

1、信号分析与处理信号分析与处理第六章第六章 快速傅里叶变换快速傅里叶变换 电气工程学院电力工程系电气工程学院电力工程系第六章第六章 快速傅里叶变换快速傅里叶变换 6.1 提高提高DFT运算速度的主要方法运算速度的主要方法 6.2 时间抽取算法（时间抽取算法（N=2M） 10.2 FFT时间抽取算法的程序时间抽取算法的程序 6.3 FFT 的频率抽取算法的频率抽取算法 （N=2M） 6.4 快速傅里叶反变换快速傅里叶反变换IFFT 6.5 快速卷积快速卷积 6.6 FFT的应用的应用 次复数乘法和次复数乘法和 次复数加法运算次复数加法运算6.1 提高提高DFT运算速度的主要方法运算速度的主要方法)

2、3()2() 1 ()0(94643404644424043424140404040404xxxxWWWWWWWWWWWWWWWW)3()2() 1 ()0(XXXX 14142449404242444640444244141424340424224,WWWWWWWWWWeWWWWWWeWjj 2N) 1(NN6.1 提高提高DFT运算速度的主要方法运算速度的主要方法的性质nkNW)(rNknNnkNWW周期性周期性 对称性对称性 可以将可以将N点点DFT变为变为N/2点点DFT，直至变为，直至变为2点点DFT 10)()(NnnkNWnxkXnkNNnkNWW)2(2/2NNWW12NNW提

3、高计算速度提高计算速度的基本原理的基本原理 时间抽取算法时间抽取算法 频率抽取算法频率抽取算法 6.2 时间抽取算法（时间抽取算法（N=2M） 1-N, 1 , 0n )(nx)(1rx奇偶分解奇偶分解 12,.,1 , 0 )2(Nrrx12,.,1 , 0 ) 12(Nrrx偶数序列偶数序列 奇数序列奇数序列 )(2rx10)()(NnnkNWnxkXkrNNrNrrkNWrxWrx) 12(12/012/02) 12()2(rkNW2/kNrkNWW2/)(1rx)(2rx时域奇偶分解时域奇偶分解 6.2 时间抽取算法（时间抽取算法（N=2M） 时域奇偶分解时域奇偶分解 rkNNrNrk

4、NrkNWrxWWrxkX2/12/012/022/1)()()() () () (21kXWkXkXkNk=0,1,2,N/2-1 长度为长度为N/2) () (21kXWkXkN2Nkk令 kk 令k=0,1,2,N/2-1 )2(2/12/012/022)2(2/1)()()2(NkrNNrNrNkNNkrNWrxWWrxNkX对应的频域顺序排列对应的频域顺序排列（前后分解）（前后分解） 6.2 时间抽取算法（时间抽取算法（N=2M） N=42 ) () ( ) () ()(2121NkkkXWkXkkkXWkXkXkNkNk=0,1,2,N/2-1 )0()0()0(2041XWXX)

5、1 ()1 ()1 (2141XWXX)0()0()2(2041XWXX)1 ()1 ()3(2141XWXX)2()0() 1 ()2()0()0( 1 , 0 ,)2()(0210211021xWxXxWxXkWrxkXrrk) 3() 1 () 1 () 3() 1 ()0(1, 0,) 12()(0220221022xWxXxWxXkWrxkXrrk 0212WW2点点DFT蝶形图蝶形图 表示放大表示放大C倍倍 表示相加表示相加 DFT代价：代价： 乘法乘法 16次次加法加法 12次次 FFT代价：代价： 乘法乘法 4次次加法加法 8次次 6.2 时间抽取算法（时间抽取算法（N=2M）

6、 计算代价：计算代价： 乘法乘法 1次次 加加法法 2次次 例例6-1（例（例5-4 ）：用时间抽取算法）：用时间抽取算法计算计算x(n)的的DFT 4121)(nxjjkX226226)(6.2 时间抽取算法（时间抽取算法（N=2M） 原序列原序列823N奇偶分解奇偶分解再奇偶分解再奇偶分解输入序列输入序列6.2 时间抽取算法（时间抽取算法（N=2M） 823N级级 FFT代价：代价： 乘法乘法 12次加法次加法 24次次 DFT代价：代价： 乘法乘法 64次加法次加法 56次次 蝶蝶 群群 6.2 时间抽取算法（时间抽取算法（N=2M） 4点点DFT4点点DFT1624NFFT代价：代价：

7、 乘法乘法 32次加法次加法 64次次 DFT代价：代价： 乘法乘法 256次加法次加法 240次次 6.2 时间抽取算法（时间抽取算法（N=2M） 2点点DFT4点点DFT8点点DFTFFT 加法运算次数加法运算次数 NNMN2log22NNNM2logFFT 乘法运算次数乘法运算次数 DFT 加法运算次数加法运算次数 2N) 1(NNDFT 乘法运算次数乘法运算次数 6.2 时间抽取算法（时间抽取算法（N=2M） 计算机对计算机对N=2048时的离时的离散傅里叶变换进行直接散傅里叶变换进行直接计算需要计算需要3个小时，而用个小时，而用FFT时间抽取算法只要时间抽取算法只要不到不到1分钟就可

8、以完成。分钟就可以完成。 6.2 时间抽取算法（时间抽取算法（N=2M） MNDFT FFT改善比值改善比值 1 1 2 2 4 4 1 1 4.0 4.0 2 2 4 4 16 16 4 4 4.0 4.0 3 3 8 8 64 64 12 12 5.3 5.3 4 4 16 16 256 256 32 32 8.0 8.0 5 5 32 32 1024 1024 80 80 12.8 12.8 6 6 64 64 4096 4096 192 192 21.3 21.3 7 7 128 128 16384 16384 448 448 36.6 36.6 8 8 256 256 65536 6

9、5536 1024 1024 64.0 64.0 9 9 512 512 262144 262144 2304 2304 113.8 113.8 10 10 1024 1024 1048576 1048576 5120 5120 204.8 204.8 11 11 2048 2048 4194304 4194304 11264 11264 372.4 372.4 2NNN2log2NN2log2码位倒置码位倒置 自然顺序自然顺序二进制表示二进制表示码位倒置码位倒置码位倒置顺序码位倒置顺序0 00000000000000 01 10010011001004 42 20100100100102 2

10、3 30110111101106 64 41001000010011 15 51011011011015 56 61101100110113 37 71111111111117 7即位运算即位运算 6.2 时间抽取算法（时间抽取算法（N=2M） N=2M 个数据有个数据有M级级蝶形运算蝶形运算 蝶形图的特点蝶形图的特点 即位运算即位运算 输出序列按自然排列，输出序列按自然排列，输入序列按二进制码输入序列按二进制码位倒置顺序排列位倒置顺序排列 N=4 N=8 每级中有每级中有N/2个个蝶运算蝶运算 第第L级中有级中有N/2L个群，个群， 群与群的间隔群与群的间隔2L 同一级中的每一个群的同一级中

11、的每一个群的WN分布相同，每一级分布相同，每一级中共有中共有2L-1个个WN 每一个群的每一个群的WN分布从分布从上而下为上而下为1) 1(22,.,3 , 2 , 1,LPNPWLN先级再群再蝶，共先级再群再蝶，共三重循环运算三重循环运算 6.2 时间抽取算法（时间抽取算法（N=2M） 10.2 FFT时间抽取算法的程序时间抽取算法的程序 Radar算法算法码位倒置的算法，将自然码位倒置的算法，将自然顺序转化为倒位序。顺序转化为倒位序。码位倒置的码位倒置的二进制码可二进制码可以通过高位以通过高位加加1，向下一，向下一位进位，产位进位，产生下一个新生下一个新的码。的码。 10.2 FFT时间抽

12、取时间抽取算法的程序算法的程序 码位倒置算码位倒置算法流程图法流程图A(I)高位是否为高位是否为1高位清零高位清零高位是否为高位是否为1高位置高位置110.2 FFT时间抽取时间抽取算法的程序算法的程序 蝶形运算蝶形运算程序算法程序算法流程图流程图级循环级循环嵌套嵌套群间隔群间隔群内蝶群内蝶间隔间隔即位运算即位运算4214jeW18W10.2 FFT时间抽取算法的程序时间抽取算法的程序 #include “math.h”#define swap(a,b) T=(a);(a)=(b);(b)=Tvoid fft(float A,float B,unsigned M) unsigned long

13、N,I,J,K,LE,LE1,P,Q,R; float Wr,Wi,W1r,W1i,WTr,WTi,theta,Tr,Ti; N=1M; J=0; for (I=0;II) swap(AI,AJ); swap(BI,BJ);K=N1;while (K =2&J=K) J-= K; K =1;J+= K; for(L=1;L=M;L+) LE=1L;LE1=LE/2; Wr=1.0; Wi=0.0;theta=(-1)*3.1415926536/LE1;W1r=cos(theta);W1i=sin(theta);for(R=0;RLE1;R+)for(P=R;P=N1+N2-1得到新序列得到新序

14、列计算新序列的计算新序列的FFTIFFT将上述结果相乘将上述结果相乘取前取前N1+N2-1位位 nxFFTkX nhFFTkH kHkXkY kYIFFTnhnxny6.5 快速卷积快速卷积 线性卷积快速算法的计算线性卷积快速算法的计算量量1.2.2次次FFT计算和计算和1次次IFFT 、一次、一次 点复数乘法点复数乘法12N补零后长度均为补零后长度均为1N nx nh12121NNN直接计算线性卷积需要进行直接计算线性卷积需要进行次实数乘法运算次实数乘法运算 21N离散时间系统的离散时间系统的 已知或已经事先求出，已知或已经事先求出，并已置于存储器中。实际中只需要并已置于存储器中。实际中只需

15、要2次次 点点FFT的运算量的运算量 kH12N1211211121log22)2(log1 22)2(log222NNNNNNN需要的全部复数乘法运算次数为需要的全部复数乘法运算次数为 )(kHkXIFFTkYIFFTnhnxny6.5 快速卷积快速卷积 重叠相加法重叠相加法 1)()(piinxnx)(*)()(nhnxnyiiMNM+N-1)()()()()()(1010nynhnxnhnxnypiipii6.5 快速卷积快速卷积 借助于借助于FFT算法的算法的重叠相加法重叠相加法需要以下步骤：需要以下步骤：（1）计算）计算 ；（2）计算）计算 ；（3）计算）计算 ；（4）计算）计算 ；

16、（5）将各子序列）将各子序列 重叠相加。重叠相加。6.5 快速卷积快速卷积 )()(nhFFTkH)()(nxFFTkXii)()()(kHkXkYii)()(kYIFFTnyii)(nyi在实际中也可以边计算在实际中也可以边计算 边进行重叠相加。这样，可以边进行重叠相加。这样，可以保证信号处理具有最小的延时。重叠相加法已被广泛地应保证信号处理具有最小的延时。重叠相加法已被广泛地应用于处理无限长信号的实时处理，例如，语音信号等。用于处理无限长信号的实时处理，例如，语音信号等。)(nyi6.6 FFT的应用的应用 测量线性测量线性系统的系系统的系统函数统函数 )()()(10zkHzHNk111

17、1)(zWzNzkNN线性系统线性系统的零状态的零状态响应响应 电力系统电力系统谐波分析谐波分析 00)()()0(1XXXNpA/D变换时，变换时，应该在整个应该在整个周期周期T0内采内采样样 002)() 1 (2TXXN002)()(2TkkXkXNkN/26.6 FFT的应用的应用 电气工程，采用正弦系统电气工程，采用正弦系统 例例1-3：求周期矩形脉冲信号的指数谱，并画出它的幅：求周期矩形脉冲信号的指数谱，并画出它的幅频特性和相频特性图形频特性和相频特性图形 )2(21220000kSAdtAeTFatjkk在指数谱在指数谱中，直流中，直流分量满足分量满足幅值包络幅值包络线函数线函数

18、1.2 周期信号的频谱：周期信号的频谱：二、指数频谱二、指数频谱滤波滤波 电力系统电力系统暂态分析暂态分析中的应用中的应用 在电力系统测在电力系统测量中的应用量中的应用 6.6 FFT的应用的应用 由采样定理和由采样定理和FFT的基的基2原则，确定采样数原则，确定采样数 采样时间间采样时间间隔隔T=0.25s f=4Hz例例: 试用试用FFT求其频谱求其频谱 ttf2sin5 . 01)(22N3n 5 . 02n 11n 5 . 10n 1)(nf周期周期T0=1s, 频率频率f0=1Hz6.6 FFT的应用的应用 3k 2k 01k j0k 4)(jkF电子工程，采用指数系统电子工程，采用指数系统 电气工程，采用正弦系统电气工程，采用正弦系统 离散信号频谱离散信号频谱)(1kFNFk0k )(2kFNFk6.6 FFT的应用的应用 DFT与与FFT的计算量的计算量FFT的时间抽取蝶形图的特点和画法的时间抽取蝶形图的特点和画法倒