快速傅里叶变换课件.ppt

《快速傅里叶变换课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章快速傅里叶变换4.1DFT的运算量分析4.1.1直接计算DFT的运算量实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)4N22N(2N–1)运算量复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)N2N(N–1)从上面的分析看到，在DFT计算中，不论是乘法和加法，运算量均与N2成正比。因此，N较大时，运算量十分可观。例，计算N=10点的DFT，需要100次复数相乘，而N=1024点时，需要1048576（一百多万）次复数乘法，如果要求实时处理，则要求有很高的计算速度才能完成上述计算量。反变换IDFT与D

2、FT的运算结构相同，只是多乘一个常数1/N，所以二者的计算量相同。4.1.2改善DFT运算效率的基本途径时域抽取与频域抽取：4.2.1.算法的的基本原理按n的奇偶把时间序列x(n)分解为两个长为N/2点的序列，即因此4.2时间抽取的基-2FFT算法由于所以即其中分别为的N/2点DFT这是前N/2点DFT对于后N/2的DFT：由于（周期性）因此可用蝶式运算图来表示上述前N/2和后N/2两式，如下图所示例如:N=8时的DFT,可以分解为两个N/2=4点DFT如图4.2.2所示:图4.2.28点DFT分解成两个4点的DFT分解后的运算量：复数乘法复数加法一个N/2点DFT(N/2)2N/2(

3、N/2–1)两个N/2点DFTN2/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计运算量减少了近一半由于,因而N/2仍是偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列从而可表示为因而有其中对也可进行同样的分解：k=0,1,...,N/4-1其中这样又一次的分解得到4个N/4点DFT如下图所示：那么依次类推，经过M-1次分解后，将N点DFT分解成N/2个两点DFT下图为N=8时的一个完整基-2DIT-FFT运算流图当时，总共有M级分解，每级有N/2个蝶式运算。每个蝶式运算需一次复乘两次复加，这样M级总共需要的运算量为复乘次数复加次数4.2.2运算量FF

4、T算法与直接计算DFT所需乘法次数的比较曲线4.2.3.FFT算法的特点1）原位计算（同址运算）m表示第m级迭代，i，j表示数据所在的行数每一级的蝶形运算的输入和输出在运算前后可以存储在同一地址的存储单元中，这种存储策略称为同址计算。显然，同址计算可以节省存储单元，从而降低算法对计算机存储容量的要求，降低了硬件实现的成本。2）输入序列的序号及整序规律DIT―FFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，所以顺序数可用M位二进制数(nM-1nM-2…n1n0)表示。在实际计算中，输入的混序是通过输入正序序列按码位倒置实现的。存储单元、正序

5、和反序之间的关系如下表存储单元自然序列二进制表示自然序列序号序号码位倒置码位倒置后的序列从上表可以看出，表的第一列即是FFT输出序列的顺序，第四列即是FFT输入序列，因此输出序列的顺序与输入序列的顺序成反序关系，这里称为倒位序。下图示出了N=8时按自然顺序存储的数据，调换成FFT原位运算所要求的倒位序存储的变址情况。输入数据的变址处理3）各类蝶形运算两节点的“距离”及的变化规律对N=2M点FFT，输入倒位序，输出自然序，第m级运算每个蝶形的两节点距离为2m–1第m级运算：蝶形运算两节点的第一个节点为i值，表示成M位二进制数，左移M–m位，把右边空出的位置补零，结果为r的二进制数。（1）

6、直接计算法级数的取值范围重复组数第一级第二级第三级第m级第M级1（2）逆推法4.2.4、DIT算法的其他形式流图输入自然序输出倒位序输入输出均自然序相同几何形状输入自然序输出倒位序4.2.5DIT基-2FFT的软件编程思想由DIT基-2FFT算法原理及特点，不难看出，FFT计算程序主要包括变址和M级递推计算两大部分。1.变址（倒序）运算在实际运算中，一般总是按自然顺序将输入序列存入存储单元，故为实现DIT基-2FFT首先必须将输入序列x(n)按二进制倒序数重排。倒序重排一般采用反向进位加法来实现，图4.2.12是反向进位加法实现变址运算的计算流程。2．M级递推计算根据DIT基-2FFT

7、的特点，可以得出图4.2.13的M轮递推计算的流程图。整个M轮递推过程由三个嵌套循环构成。外层循环控制M轮的顺序运算，内层的两个循环控制同一轮的各个蝶形运算，其中最内一层循环控制同类（指有相同的旋转因子）蝶形的运算，而中间一层循环则针对不同类的蝶形运算。I和IP代表的是一个蝶形运算的两个节点。4.3.1算法的基本原理设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：4.3频域抽取基-2FFT算法