用FPGA实现FFT的研究.pdf

北京理工大学学报 990 2 2 3 北京理工大学学报 JO U RNA L O F BEIJING INST IT U T E O F T ECH NO LO CY 1999年 第19卷 第6 期 Vo l 19 No 2 用FPG A 实现FFT 的研究 刘朝晖 韩月秋 摘 要 目的 针对高速数字信号处理的要求 给出了用现场可编程门阵列 FPG A 实现的 快速傅里叶变换 FFT 方案 方法 算法为按时间抽取的基4算法 采用递归结构的块浮点运 算方案 蝶算过程只扩展两个符号位以适应雷达信号处理的特点 乘法器由阵列乘法器实 现 结果 采用流水方式保证系统的速度 使取数据 计算旋转因子 复乘 D FT 等操作协 调一致 在计算 通信和存储间取得平衡 避免了瓶颈的出现 结论 实验表明 用FPG A 实现高速数字信号处理的算法是一个可行的方案 关键词 离散傅里叶变换 快速傅里叶变换 块浮点运算 可编程门阵列 分类号 T P39 T N957 511 Implementation of FFT with FPGA Technology Li u Zh a o h u i H a n Yu e q i u D e p a r t m e n t o f El e c t r o n i c s En g i n e e r i n g Be i j i n g I n s t i t u t e o f T e c h n o l o g y Be i j i n g 10 0 0 8 1 A b s t r a c t A i m T o p r o p o s e a s c h e m e f o r i m p l e m e n t i n g FFT w i t h FPG A i n a c c o r d a n c e w i t h t h e r e q u i r e m e n t f o r h i g h s p e e d d i g i t a l s i g n a l p r o c e s s i n g M e t h o d s T h e s t r u c t u r e o f FPG A a n d r e q u i r e m e n t o f s y s t e m w e r e c o n s i d e r e d i n t h e e x p e r i m e n t r a d i x 4 a l g o r i t h m o f D I T a n d r e c u r s i v e s t r u c t u r e w e r e a d o p t e d T h e g r o u p f l o a t p o i n t a r i t h m e t i c o p e r a t i o n w a s u s e d i n t h e b u t t e r f l y a n d t h e a r r a y m u l t i p l i e r w a s u s e d t o r e a l i z e m u l t i p l i c a t i o n Re s u l t s T h e p i p e l i n e p a t t e r n w a s u s e d t o e n s u r e t h e s y s t e m s p e e d i t m a d e f e t c h i n g d a t a c a l c u l a t i n g t w i d d l e f a c t o r c o m p l e x m u l t i p l i c a t i o n a n d D FT o p e r a t i o n c o o r d i n a t e T h e b a l a n c e o f c a l c u l a t i o n c o m m u n i c a t i o n a n d s t o r a g e w a s r e a l i z e d a n d t h e b o t t l e n e c k w a s a v o i d e d Co n c l u s i o n I t d e m o n s t r a t e s t h a t i t i s a f e a s i b l e m e t h o d t o u s e FPG A t o r e a l i z e a l g o r i t h m i n t h e h i g h s p e e d D SP K e y w o r d s d i s c r e t e Fo u r i e r t r a n s f o r m f a s t Fo u r i e r t r a n s f o r m b l o c k f l o a t p o i n t a r i t h m e t i c p r o g r a m m a b l e g a t e a r r a y s 1 FFT 算法选择 提高FFT 速度的两个主要技术途径是采用流水线结构和并行运算 1 采用高基数结构 也可以提高速度 只是算法中基数r 的选择 在考虑运算量的同时 还应综合考虑系统的要 求 FPG A 的结构特点及对片内资源的占用 1个基2 蝶算由1个复乘和2 个复加组成 而1个基4蝶算包含3个复乘和8 个复加 在硬件 上实现3个复数乘法器会占用FPG A 中太多的资源 但如果充分利用FPG A 片内的寄存器 以 f i l e E q k b j l g d x x b b j l g 99 b j l g 990 2 990 2 2 3 h t m 第 1 5 页 2 0 10 3 2 2 15 30 17 北京理工大学学报 990 2 2 3 流水的方式运算 可以用1个复数乘法器和6 个实数加法器实现蝶算 因此二者占用面积相 差不大 基2 算法虽相对基4算法占用的资源较少 但为满足系统运算的速度 要求FFT 有更小的 流水周期 当对FPG A 内部资源占用较少时 这一速度要求不难满足 但由于FPG A 的内部连 线资源有限 故当设计中对于FPG A 的资源利用率相当高时 各信号间连线延时加大 这一 要求往往不容易满足 若采用高基数结构的基4算法 降低了运算量 同时提高了速度 在 系统时钟频率相同时 基4处理器运算速度是基2 处理器的2 倍 故基4算法更便于对FPG A 的布 局 布线和调试 2 算数运算方案 若 x n 是一N点序列 其D FT 为 X K 由Pa r s e v a l 定理得 由式 1 可知变换结果的均方值是输入序列均方值的N倍 考虑基4的FFT 算法第m 级蝶式运 算 由蝶算公式 式 2 中p 1 p2 p3 p4为该级蝶算输入数据的序号 W k 为旋转因子 可得m 1级蝶算输出与 m 级蝶算输出的关系为 式 3 表明序列中数的值一般是逐级增大的 且复数的最大模值以小于每级2 个二进位的速 度增长 由以上讨论可知 当采用定点运算时 必须用定比例的方法防止溢出 即必须解决动 态范围的问题 若采用浮点运算 则运算复杂性增加且运算速度降低 这里采用文献 2 给 出的块浮点方案 其基本思想是在计算D FT 过程中要更多地扩充符号位 在D FT 输出端 检 验数据的扩充符号位 以确定数据所需右移的位数 保证下一级蝶算不溢出 可见该方案运 算操作简单且具有较高的精度 由式 3 可知 若输入数据的模可以用N位表示 则每级蝶算输出的模可以用N 2 位表 示 因而蝶算输出的实部 虚部都可以只用N 2 位表示 通常情况下 输入数据的实部 虚 部分别为N位字长 即输入数据的模为N 1位 蝶算结果必须采用N 3位字长来防止溢出 对于雷达信号处理而言 为消除盲速 一般采用零中频 正交双通道处理 因此若实 部 虚部分别用N位字长表示 则能够保证输入数据的模为N位 蝶算输出可以只用N 2 位 表示 即每级蝶算只需扩展2 个符号位 对于基2 基8 等算法 也能得出相应的结果 这一结 论的意义在于明确了输出结果的有效最高位 f i l e E q k b j l g d x x b b j l g 99 b j l g 990 2 990 2 2 3 h t m 第 2 5 页 2 0 10 3 2 2 15 30 17 北京理工大学学报 990 2 2 3 3 硬件实现方案 对于基4的FFT 算法 具体讨论以下单元电路 由于FFT 是混序算法 因而需要读取 数据的地址产生单元 相应旋转因子值的计算 由复数乘法器或CO RD I C旋转器完 成与旋转因子相乘 块浮点防溢出电路 3 1 地址发生器及旋转因子的产生 设序列x n 的长度为N 4p 其中p 为正整数 则基4按时间抽取的蝶算单元的方程为 3 其中 s 为基4 D IT 算法流图中蝶算单元的级数 s 1 2 p n b 2 4s b 1 b1取0 1 4s 1 1 b 2取0 1 4p s 1 由此可以得出每级蝶算时数据的抽取规律 旋转因子的求取是与抽取数据的地址密切相关的 4 将n b 2 4s b 1代入旋转因子的表 达式中 其中t 0 1 2 3 可将旋转因子的指数部分写为 通常旋转因子的值存储在RO M 中 读取旋转因子的地址为t b 1 4p s 其中t 0 1 2 3 s 1 2 p b 1取0 1 4s 1 1 基于式 4 和式 5 可得地址及旋转因子的产生框图 如图1所示 图1 地址及旋转因子的产生框图 3 2 复乘运算电路的结构 复乘运算可以采用CO RD I C算法或阵列乘法器实现 就硬件复杂性 速度和精确度而 言 用CO RD IC算法实现乘法并不理想 与一个阵列乘法器相比 它所需的全加器数多出 近n 2 4个 n 是微旋转的次数或字长 1 阵列乘法器是标准软件乘法的硬件等效 通过一系 列的加法和移位操作得出乘积 在硬件的情况下 所有的移位操作均通过硬线连接 h a r d f i l e E q k b j l g d x x b b j l g 99 b j l g 990 2 990 2 2 3 h t m 第 3 5 页 2 0 10 3 2 2 15 30 17 北京理工大学学报 990 2 2 3 w i r e d 完成 因此乘法器的实现问题就简化为1个矩阵部分积产生器和1个加法器阵列的实 现 该加法器阵列把各被加数相加以获得最后结果 输入数据x r j x i 与旋转因子c o s j s i n 相乘的公式为 可以看出 若在1个时钟周期内实现复乘 需4个实数乘法器和2 个实数加法器 存在如下等 式 即可用3个实数乘法器和5个实数加法器实现复乘 1个阵列乘法器所占面积远大于加法器 故 用式 7 完成复乘 3 3 块浮点电路 本实验中FFT 用于雷达视频信号检测 因此在块浮点电路中只需扩展2 位 输出数据可 以分为以下3种情况 0 0 0 x x 或 111x x x 表示0 或1 0 0 1x x 或 110 x x 0 1x x x 或 10 x x x 因此只需对蝶算输出的高3位数据进行检测 即可确定下一级蝶算时应选择的数据的位 数 这一检测电路可以由有限状态机来完成 如图2 所示 其中状态S1 S2 S3分别对应上述情 形中的 每级蝶算结束时有限状态机的最终状态决定了下一级蝶算对输入数据的选择 表1给出了有限状态机的最终状态与选择器阵列输出间的关系 图2 有限状态机的状态转换 表1 有限状态机的最终状态与选择器阵列输出间的关系 有限状态机的最终状态 S1S2S3 选择器阵列输出数据N 1 0N 1 N 1 2 f i l e E q k b j l g d x x b b j l g 99 b j l g 990 2 990 2 2 3 h t m 第 4 5 页 2 0 10 3 2 2 15 30 17 北京理工大学学报 990 2 2 3 3 4 FPG A 的选择及系统总体设计 FPG A 选择Xi l i n x 公司的产品XC40 2 8 EX XC40 2 8 EX具有足够的可配置逻辑块 CLB 能够满足时序控制和算术运算的要求 并且FPG A 片内可配置RA M 和RO M 便于使用片 内RO M 存放旋转因子 同时有丰富的连线资源和足够的全局缓冲器 能够保证10 0 的 布通率和相对较短的连线延时 基于以上考虑 作者在XC40 2 8 EX的基础上实现FFT 图3为 系统框图 图3 系统框图 整个设计采用VH D L语言描述 经过仿真 综合 映射 布局 布线及带有时延的 后仿真 p o s t s i m u l a t i o n 能够保证硬件电路达到设计要求 系统工作过程如下 当外部数 据就绪后 计数器开始工作 经地址转接电路得到读数据的地址 并可求得旋转因子 经复乘 4点D FT 完成该级蝶算后 将数据存入外部双口RA M 同时进行溢出检测 确 定下一级蝶算前数据右移的位数 经l o g 4N N为序列长度 级蝶算后将数据输出 乘法运算 采用两级流水方式实现 同时大量使用触发器锁存中间结果 即采用流水方式保证系统 的速度 使取数据 计算旋转因子 复乘等操作协调一致 以避免瓶颈的出现 本文给出的用FPG A 实现FFT 的方案 经实验证实能够达到设计要求 实验表明 随 着可编程器件规模 速度的提高 用FPG A 实现高速数字信号处理的算法是一个可行的 方案 作者单位 北京理工大学电子工程系 北京 10 0 0 8 1 参考文献 1 贡三元 VLSI 阵列处理 南京 东南大学出版社 1992 2 Ra b i n e r L R G o l d B T h e o r y a n d a p p l i c a t i o n o f d i g i t a l s i g n a l p r o c e s s i n g Pr e n t i c e H a l l I n c 197 5 3 祝裕斌 超高速FFT 芯片设计的理论和实现 学位论文 北京 中国科学院声 学研究所 1994 4 Sa y e g h S I A p i p e l i n e p r o c e s s o r f o r m i x e d s i z e FFT s I EEE T r a n s o n SP 1992 40 8 18 92 1990 收稿日期 1998 0 410 f i l e E q k b j l g d x x b b j l g 99 b j l g 990 2 990 2 2 3 h t m 第 5 5 页 2 0 10 3 2 2 15 30 17 用FPGA实现FFT的研究用FPGA实现FFT的研究 作者 刘朝晖 韩月秋 Liu Zhaohui Han Yueqiu 作者单位 北京理工大学电子工程系 北京 100081 刊名 北京理工大学学报 英文刊名 JOURNAL OF BEIJING INSTITUTE OF TECHNOLOCY 年 卷 期 1999 19 2 被引用次数 41次 参考文献 4条 参考文献 4条 1 贡三元 VLSI阵列处理 1992 2 Rabiner L R Gold B Theory and application of digital signal processing 1975 3 祝裕斌 超高速FFT芯片设计的理论和实现 1994 4 Sayegh S I A pipeline processor for mixed size FFTs 1992 08 相似文献 10条 相似文献 10条 1 期刊论文 曹伟丽 CAO Wei li 快速傅里叶变换的原理与方法 上海电力学院学报2006 22 2 对样本点为N 2 的离散傅里叶变换 按照库利 图基按时间抽取的方法 得到一组等价的迭代方程 对方程中对偶结点对的性质作了详细分析 由此简化了方程中的计算公式 与直接计 算相比 大大减少了运算次数 并且计算过程中除了N个初始数据所占的存储单元外 不需再设置其他存储单元 2 期刊论文 张宪超 武继刚 蒋增荣 陈国良 ZHANG Xian chao WU Ji gang JIANG Zeng rong CHEN Guo liang 离散傅里叶变换的算术傅里 叶变换算法 电子学报2000 28 5 离散傅里叶变换 DFT 在数字信号处理等许多领域中起着重要作用 本文采用一种新的傅里叶分析技术 算术傅里叶变换 AFT 来计算DFT 这种算法的乘法计算量仅为O N 算法的计算过 程简单 公式一致 克服了任意长度DFT传统快速算法 FFT 程序复杂 子进程多等缺点 算法易于并行 尤其适合VLSI设计 对于含较大素因子 特别是素数长度的DFT 其速度比传统的FFT方法 快 算法为任意长度DFT的快速计算开辟了新的思路和途径 3 期刊论文 薛会 张丽 刘以农 XUE Hui ZHANG Li LIU Yi nong 非标准快速傅里叶变换算法综述 CT理论与应用研究2010 19 3 非标准快速傅里叶变换算法是一种用于处理非标准采样的快速算法 在信号处理领域有着广泛的应用 本文回顾了NUFFT算法的历史和发展 对通用的算法实现形式做了详细描述 介绍了 该算法的最新进展和研究方向 对NUFFT算法在CT重建中的应用 如傅里叶重建 迭代重建 稀疏采样重建等也做了介绍 4 期刊论文 王晓明 韩晓军 WANG Xiao ming HAN Xiao jun 快速傅里叶变换的FPGA实现 天津工业大学学报2005 24 2 基于快速傅里叶变换 FFT 运算特点 提出了采用现场可编程门阵列 FPGA 实现高速实时FFT运算的设计方案 该方案技术上采用基4算法以及乒乓RAM的设计思路 较好地解决了溢出处理 双地址生成 整序和总体时序控制的问题 最终实现了在200 s时间内完成1 024点的FFT运算 达到了高速实时运算的要求 5 期刊论文 杨洪耕 惠锦 侯鹏 YANG Hong geng HUI Jin HOU Peng 电力系统谐波和间谐波检测方法综述 电力系统及其自动化学报 2010 22 2 电力系统谐波和间谐波的实时精确检测的重要性日益突出 文中根据目前谐波和间谐波检测的特点 首先分析了离散傅里叶变换 DFT 和快速傅里叶变换 FFT 在检测过程中存在的频谱 泄漏和栅栏效应 根据检测难点提出了谐波间谐波检测要解决的关键问题 对目前国内外三类检测方法 时域分析 频域分析 时频交替分析法进行了分类分析 总结DFT FFT用于谐波 间谐 波检测的主要方法 最后指出现有检测方法的主要问题所在 并提出今后几个值得研究的课题和方向 6 期刊论文 焦计平 周又玲 吴素珍 JIAO Ji ping ZHOU You ling WU Su zhen 一种基于DFT的DCT改进算法的研究 通信技术2010 43 8 离散余弦变换 DCT 是一种广泛应用于信号处理 图像处理领域的重要工具 并已被多个国际标准所接受 将DCT应用到实际系统中的前提是具有能够快速实现的算法 给出了一种基于 DFT的DCT IDCT的实现 它避免了变换序列长度的限制 由于DFT可以由FFT实现 所以这种实现方式进而利用到FFT的优势 在满足输入序列长度满足一定条件的情况下 对所提出的算法做了进 一步的优化 使得DCT的实现更加容易 7 期刊论文 陈建平 曹清林 沈世德 Chen Jianping Cao Qinglin Shen Shide 共轭对称数据的DFT及其FFT算法 电子与信息学报 2001 23 2 该文对共轭对称复数序列的离散傅里叶变换 DFT 及其快速傅里叶变换 FFT 算法进行了研究 获得共轭对称序列的DFT具有虚部为零的性质 并开发出适用于共轭对称数据的FFT算法 该算法与传统FFT算法相比减少了一半的计算量和存储单元 运算速度提高了一倍 8 期刊论文 陈鹏 侯朝焕 马晓川 CHEN Peng HOU Chao Huan MA Xiao Chuan 用于计算离散分数阶傅里叶变换的MA CDFRFT算法改进 中国 科学院研究生院学报2007 24 2 基于中心类型DFT矩阵特征分解的MA CDFRFT Multiangle Centered Discrete Fractional Fourier Transform 算法在计算一组离散分数阶傅里叶变换DFRFT Discrete Fractional Fourier Transform 时充分利用FFT运算来减小运算量 结合偶数点离散傅里叶变换DFT Discrete Fourier Transform 运算的对称性原理 通过数学推导将MA CDFRFT算法中的一维对称性扩 展到频率和变换阶数的二维平面上 利用这个二维对称性原理 改进算法将原算法的主要计算量减小了一半左右 仿真测试结果证明了改进算法的正确性 9 学位论文 张宪超 算术傅立叶变换的算法 实现和应用 1998 该文在AFT算法 实现和应用等方面作了较详细的讨论 该文首先介绍了AFT算法并对算法作了改进 改进方法克服了AFT所需样本点太多的缺点 把样本点减少了一半 从而把AFT计算速度 提高了一倍 在AFT的实现上 提出了一种较好的零次插值的具体实现方案 此方案充分体现了AFT的优点 同时又提出了一种新的插值实现方法 克服了线性插值需要附加乘法和零次插值的精 度不高或样本稠密的缺点 该文还就用AFT计算DFT问题作了详细讨论 推导了用AFT计算DFT的算法并分析了误差和计算速度 指出对某些长度的DFT AFT的效率比FFT高 同时还列举了AFT方法 的各种优点 接着又设想了两种把AFT和FFT的优点结合起来的算法 结合算法1只需O N 的乘法和O N 0 1 的加法 把AFT方法的O N 加法量大为降低 且保持了AFT的良好 性质 结合算法2可望使任意长的DFT计算效率得到进一步提高 最后 文章对AFT在二维情况下的推广作了一点介绍 10 期刊论文 吴静 赵伟 WU Jing ZHAO Wei 一种用于分析电网谐波的多谱线插值算法 中国电机工程学报2006 26 8 以矩形窗为例 尝试在一定条件下以积分求和来求解离散傅里叶变换 所得表达式可直观反映非同步采样条件下频谱分析中的长 短范围泄漏效应 据此 不同于以往应用性能较好的窗 函数来减小长范围泄漏效应的作法 提出一种能同时修正长 短范围泄漏的多谱线插值新算法 针对长范围泄漏效应可被忽略和应被计及两种情况 将所提出新算法与已有加窗插值算法进行 比较 发现已有算法是新算法的特例 而新算法具有更广泛的应用范围 以三种不同算法计算含有间谐波的信号参数 通过比较发现 新算法具有较高的准确度 利用新算法对含有高斯噪声的 信号做仿真分析 结果表明其具有良好的抗干扰能力 引证文献 41条 引证文献 41条 1 马壮 齐林 马鹏阁 司巍 基于FPGAIP核的FFT实现 期刊论文 现代电子技术 2009 7 2 潘琳 基于FPGA的改进FFT模块在数字脉冲压缩系统中的应用与实现 期刊论文 硅谷 2008 10 3 范必双 王英健 王玉凤 基于FPGA硬件实现的谐波检测方法 期刊论文 计算机仿真 2008 4 4 罗跃东 陈禾 王晓君 一种雷达信号侦察处理器的设计与实现 期刊论文 北京理工大学学报 2008 4 5 姚国珍 基于MegaCore的FFT模块在FPGA上的实现 期刊论文 山西电子技术 2008 2 6 王超 田黎育 高梅国 基于FPGA的高速数字脉冲压缩 期刊论文 计算机工程 2008 4 7 范必双 王玉凤 王英健 一种高效的电力系统谐波检测方法 期刊论文 广东电力 2007 10 8 王晓君 陈禾 罗跃东 一种EW接收机信号处理系统的设计与实现方法 期刊论文 河北科技大学学报 2007 2 9 王超 田黎育 高梅国 双蝶形高速脉冲压缩的FPGA实现 期刊论文 数据采集与处理 2006 z1 10 丁智泉 张红雨 高速浮点FFT处理器的FPGA实现 期刊论文 四川理工学院学报 自然科学版 2006 1 11 王旭东 刘渝 全并行结构FFT的FPGA实现 期刊论文 南京航空航天大学学报 2006 1 12 赵涛 傅丰林 王晓辉 基于Stratix系列FPGA的FFT模块设计与实现 期刊论文 国外电子元器件 2006 5 13 万红星 陈禾 韩月秋 并行数据FFT IFFT处理器的设计 期刊论文 北京理工大学学报 2006 4 14 张江红 基于FPGA的非真实感绘制算法设计和优化实现 学位论文 硕士 2006 15 高瞻 FFT处理器设计及其应用研究 学位论文 硕士 2006 16 蔡可红 基于FPGA的FFT设计与实现 学位论文 硕士 2006 17 谭征 张晓林 杜永久 一种基于FPGA的超高速FFT处理器设计 期刊论文 遥测遥控 2005 6 18 一种新结构FFT算法及其FPGA实现 期刊论文 无线通信技术 2005 3 19 郑哲 李加琪 吴嗣亮 引信体目标视频回波模拟器专用处理器设计 期刊论文 红外与激光工程 2005 3 20 万红星 陈禾 韩月秋 一种高速并行FFT处理器的VLSI结构设计 期刊论文 电子技术