计算一个长度为N=2”的两个序列的周期卷积怎么求信号完整的DFT需要多少次实数乘法和多少次实+数加？

来源：蜘蛛抓取(WebSpider) 时间：2023-04-12 00:39 标签： 两个序列的周期卷积怎么求
第四章快速傅里叶变换(FFT)本章学****目标学****目标:掌握基2FFT算法的基本思想和算法推导,。重点:基2FFT算法难点:,它只是DFT的一种快速算法,并且根据对序列分解与选取方法的不同而产生了FFT的多种算法。1965年库利和图基在《计算数学》(putation)杂志上发表了著名的“机器计算傅立叶级数的一种算法”论文,提出一种快速计算DFT的方法和计算机程序。揭开了FFT发展史上的第一页,促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成,电子数字计算机的条件,使DFT的运算大简化了。有限长序列通过离散傅里叶变换(DFT)将其频域离散化为有限长序列。但其计算量太大,很难实时地处理问题,因此引出了快速傅里叶变换(FFT)。FFT在离散傅里叶反变换、线性卷积和线性相关等方面也有重要应用。(n)是一个长度为N的有限长序列DFT与IDFT二者计算量相同问题提出:设有限长序列x(n),非零值长度为N,对x(n)进行一次DFT运算,共需多大的运算工作量?一般来说,x(n)和都是复数。那么,每计算一个X(k),需要的运算量为:由于一共有N个抽样值,所以共需完成的运算量为:N2次复乘和N(N-1)次的复加N次复乘,N-1次的复加以DFT为例,计算DFT复数运算量如k=1时,一次复数乘法换算成实数运算量复数运算要比加法运算复杂,需要的运算时间长。4次实数乘法2次实数加法(a+jb)(c+jd)=(ac-bd)+j(bc+ad)一次复数乘法需用四次实数乘法和二次实数加法;一次复数加法则需二次实数加法。(a+jb)+(c+jd)=(a+c)+j(b+d)2次实数加法一次复数乘法换算成实数运算量复数运算要比加法运算复杂,需要的运算时间长。4次实数乘法2次实数加法(a+jb)(c+jd)=(ac-bd)+j(bc+ad)一次复数乘法需用四次实数乘法和二次实数加法;一次复数加法则需二次实数加法。(a+jb)+(c+jd)=(a+c)+j(b+d)2次实数加法计算DFT需要的实数运算量每运算一个X(k)的值,需要进行4N次实数相乘和2N+2(N-1)=2(2N-1)次实数相加。整个DFT运算量为:4N2次实数相乘和2N(2N-1)次实数相加。由此看出:直接计算DFT时,乘法次数与加法次数都是和N2成比例的。当N很大时,所需工作量非常可观。改善DFT运算效率的基本途径利用DFT运算的系数的固有对称性和周期性(1)例(2)例
快速傅立叶变换(FFT)课件 来自淘豆网www.taodocs.com转载请标明出处.

我要回帖

更多关于 两个序列的周期卷积怎么求 的文章

 

随机推荐