基于FPGA的新型高速FFT算法研究与实现

1、第 31卷 第 4期2008年 8月电 子 器 件Chinese J ournal Of Elect ron DevicesVol. 31 No. 4Aug. 2008R esearch and Implementation of a Novel F ast FFT Algorithm B ased on FPGAGU Yan 2li3, Z HOU Hon g 2mi n(College of optoelect ronic engineering , N anj i ng Uni versit y of posts and telecommunications , N anj ing 21

2、0003, China Abstract :A novel radix 28/4FF T algorit hm and architect ure are introduced , fast p rocessor is designed. The design can realize 8k 、 4k or 2k point alternatively ; obtain significant hardware reduction by multipliers multiplexing ; increase t he continuous comp uting capability of t h

3、e butterfly core by using a symmetry ping 2pang RAM st ruct ure. The module is described wit h Verilog HDL ,and performed wit h translated synt he 2sized , routed in t he Quart us5. 0software. The result shows t hat t he algorit hm architect ure has achieved t he expected p urpo se bot h on precisio

4、n and speed , and can meet t he demand of reality needs. K ey w ords :novel and fast FF T ;ping 2pang RAM ;butterfly p rocessing ;verilog EEACC :6140基于 FPGA 的新型高速 FFT 顾艳丽 3(, 收稿日期 :2007210216作者简介 :顾艳丽 (19812 , 女 , 硕士研究生 , 助教 , 从事电子电路教学工作 ,nlggyl 163. com摘 要 :, 设计出高速的处理模块 。该设计可选择性地实现 8k 、 4k 及 2k 点FF

5、T ; , ; 应用对称乒乓 RAM 结构提高了蝶型运算单元的连续运算能力 。 模块利用 Ver 2ilog 语言进行描述 , 在 Quartus5. 0软件环境中完成输入 、 综合及布局布线 。 结果表明本文提出的算法结构具有优越的精度和速度 , 充分能够满足实际应用要求 。关键词 :新型高速 FFT ; 乒乓 RAM ; 蝶型运算 ;Verilog 中图分类号 :TN911. 23 文献标识码 :A 文章编号 :100529490(2008 0421249203 快速傅立叶变换 (FF T 不是一种新的变换 , 是 离散傅立叶变换 (DF T 的一种快速算法 , 是描述离 散信号时域和频域

6、关系的重要数学工具 , 在图像处 理和数字信号处理方面得到广泛的应用 。 FF T 算 法可以采用软件 、 DSP 、 专用 FF T 处理芯片或 FP 2GA 等来实现 。 软件和 DSP 实现的速度较慢 ; 专用处理芯片速度虽快 , 但价格高 、 不易扩展 ; 而 FP GA 资源丰富 , 组织结构便于采用流水线结构和并行运 算 , 这样不仅速度快 、 扩展能力强 , 而且增加设计灵 活性 、 节约开发成本 。文中提出一种新型基 8/4算法结构 , 能实现 8k 、 4k 、 2k 点 FF T 。 设计中采用单个基 8蝶形运算单元顺序处理 ; 通过乘法器复用 , 有效平衡处理速度 与资源

7、消耗之间的矛盾 ; 同时采用防溢出机制和对称乒乓 RAM 结构 , 提高运算精度及连续运算能 力 。 该结构利于扩展 , 可广泛应用于各种系统中 , 如 DVB 、 图象处理系统等 。1 FFT 算法基本原理对于 N 点 序 列 x (n , 其 离 散 傅 立 叶 变 换(DF T 变换可写为 :X (k = N -1n =0x (n WnkN 0n N -1其中 :W =e -j2/N 。分析可知 , 直接计算 DF T , 乘法和加法次数都 和 N 2成正比 , 当 N 很大时 , 运算量是很可观的 。 若 利用旋转因子的对称性 、 周期性和可约性 , 将 DF T 逐次分解成几个较短序

8、列的 DF T ,可使计算量大 大降低 。 快速傅立叶变换算法正是基于这样的基本 思路发展起来的 1。2 FFT 的实现结构FF T 的设计结构框图如图 1所示 , 结构中包含控制模块 、 旋转因子 ROM 、 8k 数据存储 RAM 、 输 入缓冲 (实际结构中是将一个 8kRAM 分成 4个 2kRAM 并行使用 、 基 8/4运算模块 、 限制模块 223。 设计中 FF T 的精度取 10位有符号数 。图 1 FF T 实现框图2. 1 基 8/4运算模块基 8/4分 , 理器的性能 。基 8+基 4” 模块 (如图 24复用蝶型运算模块 , 两模块分别运算之后共用一个限制模块 , 进

9、行数据溢出检测和溢出处理 。图 2 基 8FFT 基本运算的信号流图2. 2 复乘法器实现复乘法是设计中关键模块均要用的一种运算 。 复乘包含实加和实乘两种运算 , 当参与运算数据位数较多时 , 加法较乘法所占资源比例是相当小的 。 为此改进复乘算法 , 减少实数乘法次数可以节省大 量硬件资源 。这里的复乘一般是指一个复数 x r +j x i 和旋转因子 W =-j2/N=co s A -jsin A 相乘 , 结果仍为复数 y r +j y i =(x r cos A -x i sin A +j (x i co sA +x r sin A , 可见完成一次复乘要进行 4次实乘和 2次实加运

10、算 。 为减少乘法次数 , 将 y r +j y i 做以下变换 :y r =(x r +x i co s A -x i (sin A +co s A , y i =(x r +x i cos A +x r (sin A -cos A , 从而完成一次复乘则只需进行 3次实乘和 5次实加 , 较变换前减 少一次实数乘法运算 , 减少了使用面积 。2. 3 RAM 和 R OM 的地址产生规律RAM 采用对称乒乓结构 , 蝶型运算开始时使用 8kRAM 1、 8kRAM 2作为乒乓结构即可实现 。 根据产生的 RAM 读地址 , 并行的从 4个 2kRAM 中分别读取 8个数据 , 每隔 2个时

11、钟分时送入基 8/4蝶算单元进行运算 , 隔 8个时钟后得到 64个结果 , 再根据产生的 RAM 写地址写入 8kRAM 2, 然后 8kRAM 1和 8kRAM 2交换功能 。对于 4k 点 , 要进行 64次完成一级基 8/4蝶形运算 , 因此经过 4级 8/4蝶算后 ,8kRAM 1中为输出结果 , 此时将输入缓存和 8kRAM 2作为乒乓结构实现蝶型运算 。这 样就保持了数据输入和运算的连续性 , 加快了处理 速度 。本设计可以有选择的实现 8、 4k 、 2k 点的 FF , 中并行使、 余弦0, 2周期内的正 、 余 1/4周期内旋转因子变换得到 , 所以 可只存 储 2k 旋转

12、 因子 。下 面 具 体 讨 论 RAM 、ROM 的数据存储规律 2,425。 2. 3. 1 抽取数据规律本文采用以基 8/4为基本单元的混合基顺序处 理算法 , 选择性的实现 8k 、 4k 或 2k 点 FF T 。根 据 FF T 算法分解过程 , 具体的基数划分如表 1。如 要实现 N =8192=4×4×8×8×8点的 FF T , 需要 进行 2次基 4运算 , 再进行 3次基 8运算 。表 1 FFT 基数划分选择性radixtemp remain 8k 4×4×8×8×81×4

13、5;16×128×10242048×512×64×8×14k 8×8×8×81×8×64×512512×64×8×12k4×8×8×81×4×32×256512×64×8×1 Radix :每级的实际基数 。 判断调用何模块进行 FF T ; 抽取旋转因子的个数 ; 第一级不乘旋转因子 。Temp :为 1时不抽取旋转因子 ; 每个蝶型单元的结点间距 ;te

14、mp 3radix 的结果为蝶型单元间距 ;做每级 FF T 时 , 旋转因子变化的次数 。Remain :相同的旋转因子中蝶型运算的次数 。 2. 3. 2 抽取旋转因子举例说明 :进行 2k 2FF T 的第 2级时 , 最后 8位 数的旋转因子为 , 见表 2。0521电 子 器 件 第 31 卷表 2 2k 2FFT 的第 2级最后 8位数的旋转因子 RAM 地址 cos sin2019 1. 000000 0. 000000 2023 0. 831470-0. 555570 2027 0. 382683-0. 923880 2031-0. 195090-0. 980785 2035-

15、0. 707107-0. 707107 2039-0. 980785-0. 195090 2043-0. 923880 0. 382683 2047-0. 555570 0. 831470 利用算法得出表 2中旋转因子的地址位置分别 为 (暂不考虑符号和第一个旋转因子 :768,1536, 1792,1024,256,512,1280。 设 a =768, 则其它数分别 为 :2×a ,4096-3×a ,4096-4×a ,4096-5×a , 6×a -4096,7×a -4096。 若用 13bit 二进制数表 示七个地址数 ,

16、 则如表 3中 b12b0一栏所示。 若高 两位 (b12,b11 =00或 10时 , 取低 11位的原码输出 , 当 (b12,b11 =01或 11时 , 取低 11位的补码输出 , 此 时发现换算后的 13位二进制数如表 3中乘值一栏所 示。 若仍设 a =768, 则乘值一栏的十进制值可表示 为 :a, 2×a, 3×a, 4×a, 5×a, 6×a, 7×a 。表 3 FFTa 值 由于 ROM 存取地址为 02047, 所以乘值一列 中所有数均需 -1。2. 3. 3 旋转因子的取值象限表 3中的 (b12,b11 两位

17、除了上面所说作用以 外 , 其四种取值情况还可以用来定义旋转因子的各 种象限关系 , 如表 4。 当 (b12,b11 =0011时 , 分 别对应为第一到第四象限 。表 4 旋转因子各象限取值关系(b12,b11 00011011象 限 cos -cos -cos cos sin sin -sin -sin2. 4 溢出处理对于 FF T 的每级运算结果都可能存在溢出的 问题 , 但是溢出的数据较少 。对于一次基 8的运算 来说 , 若截掉低 3位 , 即可防止溢出 , 但这样对没有 溢出的数据同样进行了截位 , 大大降低了精度 。根据运算规律 , 文中采用一个限制模块来防溢出。 因取 FF

18、T 的精度为 10位有符号数 , 故数据范围为 -512511。 每一级运算后保留数据的 b 11b 1位 (相当 于除以 2 。 此时数据中超过范围的按就近原则处理 , 即小于 -512的数都取 -512, 大于 511的数都取 511; 范围之内的数取 b 10b 1位。 这样经过几级运算 , 只对 少部分有溢出的数据进行了处理 , 大部分无溢出的数 据进入运算 , 大大提高了精度。 每一级运算后的截位 范围可以根据原始数据进行调整 , 如原始数据较大 , 可 取 b12b2位 (相当于除以 4 。3 性能分析本文提出了新型高速 FF T 的完整设计方案 , 并 在 Altera 公司 C

19、yclone 系列的 EP1C20F400C6芯 片上加以实现 6。整个设计占用 6700个逻辑单 元 , 处理器时钟频率最高可达 53M Hz , 运算结果绝 对误差仅为 0. 16, 信噪比很高 ,。, 从本文详细描述了基于 FP GA 的混合基 8/4FF T 算法 , 设计 、 实现了硬件系统 。 该设计可选择性的实 现 8k 、 4k 、 2k 点的 FF T 运算 ; 采用新的乘法器结 构 , 减小了硬件面积 , 加快了运算速度 ; 数据 RAM 应用对称乒乓结构 , 提高了连续运算能力 ; 溢出电路 简单且提高了计算精度 。硬件运行结果表明 , 本文 提出的大点 FF T 系统是切实可行的 , 获得了