快速傅立叶变换

第十二章快速傅立叶变换12.1离散傅立叶变换(DFT)1.连续信号的傅立叶变换:函数x(t)满足傅立叶积分条件,则:傅立叶变换:傅立叶逆变换（积分）:()()itXxtedt1()()2itxtXed2.离散信号的傅立叶变换:如对于连续信号x(t)等间隔采样得:x(n)=x(nT),n=…,-2,-1,0,1,2,…;T为采样周期.离散信号的傅立叶变换(DFT):离散信号的傅立叶反变换:()()innXxne1()()2inxnXed()()()nxtxnxnTX()是以2为周期的的连续函数.称为数字域频率,f0=1/T为采样频率.3.有限信号的离散傅立叶变换(DFT):对于[0,L]时域的有限信号x(t),等间隔采样x(n)=x(nL/N),n=0,1,…,N-1离散傅立叶变换:离散傅立叶反变换:210()(),0,1,2,...,1nNikNnXkxnekN2101()(),0,1,2,...,1nNikNkxnXkenNN记:DFT:IDFT:2/iNwe10()()NnknXkxnw101()()NnkkxnXkwN210()(),0,1,2,...,1kNinNnXkxnekN2101()(),0,1,2,...,1kNinNkxnXkenNNfunctionX=dft(x)ss=size(x);ifss(1,1)2x=x';endN=length(x);W=exp(-i*2*pi/N);fork=1:NX(k)=(W.^((k-1)*[0:N-1]))*x;endt=0:0.1:30;x=sin(5*t);X=dft(x);plot(2*pi*t/30,abs(X))01234567020406080100120140160若x(n)为实数,则:所以:对称性：周期性：10()()NnkNnXkxnW1()0()()NnNkNnXNkxnW10()NnNnkNNnxnWW10()NnkNnxnW)()(kNXkX)()(kNXkX)()(kNXkX快速傅立叶变换(FFT)设N=2r,令r=2,则N=4,由于:0000012302460369(0)(0)(1)(2)(3)(1)(0)(1)(2)(3)(2)(0)(1)(2)(3)(3)(0)(1)(2)(3)XxWxWxWxWXxWxWxWxWXxWxWxWxWXxWxWxWxW2iWe01W/21NW/2NllWWNllWW故上式可化简为:0000012302020321(0)(0)(1)(1)(2)(2)(3)(3)Xx0000010100000101(0)(0)(1)(1)(2)(2)(3)(3)Xx换行:合并:0000000001010101(0)(0)(2)(1)(1)(2)(3)(3)Xx00000101(0)(0)(2)(1)(3)(2)(0)(2)(1)(3)(1)(0)(2)(1)(3)(3)(0)(2)(1)(3)XxxWxxWXxxWxxWXxxWxxWXxxWxxW令:则:1111(0)(0)(2)(1)(1)(3)(2)(0)(2)(3)(1)(3)xxxxxxxxxxxx0011001101110111(0)(0)(1)(2)(0)(1)(1)(2)(3)(3)(2)(3)XxWxWXxWxWXxWxWXxWxW生成的X(n)的排序:(0)(00)(00)(0)(2)(10)(01)(1)(1)(01)(10)(2)(3)(11)(11)(3)XXXXXXXXXXXXXXXX蝶形图:(0)(1)(2)(3)xxxx1111(0)(1)(2)(3)xxxx-1-1(0)(2)(1)(3)XXXX-1-104W14WN=8的蝶形图(0)(1)(2)(3)(4)(5)(6)(7)xxxxxxxx(0)(4)(2)(6)(1)(5)(3)(7)XXXXXXXX08W18W28W38W08W28W08W28Wl=1(x1)l=2(x2)l=3(x3)FFT程序第l层节点的计算方法:其中k的取值为(设N=2m):或:1111()()()2()()()22pllllplllllNxkxkWxkNNxkxkWxk0(1);2lN11(1);222lllNNN1...()(1);22llNNNN0(21);ml112(221);mlmlml对于每一段,k有2l-1个取值.Wp的取值:对于节点（l,n）,Wp中的p值可按照如下方法确定。首先将n用r位二进制形式表示；再将该二进制右移r-l位，左面空位补零；然后将其码序倒置；最后再将其写成十进制数的形式，即为p。例如，对于N=8,r=3,节点(2,3)的p值确定过程为：1...(22)(221);mmlmmlpn4)100()001()011(3