基4FFT算法的FPGA实现.ppt

1、基4FFT算法的FPGA实现,FFT是快速的傅立叶变换，它不是一种新的变换，是人们意识到DFT（离散傅立叶变换）运算的一些内在的规律，从而很快发展和完善的一套高速有效的运算方法。 在进行高速实时的数字信号处理过程中，FFT运算是很耗时的，因此本文提出了基于FPGA的基-4FFT算法的实现，随着带硬件乘法器的FPGA越来越普遍，用硬件来代替软件的今天，用FPGA实现FFT，提高了运算速度，缩短了计算时间。,传统基2FFT的算法,以按时间抽取基2算法为例： 设N（N= ） 为正整数， A 、B 为时间序列， A 、B 为频率序列， 为旋转因子，如右图1 可知其基本迭代运算为：,（1-1）,设 则代

2、入 （1-1）式得： 由1-1式可以看出来基2按时间抽取的FFT蝶形单元运 算需要一次复数乘法运算、两次复数加（减）法运算 由1-2式可以看出4次实数乘法运算和6次实数加（减)法运算。 传统的基-2对于 个点,有 次迭代运算, 每次迭代运算包含N/2个蝶形单元。,（1-2）,基-4算法原理,我们也同样采用按时间抽取的方式讲解基-4算 法的蝶形单元。 设A、B 、C 、D 为时间序列，A、B、C、D 为频率序列， 为旋转因子，则蝶形 单元运算表达式为式1-3：,（1-3）,基-4蝶形单元信号流图如下：,图 1-2 基-4单元信号流图,由1-3式可以看出，基-4蝶形单元需要三个复数 乘法器及十二个

3、复数加法（减）器，而且对于 N= 有 次迭代运算，每次迭代运算 包含N/4次蝶形运算，每个基-4的蝶形单元与四个 基-2蝶形相比较，减少一次复数乘法，在相同N点 的FFT运算过程中，基-4运算的迭代运算和每次迭 代包含的蝶形单元要少于基-2FFT算法，可以看出 基-4算法的研究可以大大提高FFT运算的速度，更 加发挥FFT运算快的优势 。,基-4算法的模块实现,FFT模块的构成： 1：旋转因子乘法器；2：基-4蝶形运算器； 3：地址产生器； 4：控制信号产生器 5：中间变量存放组 本文设计的FFT模块的划分图如图1-3,图中 各个模块在中央控制单元的管理下并行工作。,图 1-3 FFT实现框图

4、,在图1-3中，运算模块为基-4运算模块，控制模块产生 所有的控制信号、存储器1和2的读写地址、写使能、 运算模块的启动信号因子表的读写地址等信号。,存储器1作为当前输入标志对应输入N点数据缓 冲器，存储器2作为中间变量结果存储器，用于 存储运算模块计算出各个通道的结果。 举例：外部输入为N点数据段流和启动信号，一方 面，外部数据存入存储器1中，同时通过控制模块的 控制，读出存储器1中的前段N点数据和ROM表中的 因子及相关控制信号送入运算核心模块进行各个Pass 运算,每个Pass运算的输出都存入存储器2中，最后一个 Pass的计算结果存入存储器2中，启动并在下一个启动 头到来后，输出计算结

5、果。,FFT硬件实现,1：旋转因子乘法器的实现 FFT设计一个旋转因子存储单元可以提高FFT的 计算速度，因此需要合理的设计旋转因子的存 储单元，在FFT硬件设计中占重要地位。本文采用 一种高效的算法来实现存储旋转因子。 设复数旋转因子乘法器R+ jI=(X+ jY) (C+ jS) 因为C、S可以预先计算的，并可以存储在一个表 中。所以我们可以存储下面三个系数： C、C+S、C-S,有了这3个预先计算的因子，我们可以首先计算： E=X-Y和Z=C*E=C*（X-Y） 然后用： R=（C-S）*Y+Z I=（C+S)*X-Z 计算最后乘积，我们可以验证这种算法的 正确性： R=（C-S）*Y+

6、Z=（C-S）*Y+C（X-Y） =CY-SY+CX-CY=CX-SY,I=（C+S）*X-Z=（C-Z）*X-C（X-Y） =CX+SX-CX+CY=SX+C 该运算只需要将C、C+S、C-S三个系数存在 表中，在通过查表计算出旋转因子的实部和虚 部，选用一个地址发生器来通过调用不同的地 址来调用旋转因子的实部和虚部。 本文设计了一个512*16的ROM，如图1-4，把C、 C+S、C-S，分别存储在ROM中，这样蝶形单 元运算就可以直接调用旋转因子实部和虚部， 大大提高了FFT运算速度。,图 1-4 旋转因子存储器,2：蝶形运算单元设计： 已知基-4的蝶形单元运算如式1-3，设式1-3的

7、复数数据为： 并将其代入1-3式，按以上数据我设计了三个 模块单元，他们分别是： 则在Quartus中设计的模块图如图1-5,图 1-5 单元4_fft模块图,使用4_fft模块并按照将复数数据代入1-3式可搭建单元蝶形图，其模块图如图1-6,图1-6 蝶形单元设计图,小结,本文通过设计一种基于FPGA的基-4的FFT，探讨 FPGA在实现FFT算法中的应用。本文重点设计了采用 一种旋转因子存储器搭建基-4FFT蝶形模块，实现蝶 形运算单元。本系统最大的优势在于利用FPGA丰富逻 辑资源，及其灵活的可编程特性使运算速度较传统方 法有了很大提高。 用FPGA实现基-4FFT可以获得高性能，满足成本 要求，并享有快速有效地对新设计进行优化