2005年第 2期
研究与开发
RESEARCH & D EVELO PM ENT
文章编号 : 1001 - 893X (2005) 02 - 0188 - 04
基于 FPGA的高速高阶流水线工作 FFT
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
3
邓学禹
(电子科技大学 电子工程学院 ,四川 成都 610054)
摘 要 :为了提高快速傅里叶变换 ( FFT)处理数据的实时性 ,本文利用现场可编程阵列 ( FPGA )逻辑
资源丰富、运算速度快的特点以及 FFT算法的分级特性 ,实现了高速、高阶 FFT的流水线工作方式
设计。通过本文介绍的设计方法 ,在 Xilinx公司 V irtex
-
II系列 FPGA上实现了工作频率 50 MHz以
上、数据流水输入、输出的 1 024点按时间抽取 FFT。
关键词 :数字信号处理 ;流水线 ;按时间抽取 ;快速傅里叶变换
中图分类号 : TN911172 文献标识码 : A
High - speed and High - order Assembly L ine
FFT Design Based on FPGA
D EN G Xue - yu
( School of Electronic Engineering, University of Electronic Science and Technology
of China, Chengdu 610054, China)
Abstract: To imp rove the ability of FFT’s ( Fast Fourier Transform) p rocessing data in real time, this paper
introduces a method to achieve high - speed, high - order and assembly - line FFT design based on FPGA
( Field Programmable Gate A rray) which has characteristic of high speed and p lenty of logical sources and
FFT’s grading. W ith this method, 1024 points FFT sampled by time order has been realized by using Xilinx’s
Virtex
-
I FPGA which has operation frequency above 50 MHz.
Key words:D igital signal p rocessing; A ssembly line; Samp led by time; FFT
一、引 言
现场可编程门阵列 ( FPGA )是 20世纪 80年代
中期出现的一种新型用户可编程器件 ,具有集成度
高、逻辑实现能力强、设计灵活等特点 ,有着 ASIC、
DSP所不能替代的优点 ,使得成为解决系统设计的
重要选择。快速傅里叶变换 ( FFT)技术广泛的应用
于语音处理、图像处理、雷达、通信、生物医学电子等
方面。
在实际应用中 ,对数字信号处理的实时性要求
越来越高 ,因此对数字信号处理系统的处理能力的
要求也越来越快。流水线工作方式是提高系统处理
能力的可行方法。本文介绍了基于 Xilinx V irtex - II
的 FPGA ,采用流水线工作方式实现高速、高阶按时
间抽取的固定系数 FFT。
二、按时间抽取的 FFT算法结构
快速傅里叶变换 ( FFT)利用三角函数的周期性
和对称性 ,使离散傅里叶变换 (DFT)的复数乘法运
算量从 N2 次减少到 N2 log2 N次。
DFT函数定义如下 :
·881·
3 收稿日期 : 2004 - 12 - 10
2005年第 2期
研究与开发
RESEARCH & D EVELO PM ENT
X ( k) = ∑
N - 1
n =0
x ( n)W nk n = 0, 1, 2, ⋯N - 1 (1)
8点基 2按时间抽取 FFT流程如图 1所示。
图 1 8点基 2按时间抽取 FFT流程图
三、基 2蝶形运算算法及高效
复数乘法器实现
FFT运算是一种蝶形运算。实际上 , FFT运算
就是反复进行蝶形运算。基 2按时间抽取算法的蝶
形运算
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
达式如下 :
xl ( i) = xl - 1 ( i) + xl - 1 ( k)W p (2)
xl ( k) = xl - 1 ( i) - xl - 1 ( i)W p (3)
式中 l表示迭代次数 , i、k为数据序列的标号 ,
构成一个结点对。由上可知 ,蝶形处理器由一个复
数加法、一个复数减法器和一个旋转因子的复数乘
法器组成 ,其中复数旋转因子乘法器可以采用高效
复数乘法器实现。
设
R + jI = (X + jY) 3 (C + jS ) (4)
Z = C3 (X - Y) (5)
则
R = (C - S ) 3 Y + Z (6)
I = (C + S ) 3 Y - Z (7)
因此高效复数乘法器可只用 3次实数乘法和 3
次加减法运算实现复数乘法 ,节约了系统资源。
四、FFT的流水线工作原理
FFT算法具有分级运算的结构 ,为了提高运算
速度 ,可以在每一级运算中采用单独的蝶形运算处
理器 ,形成流水线接力的工作线 ,以 N = 8的 FFT算
法为例 ,如图 2所示。
图 2 N = 8时 FFT流水线工作示意图
由图 2可知 ,完成 N = 8点 FFT运算需要三级流
水线。信号输入时 ,必须将前 N /2个数据存在第一
级存储器中 ,算完后将数据送入第二级存储器 ,这样
在第二组 8点到来以前 ,第一级运算器正好完成第
一组信号的全部运算 ,第二组信号入第一组一样 ,先
寄存一半数据 ,等 x ( 12)到达时第一级运算器又开
始下一个循环的运算。如果各级都按同一节拍工
作 ,则每一级都可以在半个周期的时间完成各自的
运算 ,因而整个运算可以进行下去。这样 ,我们可以
看到 ,一个 N点的 FFT流水线运算 ,需要 M = log2 N
级运算器 ,每级运算器只要求 1次乘法 /每采样周期
就够了 ,这就大大提高了系统的处理能力。这样做
的代价是运算器需要增加 M倍 ,存储单元也要增加
约 M /2倍。
五、流水线 FFT的设计
以 8点流水线 FFT实现为例进行设计。如图 3
所示 , 8点 FFT由三阶运算处理模块及输出结果位
倒序模块组成。数据分为实部、虚部输入 ,经过三阶
运算后 , 完成 DFT 输出。其中 D IN
-
READY 与
DOUT
-
READY对输入输出数据块进行同步。整个
系统工作在同步模式下。
·981·
2005年第 2期
研究与开发
RESEARCH & D EVELO PM ENT
图 3 点流水线工作 FFT结构示意图
图 4是第一级运算模块结构方框图。在第一级
运算模块中 ,旋转因子系数为 1,因此蝶形运算不涉
及乘法器和旋转因子系数的使用 ,可以节省 3个乘
法器和相应的旋转因子 ROM。当数据准备好输入
时 ,通路选择器接通数据存储系统 ,前一半数据存入
存储系统。当存入一半数据后 ,通路选择器将输入
数据送入蝶形运算单元 ,同时控制系统控制存储系
统依次读出前一半数据 ,送入蝶形运算单元 ,与对应
的数据进行第一级蝶形运算。
图 4 8点 FFT流水线工作方式第一级运算模块结构方框图
图 5是第二级运算模块结构方框图。在第二级
运算模块中 ,旋转因子系数为 l和 j,可以不通过乘
法器来完成蝶形运算 ,因此可以节省 3个乘法器和
相应的旋转因子 ROM。当第一级输出数据时 ,由加
法器输出的数据通过通路选择器进入数据存储系
统 ,由减法器输出的数据直接进入数据存储系统。
当由加法其输出的数据达到 N /4 (N = 8)时 ,通路选
择器直接将从上一级加法器中输出的数据送入蝶形
运算单元 ,同时从数据存储系统中读出已存的从上
一级加法器中输出对应数据并选通至蝶形运算单
元 ,完成相应的蝶形运算。此时由上一级减法器中
输出的数据继续存入数据存储系统 ,当由上一级加
法器中输出的数据运算完毕时 ,控制系统将由上一
级减法器中输出的数据按第二级蝶形运算的顺序成
对输出 ,由通路选择器送入蝶形运算单元。此时 ,若
第一级运算模块有运算数据连续输出 ,则需要将数
据存入数据存储系统。对于由上一级加法器中输出
的数据可以使用普通存储模式 ,替换掉原有数据。
而对于上一级减法器中输出的数据 ,写入模式应为
READ BEFOR WR ITE (参见 X IL INX用户手册 ) ,即
在写入新数据前将老数据读出 ,这样可以节约存储
资源。
图 5 8点 FFT流水线工作方式第二级运算模块结构方框图
图 6是第三级运算模块结构方框图。在第三级
运算模块中需要相应的旋转系数 ROM存储相应的
旋转因子系数。第三级的运算过程与第二级运算模
块相似 ,即对上级蝶形处理器中由加法和减法形成
的数据分别处理 ,同时配置相应的旋转系数完成蝶
形运算。
图 6 8点 FFT流水线工作方式第三级运算模块结构方框图
由于 ,顺序输入的 FFT输出结果按位倒序输
·091·
2005年第 2期
研究与开发
RESEARCH & D EVELO PM ENT
出 ,因此在三级运算完成后 ,进入位倒序模块 ,使得
输出结果顺序输出。
通过以上的设计可以对输入数据进行流水线工
作方式处理 ,提高了数据的处理能力。利用这种设
计方法可以完成高阶高速的 FFT设计。
六、高速高阶 FFT设计实现
采用以上设计中分级结构及每级的储存、计算
时序安排 ,在 Xilinx V irtex - II FPGA上实现了 50 M
以上数据采样率、1 024点流水线工作的 FFT设计。
图 7为设计的 1 024点流水线工作的 FFT输入前 5
点为 1 000、以后全为零的 modelsim仿真输出结果 ,
图 8为该输出结果的部分放大图。通过与 matlab中
FFT函数计算的比较 ,可知满足设计要求。
图 7 仿真输出结果图
图 8 仿真输出结果图部分放大图
参考文献
[ 1 ] 侯朝焕 ,阎世尊 ,蒋银林. 实用 FFT信号处理技术 [M ].
北京 :海洋出版社 , 1990. 91~107.
[ 2 ] 邹理和. 数字信号处理 [M ]. 西安 :西安交通大学出版
社 , 1995. 158~159.
[ 3 ] 赵忠武 ,陈禾 ,韩月秋. 基于 FPGA的 32位浮点 FFT
处理器的设计 [ J ].电讯技术 , 2003, 43 (6).
[ 4 ] V ietex II Platform FPGA handbook [ DB /OL ]. www. xil2
inx. com, December, 2001.
[ 5 ] Uwe Meyer - Baese. 数字信号处理的 FPGA实现 [M ].
北京 :清华大学出版社 , 2003. 178~215.
[ 6 ] 韩颖 ,王旭 ,吴嗣亮. FPGA实现高速 FFT处理器的设
计 [ J ]. 电讯技术 , 2003, 43 (2) : 74~78.
[ 7 ] Mark Zwolinski. D igital System Design with VHDL [M ].
北京 :电子工业出版社 , 2002.
作者简介 :
邓学禹 ( 1976~) ,男 ,四川成都人 ,
电子科技大学信息与信号处理专业硕士
研究生 ,主要研究方向 :数字信号处理的
FPGA实现。
·191·