2 2 2 嵌 入 式 技 术 戢小亮 :基于 FP GA 快速平方根算法的实现 基于 FPGA 快速平方根算法的实现 戢小亮 (西安邮电学院 　陕西 西安 　710121) 摘 　要 :平方根算法是科学计算和工程应用中的基本运算之一 ,然而由于此算法的复杂性 ,因此用 FP GA 很难实现 。一 般的平方根算法 ,使用一定量的迭代运算 ,由传统的加法器和减法器构成 ,资源占用少 ,但速度较慢 。而在一些实时性要求 较高的系统中 ,对速度的需求比较高 。基于此 ,给出了一种平方根算法 ,是由高通流水线方式实现 ,由多路加法器和减法器 构成 ,能够在一个周期内给出结果 ,相对于传统的平方根算法速度大大增加了 。 关键词 : FP GA ;平方根 ;加法器 ;减法器 ;高通流水线 中图分类号 : TP342 　　　　　文献标识码 :B 　　　　　文章编号 :1004 373X(2007) 14 064 02 Implementation of Square Root Arithmetic Based on FPGA ( Xi′an University of Po st s &Telecommunications ,Xi′an ,710121 ,China) J I Xiaoliang Abstract :Square root arithmetic is one of the basic arithmetic ,but it is hard to implement on FP GA because of the com cost iterative implementation which uses a traditional adder/ plexity. U sually ,the non subtrator. While making better use of the resource ,the speed is much slower. In this paper ,we present a fast square root based on FP GAs ,it is high throughput pipelined implementation which uses multiple adder/ subtractors. restoring square root algorithm is low Keywords : FP GA ;square root ;adder ;subtractor ;high throughput pipelining 1 　引 　言 现场可编程门阵列( FP GA) 的出现是超大规模集成电 路(VL SI) 技术和计算机辅助设计技术发展的结果 。使用 FP GA 器件可以大大缩短系统的研制周期 ,减少资金的投 入 。如今 ,现场可编程门阵列 ( FP GA) 正处于革命性数字 信号处理的前沿。 加减乘除以及平方根运算是科学计算和工程应用中 最基本的运算 ,他们广泛应用于三角学、二次方程求解 、二 维建模、误差计算 、数值分析、概率统计、图像处理以及信 号处理等许多领域 。关于整数及浮点数的运算已经在 VL SI(超大规模集成电路) 标准中有规定。一些计算已经 在 FP GA 中实现了。Shirazietal 提出用 FP GA 实现18 位 浮点数的加减乘除法运算 ,Loucaetal 提出了用 FP GA 实 现单精度浮点数的加减法和乘法运算 。 平方根算法虽然不如加减乘除使用频繁 ,然而平方根 计算相对复杂 ,处理速度明显低于其他运算 ,因此用FP GA 实现快速的平方根运算是比较困难的 。本文实现的平方 根算法 ,采用流水线的结构 ,以二进制手算平方根方法为 基础 ,可以实现在每个时钟周期内接受 1 个平方根指令 。 对于 16 位的被开方数 ,流水线延迟为 7 个周期 。此快速 收稿日期 :2007 02 03 46 算法已在实际中获得了应用 ,结果令人满意。 2 　平方根算法综述 目前所研究的开方算法主要有以下几种方法 : New Raphson(牛顿 Redundant 方法和 Non ton Redundant 方法。 拉斐森) ,SR T Newton 了计算出 Y = Raphson 方法已经广泛应用于许多工程 。为 X ,可以用迭代法算出一个近似值 。例 如 ,利用牛顿 拉斐森公式 ,可以从 f ( T) = 1 T2 - X 推导出 迭代等式 T i+1 = T i ×(3 - T2 ×X) / 2 ,其中 T i 是 1/ X 的 近 似 值。 在 n 次 迭 代 之 后 , 就 可 以 通 过 等 式 Y = X T n ×X 近似获得 X 的平方根。 这个算法需要种子生成器以产生 T0 , 一个 ROM 表 用于初始化 。在每次迭代过程中需要乘法 、加法或减法 器 。为了提高运算速度 ,通常使用快速并行乘法器 。因为 乘法器需要大量的门单元 ,然而为了实现完全的流水线操 作而使用大量的乘法器是不切实际的 ,即使可以做到 ,成 本也是非常高的 。在大多数商业 RISC 处理器中 ,迭代的 乘除法和平方根运算都是共用一个乘法器 ,这就成为开发 多处理器的并行指令的障碍。并且 ,利用这种方法也很难 获得精确的平方根余数。 传统二进制 SR T Redundant 方法的计算基础是递归 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 

《现代电子技术》2007 年第 14 期总第 253 期 　　嵌入式与单片机 　 关系 式 X i+1 = 2 X i - 2 Y i y i+1 y2 i+12 - ( i+1) , Y i+1 = Y i + ,这里 X i 是第 i 次的部分余数( X 0 是被开方数) , y i+12 - ( i+1) Y i 是令 Y 0 = 0 的第 i 次部分相除的平方根 , y i 是第 i 次平 方根的位 ,其中 y i ∈{ - 1 ,0 ,1} 。y i+1 由数选函数 y i+1 = - 制数开方的基本方法与 10 进制开方基本类似 ,试根总是 两位一试 ,所以用上一次的“根”乘 2 后加 1 就产生了新的 试根 。过程如图 1 所示。 ) 算出 ,在高进制 SR T Redundant 方法中 y i+1 = ～ Select ( X i ～ ～ Select ( X i , Y 而得到的。 ～ i) ,这里的 X ～ i , Y i 分别是通过截去其多余的位 在每次迭代中 ,需要 4 步运算 : 左移 1 位得到 2 X i ;确 i+12 - ( i+1) ;将 F和 2 X i 相 定 y i+1 ;构造公式 F = - 2 Y i y i+1 - y2 加得到 X i+1 。 可以用 1 个进位存储加法器 CSA 来加快 F 和的相加 速度。为了满足 CSA , F 需要表示成二进制补码的形式 , 但确定 y i+1 的选择函数是比较难的 ,特别是对于高进制的 SR T 算法 ,虽然他只是对 X i 和 Y i 的低精度估算 。在最后 一步计算里 ,需要一个进位传递加法器 CPA 将平方根从 多位表示转换为补码表示形式 。由于电路系统的复杂性 , 所有的迭代共用相同的硬件资源 。因此 ,这些操作就不能 够在每个时钟周期内接收一个平方根指令。值得注意的 是 ,这种算法可能在最后数字位产生误差 ,因为他满足的 条件是 X i ≤2 ( Y i + 2 - ( i+1) ) ,而正确的 Y i 应该满足条件 X i ≤2 Y i 。 Non Redundant 方法类似 ,但 他是用补码的形式来表示平方根 。传统 Non Redundant 方法的计算基础是关系等式 : R i+1 = X - Y 2 i , Y i+1 = Y i + y i+12 - ( i+1) ,其中 R i 是第 i 次运算的部分余数 , Y i 是令 Y 1 = 0. 1 第 i 次的部分平方根 , y i 是第 i 次平方根的位。平方根 结果的值是根据余数的标志位来确定的。如果 R i+1 ≥0 , y i+1 = 1 ,反之 , y i+1 = - 1 。计算过程可以通过对 X i+1 = ( X i ) 2 i 进行变量代换 , 消掉平方运算而得到简化 , 其中 - Y 2 i 2 - i , Y i+1 = Y i + y i+12 - ( i+1) ,这里 X i X i+1 = 2 X i - 2 Y i y i + y2 是第 i 次的部分余数 ( X1 是被开方数) 。 Redundant 方法与 SR T 图 1 　二进制开发手算过程举例 由于每一步需要减法运算 ,可以用补码形式表示 ,这 样就可以只用加法器 ,而不用关心负号的问题 。第 n 步需 要丢弃被开方数的高 2 n 位而保留余下的位数 。每一步 都需要一比较器 ,以确定开方上 1 还是 0 。 利用此方法可以实现高速流水线操作 ,流水延迟为 7 个时钟周期。 3. 2 　FP GA 下仿真 本文 仿 真 所 使 用 的 PLD 器 件 是 Alter 公 司 的 5 ,其提供 256 个宏单元 。仿真工具 MAX7256A EQC208 采用 Alter 公司的 Quart us Ⅱ4. 0 软件。仿真结果如图 2 所示 。输入为 16 位的被开方数 ,时钟为 50 M Hz 。 这种方法与 SR T Redundant 不同的是他的结果值是 在计算出 X i+1 以后得出的 , 而 SR T 法是在计算出 X i+1 之 前 。这种方法也可能在最后数字位产生误差 , 并且也需要 构造 F = - 2 Y i y i+1 - y2 i+12 - ( i+1) ,然后将 F 和 2 X i 相加。有 些人将 Non Redundant 算法归类为“返回型”和“非返回 型”2 种 。例如上面提到的算法就是非返回型算法 。但实 际上 ,这里所说的返回 ( 非返回) 指的是平方根 , 而不是 余数。 3 　快速平方根计算 3. 1 　算法简介 在实时性要求较高的系统中 ,希望能够流水作业 ,因 此寻找一种能够快速计算平方根的算法就显得尤为重要 。 本文中的快速算法是以二进制手算方法为基础的 。二进 图 2 　快速开方仿真结果图 由图 2 分析可得 ,流水线延迟为 7 个时钟周期 ,并且 在每个周期都能接受一个平方根指令 ,是高通流水作业。 从 Quart us Ⅱ的资源报告可得到此算法消耗的宏单元为 235 个 。 此算法的优点是能够快速进行运算 ,但他是以面积换 速度而得到的 。因此在后续的研究中 ,如何能够以最少的 资源实现快速的平方根算法是值的研究的 。 4 　结 　语 半导体技术的发展以及 FP GA 的广泛应用 ,越来越多 的算法集成到硬件中 ,用以提高处理的速度。平方根运算 由于其计算的复杂性 ,从而导致了处理速度的降低 ,因此 (下转第 72 页) 　 56 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net 

2 2 2 2 嵌 入 式 技 术 黄双萍等 :基于 A RM 的嵌入式零树编码图像压缩的实现 (0) (101000) (101011) (0) (101001) (0) (111100) 到的重构图像其主观视觉效果良好 ,与 EZW 算法相比 ,压 缩比和信噪比有明显的提高。 参 　考 　文 　献 [ 1 ] Calderbank A R ,Daubechies I , Sweldens W , et al . Lossless Integer Wavelet Image Compression U sing Integer Thansforms[J ]. Tech. Report ,1997 :596 to 599. 图 3 　三级小波分解系数图 4 　结 　语 实验表明 ,本文所提出的改进嵌入式零树编码压缩效 果好 ,利于在 ARM 微处理器上实现 。与 EZW 相比 ,因为 将最高层低频子带进行 DPCM 编码 ,减小了编码失真 ,提 高了压缩质量 , 在压缩比为 16 时 , EZW 编码的信躁比 PSNR 为 33. 12 ,本文方法的信躁比 PSNR 为 34. 16 。而本 文中对主表先进行游程编码 ,会大大的提高压缩比 ,在相 同信躁比 PSNR 为 35. 41 的情况下 ,不采取游程编码的压 缩比为 8. 4 ,而采取游程编码的压缩比会提高到 14. 3 。总 之 ,实验证明本文所提出的压缩方法是可行的 ,并且所得 [ 2 ] Claypoole R L , Davis G M , Sweldens W , et al . Nonlinear Wavelet Transforms for Image Coding via Lifting[J ]. IEEE Transactions on Image Processing , 2003 , 12 ( 12 ) : 1 449 1 459. [ 3 ] Mallat G. A Theory for Multiresolution Signal Decompo si tion : The Wavelet Representation[J ]. IEEE Transactions on Pattern Analysis on Machine Intelligence , 1989 , 11 ( 7 ) : 674 693. [ 4 ] Shapiro J M. Embedded Image Coding U sing Zerotrees of Wavelet Coefficient s[J ]. IEEE Transactions on Image Pro cessing ,1993 ,41 (12) :3 445 3 462. [ 5 ] 吴晓光 ,谭云兰 ,柳志新. 基于小波多分辨率分解的图像压 缩技术及分析[J ]. 计算机与现代化 ,2004 (4) :19 21. [ 6 ] 钟斌 ,晏磊 ,许超. J PEG2000 标准下提升小波的设计与分析 [J ]. 计算机工程与应用 ,2003 (15) :71 73. [ 7 ] 王树亮 ,任灵萍 ,郑成增. 基于小波变换的图像压缩方法 [J ]. 计算机工程与应用 ,2004 (10) :68 70. 作者简介 　黄双萍 　女 ,1972 年出生 ,讲师 。主要从事图像小波分析 、图像通信及模式识别的研究 。 俞 　龙 　男 ,1975 年出生 ,讲师 。主要从事嵌入式系统及其在农业工程中的应用的研究 。 (上接第 63 页) 参 　考 　文 　献 [ 1 ] Neal Bierbaum. MPI and Embedded TCP/ IP Gigabit Ether net Cluster Computing. Local Comp uter Networks. Proceed ings. L CN 2002. 27th Annual IEEE Conference on. 2002 : 733 734. [ 2 ] Minturn D ,Regnier G , Krueger J ,et al . Addressing TCP/ IP Processing Challenges Using the IA and IXP Processors[J ]. Intel Technology Journal ,2003 ,7 (4) :39 50. [ 3 ] Stevens RW. TCP/ IP Illustrated , Volume 1 : The Protocol [ M ]. Addison Wesley ,1993. [ 4 ] Borman D ,Research C , Partridge C. Comp uting the Internet checksum. RFC1071 , 1988. http :/ / www. faqs. org/ rfcs/ rfc1071. html. 作者简介 　王卫源 　男 ,1979 年出生 ,硕士研究生 。主要从事信息安全领域的研究与开发工作 。 钱育蓉 　女 ,1980 年出生 ,讲师 ,硕士研究生 。主要从事软件设计与开发工作 。 (上接第 65 页) 如何能够提高开方的速度是具有挑战性的。本文中的快 速平方根算法由于采用流水线结构 ,因此能够极大提高处 理速度 ,虽然资源上消耗很多 ,但在处理速度提高了很多 。 实际使用的情况也是令人满意的 。 参 　考 　文 　献 PL A[J ]. IEEE Transaction on Computers ,1990 ,39. [ 2 ] 毛晓波 ,贾更新. 基于定点 DSP 的浮点开平方算法的实现 [J ]. 微机计算信息 ,2003 ,19 (4) :40 42. [ 3 ] 赵伟 ,王晶芝. 单片微型计算机多字节浮点快速相对移位法 开平方运算的实现 [J ]. 微型电脑应用 , 2000 , 16 ( 10) : 32 33 ,38. [ 4 ] Uwe Meyer Baese. 数字信号处理的 FP GA 实现[ M ]. 北京 : [ 1 ] Ecegovac M ,lang T. Radix 4 Square Root Withort Initial 清华大学出版社 ,2003. 作者简介 　戢小亮 　女 ,1981 年出生 ,硕士 ,西安邮电学院教师 。主要从事信号与信息处理方面的研究工作 。 27 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net