[工学]第4章 丁玉美.pptVIP

图4.2.6 DIT-FFT运算和程序框图 　　另外，DIT-FFT算法运算流图的输出X(k)为自然顺序，但为了适应原位计算，其输入序列不是按x(n)的自然顺序排列，这种经过M次偶奇抽选后的排序称为序列x(n)的倒序(倒位)。因此，在运算M级蝶形之前应先对序列x(n)进行倒序。下面介绍倒序算法。 　　5． 序列的倒序 　　DIT-FFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，因此顺序数可用M位二进制数(nM－1nM－2…n1n0)表示。M次偶奇时域抽选过程如图4.2.7所示。 　　5． 序列的倒序 　　DIT-FFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，因此顺序数可用M位二进制数(nM－1 nM－2…n1n0)表示。M次偶奇时域抽选过程如图4.2.7所示。 　　第一次按最低位n0的0和1将x(n)分解为偶奇两组，第二次又按次低位n1的0、1值分别对偶奇组分组；依次类推，第M次按nM－1位分解，最后所得二进制倒序数如图4.2.7所示。表4.2.1列出了N=8时以二进制数表示的顺序数和倒序数，由表显而易见，只要将顺序数(n2n1n0)的二进制位倒置，则得对应的二进制倒序值(n0n1n2)。按这一规律，用硬件电路和汇编语言程序产生倒序数很容易。但用有些高级语言程序实现时，直接倒置二进制数位是不行的，因此必须找出产生倒序数的十进制运算规律。 　　由表4.2.1可见，自然顺序数I增加1，是在顺序数的二进制数最低位加1，逢2向高位进位。而倒序数则是在M位二进制数最高位加1，逢2向低位进位。例如，在(000)最高位加1，则得（100），而(100)最高位为1，所以最高位加1要向次高位进位，其实质是将最高位变为0，再在次高位加1，得到(010)。用这种算法，可以从当前任一倒序值求得下一个倒序值。 图4.2.7 形成例序的树状图（N=23） 表4.2.1 顺序和倒序二进制数对照表 　　为了叙述方便，用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)， 否则将次高位变成0(JJ－N/4)，再判断下一位；依此类推，直到完成最高位加1，逢2向右进位的运算。图4.2.9所示的倒序的程序框图中的虚线框内就是完成计算倒序值的运算流程图。 　　形成倒序J后，将原数组A中存放的输入序列重新按倒序排列。设原输入序列x(I)先按自然顺序存入数组A中。例如，对N=8，A(0)，A(1)，…，A(7)中依次存放着x(0)，x(1)，x(2)，…，x(7)。对x(n)的重新排序(倒序)规律如图4.2.8所示。倒序的程序框图如图4.2.9所示。由图4.2.8可见，第一个序列值x(0)和最后一个序列值x(N－1)不需要重排， 每计算出一个倒序值J，便与循环语句自动生成的顺序I比较，当I=J时，不需要交换，当I≠J时, A(I)与A(J)交换数据。 另外，为了避免再次调换前面已调换过的一对数据，框图中只对IJ的情况调换A(I)和A(J)的内容。 图4.2.8 倒序规律 图4.2.9 倒序程序框图 　　第3章介绍的MATLAB函数fft是一个计算DFT的智能程序，如果计算点数N=2M，则自动按DIT-FFT快速算法计算，否则，直接计算DFT。所以，调用该函数计算DFT时，最好选取N=2M，使处理速度大大提高。 4.2.5 频域抽取法FFT(DIF-FFT) 　　在基2FFT算法中，频域抽取法FFT也是一种常用的快速算法，简称DTF- FFT。 　　设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式： 式中  将X(k)分解成偶数组与奇数组，当k取偶数(k=2m, m=0, 1, …, N/2－1)时  当k取奇数(k=2m+1, m=0, 1, …, N/2－1)时， 令  将x1(n)和x2(n)分别代入(4.2.14)和(4.2.15)式，可得  　　　　　　　　　　　　　　　 (4.2.16) (4.2.16)式表明，X(k)按奇偶k值分为两组，其偶数组是x1(n)的N/2点DFT，奇数组则是x2(n)的N/2点DFT。x1(n)、x