毕业设计（论文）-基于现代DSP技术的FFT算法的实现.doc

编号：03063033南阳师范学院2007届毕业生毕业论文（设计）题 目： 基于现代dsp技术的fft算法的实现 完 成 人： 班 级： 2003-03 学 制： 4 年 专 业： 电子信息与科学技术 指导教师： 完成日期： 2007-03-31 目 录摘要 1 引言（3）2 系统总体设计（4）3 fft算法及原理（4）3.1 fft算法概述（4）3.2 fft算法原理（5）3.3 按时间抽选的fft算法的其它形式流图（10）4 fft算法在dsp上的实现（10）4.1 8点dit fft模型的建立（11）4.2 8点dit fft模型的实现（14）5 结论（15）参考文献.（16）abstract(16）基于现代dsp技术的fft算法的实现作 者：胡桂芬指导老师：张 帅摘要：在信息信号处理过程中，fft是最基础的一种方法，同时是声学、语音、通信等领域的一种重要分析工具。本文主要介绍了实现fft的方法并在dsp builder软件上得以实现。关键词：离散傅立叶变换;快速傅立叶变换;数字信号处理器1 引言傅立叶变换是一种将信号从时域变换到频域的变换的形式。是声学、语音、电信和信号处理等领域中一种重要的分析工具。离散傅立叶变换（dft）是连续傅立叶变换在离散系统中的表示形式。由于dft的计算量很大，因此在一段时间内受到很大的限制。快速傅立叶变换（fft）是快速计算dft的一种高效方法，它使dft的运算大大简化，从而使dft在实际应用中得到了广泛的应用。fft不仅是一种快速计算方法，它的出现还有助于启发人们创造新理论和发展新的设计思想。经典的线性系统中的许多概念，例如，卷积、相关、系统函数、功率谱等概念，都要在离散傅立叶变换的意义上重新加以定义和解释；同时，用fft算法来实现卷积运算的概念后，人们发现也可以以很高的运算效率来实现高阶fir滤波器的设计方法和数字滤波器的频域设计方法进行了大量研究，从而在其后相当长时期内形成了数字滤波器的时域设计方法与频域设计方法并驾齐驱的局面。然而,这些均属于数字滤波器的早期研究工作,而且主要是用软件来实现的。现代dsp技术在数字信号处理涉及的应用领域中都是不可或缺的。2 系统总体设计 本文主要是利用现代dsp技术来实现fft算法，具体是使用eda软件dsp_builder、quartus、matlab结合数字信号处理的一些知识来设计fft算法。首先需要熟悉fft算法的基本原理，然后使用dsp_builder、matlab软件进行算法模型设计，设计完成后在simulink工具箱中进行仿真，观察设计是否正确。如果正确，则使用quartus软件对设计好的模型进行转化，将其转化为vhdl语言，编译、仿真，全部正确后，下载到fpga芯片上，利用pld器件的可重构性，在芯片上就构建了fft算法的硬件结构，就可以对输入的信号进行相应的处理。3 fft算法及原理3.1 fft算法概述在电力系统中，通常是以正弦波方式进行供电的，这不仅给电力系统的分析设计带来方便，而且使系统及附电设备运作在最佳状态。而在实际的供电电网中由于工频电压或电流直接作用在非线性负载等原因，往往产生倍频谱分量。另外，当电网发生故障时，测量得到的电参量往往在基波的基础上叠加有衰减的非周期分量和各种高频谱波。离散傅立叶变换(discrete fourier transistor，dft)在信号的频谱分析，数字系统的分析，设计和实现中得到了广泛的应用。原因之一就是计算dft有很多的快速算法，快速傅立叶变换(fast fourier transform，fft)算法就是其中之一。在使用数字信号处理领域，离散傅立叶变换算法不具有较强的滤波功能，而且通过该算法还可获得信号的实部和虚部，为确定短路电流、电压的大小，性质及功率的计算提供了极大的方便，因而被广泛采用。快速傅立叶变换(fft)属于数字信号处理中最基础的运算，有多种算法实现fft变换。如基-2fft算法、裂基fft算法、混合基fft算法、基-4fft算法等。(1)基-2fft法：这种算法是将输入序列在时域、频域上的次序按偶数和奇数来抽取。对于任意一个n=2k点长序列的fft运算，可以采用n次分解，最后分解成2点的fft运算的组合、从而降低了运算量。基-4fft算法与此类似，把n点序列最后分解成4点的fft运算的组合。(2)混合基fft算法：该算法是把fft的运算通过分解成很多短长度的fft来完成的。如果能分解成4点或2点的fft，就按上面提到的特殊情况开始处理。(3)分裂基fft算法：该算法是利用将基2和基4变换到不同部位，进一步改善固定基和混合基的算法。该算法的思想是：对偶序号输出使用基2算法，对奇序列输出使用基4算法，将大点数的dft逐级分解成小点数的dft运算，由于分解的不对称性，算法结构比固定基算法稍微复杂一些，但其乘法和加法次数比较少，又允许以同址计算和蝶形方式来实现，所以被认为是最好的快速傅立叶变换算法。3.2 fft算法原理(1)按时间抽选(dit)的基-2fft算法 (库利-图基算法)先设序列点数n=2l,l为整数。如果不满足这个条件，可以人为地加上若干零值点，使之达到这一要求。这种n为2的整数幂的fft也称基-2 fft。将n=2l的序列x(n)（n=0，1，n）先按n的奇偶分成以下两组： (1)则可将dft化为： (2)n为偶数 n为奇数 利用系数wnkn的可约性，即 (3)上式可表示成 (4)式中与分别是及的n/2点dft： (5) (6)由(4)式可看出，一个n点dft分解成两个n/2点的dft，它们按(3-3)式又组合成一个n点dft。但是，、以及、都是n/2点反例，即r，k满足r，k=0,1,，（n/2）1。而却有n点，而用(3-3)式计算得到的只是的前一半项数的结果，要用、来表达全部的值，还必须应用系数的周期性，即： （7）这样可得到： (8)同理可得： (9)(6)式、(7)式说明了后半部分k值()所对应的、分别等于前半部分k值(0kn/2-1)所对应的、。再考虑到的以下性质 (10)这样，把(8)式、(9)式、(10)式、代入(4)式，就可将表达为前后两部分：前半部分(k=0，1，/)，k=0，1，n/2-1 (11)后半部分(k=n/2，n)，k=0，n/2-1 (12)这样，只要求出0到（n/2）区间的所有、值，即可求出0到（n）区间内的所有值，这就大大节省了运算。 (11)式和(12)式的运算可以用图1的蝶形信号流图符号表示。图1 时间抽取法蝶型运算流图符号采用这种表示法，可将上面讨论的分解过程表示于图2中。此图表示n=23=8的情况，其中输出值x(0)到x(3)是由(3-9)式给出的，而输出值x(4)到x(7)是由(3-10)式给出的。图2 按时间抽取，将一个n点dft分解为两个n/2点dft可以看出，每个蝶形运算需要一次复数乘法x2(k)wnk及两次复数加(减)法。据此，一个n点dft分解为两个n/2点dft后，如果直接计算n/2点dft，则每一个n/2点dft只需要(n/2)2=n2/4次复数乘法，n/2(n/2-1)次复数加法，两个n/2点dft共需要2(n/2)2=n2/2次复数乘法和n(n/2-1)次复数加法。此外把两个n/2点dft合成为n点dft时，有n/2个蝶形运算，还需要n/2次复数乘法及2n/2=n次复数加法。因而通过这一步分解后，总共需要n2/2+n/2=n（n+1）/2n2/2次复数乘法和n(n/2-1)+n=n2/2次复数加法，因而通过这样分解后运算工作量差不多减少到一半。既然如此，由于n=2l，因而n/2仍是偶数，可以进一步把每个n/2点子序列再按其奇偶分解为两个n/4点的子序列。 (13)k=0,1,n/4-1 (14)且，k=0,1,n/4-1 (15)其中 (16)图3给出n=8时，将一个n/2点dft分解成n/4点dft，由这两个n/4点dft组合成一个n/2点dft的流图。也可进行同样的分解： （17），k=0,1,n/4-1 (18)其中 (19) (20)图3 将两个n/4点dft组合成一个n/2点dft将系数统一为,则一个n=8点dft就可分解为四个n/4=2点dft,这样可得图4所示的流图。图4 按时间抽取，将一个n点dft分解为四个n/4点dft根据上面同样的分析知道利用四个n/4点的dft及两级蝶形组合运算来计算n点dft，比只用一次分解蝶形组合方式的计算量又减少了大约一半。由此可得出一个按时间抽选运算的完整的8点dft流图，如图5所示。图5 n8按时间抽取法fft运算流图这种方法的每一步分解都是按输入序列在时间上的次序是属于偶数还是奇数来分解为更短的子序列，所以称为“按时间抽选法”。(2)按频率抽选(dif)的基2 fft算法(桑得图基算法)此算法是把输出序列x(k)(也是n点序列)按其顺序的奇偶分解为越来越短的序列。3.3 按时间抽选的fft算法的其它形式流图对于任何流图，只要保持各节点所连的支路及其传输系数不变，则不论节点位置怎么排列所得流图总是等效的，所得最后结果都是x(n)的dft的正确结果，只是数据的提取和存放的次序不同而已。这样就可得到按时间抽选的fft算法的若干其它形式流图。图6 按时间抽取，输入自然顺序，输出倒位序的fft流图图7 按时间抽取，输入输出都为自然顺序的fft流图4 fft算法在dsp上的实现由于蝶形运算涉及复数运算，较为复杂，dsp builder为能实现fft模型的建构，专门引入了蝶形算子模块butterfly，如下图。butterfly模块图8 butterflybutterfly模块可以完成复数有符号数的蝶形运算。对于输入信号(复数)a=x+jx；b=y+jy蝶形运算系数：蝶形运算： （21）由于fft的算法过于复杂，在以往的数字信号处理器上实现一个高速信号的fft变换是不可想象的。数字信号处理器固有的串行(顺序)执行结构，对一个高速(与该处理器的主频相当)的信号序列进行fft，是很难实现的。然而，在fpga上实现时，可以采用并行分布式结构，实现一个实时fft的难度就比较小了。4.1 8点dit fft模型的建立 在这里将介绍如何实现一个n=8的时间抽取fft模型。在simulink中建立一个新模型。参照图5的结构。调用dsp builder模块完成dit8fft模型的绘制。模型如图9所示。 图9 dit8fft模型dit8fft模型中各个模块的参数设置如下：x模块：(altbus)库：altera dsp builder中bus manipulation库参数“bus type”设为“signed integer”参数“number of bits.”设为“8”xr、xr1、xr2、xr3、xr4、xr5、xr6、xr7模块：(altbus)库：altera dsp builder中bus manipulation库参数“bus type”设为“signed integer”参数“number of bits.”设为“16”xi、xi1、xi2、xi3、xi4、xi5、xi6、xi7模块：(altbus)库：altera dsp builder中bus manipulation库参数“bus type”设为“signed integer”参数“number of bits.”设为“16”shift taps模块：(shift taps)库：altera dsp builder中storage库参数“number of taps”设为“8”参数“distance between taps”设为“1”选择“use deicated circuitry”x0、x1、x2、x3、x4、x5、x6、x7模块：(real=imag to complex)库：altera dsp builder中complex signals库参数“bus type”设为“signed integer”参数“number of bits.”设为“8”constant、constant1、constant2、constant3、constant4、constant5、constant6、constant7模块：(constant)库：altera dsp builder中bus manipulation库参数“bus type”设为“signed integer”参数“number of bits.”设为“8”参数“constant value”设为“0”参数“sampling period”设为“1” w0、w0_1、w0_2、w0_3模块：(complex constant)库：altera dsp builder中complex signals库参数“bus type”设为“signed integer”参数“number of bits.”设为“8”参数“.number of bits”设为“0”参数“real value”设为“127”参数“imaginary value”设为“0”butterfly000、butterfly001、butterfly002、butterfly003模块：(butterfly)库：altera dsp builder中complex signals库参数“input bit width(a,b,w)”设为“8”参数“output bit width(a,b)”设为“16”参数“output lsb bit”设为“2”w0_6、w2_5、w0_4、w2_7模块：(complex constant)库：altera dsp builder中complex signals库参数“bus type”设为“signed integer”参数“number of bits.”设为“16”参数“.number of bits”设为“0”对于w0_6、w2_5参数“real value”设为“1”参数“imaginary value”设为“0”z对于w0_4、w2_7参数“real value”设为“0”参数“imaginary value”设为“127”butterfly010、butterfly020、butterfly030、butterfly040模块：(butterfly)库：altera dsp builder中complex signals库参数“input bit width(a,b,w)”设为“16”参数“output bit width(a,b)”设为“16”参数“output lsb bit”设为“2”w0_6、w2_5、w0_4、w2_7模块：(complex constant)库：altera dsp builder中complex signals库参数“bus type”设为“signed integer”参数“number of bits.”设为“8”参数“.number of bits”设为“0”对于w0_8参数“real value”设为“127”参数“imaginary value”设为“0”对于w2_10参数“real value”设为“0”参数“imaginary value”设为“127”对于w1_9、w3_11参数“real value”设为“90”参数“imaginary value”设为“90”x0、x1、x2、x3、x4、x5、x6、x7模块：(complex to real-imag)库：altera dsp builder中complex signals库参数“bus type”设为“signed integer”参数“number of bits.”设为“8”在dit8fft模型中除了使用butterfly模块进行蝶形运算外，还使用了有符号数到复数、复数到有符号数的转化，运算量是较大的。在模型中使用了移位寄存器来锁存输入序列，在每一个时钟都完成对当前输入序列前8个值的fft操作。4.2 8点dit fft模型的实现通过signalcompiler，把上面的fft模型转换成vhdl，在quartusii中进行编译下载。下图显示了synplify pro的综合结果。综合结果(部分) 图10 综合结果(部分)5 结论本文重点研究了基于现代dsp技术,采用时间抽选的基-2fft方法实现和在软件上的实现。该dspbuilder软件是内嵌在matlab环境的simulink工具箱中，里面有现成的相关模块可以直接使用。只要对fft算法有一定的了解，就可以直接调用模块进行链接fft模块。实践证明，这种方法与直接dft算法运算量相对而言少。当点数n越大时，fft的优点更突出。同时，fft算法在计算机的运算实现上是有规律的，有效的利用存储单元。参 考 文 献1.程佩青.数字信号处理教程m.北京：清华大学出版社，1995.2.宁凯娣，杨栓科.dsp控制器原理及应用m.北京：科学出版社，2002:193-194.3.胡广书.数字信号处理理论、算法与实现m.北京：清华大学出版社，1997:133-137.4.张雄伟，陈亮，徐光辉.dsp芯片的原理与开发应用（第三版）m.北京：电子工业出版社,2003:394-395.5.候伯亨,顾新.vhdl硬件描述语言与数字逻辑