第4章快速傅立叶变换(fft)a.ppt

图4.2.4 N点DIT―FFT运算流图(N=8) 第4章 快速傅立叶变换（FFT） 4.2.3 DIT―FFT算法与直接计算DFT运算量的比较 每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为 复数加次数为 例如，N=210=1024时 第4章 快速傅立叶变换（FFT） 若直接计算DFT则：N=1024,时N2=1048576 图4.2.5 FFT算法与直接计算DFT所需乘法次数的比较曲线 第4章 快速傅立叶变换（FFT） 1.原位计算 由图4.2.4可以看出，DIT―FFT的运算过程很有规律。N=2M点的FFT共进行M级运算，每级由N/2个蝶形运算组成。 　　在N点DIT-FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子　　，称其为旋转因子，p为旋转因子的指数。但各级的旋转因子和循环方式都有所不同。为了编写计算程序，应先找出旋转因子　　与运算级数的关系。用L表示从左到右的运算级数(L=1，2，…，M)。观察图4.2.4不难发现，第L级共有2L－1个不同的旋转因子。N=23=8时的各级旋转因子表示如下： 4.2.4 DIT―FFT的运算规律及编程思想 2．旋转因子的变化规律 图4.2.4 N点DIT―FFT运算流图(N=8) 第4章 快速傅立叶变换（FFT） 对N=2M的一般情况，第L级的旋转因子为 3. 蝶形运算规律 设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式： AL (J) AL-1(J)+A L-1(J+B)WpN AL(J+B) AL-1(J)-A L-1(J+B)WpN 式中 p=J·2 M-L；J=0,1,…，2 L-1-1；L=1,2,…，M 下标L表示第L级运算，AL(J)则表示第L级运算后数组元素A(J)的值。而AL－1(J)表示第L级运算前A(J)的值（即第L级蝶形的输入数据） 4. 编程思想及程序框图 图4.2.6 DIT―FFT运算和程序框图 三层循环的功能是： 最外层（大）循环完成M次迭代过程即L=1,2, ..,M 级，即每次循环为一级。 中间（中）循环完成在一级中共有B个不同因子WNk对应2M-L个蝶形运算，同一个旋转因子对应着相隔2L点的2M-L个蝶形。 最里层（小）循环完成同一个旋转因子不同蝶形的运算；其循环体为一个蝶形运算。 DIT―FFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，所以顺序数可用M位二进制数(nM-1nM-2…n1n0)表示。 图4.2.7 形成倒序的树状图(N=23) 5. 序列的倒序 　　第一次按最低位n0的0和1将x(n)分解为偶奇两组，第二次又按次低位n1的0、1值分别对偶奇组分组；依次类推，第M次按nM－1位分解，最后所得二进制倒序数如图4.2.7所示。表4.2.1列出了N=8时以二进制数表示的顺序数和倒序数，由表显而易见，只要将顺序数(n2n1n0)的二进制位倒置，则得对应的二进制倒序值(n0n1n2)。按这一规律，用硬件电路和汇编语言程序产生倒序数很容易。但用有些高级语言程序实现时，直接倒置二进制数位是不行的，因此必须找出产生倒序数的十进制运算规律。 表4.2.1 顺序和倒序二进制数对照表 　　由表4.2.1可见，自然顺序数，增加1，是在顺序数的二进制数最低位加1，逢2向高位进位。而倒序数则是在M位二进制数最高位加1，逢2向低位进位。例如，在(000)最高位加1，则得（100），而(100)最高位为1，所以最高位加1要向次高位进位，其实质是将最高位变为0，再在次高位加1，得到(010)。用这种算法，可以从当前任一倒序值求得下一个倒序值。 图4.2.8 倒序规律 　　为了叙述方便，用J表示当前倒序数的十进制数值。对于N=2M，M位二进制数最高位的十进制权值为N/2，且从左向右二进制位的权值依次为N/4，N/8，…，2，1。因此，最高为加1相当于十进制运算J+N/2。 如果最高位是0(JN/2)，则直接由J+N/2得下一个倒序值；如最高位是1(J≥N/2), 则先将最高位变成0(J　J－N/2)，然后次高位加1(J+N/4)。但次高位加1时，同样要判断0、1值，如果为0(JN/4)，则直接加1(J J+N/4)， 否则将