摘要
随着电子技术和集成电路技术的飞速发展，数字信号处理已广泛应用于语音、图像处理，通信和多媒体等领域中。傅立叶变换（DFT）作为其数字信号处理中的基本运算，发挥着重要作用。特别是快速傅立叶变换（FFT）算法的提出，减少了当N很大的时候DFT的运算量，使得数字信号处理的实现和应用变得更加容易，因此对FFT算法及其实现方法的研究具有很强的理论和现实意义，且实际价值不可估量。
本文主要探讨了基于FPGA数字信号处理的实现。首先详细阐述了数字信号处理的理论基础，重点讨论了傅立叶变换算法原理，由于快速傅立叶变换算法在实际中得到了广泛的应用，本文给出了基-2 FFT原理、讨论了按时间抽取FFT算法的特点。本论文对硬件描述语言的描述方法和风格做了一定的探讨，介绍了硬件描述语言的开发环境MAX+PLUSII。在此基础上，本论文详细阐述了数字集成系统的高层次设计方法，讨论了数字系统设计层次的划分和数字系统的自顶向下的设计方法，探讨了数字集成系统的系统级设计和寄存器传输级设计，描述了数字集成系统的高层次综合方法。最后本文描述了数字信号处理系统结构的实现方法，指出常见的高速、实时信号处理系统的四种结构：由于FFT算法在数字信号处理中占有重要的地位，所以本文提出了用FPGA实现FFT的一种设计思想，给出了总体实现框图:重点设计实现了FFT算法中的蝶形处理单元，采用了一种高效乘法器算法设计实现了蝶形处理单元中的旋转因子乘法器，从而提高了蝶形处理器的运算速度，降低了运算复杂度。
关键词：数字信号处理；VHDL语言；FPGA；FFT算法
Abstract
With the rapid development of electronic and integrate circuit technology,digital signal processing has been widely applied in various field, like speechingand graphing processing, communication, multimedia. DFT plays an important part in digital signal processing as a basic calculation. Especially, FFT algorithmreduces the calculation quantity when N is a little great, which makes it much easier for implement and application. It is strongly theory and real signification to research on the FFT algorithm and its method for design and its value cannot be computed.
The paper mainly probes into the realization of digital signal processing based on FPGA.At first the fundamental theory of digital signal processing and the DFT algorithm are expounds, then radix-2 FFT and the characteristic of DIT FFT are discussed.In this paper,the description method and style of hardware description language and its development environment MAX+PLUSII are detailed. On the basis of that,the high level design method of integrated digital system and the partition of disign level of digital system are discussed, the top-down design strategy and the high level synthesis method of digital system are also detailed. After doing that, the paper points out the universal architectures of the high-speed real-time signal processing system and describes how to implement them. Since FFT plays an important role in digital signal processing, implementing FFT with FPGA is presented and the total realization graph is designed. For improving speed and decreasing computing complexity, high efficiency multiplier algorithm is used to realizing twiddle factor multiplier of butterfly processing unit.
Key words：Digital Signal Processing;VHDL;FPGA;FFT Algorithm
目录
第1章绪论 (1)
1.1 数字信号处理概述 (1)
1.2 FPGA简介 (2)
1.3 FFT算法的发展 (3)
1.4 用FPGA实现数字信号处理的特点 (4)
1.5 本文的主要工作 (5)
第2章数字信号处理的理论基础 (7)
2.1 离散傅立叶变换 (7)
2.1.1 傅立叶变换的几种形式 (7)
2.1.2 离散傅立叶变换算法 (8)
2.2 快速傅立叶变换 (9)
2.2.1 FFT算法基本思想 (9)
2.2.2 按时间抽取基-2FFT算法 (10)
2.2.3 按时间抽取FFT算法的特点 (11)
第3章硬件描述语言及MAX+PLUSⅡ平台 (14)
3.1 硬件描述语言（HDL） (14)
3.1.1 HDL概述 (14)
3.1.2 HDL设计方法 (14)
3.2 VHDL语言 (16)
3.2.1 VHDL语言简介 (16)
3.2.2 VHDL的优点 (16)
3.2.3 VHDL设计特点 (17)
3.2.4 VHDL基本设计流程 (18)
3.2.5 VHDL设计单元模型 (18)
3.2.6 VHDL语言中顺序执行语句和并行执行语句 (22)
3.3 VHDL语言开发环境MAX+PLUSⅡ介绍 (24)
第4章用FPGA实现数字信号处理算法 (26)
4.1 数字信号处理的系统结构的实现方法 (26)
4.2 基于FPGA的FFT算法实现 (28)
4.2.1 FFT处理器的实现框图 (28)
4.2.2 复数乘法器的实现 (29)
4.2.3 蝶形运算单元的实现 (31)
4.2.4 数据存储单元RAM的实现 (32)
4.2.5 旋转因子存储器ROM的实现 (33)
4.2.6 控制单元的设计 (34)
4.3 小结 (34)
第5章结论 (35)
参考文献 (37)
致谢 (39)
附录 (40)
第1章 绪 论
1.1 数字信号处理概述
数字信号处理是利用计算机或专专用处理设备，以数字形式对信号进行采
集、变换、滤波、估值、增强、压缩、识别等处理，以得到符合需要的信号形式。
数字信号处理技术的实质就是将模拟信号或我们现实生活中的一些信号转化为数
字信号并对转换后的数字信号进行相应的处理。
字信号处理是从20世纪60年代以来，随着信息科学和计算机学科的高速发
展而迅速发展起来的一门新兴学科。70年代以来，随着电子计算机、大规模集成
电路、超大规模集成电路以及微处理器技术的迅猛发展，数字信号处理得到了飞
速的发展，它的重要性日益在各个领域的应用中表现出来。
图1.1给出了数字信号处理系统的简化框图。此系统先将模拟信号变换为数
字信号，经数字信号处理后，再变换成模拟信号输出。其中抗混叠滤波器的作用，
是将输入信号()x t 中高于折叠频率（其值等于采样频率的一半）的分量滤除，以
防信号频谱的混叠。随后，信号经采样和A/D 变换后，变成数字信号()x n 。数字
信号处理器对()x n 进行处理，得到输出数字信号()y n ，经D/A 变换器转换成模
拟信号，此信号经低通滤波器，滤除不需要的高频分量，最后输出平滑的模拟信
号()y t 。
图1.1 数字信号处理系统简化框图
数字信号处理与模拟信号处理相比具有如下优点：
1.数字信号在处理过程中更加稳定
数字信号参数不象模拟信号参数那样容易受电阻、电容、运算放大器或是温
度变化的影响。一个数字系统也很少受器件使用时间的影响，所以数字系统要比
模拟系统稳定得多。这保证了应用系统的稳定性以及较长的使用寿命。
2.数字信号处理系统的可预见性
当一个数字信号处理系统设计完成后，我们可以通过仿真或是其它手段直接
看到结果，而且这与最终应用中出现的情况是一样的：同时，所有拷贝的数字信号处理系统间是没有性能差别的。
3.特殊功能
数字信号处理可以完成许多模拟信号处理所达不到的功能，如线性相位响应，还有一些模拟信号不能处理的问题如无损压缩、纠错编码等。
4.性和可编程能力
数字信号处理具有极强的适应能力，可以在多种领域内应用。同时，数字信号处理的设计也相对简单，并且可以根据不同的应用迅速对设计进行改进或重新设计。
5.成本低廉
数字信号处理器多通过超大规模集成电路实现，相对使用大量的模拟器件完成同一任务来讲，数字信号处理器的成本是很低的。
由于数字信号处理具有以上优点，数字信号处理在现实生活中得到了广泛的应用。目前，数字信号处理技术已广泛应用于数字通信、语音合成、图像处理、多媒体技术、高清晰度电视、数字音响、以及机器人等各个领域。
1.2FPGA简介
可编程逻辑阵列器件是可以由用户进行编程以实现所需逻辑功能的数字集成电路，利用其内部的逻辑结构实现任何布尔表达式、寄存器函数。和一般的ASIC 电路相比，可编程逻辑阵列器件具有设计周期短，修改方便的优点。
现场可编程门阵列FPGA是八十年代中期出现的新型高密度可编程逻辑器件，它是在PAL、GAL、EPLD等可编程器件的基础上进一步发展的产物。通过编程可以立刻把一个通用的FPGA芯片配置成用户需要的硬件数字电路，因而大大加快电子产品的研发周期，降低研发成本，缩短产品上市时间。FPGA具有高密度（一个器件内部可用逻辑门可达数万门），运行速度快（管脚间的延时小，仅几个ns）的特点。用它来设计数字电路可以简化系统设计，缩小数据规模，提高系统的稳定性。ALTERA公司的FPGA器件FLEX 10K 器件内含随机静态存储器，方便数据的暂时存储。
FPGA兼有串、并行工作方式和高集成度、高速、高可靠性等明显的特点，其时钟延迟可达纳秒级，同时，在基于芯片的设计中可以减少芯片数量，缩小系统体积，降低能源消耗，提高系统的性能指标和可靠性。正是由于FPGA具有这些优点，FPGA在超高速应用领域和实时测控方面有非常广阔的应用前景。在高可靠应用领域，如果设计得当，将不会存在类似于MCU的复位不可靠和PC可能
跑飞等问题。FPGA 的高可靠性还表现在，几乎可将整个系统下载于同一芯片中，
实现所谓片上系统，从而大大缩小了体积。与AMU 设计相比，FPGA 显著的优
势是开发周期短，投资风险小、产品上市速度快，市场适应能力强和硬件升级回
旋硕士学位论文余地大，而且当产品定型和产量扩大后，可将在生产中达到充分
检验的VHDL 设计迅速实现ASIC 投产。
随着大规模现场可编程逻辑器件的发展，系统设计进入“片上可编程系统”
（SOPC ）的新纪元；芯片朝着高密度、低压、低功耗方向挺进：在SOC 芯片上
可以将微处理器、数字信号处理器、存储器、逻辑电路、模拟电路集成在一个芯
片上。而如果将可编程逻辑电路IP 核集成到SOC 芯片上则会大大提高SOC 芯片
的灵活性与有效性，并且缩短了SOC 芯片的设计周期。因此国际各大公司都在积
极扩充其IP 库，以优化的资源更好的满足用户的需求，扩大市场。
由此可见，FPGA 不仅可以解决电子系统小型化、低功耗、高可靠性等问题，
而且其开发周期短、开发软件投入少、芯片价格不断降低，这使得FPGA 占有越
来越多的市场，特别是对小批量、多品种的产品需求，使FPGA 成为首选。FPGA
普及的另一重要原因是IP （知识产权）越来越被高度重视，带有IP 内核的功能
块在ASIC 设计平台上的应用日益广泛。越来越多的设计人员，采用设计重用，
将系统设计模块化，为设计带来了快捷和方便。并可以使每个设计人员充分利用
软件代码，提高开发效率，减少上市时间，降低研发费用，缩短研发周期，降低
风险。
1.3 FFT 算法的发展
DFT 在信号的频谱分析、系统分析、设计和实现中得到了广泛的应用，原因
之一就是计算DFT 有很多的快速算法，从快速计算DFT 的理论观点看，这些快
速计算DFT 的方法大概可以分为两类。
一类是递归型算法，是将一维DFT 转化为容易计算的二维或多维DFT,其代
表算法Cooley-Tukey 算法，Rader-Brenner 算法等。例如，分裂基算法、基2、基
4、基8、基16及任意组合因子等的组合数FFT 算法，利用nk N W
的周期性和对称性，使长序列的DFT 分解为更小点数的DFT ，从而大大减少了运算工作量，共
同特点是每两级DFF 之间需要乘以旋转因子。
另一类是将DFT 转变为卷积，利用计算卷积的方法计算，其代表是Winograd
傅立叶变换算法（WFTA ）和素因子（FPA ）。这种算法是根据Good-Thomas 提出
的索引变换，将一个长度12N N N 的DFT 变换成“实际的”二维DFT ，也就是
说没有Cooley-Tukey 中的旋转因子。只要索引映射计算是在线进行的，而且没有
预先计算好的表可以使用，那么索引映射就会变得更加复杂。
目前，FFT已广泛应用在无线通信、语音识别、图像处理和频谱分析等领域。在不同应用场合，需要不同性能要求的FFT处理器，特别是随着OFDM（正交频分复用）技术的出现，FFT作为OFDM系统中调制解调的关键，如何更快速、更灵活地实现FFT变得越来越重要。
到现在为止，FFI的理论研究已经趋于成熟，但是随着通讯技术的飞速发展，很多场合需要快速、高性能的FFT处理器，且随着大容量、高速芯片的出现，自己研发高性能的FFT处理器成为可能，速度可以大大的提高，因此很多人在自己研究的课题领域，对它进行了大量的研究，通过选用不同的硬件，在综合考虑硬件特性和满足系统的前提下，对FFI处理器的流程、算法进行进一步的优化处理，使它的处理速度能有所提高。
1.4用FPGA实现数字信号处理的特点
早期的FPGA设计大都是使用FPGA供应商提供的设计软件工具，进行门级设计。而本文的一个特点是首先采用VHDL语言进行电路描述，然后使用高层次的EDA综合工具进行综合，最后使用FPGA供应商提供的布局布线工具进行布局布线。要求在系统设计、综合技巧等方面就要考虑FPGA的特点。在代码设计时，遵从VHDL描述一系统仿真一系统综合一FPGA实现这一高层次设计方法来完成系统的设计与实现。
FPGA实现数字信号处理最显著的特点就是高速性能好。
以软件方式控制操作和运算的系统速度显然无法与纯硬件系统相比，因为软件是通过顺序执行指令的方式来完成控制和运算步骤的，而用HDL语言描述的系统是以并行方式工作的。以对A/D进行数据采样控制为例，采样周期包括对A/D工作时序的控制和将每一次获得的数据存入RAM（或FIFO）中。工作于12MHz晶振频率的MCS-51系列单片机对A/D控制的采样频率为20KHz上下，即约每秒两万次。但若用FPGA中设计的状态机来完成同样的工作，如对于具有流水线采样工作时序的A/D来说，只需两个状态即可完成一次采样，状态间转换的时间仅为一个时钟周期，而如果FPGA的工作频率是100MHz，则采样频率可达50MHz。
这在算法方面同样具有巨大的优势。这里以数字滤波器的设计为例作一比较：
表1.1FPGA和DSP芯片实现FIR滤波器的速度对比
从表1.1可以看出，用FPGA实现32阶8位FIR滤波器的处理速度为105MSPS 时，用DSP芯片实现的滤波器要达到相当速度，则需要指令执行速度为3360MIPS。
然而目前还没有如此高速的单处理器的DSP芯片。由此可见，在一些DSP 芯片不能满足数字信号处理要求的场合，可以采用FPGA来完成数字信号处理。
综上所述，与ASIC和通用DSP相比，FPGA器件能够以高速、实时、低成本、高灵活性的优点应用于数字信号处理领域，利用FPGA实现数字信号处理成为数字信号处理领域的一种新的趋势，它可以完全取代通用DSP芯片或作为通用DSP芯片的协处理器进行工作。如果将通用处理器和FPGA融合在一起，把需要多个时钟周期的运算交给FPGA完成，DSP芯片主要完成单时钟的运算和控制FPGA的“可再配置计算”功能，会更好地将两者的优势发挥出来。
1.5本文的主要工作
在广泛阅读文献资料的基础上，分析了基2FFT，算法的原理与特性。对FFT 算法实现的方式和结构进行了深入的研究，特别对FFT，处理过程中数据的通信进行了研究和分析.整个设计采用了先进的结构化设计思想，针对基-2算法，设计了一种FFT实现方法，主要内容如下：
第一章绪论部分，概要地叙述了数字信号处理的定义以及数字信号处理系统的简化框图，指出了数字信号处理的几种常用方案，简要地介绍了FPGA，就FPGA 实现数字信号处理的特点进行了描述。
第二章就数字信号处理的理论基础进行了探讨，首先介绍了傅立叶变换的几种形式，重点探讨了离散傅立叶变换算法原理。由于快速傅立叶变换算法在实际中得到了广泛的应用，本章描述了快速傅立叶变换算法基本思想，给出了按时间抽取基-2 FFT算法实现原理。最后讨论了按时间抽取FFT算法的特点。
第三章首先介绍了硬件描述语言及其设计方法，其次介绍硬件描述语言中的VHDL语言及其设计优点、设计特点及组成，最后介绍了硬件描述语言的开发环境MAX+PLUSII。
第四章本文提出了用FPGA实现数字信号处理的一种设计思想，首先就数字信号处理系统结构的实现方法进行了描述，指出常见的高速、实时信号处理系统的四种结构，给出了总体实现框图，重点设计实现了FFT算法中的蝶形处理单元，采用了一种高效乘法器算法设计实现了蝶形处理单元中的旋转因子乘法器。
第2章 数字信号处理的理论基础
2.1 离散傅立叶变换
2.1.1 傅立叶变换的几种形式
傅立叶变换是信号分析和处理的有力工具，在以快速傅立叶变换算法为代表的一系列有效算法出现后，傅立叶变换不但在信号处理领域起着支柱作用，而且在其它工程领域也获得了广泛的应用。
根据信号的连续性、离散性、周期性、非周期性，傅立叶变换可以分为四种不同的形式，形成四种不同的傅立叶变换对，以下分别予以描述。
一．连续时间非周期信号
连续时间非周期信号()x t 在频域中得到的是连续非周期的频谱密度函数()X jw ，傅立叶变换对如下：
()()j w t X j w x t d t e +∞--∞=
? （2-1） ()()1
2j w t
x t X j w d w e π+∞-∞=? （2-2）
这种类型信号的典型信号有指数衰减信号和高斯信号，这种类型信号的变换就称为傅立叶变换。
二．连续时间周期信号
连续时间周期信号()x t 当满足狄里赫利条件时在频域中得到的是离散非周期的傅立叶级数，傅立叶级数的系数为()X jkw ，()X jkw 为离散非周期函数，()x t 和()X jkw 组成的变换对如下：
()()1T j k w t T X j k w x t d t T e --=
? （2-3）
()()j k w t k x t X j k w e ∞=-∞=∑ （2-4）
这种类型信号的典型信号有正弦信号和周期方波信号，这种类型信号的傅立叶变换就称为傅立叶级数。
三．离散时间非周期信号
离散时间非周期信号()x n 也称为序列，序列的傅立叶变换对如下所示：
()()j t jn T n X x nT e e
∞Ω-Ω=-∞=
∑ （2-5）
()()221j T jn T x nT X d e e ΩΩΩ-Ω=ΩΩ? （2-6）
这种信号的傅立叶变换称为离散时间傅立叶变换
四．离散时间周期信号
离散时间周期信号的傅立叶变换有时称为傅立叶级数，但最常被称为离散傅立叶变换。
2.1.2 离散傅立叶变换算法
上面讨论的四种傅立叶变换对前三种由于至少在时域或频域是离散的，都不适于在计算机上运行。然而、现实世界中的声音图像等各种信号大都为模拟信号，要用计算机对这些信号进行数字信号处理，这些信号必须通过采样量化编码变成有限长的数字信号序列。
对于有限长序列，可以得出另外一种傅立叶表示，称为离散傅立叶变换(DFT)。离散傅立叶变换本身是一个序列，而不是一个连续变量的函数，它相应于对信号的傅立叶变换进行频率的等间隔取样的样本。因为存在着计算DFT 的高效算法，作为序列的傅立叶表示，DFT 除了在理论上十分重要外，在实现各种数字信号处理算法中还起着核心作用。
离散傅里叶变换描述分析有限长序列，其本质是建立了以时间为自变量的信号与以频率为自变量的频谱函数之间的变换关系，换言之，离散傅里叶变换定义了时域与频域之间的一种变换或者说是映射。对于DFT 时间和频率变量都取离散值。
下面讨论一下有限长序列的离散傅立叶变换。
对于一个长度为N 的有限长序列()x n ，亦即只在0n =到()1n -个点上为非零值，其余皆为零，我们可以把它看成周期为N 的周期序列()x n 中的一个周期
即
当01n N ≤≤-， ()()x n x n =
当n 为其它值， ()0x n =。
其中()()r x n x n rN ∞=-∞=
+∑ （2-7）
从而有限长序列的傅立叶变换定义为 正变换： ()()()1
0N nk N n X k DFT x n x n W -===????∑ 01k N ≤≤-
（2-8） 反变换： ()()()101N nk
N n x n IDFT X k X k N W --===????∑ 01n N ≤≤- （2-9） 其中，2nk jkn N N W e π-=
由此可见，离散傅立叶变换开辟了频域离散化的道路，使数字信号处理也可以在频域上采用数字运算方法进行，它可以作为一种数学工具来描述离散信号的时域和频域表示的关系，大大增加了数字信号处理的灵活性，特别是它的多种快速算法，使信号的实时处理和设备的简化得以实现，所以离散傅立叶变换不仅在理论上有重要意义，而且在各种数字信号处理中起着核心的作用。
2.2 快速傅立叶变换
对于式（2.8）DFT 的直接计算法。若()x n 为复数的话，则计算DFT 每一个值就需要N 次复数乘法和()1N -次复数加法。因此计算全部的N 个值总共需要
2N 次复数乘法和()1N N -次复数加法。
而每一个复数乘法需要4次实数乘法和2次实数加法。所以，对于每一个k 值，直接计算()X k 就需要42N 次实数乘法和()221N N -次实数加法。除了这些运算量外，通用计算机或专用硬件来做DFT 数字计算还需要存储和读取N 个复数输入序列值()x n 以及复系数nk N W
值的设备。由于计算的总次数以及所需的时间大致上正比于2N ，显然当N 值很大时直
接计算DFT 所需要的算术运算的次数就非常大。 可见，离散傅里叶变换算法实现了频域离散化，在数字信号处理中起着极其重要的作用，它可以直接用来分析信号的频谱、计算滤波器频率响应、以及实现信号通过线性系统的卷积运算。但对于N 点DFT 运算总共需要42N 次实数乘法和()221N N -次实数加法，这样庞大的运算量使得DFT 的实际应用特别是实时处理难以实现，直到1965年库利和图基首次提出了计算DFT 的一种快速算法，人们开始认识到DFT 运算的一些内在规律，发展和完善了一套高效的运算方法，DFT 的运算在实际中才得到广泛的应用。
继CooleyTukey 算法以后，SandeTukey 等快速算法相继出现，很快形成了一套高效运算方法，这就是现在的通用快速傅里叶变换，简称为FFT 。这种方法使复数乘法的次数从2N 次减少到了20.5log N N 次。如1024N =时运算量从1048576次减少到5120次，运算效率提高了204.8倍，为DFT 乃至数字信号处理技术的实际应用特别是实时处理创造了良好的条件，大大地推动了数字信号处理技术的发展。所以实际工程中用到的都是DFT 的快速算法：快速傅里叶变换（FFT ）。
2.2.1 FFT 算法基本思想
FFT 算法的基本思想：可以将一个长度为N 的序列的离散傅里叶变换逐次分解为较短的离散傅里叶变换来计算，这些短序列的DFT 可重新组合成原序列的DFT ，而总的运算次数却比直接的DFT 运算少得多，从而达到提高速度的目的。
快速傅立叶变换就是利用N 的特性，逐步地将N 点序列分解成较短的序
列，计算短序列的DFT ，然后组合成原序列的DFT ，使运算量显著减少。这种分解基本上可分为两类，一类是将时间序列()x n 进行逐次分解，称为按时间抽取算法（Decimation In Time ）；另一类将傅立叶变换序列()X k 进行分解，称为按频率抽取算法（Decimation In Frenquency ）。本文主要介绍T 按时间抽取基-2FFT 算法。
2.2.2 按时间抽取基-2FFT 算法
我们已经知道FFT 算法主要是利用nk N W 的性质，通过把序列逐渐分解为短序列实现运算量的减少。nk N W
的以下三种性质在FFT 运算中得到了应用： 性质1：nk N W
的周期性 ()n k n k N N N W W += 性质2：nk N W
的对称性 ()nk nk N N W W ?-= 性质3：nk N W
的可约性 nk mnk N mN W W =， nk nk m N N m W W = 由于目前FFT 比较普遍使用的算法还是基二算法，本节将讨论基二的按时间
抽取算法。
基二算法中，序列()x n 的长度N 为2的整数次幂，即2M N =，其中M 为正整数。最初通过将()X n 分解为奇数项序列和偶数项序列的形式使FFT 运算分为两组。
设： ()()12x r x r =
()()221x r x r =+ 0,1,...,12N r =- （2.10） 设()1X k 为()1x r 的DFT ，()2X k 为()2x r 的DFT ，利用nk N W
的性质可得()
x n 的DFT 运算为： ()()()()()12122k N k N X k X k X k N X k X k X k W W ?=+????+=-? ??
?? 0,1,...,12N k =- （2-11） 上面式子的运算可用下图的蝶形信号流图符号表示：
图2.1 时间抽取算法蝶形运算图
由此可见，一个N 点DFT 分解为两个2N 点的DFT
，从而实现了运算量的
减少，再经过逐次分解最终分解为
特点1：同址运算
由图2.2看出，对于长度为N 的序列，每一级计算均需要一组N 个复数，并通过图 2.1形式的基本蝶形把它们变换为下一组的N 个复数，这种过程重复2log N 次，最后得到所要求的离散傅立叶变换。当实现图2.2中描述的运算时，
我们可以想象使用两列（复数的）存贮寄存器，一列存贮要计算的数，另一列存贮计算中要用到的数据。例如，当计算图2.2中的第一列时，第一组存贮寄存器应当存放输入数据，而第二组存贮寄存器应当存放第一级计算出的结果。把第m 级计算得出的复数序列记作[]m X n ，其中0,1,...,1n N =-，把从第m 级输入的复数序列记作[]o X n 。对于第m 级计算，可以认为[]1m X n -是输入列，[]m X n 是输出列。这样，对于图2.2中所示的8N =的情况，有
[][]00o X x =
[][]14o X x =
[][]22o X x =
[][]36o X x =
[][]41o X x = （2-12）
[][]55o X x =
[][]63o X x =
[][]77o X x =
利用这种表示法，可将图2.1中蝶形计算的输入和输出标记为图2.3所示的那样，并有相应的方程
[][][]11nk
m m m N X p X p X q W --=+ （2-13 a ） [][][]11nk m m m N X q X p X q W --=- （2-13 b ）
图2.3 式（2.11）的流图 在式(2.11)中，p ，q 和r 从一级到另一级是不同的，从图2.2和图2.3中可以清楚地看出，要计算第m 列的p 和q 位置上的复数节点值，只需要第(m-1)列在p 和q 位置上的复数节点值。因此，若将[]m X p 和[]m X q 分别存放在原存放[]1m X p -和[]1m X q -的同一存贮寄存器中，则实现全部计算实际上只需要一列存贮N 个复数的寄存器。这种计算通常称为同址计算。
由此可见，采用同址运算只需N 个存储单元，大大节省了存储单元，从而降低了设计成本。
特点2：倒位序规律
为了实现同址计算，输入序列不能按照原来的先后顺序存贮（或至少不能这样读取），而应如图2.2的流图那样，实际上，这种输入数据存贮和读取的顺序称为倒位序。我们注意到，对于已经讨论过的8点流图，只需要用三位二进制码来标注整个数据。如果用二进制形式写出式（2.10）中的标号，就得到如下一组式子：
[][]000000o X x =
[][]001100o X x =
[][]010010o X x =
[][]011110o X x =
[][]100001o X x = （2.14）
[][]101101o X x =
[][]110011o X x =
[][]111111o X x =
若210(,,)n n n 为序列[]x n 中标号的二进制表示，则序列值[]210,,x n n n 存放在数列[]0012,,X n n n 的位置上。也就是说，要确定[]210,,x n n n 在输入序列中的位置，我们必须将标号n 的位序颠倒。
表 2.1给出了8N =时的自然顺序二进制数以及相应的倒位序二进制数。
表2.1码位的倒位序
实际运算中，总是先按自然顺序将输入序列存入存储单元，要实现FFT 算法，首先将按自然顺序存放的序列经变址运算变换得到倒位序的排列。
第3章硬件描述语言及MAX+PLUSⅡ平台
3.1硬件描述语言（HDL）
3.1.1HDL概述
硬件描述语言（HDL）是相对于一般的计算机软件语言如C，PASCAL而言的。硬件描述语言HDL是一种用形式化方法描述数字电路和系统的语言，它描述电子系统的逻辑功能、电路结构和连接方式。利用这种语言，数字电路系统的设计可以从上层到下层（从抽象到具体）逐层描述自己的设计思想，用一系列分层次的模块来表示极其复杂的数字系统。然后，利用电子设计自动化（EDA）工具，逐层进行仿真验证，再把其中需要变为实际电路的模块组合，经过自动综合工具转换到门级电路网表。接下去，再用专用集成电路ASIC或现场可编程门阵列FPGA自动布局布线工具，把网表转换为要实现的具体电路布线结构。
硬件描述语言具有以下几个优点：
（1）设计技术齐全，方法灵活；
（2）加快了硬件电路的设计周期，降低了硬件电路的设计难度；
（3）采用系统早期仿真，在系统设计早期就可发现并排除存在的问题；
（4）语言设计可与工艺技术无关；
（5）语言标准、规范，易共享和复用。
目前，采用硬件描述语言进行数字系统的设计己被广泛采用。据统计，目前在美国硅谷约有90%以上的ASIC和FPGA采用硬件描述语言进行设计。
硬件描述语言HDL的发展至今已有20多年的历史，并成功地应用于设计的各个阶段:建模、仿真、验证和综合等。到20世纪80年代，已出现了上百种硬件描述语言，对设计自动化曾起到了极大的促进和推动作用。但是，这些语言一般各自面向特定的设计领域和层次，而且众多的语言使用户无所适从。因此，急需一种面向设计的多领域、多层次并得到普遍认同的标准硬件描述语言。20世纪80年代后期，VHDL和Verilog HDL语言适应了这种趋势的要求，先后成为IEEE 标准。就FPGA/CPLD开发而言，VHDL语言是最常用和流行的硬件描述语言之一，在数字信号处理的FPGA设计中得到了广泛的使用。
3.1.2HDL设计方法
HDL设计方法基本上包含3方面：
（1）设计描述的开发，这种描述必须是有效的；
（2）综合，将设计描述转换成优化的门级表示，目前的综合工具只是将输入的寄存器传输级(RTL)的HDL 描述转换为门级的网表，再由门级的网表实现互连的门级宏单元结构。因为厂家所支持的各个工艺库中有门级宏单元模块，所以有了门级网表就能按照技术条件进行优化，得到一个优化了的门级结构；
（3）对设计加以验证。
硬件描述语言RTL 级设计的流程框图如图3.1所示，其中的综合部分是HDL 设计方法中的关键。
图3.1 HDL 设计方法流程框图
HDL 综合设计方法优点如下：
（1）提高设计效率：设计者不需人工进行门级描述，节省了设计时间；
（2）设计是在较高的抽象层次上进行，设计者不用更多地考虑门级，可花费更多的时间考虑概念级方面；
综合
（3）利用HDL具有的自动优化和快速探索各种设计方案的能力，可使设计者迅速而成功地得到高质量设计的最终结果，从而改善了设计质量；
（4）设计与工艺无关，便于设计的再利用。
3.2VHDL语言
3.2.1VHDL语言简介
VHDL的英文全名是Very-High-Speed Integrated Circuit Hardware Description Language（超高速集成电路硬件描述语言)，VHDL语言是美国国防部资助的VHSIC（Very High Speed Integrated Circuit超高速集成电路）项目开发的产品，诞生于1982年。1987年底VHDL被IEEE和美国国防部确认为标准硬件描述语言。自IEEE公布了VHDL的标准版本（IEEE std 1076-1987）之后，各EDA公司相继推出了自己的VHDL设计环境。此后，VHDL在电子设计领域受到了广泛的接受，并逐步取代了原有的非标准HDL。1993年，IEEE对VHDL进行了修订，从更高的抽象层次和系统描述能力上扩展VHDL的内容，公布了新版本的VHDL，即ANSI/IEEE std 1076-1993版本。1996年IEEE 1076.3成为VHDL综合标准。
VHDL主要用于描述数字系统的结构、行为、功能和接口，非常适用于可编程逻辑芯片的应用设计。与其它的HDL相比，VHDL具有更强的行为描述能力，从而决定了它成为系统设计领域最佳的硬件描述语言。强大的行为描述能力是避开具体的器件结构，从逻辑行为上描述和设计大规模电子系统的重要保证。就目前流行的EDA工具和VHDL综合器而言，将基于抽象的行为描述风格的VHDL 程序综合成为具体的FPGA和CPLD等目标器件的网表文件已不成问题。
VHDL语言可以支持自上而下和基于库的设计方法，并支持同步电路、异步电路、FPGA以及其它随机电路的设计。目前大多数EDA工具几乎在不同程度上都支持VHDL语言。这给VHDL语言进一步推广和应用创造了良好的环境。VHDL 具有多层次描述系统硬件功能的能力，可以描述系统模型直到门级电路。
VHDL语言在硬件设计领域的作用将与C和C++在软件设计领域的作用一样，在大规模数字系统的设计中，它将逐步取代如逻辑状态表和逻辑电路图等级别较低的繁琐的硬件描述方法，而成为主要的硬件描述工具，它将成为数字系统设计领域中所有技术人员必须掌握的一种语言。VHDL和可编程逻辑器件的结合成为一种强有力的设计方式，将为设计者的产品上市带来创记录的速度。
3.2.2VHDL的优点
VHDL是一种全方位的硬件描述语言，包括系统行为级、寄存器传输级和逻