基于modelsim的fft算法的设计学士学位论文(编辑修改稿)

基于modelsim的fft算法的设计学士学位论文(编辑修改稿)内容摘要：

就是 DITFFT这一算法。 设序列 x(n)的长度为 N，并且有以下的条件成立 N=2M， M为自然数 1(r)和 2(r)是 x(n)按 n的奇偶性分解成的两个 N/2 点的子序列，如下式所示 12,.. .1,0),2()(1  Nrrxrx 12,...,1,0),12()(2  Nrrxr 那么 x(n)的 DFT 为    n knNn knN WnxWnxkX )()()(     12/ 0 )12(212/ 0 2 )12()2( N r rkNN r krN WrxWrx    12/ 0 2212/ 0 1 )()( N r krNN r kN WrxWrx 由于 krNkrNjkrNjkrN WeeW 2 2/22222  ππ 所以 1,.. .,1,0)()()()()( 2112/0 2/212/0 2/1  NkkXWkXWrxWWrxkW kNNrkrNkNNrkrN （ ） 其中)(1kX和)(2k分别为 1rx和(2r的 N/2 点 DFT，即 理工大学学士学位论文 8 )]([)()()]([)()(212/02/22112/02/11rxDFTWrxkXrxDFTWrxkXNrkrNNrkrN （ ） （ ） 又由于)(1kX和)(2k都是以 N/2 为周期，且 kNNkN WW  2 所以 X(k)又可 以表示为如下所示的表达式 12,...,1,0)()()( 21  NkkXWkXkX kN （ ） 12,...1,0)()()2( 21  NkkXWkXNk kN （ ） 这样一个 N点的 DFT就被拆分成为了两个 N/2点的 DFT。 式 ()和式 ()说明了原 N点的 DFT和这两个 N/2点的 DFT之间的关系。 通常为了后续说明的方便，和其它许多文献一样，在本文中也将式 ()和式 ()的运算用图。 因为这个流图符号形状酷似一只蝴蝶，所以称其为蝶形运算符号。 图 采用蝶形运算符号的这种图示方法，可以用图 2． 2来表示前面所讲到的运算。 在图 ， N=23=8，式 ()给出了 X(O)～ X(3)的计算方法，而式 ()给出了 X(4)～ X(7)的计算方法。 由图 ，要完成一个蝶形运算，需要一次复数乘法和两次复数加法运算。 由图 ，经过一次分解后，计算一个 N点 DFT共需要计算两个 N/2点DFT可和 N/2个蝶形运算。 由前面的说明可以 知道，计算一个 N/2点 DFT需要 (N2)2次复数 乘 法 和 N/2(N/21) 次 复 数 加 法。 那 么 按 图 计算 N 点 DFT 共需要 2(N ／2)2+N/2=N(N+1)/2≈N2/2（ N1） 次复数乘法和 N(N/21)+2N/2=N2/2次复数加法运算。 通过对比可以看出，只进行过这样的次分解就使得运算量减少了近一半，充分说明了这样分解对减少 DFT的运算量是十分有效的。 由这里 N=2M， N/2仍然是偶数，为了使得计算理工大学学士学位论文 9 量能够得到进一步的减少，可以仿效前面的做法对 N/2点 DFT再做进一步分解。 图 N点 DFT的一次时域抽取分解图 (NtiS) 与第一次分解相同，1(3x和 4为)rx按奇偶分解成的两个长为 N/4的子序列，即 14,.. .,1,0,)12()( )2()(1423  Nllxlx lxlx 那么，)(1kX又可表示为     14/ 0 )12( 2/114/ 0 2 2/11 )12()2()( N i lkNN i klN WlxWlxkX    14/ 0 4/42/14/ 0 4/3 )()( N i klNkNN i klN WlxWWlx 12/,.. .,1,0),()( 42/3  NkkXWkx kN （ ） 其中 14/044/414/034/33)]([)())]([)()(NiklNNiklNlxDFTWlxklxDFTWlxkx 同理，由)(3kX和)(4k的周期性和 Wm2/N尼的对称性2/2/4/ NkNNk WW 最后得到： 理工大学学士学位论文 10 14/,.. .,1,0,)()()4/( )()()(42/3142/31   NkkXWkXNkX kXWkXkXkNkN （ ） 同理可得 14/,.. .,1,0,)()4/( )()()(62/5262/52   NkkXWkXNkX kXWkXkXkNkN （ ） 其中有 14/,.. .1,0,)12()()2()()]([)()()]([)()(2625614/04/66514/04/55NllxlxlxlxlXDFTWlxkXlXDFTWlxkXNiklNNiklN 这样，如图 ，经过第二次的分解，一个 N/2点的 DFT就被拆分成为了两个 N/4点的 DFT了。 式 ()和式 (2． 11)说明了原 N/2点的 DFT和这两个 N/4点的 DFT之间的关系。 依次类推，经过 M1次分解，最后将 N点 DFT分解成 N/2个 2点 DFT。 将前面两次分解的过程综合起来，就得到了一个完整的 8点 DITFFT运算流图，如图。 图中 用到关系式mkNk m WW /。 图中的输入序列不是顺序的，但是后面会看到，其排列是有规律的。 图 N点 DFT的第二次时域抽取分解图 (N_8) 理工大学学士学位论文 11 图 N点 DITFFT运算流图 （ N=8） DITFFT算法与直接计算 DFT运算量的比较 由 DITFFT算法的分解过程及图 ， N=2M时，其运算流图应该有 M级蝶形，每一级都由 N/2蝶形 运算构成。 每一级运算都需要 N/2次复数乘和 N次复数 an(每个蝶形需要两次复数加法 )。 所以， M级运算总共需要的复数乘次数为 NNMNC M 2log22)2(  复数加次数为 NNNMC A 2log)2(  而由前面的介绍，直接计算 N点的 DFT需要 N2次复数乘法以及 N(N1)次复数加法运算。 N1时， N(N1)是约等于 N2的。 当 N=210=1024时，可以求得直接计算 N点的 DFT和使用基 2DITFFT算法的所需乘法次数的比值为 )2/( 22 NN N 这样，运算效率就提高了 200多倍。 图 FFT算法与直接计算 DFT所需乘法次数的比较曲线。 由此图更加直观地看出 FFT算法的优越性，从图 ， N越大时，优越性就越明显。 理工大学学士学位论文 12 图 FFT算法与直接计算 DFT所需乘法次数的比较曲线 DITFFT的一些运算规律 DITFFT运算中是存在一些规律的，下面简单的介绍一下这些规律。 (1)原址计算 由 图 ， DITFFT的运算过程是很有规律的。 N=2M点的 FFT共需要进行进行 M级运算，每级由 N/2个蝶形运算组成。 在同一级运算中，每一个蝶形运算是有两个输入和两个输出的。 这两个输入、输出数据节点在同一水平线上，并且它们只对本蝶形运算有效，对其它的蝶形运算是无效的。 因为这样，当计算完一个蝶形以后，所得输出数据可立即存入原输入数据所占用的存储单元 i以此类推，当 M级运算都计算完毕以后，原来存放输入序列数据的 N个存储单元中便依次存放了 X(k)的 N个值。 这种利用同一存储单元存储蝶形运算计算输入、输出数据的 方法就称为原址计算。 很明显原址计算可以节省存储资源，从而降低硬件的成本。 (2)旋转因子的变化规律 由 8点 DITFFT的运算流图可以推得在 N点 DITFFT运算流图中，每级都有 N/2个蝶形。 每个蝶形都要乘以因子pW。 p被称为旋转因子，其中 p为旋转因子的指数。 通过观察图 ，第 L级共有 2L1个不同的旋转因子。 N=23=8时的各 级旋转因子表示如下： 理工大学学士学位论文 13 3,2,1,0,31,0,20,1222/24/JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLL时，时，时， () 对 N=2M的一半情况，第 L级的旋转因子为 LMLJNJNpNMLMLMLLJpNJpJWWWNJLWWLMML212,.. .,2,1,0,222212,.. .,2,1,0,12212 （ ） (3)蝶形运算规律 设序列 x(n)经时域抽选 (倒序 )后，存入数组 X中。 如果蝶形运算的两个输入数据相距 B个点，应用原位计算，则蝶形运算可表示成如下形式： pNLLpNLLWBJXJXBJ WBJXJXJX )()()( )()()( 11 11     其中 p=J2ML； J=0,1,...,2L1。 L=1,2,...,M 下标 L表示第 L级运算， XI， (J)则表示第 L级运算后数组元素 X(J)的值。 (4)序列的倒序 仔细分析可以发现看似毫无规律可循的 DITFFT算法的输入序列的排序其实是很有规律的。 由于 N=2M，所以顺序数可用 M位二迸制数 (0121 ... nnnn MM )表示。 当 N=8时，这种规律就可以用图。 图 形成倒序的树状图 (N23) 理工大学学士学位论文 14 表 顺序和倒序二进制数对照表 顺序 倒叙 十进制数 I 二进制数 二进制数 十进制数 J 0 000 000 0 1 001 100 4 2 010 010 2 3 011 110 6 4 100 001 1 5 101 101 5 6 110 011 3 7 111 111 7 DITFFT的输入顺序输出倒序的信号流图 DITFFT的信号流图的形式不是唯一的，它还有多种表现形式。 图 DITFFT的一种变形的运算流图，其中蝶形运算的旋转因子、运算量与图。 从图中很容易看出它是一种顺序输入，倒序输出的方式。 这种结构的信号流图有一个非常特别的优点就是前一级的旋转因子刚好是后一级上一半蝶形运算的旋转因子，且顺序不变，如果旋转因子的计算采用查表法，只要构造出一个 N/2点的NpW，就可以 用它来计算 N、 N/ N/ ...长度的 FFT。 因此在大型数据处理系统的 FFT算法中，较多采用的是图 法。 本课题也是采用的图。 图 DITFFT的顺序输入倒序输出形式 理工大学学士学位论文。