离散傅里叶变换和快速傅里叶变

《离散傅里叶变换和快速傅里叶变》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散傅里叶变换和快速傅里叶变换XinLi(李新)Email:lixustc@ustc.edu.cnPhone:0551-63607202为什么用离散傅里叶变换实际的信号是离散的分析有限长序列的有用工具；在信号处理的理论上有重要意义；在运算方法上起核心作用•谱分析、卷积等为什么研究连续傅里叶变换连续傅里叶变换------离散傅里叶变换•采样•可以有理论保证离散傅里叶变换------连续傅里叶变换•预测•没有保证DFT离散与量化，快速运算。傅氏变换离散量化信号处理DFT(FFT)离散时间信号对模拟信号

2、f(t)进行等间隔采样，采样间隔为T；x=f(jT),−∞

3、f(j)=x(j)*y(j)序列的移位：y(j)=x(j-j0)∞2序列的能量：S=∑x(j)j=−∞∞2能量有限：∑x(j)<∞j=−∞序列的单位脉冲序列表示：∞x(j)=∑x(k)δ(j−k)k=−∞周期系列的DFT∞周期为n的系列：y={yj}−∞,yj=yj+nDFT：__F(y)=y={y}nj_n−12πijky=∑yω,ω=enjkk=0IDFT:1n−1jkyj=∑ykω,nk=0快速傅里叶变换（FFT）虽然频谱分析和DFT运算很重要，但在很长一段时间里，由于DFT运算复杂，并没有得到

4、真正的运用，而频谱分析仍大多采用模拟信号滤波的方法解决，直到1965年首次提出DFT运算的一种快速算法以后，情况才发生了根本变化，人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法——快速付里变换(FFT)算法。FFT的出现，使DFT的运算大大简化，运算时间缩短一～二个数量级，使DFT的运算在实际中得到广泛应用。直接计算量24n实数相乘和n(4n-2)次实数相加;计算n=10点的DFT，需要100次复数相乘，而n=1024点时，需要1048576（一百多万）次复数乘法反变换I

5、DFT与DFT的运算结构相同，只是多乘一个常数1/n，所以二者的计算量相同。基本思想2π−ijkjkn系数ω=e是一个周期函数n长度为n点的大点数的DFT运算依次分解为若干个小点数的DFT。因为DFT的计算量正比于n2，n小，计算量也就小。n=2m，m：正整数首先将序列x(j)分解为两组，一组为偶数项，一组为奇数项，x(2r)=x1(r)r=0,1，…，n/2-1x(2r+1)=x(r)2n−1n/2−1n/2−1jk2rk(2r+1)kX(k)=Fn(x)=∑x(j)ωn=∑x(2r)ωn+∑x(2r+

6、1)ωnj=0r=0r=0n/2−1n/2−12rkk2rk=∑x(2r)ωn+ωn∑x(2r+1)ωnr=0r=02π2π−ij2j−i2jnjω=n=2=ωneen/2n/2−1n/2−1rkkrkX(k)=∑x(2r)ωn+ωn∑x(2r+1)ωnr=02r=02k=G(k)+ωnH(k)n/2−1rkG(k)=∑x(2r)ωnr=02n/2−1rkH(k)=∑x(2r+1)ωnr=02r(n/2+k)rknω=ωn(k+)kn222ωn=−ωnnknX(k+)=G(k)−ωnH(k),k=0,1,−122

7、可见，一个n点的DFT被分解为两个n/2点的DFT，这两个n/2点的DFT再合成为一个n点DFT.knX(k)=G(k)+ωnH(k),k=0,1,,−12nknX(k+)=G(k)−ωnH(k),k=0,1,−122依此类推，G(k)和H(k)可以继续分下去，这种算法是在输入序列分成越来越小的子序列上执行DFT运算，最后再合成为n点的DFT。蝶形信号流图将G(k)和H(k)合成X(k)运算可归结为：a−bWa+bWaa+bWWaa+bWWba-bWa-bWb-1-W(a)(b)蝶形运算的简化图(a)为实

8、现这一运算的一般方法，它需要两次乘法、两次加减法。考虑到-bW和bW两个乘法仅相差一负号，可将图(a)简化成图2.7(b)，此时仅需一次乘法、两次加减法。图(b)的运算结构像一蝴蝶通常称作蝶形运算结构简称蝶形结，采用这种表示法，就可以将以上所讨论的分解过程用流图表示。n=23=8的例子。x(0)G(0)X(0)x(2)n/2点G(1)X(1)x(4)DFTG