《毕业设计（论文）基于NIOSⅡ的FFT实现.doc》由会员分享，可在线阅读，更多相关《毕业设计（论文）基于NIOSⅡ的FFT实现.doc（23页珍藏版）》请在三一办公上搜索。
1、目 录摘要11 前言22 数字信号处理简介23 SOPC简介34 快速傅立叶变换44.1 计算DFT的特点及FFT的预算基本途径44.2 时域抽取法基2FFT基本原理54.3 直接计算DFT与DIT-FFT算法运算量的比较95 DIT-FFT的运算规律95.1 原位计算105.2 旋转因子的变化规律105.3 蝶形运算规律106 系统设计116.1 Quartus部分的系统设计116.1.1 Quartus简介116.1.2 创建一个Quartus工程126.1.3 创建CPU系统模块126.1.4 建立图形设计文件136.2 NIOS部分的系统设计136.2.1 NIOS简介136.2.2
2、启动NIOS IDE146.2.3 建立新的软件工程146.2.4 编程思想与程序框图146.2.5 序列的倒序156.2.6 输入程序与编译工程186.2.7 运行与调试程序187 结论198 致谢19参考文献19附录20基于NIOS的FFT实现专业名称 电子信息科学与技术专业 作者 *指导老师 *摘要：在数字信号处理中，FFT占有很重要的位置，其运算速度影响整个系统的性能。传统实现方法速度慢，难以满足信号处理的实时要求。针对这一现状，本文研究了FFT算法的C语言程序设计方法，讨论了基于NIOS实现FFT处理中的若干问题。仿真结果表明该方案正确可行，可以满足需要处理的应用场合。关键词：快速傅
3、立叶变换（FFT）；可编程片上系统（SOPC）；C语言; Realization of FFT Based on NIOSElectronic information science and technical specialtyOUYANG Xu Instruction TeacherSHI WeiAbstract: FFT plays an important role in signal processing and its operation time has effect on the performance of the system. The operational speed
4、of traditional implement method is too low to meet the need of signal processing for real-time. So, it is introduced a kind of C language program design for FFT algorithm and some problems are discussed in design when FFT is realized based on NIOS. The simulation result verified the correctness of p
5、rogram which can be applied to the fields needed.Keywords: FFT; SOPC; C Language; 1 前言DFT(Discrete Fourier Transformation)是数字信号分析与处理如图形、语音及图像等领域的重要变换工具。DFT是连续傅里叶变换在时域和频域上都离散的形式，将时域信号的采样变换为在离散时间傅里叶变换（DTFT）频域的采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作经过周期延拓成为周期信号再
6、作变换。DFT不仅在理论上有重要意义，而且在各种信号的处理中亦起着核心作用。直接计算DFT的计算量与变换区间长度N的平方成正比。当N较大时，因计算量太大，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。快速傅立叶变换(Fast Fourier Transformation，简称FFT)使DFT运算效率提高12个数量级。其原因是当N较大时，对DFT进行了基4或基2分解运算，可以有效的减少运算量。FFT算法除了必需的数据存储器ram和旋转因子rom外，仍需较复杂的运算和控制电路单元，即使现在,实现长点数的FFT仍然是很困
7、难。本文提出的FFT实现算法是基于SOPC之上的，算法由C语言编程实现，完成对点FFT的计算。2 数字信号处理简介数字信号处理以信号系统的一般理论为基础，在理论体系上发展专门适合于离散时间（或者空间）上的信号分析原理和方法，在实践上发展适合于计算机处理的器件和设备，在应用上建立针对不同信号的模型和计算方法。数字信号处理的基础理论是在针对确定信号的讨论发展起来的，但是其应用几乎无一例外地涉及随机信号的分析，从这个意义上说，统计信号处理是数字信号处理的应用表现。因此，数字信号处理的理论体系大体可以归纳为三个层次的结构，这个结构更低层的基础是数学，更上层的是具体的应用。 事实上，统计信号处理的大多数
8、原理并不直接来源于离散时间（空间）系统的分析，而是来源于对一般时间（空间）序列的研究。然而上面这样的层次对于我们利用计算机为工具来解决问题是有用的。譬如，我导师在他的博士论文工作中使用的程序库（包含他自己编写的大量代码）基本上就是由数理统计和数值计算、信号处理工具、信息处理工具以及它们所支持的统计信号处理工具库所构成的。上面的不同层次，有不同的关键问题。信号与系统的理论基础讨论的核心问题就是变换域上表示信号的问题。C.E.Shannon的抽样定理（Theorem 13 in “A mathematical Theory of Communcation”,Shannon）被工程师们公认为影响这个
9、世界的最重要的公式之一（根据一项非正式的调查显示，抽样定理列于该调查所排列的10个最重要公式中。注意，第一位是牛顿第二定律，第二位是万有引力定律，第五位是Maxwell方程组，抽样定理列第八，却足以说明它的重要性。）抽样定理唯一地提供了这样的可能性：能够用有限的离散的计算手段来研究连续发生的信号。1离散信号分析的理论一方面把连续时间的信号分析的方法和原理引进到离散系统的领域，比如z-变换、DTFT、DFT以及根据模拟滤波器按照一定准则设计数字滤波器的方法；另一方面独立发展关于离散系统和信号分析的专门的理论和方法，比如滤波器的算法设计、量化的理论、有限字长的效应。这些理论的发展有一个共同的特点，
10、就是适应数字计算机解决信号处理的问题。需要注意到，离散信号和系统的理论不仅仅解决现实世界中连续系统的问题，也开辟了解决本身就具有离散特征的系统的问题，比如，雷达天线阵列的方向图问题，本身就是空间离散Fourier变换的问题。现实问题中的信号一般都不是确定的，而是随机的。统计信号处理引进随机过程和数理统计的成果，并且运用信号处理的基本原理，建立模型和参数估计的理论，并且同信息论关于信源和信道及其相互关系的理论结合在一起，用于解决特定系统、特定模型的问题。模型决定算法，而算法决定实现。写到这样一句话的时候，可以这么来归纳工程师们在数字信号处理领域所取得的成就：理论-模型-算法-工程实现-应用。最终
11、解决问题的一定是可以运行的代码或者设备。3 SOPC简介SOPC (System On Programmable Chip )即可编程的片上系统，或者说是基于大规模FPGA的单片系统。SOPC的设计技术是现代计算机辅助设计技术、FDA技术和大规模集成电路技术高度发展的产物。SOPC技术的目标就是试图将尽可能大而完整的电子系统，包括嵌入式处理器系统、接口系统、硬件协处理器或加速器系统、DSP系统、数字通信系统、存储电路以及普通数字系统等，在单一FPGA中实现，使得所设计的电路系统在其规模、可靠性、体积、功耗、功能、性能指标、上市周期、开发成本、产品维护及其硬件升级等多方面实现最优化。SOPC技术
12、是一门全新的缘合性电子设计技术，在电子设计技术上给出了一种以人的基本能力为依据的软硬件综合解决方案。由于同时涉及底层的硬件系统设计和相应的软件设计，在系统优化方面有了前所未有的自由度。SOPC技术使开发者更能动地在软硬件系统的综合与构建两个方面有了充分发挥自己创造性和想象力的巨大空间，从而使得从多角度、多因素和多结构层面上大幅度优化自己的设计成为可能。事实上，诸如单片机、DSP或ARM系统等基于传统开发技术的设计流程而言，不存在严格意义上的硬件设计，而只有软件设计。这是因为，一旦方案确定，硬件系统的核心器件是现成的，功能是确定的，结构是固定的，指令系统是不可更改的，从面导致硬件组织方案和连接方
13、案是限定的，用户只能被动地遵循和适应，这时的硬件“设计”只能流于拼装和连接。系统构成后的惟一任务是依据既定的指令系统来编程，除了系统功能和算法可以通过软件改变外，系统的性能和指标己无从改变。设计者的创新能力、想象力和优化设计能力的发挥空间已被选定的硬件性能所界定。没有了创造，更谈不上超越了，进而导致了系统的综合性能基本取决于器件原有的性能和指标。换言之，传统技术是以既定的硬件及其性能而非以人的能力为主轴的技术。这样不难明白，在这个以硬件决定“创造”的世界里，为什么在优秀的8031单片机出现以后，仍然层出不穷地涌现出其他各种功能和性能的单片机:而同样是DSP处理器，C5X系列与C6X系列器件则把
14、开发者带到完全不同的技术领域和功能范畴。显然，硬件的可设计性和用户目标的适应性在系统性能指标上占有更大的份额，而SOPC技术的优势正在于是设计者本身而非器件设计商去更有效地占据这一份额。SOPC在应用理论和知识构成上，达到了一种有机融合。基于SOPC的结构特点，SOPC系统的开发对于设计者的知识范围有了更高的要求。除了必须了解基本的EDA软件、硬件描述语言和FPGA器件相关知识外，还必须熟悉计算机组成与接口、汇编语言和C语言、DSP算法、数字通信、嵌入式系统开发、嵌入式操作系统、片上系统构建与测试等知识。这样，SOPC技术的普及必将有力地推动电子信息及工程类各学科分支与相应的课程类别间的融合。
15、这种融合在SOPC技术中已不是简单的合并与算术相加，而是有机的融汇和充满设计者创新意识的升华。例如可以利用Matlab/DSP Builder/Quartus完成纯硬件的DSP算法模型及实现，进而构成嵌入式系统外围接口的协处理模块，再进一步构成软件程序中的精简指令，从而实现完全自主的、真正意义上的硬件设计和系统优化。与现有的诸多电子系统设计理念和解决方案相比，SOPC技术更具代表性、主流性、规范性与普遍性。SOPC从设计层次上讲，分硬件设计和软件设计;从设计流程上讲，是典型的自顶向下的流程:从设计手段上讲，相比于传统技术，更广和更深入地利用了计算机，而计算机技术无疑是当今的主流技术。在这一平台
16、上，学科知识的融合，设计手段的融合，测试技术的融合，使SOPC设计者最大限度地在优化系统的性能上得以发挥自己的聪明才智，不再如传统技术中那样，把大量的时间花费在无谓的软硬件构建细节上，从而使人们常说的“动手能力”成了计算机应用能力的组成部分，而非仅为诸如“焊接”、“钻孔”和“连线”等操作行为的代名词了。从未来的电子系统设计技术走势上看，SOPC技术更具发展性和前瞻性。From Concept to System in minutes”显然是现代电子技术追求的方向和境界。在那里，人们可以远离“十年磨一剑”的经验、变化无端的硬件结构、空耗时光而难得要领的排错，潜心于己把握的知识、智慧与灵感，把电路
17、模型、系统模型、功能模型、行为模型及数学模型直接通过计算机在短时间内形成高效实用的电子线路系统，这不能不说是一种大胆的设想。然而，在SOPC领域，这种设想已得到了部分的实现。SOPC技术不能简单归属于哪一个学科分支。广义地讲，它是一种理念、一种思想方法、一种境界、一种趋势。4 快速傅立叶变换4.1 计算DFT的特点及FFT的预算基本途径长度为N的有限长序列x(n)的DFT为X(k)= ，k=0，N考虑x(n)为复数序列的一般情况，对某一个k值，直接按上式计算X(k)值需要次复数乘法、（）次复数加法，因此，对所有个k值，共需次复数乘法及N（）次复数加法运算。当N时，N（）。由上述可见，N点DFT
18、的乘法和加法预算次数均与成正比。当N较大时，运算量相当可观。这对于要求实时信号处理来说，必将对计算速度提出难以实现的要求。所以，必须减少其运算量，才能使DFT在各种科学和工程计算中得到应用。FFT算法就是不断的把长序列的DFT分解成几个短序列的DFT，并利用的周期性和对称性来减少DFT的运算次数。对于变换长度为N的序列x(n)其傅立叶变换可以表示如下：X(k)=DFTx(n)= 其中，W=exp(-2/N)。4.2 时域抽取法基2FFT基本原理 FFT算法有按时间抽取(DIT)和按频率抽取(DIF)两种形式，其区别在于输入书记和旋转因子乘、加的顺序不同。在DIT中，蝶形运算的输入数据和旋转因子
19、是先乘后加；而在DIF中，是先加后乘。下面先介绍DIF-FFT算法。设序列x(n)的长度为N，且满足，为自然数按n的奇偶把x(n)分解为两个N/2点的子序列则x(n)的DFT为由于所以K=0,1,N1其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT，即 由于X1(k)和X2(k)均以N/2为周期，且，所以X(k)又可表示为 （式）（式）这样，就将N点DFT分解为两个N/2点的DFT和式以及式的运算。上面两个式子的运算可用图所示的流图符号表示，根据其形状称之为蝶形运算符号。图 蝶形运算符号采用这种图示法，可将上述分解运算表示于图中，图中，N=2=8，X(0)X(3)由(式1
20、)给出，而X(4)X(7)则由(式2)给出。由图可见，要完成一个蝶形运算，需要一次复数乘和两次复数加法运算。由图容易看出，经过一次分解后，计算一个N 点DFT共需要计算两个N/2点DFT和N/2个蝶形运算。而计算一个N/2点DFT需要次复数乘和N/2(N/21)次复数加法。所以，按图2计算N点DFT总共需要2+N/2=N(N+1)/2/2(N 1时)次复数乘法和N(N/21)+2N/2= /2次复数加法运算。由此可见，仅仅经过一次分解，就使运算量减少近一半。既然这样分解对减少DFT的运算量是有效的，且N=，N/2仍然是偶数，故可以对N/2点DFT再作进一步分解。图 N点DFT的一次时域抽取分解
21、图(N=8)与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即那么，X1(k)又可表示为 式中 同理，由X3(k)和X4(k)的周期性和Wm N/2的对称性 Wk+N/4 N/2=-Wk N/2 最后得到： （式）用同样的方法可计算出（式）其中这样，经过第二次分解，又将N/2点DFT分解为两个N/4点DFT和(式)或(式)所示的N/4个碟形运算，如图3所示。依次类推，经过M1次分解，最后将N点DFT分解成N/2个2点DFT。图3 N点DFT的第二次时域抽取分解图(N=8)一个完整的8点DIT-FFT 运算流图如图4所示。图中输入序列不是顺序排列，但后面会看
22、到，其排列是有规律的。图4 N点DIT-FFT运算流图(N=8)4.3 直接计算DFT与DIT-FFT算法运算量的比较由DIT-FFT算法的分解过程及图4可见，N=时，其运算流图应有M级碟形，每一级都由N/2个蝶形运算构成。因此，每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为复数加次数为而直接计算DFT的复数乘为次，复数加为N(N1)次。当N1时，(N/2) N，从而，DIT-FFT算法比直接计算DFT 的运算次数大大减少。例如，N=210=1024时这样，就使运算效率提高200多倍，图5为FFT算法和直接DFT算法所需运算量与计算
23、点数N的关系曲线。由此图更加直观地看出FFT 算法的优越性，显然，N越大时，优越性越明显。图5 直接计算DFT与DIT-FFT算法所需乘法次数的比较曲线5 DIT-FFT的运算规律为了最终写出DIT-DFT运算程序或设计出硬件实现电路，下面介绍它的运算规律。5.1 原位计算由图可以看出，DIT-FFT的运算过程很有规律。N=点的FFT共进行M级运算，每级由N/2个蝶形运算组成。同一级中，每个蝶形的两个输入数据只对计算本蝶形有用，而且每个蝶形的输入、输出数据结点又同在一条水平线上，这就意味着计算完一个蝶形后，所得输出数据可立即存入原输入数据所占用的存储单元。这样，经过M级运算后，原来存放输入序列
24、数据的N个存储单元中便依次存放X(k)的N个值。这种利用同一存储单元存储蝶形计算输入、输出数据的方法称为原位计算。原位计算可节省大量内存，从而使设备成本降低。5.2 旋转因子的变化规律如上所述，N点DITFFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子，称其为旋转因子，p称为旋转因子的指数。但各级的旋转因子和循环方式都有所不同。为了编写计算程序，应先找出旋转因子与运算级数的关系。用L表示从左到右的运算级数(L=1,2,M)。观察图不难发现，第L级共有2 L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下： L=1时，= = ， J=0 L=2时， = = ， J=0，1
25、L=3时， = = ， J=0，1，2，3 对N=2M的一般情况，第L级的旋转因子为由于所以(式) (式)这样，就可按(式5)和(式6)确定第L级运算的旋转因子(实际编程序时，L为循环变量)。5.3 蝶形运算规律设序列x(n)经时域抽选(倒序)后，存入数组X中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式：式中；J=0,1, 1；L=1,2,M下标L表示第L级运算，则表示第L级运算后数组元素X(J)的值。如果要用实数运算完成上述蝶形运算，可按下面的算法进行。设 式中下标R表示取实部，I表示取虚部，则6 系统设计6.1 Quartus部分的系统设计6.1.1 Q
26、uartus简介Quartus是高级和复杂的用于可编程片上系统的一种设计环境。 QuartusII提供完善的 timing closure 和 LogicLock 基于块的设计流程。QuartusII是唯一一个包括以timing closure 和 基于块的设计流为基本特征的programmable logic device (PLD)的软件。 Quartus II 设计软件改进了性能、提升了功能性、解决了潜在的设计延迟等，在工业领域率先提供FPGA与mask-programmed devices开发的统一工作流程。 Altera Quartus II 作为一种可编程逻辑的设计环境, 由于其强
27、大的设计能力和直观易用的接口，越来越受到数字系统设计者的欢迎。 Altera Quartus II （3.0和更高版本）设计软件是业界唯一提供FPGA和固定功能HardCopy器件统一设计流程的设计工具。工程师使用同样的低价位工具对Stratix FPGA进行功能验证和原型设计，又可以设计HardCopy Stratix器件用于批量成品。系统设计者现在能够用Quartus II软件评估HardCopy Stratix器件的性能和功耗，相应地进行最大吞吐量设计。 Altera的Quartus II可编程逻辑软件属于第四代PLD开发平台。该平台支持一 个工作组环境下的设计要求，其中包括支持基于In
28、ternet的协作设计。Quartus平台与Cadence、ExemplarLogic、MentorGraphics、Synopsys和Synplicity等EDA供应商的开发工具相兼容。改进了软件的LogicLock模块设计功 能，增添 了FastFit编译选项，推进了网络编辑性能，而且提升了调试能力。Altera QuartusII提供了完全集成且与电路结构无关的开发包环境，具有数字逻辑设计的全部特性，包括：可利用原理图、结构框图、VerilogHDL、AHDL和VHDL完成电路描述，并将其保存为设计实体文件；芯片（电路）平面布局连线编辑；LogicLock增量设计方法，用户可建立并优化系
29、统，然后添加对原始系统的性能影响较小或无影响的后续模块；功能强大的逻辑综合工具；完备的电路功能仿真与时序逻辑仿真工具；定时/时序分析与关键路径延时分析；可使用SignalTapII逻辑分析工具进行嵌入式的逻辑分析；支持软件源文件的添加和创建，并将它们链接起来生成编程文件；使用组合编译方式可一次完成整体设计流程；自动定位编译错误；高效的期间编程与验证工具；可读入标准的EDIF网表文件、VHDL网表文件和Verilog网表文件；能生成第三方EDA软件使用的VHDL网表文件和Verilog网表文件。6.1.2 创建一个Quartus工程在Quartus软件中利用创建工程向导（New project
30、Wizard）创建一个新的工程。在向导中需要指定工程的工作目录、工程名以及顶层文件名（工程名和顶层文件名必须一致），同时指定工程中所需要用到的设计文件、其他源文件、用户库及第三方EDA工具。6.1.3 创建CPU系统模块A 启动SOPC Builder：点击TOOLS-SOPC Builder，在弹出的Create New System对话框中，输入系统名称为cpu并选择目标硬件语言为VHDL。B 定目标FPGA和时钟设置：在Target栏中选择Unspecified Board,在Device Family栏中指定目标板所使用的类型，此处为Stratix。指定系统的频率为50MHz。C 添加
31、NIOS处理器内核：在元件列表中的Avalon Components目录下双击NIOS2 Process-Altera Corporation,出现Altera NIOS配置向导，从NIOS Core选项卡的三种类型的CPU中选择经济型的NIOS/e，其它的不变，点击NEXT直到出现JTAG Debug Module选项卡，为CPU添加JTAG调试模块为Level 1,支持软件断点调试。最后单击FINISH完成处理器配置。D 添加片内存储器：在元件列表中的Avalon Components目录Memory组件下的On-Chip Memory0,设置Memory width为32位，Total
32、Memory Size为4Kbytes。再依此添加1个On-Chip Memory1。 E 添加一个JTAG UART内核：在元件列表中的Avalon Components目录Communication组件下的JTAG UART，进入向导指定写IFO缓冲区的深度设为64字节，IRQ阈值为8。读FIFO缓冲区的深度设为64字节，IRQ阈值为8。F 添加PIO：在元件列表中的Avalon Components目录Other组件下的PIO，出现Avalon PIO配置向导，宽度设置为8，Direction栏选择为Input ports only,即为输入模式，输入8位数据，重命名为pio_i_re
33、。再添加一个8位的输入pio_i_im。按照同样的方法，添加2个16位的PIO作为输出口，分别命名为pio_i_re和pio_i_im。6.1.4 建立图形设计文件图6 CPU模块图选择FILE-NEW工作菜单，选择对话框中的Block Diagram/Schmatic File,点击OK按钮，打开图形编辑对话框。在图形编辑器中，双击空白处，把刚才建立的模块调入，就完成了如图6所示的功能模块。6.2 NIOS部分的系统设计6.2.1 NIOS简介NIOS嵌入式处理器是FPGA生产厂商Alters推出的软核(Soft Core ) CPU，是一种面向用户的，可以灵活定制的通用RISC(精简指令集
34、架构)嵌入式CPU。 NIOS以软核的方式提供给用户，并专为在Altera的FPGA上实现作了优化，用于SOPC(片上可编程系统)集成，最后在FPGA上实现。NIOS在FPGA上实现具有一系列不同于普通嵌入式CPU系统的特性，它的外设可以灵活选择或增删，可以自定制用户逻辑为外设，可以允许用户定制自己的指令集，设计者可以使用NIOS加上外部的Flash、SRAM来构成一个嵌入式处理器系统。NIOS嵌入式CPU是一种专门为单芯片可编程系统(SOPC)设计应用而优化的CPU软核。SOPC Builder是Alters公司为硬件设计人员开发的一套系统设计工具，通过它可以创建NIOS CPU设计项目，从
35、而为设计人员提供SOPC设计必需的软硬件设计平台。利用SOPCBuilder创建NIOS CPU设计项目之后，主要生成以下3方面的结果:首先，进行系统内存映像一致性检查，外设地址和中断优先权的统一，以及CPU有效入口范围的正确性检查。SOPC Builder将报告检查过程中出现的错误，并提示设计者修正错误。然后，对于不同的CPU系统进行软件开发将对应不同的编译器、开发平台及开发包。SOPC Builder创建 NIOS CPU成功后，也将为用户创建好的特定的NIOS系统生成一个定制的软件开发包(SDK)。最后，NIOS系统硬件设计人员也将得到一个SOPC Builder生成的NIOS硬件设计文
36、件，从而将NIOS CPU应用在整个硬件系统中。Altera推出的NIOS II系列嵌入式处理器扩展了目前世界上最流行的软核嵌入式处理器的性能，把NIOS II嵌入到Altera的所有FPGA中，例如StratixII、Stratix、CycloneII,Cyclone、APEX,ACEX和HardCopy系列器件中，用户可以获得超过200 DMIPS的性能，用户可以从三种处理器以及超过60个的IP核中选择所需要的，NIOS II系统为用户提供了最基本的多功能性，设计师可以以此来创建一个最适合他们需求的嵌入式系统。使用NIOS II处理器的用户可以根据他们的需要来调整嵌入式系统的特性、性能以及
37、成本，快速使得产品推向市场，扩展产品的生命周期，并且避免处理器的更新换代。6.2.2 启动NIOS IDE在Alter SOPC Builder NIOS-cpu窗口中System generation栏中点击Run NIOS IDE按钮。在弹出的对话框中，选择工作场所。6.2.3 建立新的软件工程(1)选择IDE软件中FILE-NEW-C/C+ Application命令。(2)在出现的对话框中确定以下选项：在name栏填入新建项目的项目名为FFT。确定选中Use Default Location栏。在Select Target Hardware中指定当前硬件设计系统为NIOS_fft。(3
38、)点击FINISH按钮后，新建的工程就会添加到工作区中，同时NIOS IDE会创建一个系统库项目。6.2.4 编程思想及程序框图创建完工程以后，需要在窗口的编辑区中输入FFT的C语言程序，其编程思想及程序框图如图。仔细观察图4，还可归纳出一些对编程序有用的运算规律；第L级中，每个蝶形的两个输入数据相距个点；同一旋转因子对应着间隔为点的个蝶形。总结上述运算规律，便可采用下述运算方法。先从输入端（第级）开始，逐级进行，共进行M级运算。在进行第L级运算时，依次求出个不同的旋转因子，没求出一个旋转因子，就计算完它对应的所有个蝶形。这样，我们可用三重循环程序实现DIT-FFT运算，程序框图如图7所示。另
39、外，DIT-FFT算法的输出X(k)为自然顺序，但为了适应原位计算，其输入序列不是按x(n)的自然顺序排序，这种经过M1次偶奇抽选后的排序称为序列x(n)的倒序。程序框图中的倒序框就是成这一功能的。图7 DIT-FFT运算和程序框图6.2.5 序列的倒序DIT-FFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于，所以顺序数可用位二进制数()表示。次偶奇时域抽选过程如图6所示。第一次按最低位的和将x(n)分解为偶奇两组，第二次又按次低位的、值分别对偶奇组分解；依次类推，第次按位分解，最后所得二进制倒序数如图所示。图 形成倒序的树状图(N=)表列出了时以二进制数
40、表示的顺序数和倒序数，由表显而易见，只要将顺序数()的二进制位倒置，则得对应的二进制倒序值()。按这一规律，用硬件电路和汇编语言程序产生倒序数很容易。但用高级语言程序实现时，直接倒置二进制数位是不行的，因此必须找出产生倒序数的十进制运算规律。由表1可见，自然顺序数增加，是在顺序数的二进制数最低位加，向左进位。而倒序数则是在位二进制数最高位加，逢2向右进位。例如，在(000)最高位加1，则得(100)，而(100)最高位为1，所以最高位加要向次高位加进位，其实质是将最高位变为，再在次高位加。用这种算法，可以从当前任一倒序值求得下一个倒序值。表 顺序和倒序二进制数对照表顺序十进制数I二进制数倒序二
41、进制数十进制数0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 4 2 0 1 0 0 1 0 2 3 0 1 1 1 1 0 6 4 1 0 0 0 0 1 1 5 1 0 1 1 0 1 5 6 1 1 0 0 1 1 3 7 1 1 1 1 1 1 7 为了叙述方便，用J表示当前倒序书的十进制数值。对于N=，M位二进制数最高位的权值为N/2，且从左向右二进制位的权值依次为N/4，N/，2，1。因此，最高位加1相当于十进制运算J+N/2。如果最高位是0(JN/2)，则直接由J+N/2得下一个倒序值；如果最高位是1()，则要将最高位变成0()，次高位加1(J+N/4)。但次高位加1
42、时，同样要判断0、1值，如果0(JN/4)，则直接加1()，否则将次高位变成0()，再判断下一位；依次类推，直到完成最高位加，适向右进位的运算。图 倒序规律形成倒序J后，将原存储器中存放的输入序列重新按倒序排列。设原输入序列x(n)先按自然顺序存入数组A中。例如，对N=8，A(0)，A(1)，A(2)，A(7)中依次存放着x(0)，x(1)，x(7)。对x(n)的重新排序（倒序）规律如图所示。倒序的程序框图如图10所示，图中的虚线框内是完成计算倒序值的运算流程图。由图可见，第一个序列值x(0)和最后一个序列值x(N1)不需要重排；当I=J时不需要交换，所以图10中，顺序数I的起始、终止值分别为1和N；倒序数J的起始值为N/2。另外，为了避免再次调换前面已调换过的一
