乘除法和开方运算的FPGA串行实现
陈国军，万明康，王大鸣，郭锐
（解放军信息工程大学信息工程学院  河南 郑州 450002）
摘要：高精度的乘除法和开方等数学运算在FPGA实现中往往要消耗大量专用乘法器和逻辑资源。在资源敏感而计算时延要求较低的应用中，以处理时间换取资源的串行运算方法具有广泛的应用价值。本文即给出了采用递推结构的乘除法和开方运算的串行实现方法，该方法具有占用硬件资源少，实现简单的特点。 关键字：乘除法；开方；FPGA；串行 中图分类号：TP312 文献标识码：B
Serial Implementation of Multiplication, division and Square Root Operation based on FPGA
Chen Guojun  Wan Mingkang  Wang Daming Guo Rui
(Institute of Information Engineering, Information Engineering University, Zhengzhou 450002)
Abstract : A great amount of multipliers and logic resources would always be consumed in FPGA implemented high accuracy multiplication, division and square root operations. In the applications which are sensitive to resource and have low requirement in delay, the serial implementation of multipli
cation, division and square root operations could be applied broadly, which could barter processing time for resource. This paper proposed the serial implementation of multiplication, division and square root operations by using recursive architecture, which characterize with  saving  hardware resource and implementing easily.
Key Words : multiplication; division; square root; FPGA; serial 1、引言
在FPGA的开发应用中，大多数EDA软件（后面以altera QuartursII为例）都提供乘除法、开方运算的设计向导，或提供LPM宏函数，但普遍占用资源量大。而在许多信号处理应用中，要求计算精度高、资源敏感而计算时延要求并不高，这时我们需要一种保证计算正确且资源开销最低的FPGA实现方法，本文给出了实现乘除法、开方运算的FPGA串行实现算法，并与LPM宏函数进行了性价比比较。结果表明，本文给出的各算法计算准确，资源量远小于调用LPM宏函数。 2、算法描述 2.1、乘法
由于原码乘法实现相对简单，并结合实际应用情况，我们重点讨论补码乘法的实现方法。一种比较好的带符号数乘法的方法是布斯(Booth)算法。设y=y 0,y l y 2…y n 为被乘数，x为乘数，y i 是第i位(当前位) (i=3l，30，… …，1，0)，那么Booth算法可表示为下式：
3130001313130001310131
2)(22......2)
(0)2()2......()2(2)(0)(2)()......(2)()x y
x y y y x y y y x y x y y x y y x y x y y x y y ×=××+×++×=×−×+×++×=×−×+×−×+×−×=××−+××−+××−
乘法过程中，每次循环中的运算可表示对于x(i+1y -i y )2
31-i
项的加法运算，由于乘以2的幂只需
向左移位操作，那么乘积右移一位，相对而言可以认为乘数被放大两倍。可见Booth算法只采用加法、减法和右移操作便可计算补码数据的乘积。对乘数从低位开始判断，根据两个数据位的情况决定进行加法或减法运算，每次将乘积项向右移一位。判断的两个数据位为当前位及其右边一位，初始时需要增加一个辅助位0。根据i y 与i+1y 的值，Booth算法单次循环的操作方式取决于表达式(i+1y -i y )的值，可表示为下表：
i y
i+1y
操作 ０ ０ 无 ０ １ 加x １ ０ 减x １
１
无
表1
图1
实现结构如图1。可见，本算法将乘法转化为串行的加减和移位运算，从而节省了大量逻辑资源。 2.2、除法  除法计算我们采用经典的计算的方式，这种算法的实现思路清晰，实现的结构也很简单。我们首先介绍原码除法的实现。
设：A、B均为无符号数，A=1011，B=0011，求A/B。其计算如下图： 1011
11101………相减结果10+A 左移进的11111
11
图2
其特点可归纳如下：
（1）、 每次比较余数(被除数)和除数的大小，确定商为1还是0；
（2）、 每做一次减法，保持余数不动，低位由被除数低位补进，再减去右移后的除数。
对于补码除法运算，为了简化中间判断过程，我们可以先将除数和被除数取模，然后按照原码的计算方法求出商和余数，再根据除数和被除数的符号对计算结果进行修正即可。由此可见，有符号除法包
含了无符号除法的运算过程，所以我们这里也着重介绍有符号除法的计算过程。设：被除数（x）为56位，除数（y）为28位，考虑所有可能性，则商（q）取56位，余数（r）取28位。具体实现步骤如下：
（1）、56位余数移位寄存器shx=mod(x)，28位余数寄存器reg=mod(y)，被除数符号flagx=sign(x)，除数符号flagy=sign(y), 29位余数移位寄存器shr=0，56位余数移位寄存器shq=0，k=112； （2）、 若k为奇数， shr左移一位低位补shx最高位， shx左移一位低位补0；
若k为偶数，则 if shr <reg，shq左移一位低位补0，
else        shq左移一位低位补1，shr=shr-reg；
（3）、 重复步骤2，直到k=0； （4）、 结果修正（如表2）。
说明：最后需要根据A、D的符号和shQ、shR、regD的值对计算结果进行修正。修正方法如下表。
shr flagx flagy q r － 正 正 shq shr（27..0）
0 负 正 （not shq）+10
非0 负 正 not shq reg-shr（27..0）
0 负 负 shq 0
非0 负 负 shq+1 reg-shr（27..0） －
正 负 （not shq）+1
shr（27..0）
表2
本算法由于基于经典方式实现，思路清晰，同时全串行操作也很大程度上降低了资源量。 2.3、开方
非冗余算法是经典的开方算法，其基于如下计算：
2i+1i R =X-Y
-(i+1)i+1i i+1Y =Y +y 2×
其中X 为被开方数，i R 为第i 次部分余数，i Y 是i 次部分平方根（0Y =0），i y 是第i 次迭代的
booth算法乘法例题讲解平方根结果位的值，该值由余数的正负来决定。如果i+1R 0≥，i+1y 0=；
反之则，i+1y 1=−【2】。 这里介绍的非冗余算法在每次迭代中都会产生准确的结果位，而且在迭代最后可以不加修
正的获得准确的余数。假设被开方数用16bit无符号数表示为：15141310D D D D ...D D =。被开方数的值为15
14
13
1
15141310D 2+D 2+D 2+...D 2+D 2×××××。由于对应每2bit被开方数，平方根的整数部分为1bit ，所以对应16bit 的被开方数其平方根的整数部分为8bit ：76510Q=Q Q Q ...Q Q 。其余数R=D Q Q −×最多有9bit （我们有等式
D=(Q Q+R)<(Q+1)(Q+1)××，所以R<(Q+1)(Q+1)(Q Q)=2Q+1×−×。由于R为整数，所以R 2Q ≤。这就意味着余数最多比平方根多1bit）：87610R=R R R ...R R 。具体步骤如下
（1）、 初始化数据， 78q =0,r =0,k=7； （2）、 if k+1r 0≥，
k k+12k+12k k+1r =r D D q 01−，
else          k k+12k+12k k+1r =r D D q 11−；
（3）、 if k r 0≥，
k k+1k q =q ,Q 0)=，
else          k k+1k q =q ,Q 1)=；
（4）、 重复步骤2和步骤3，直到k=0； （5）、 if 0r 0<,    000r r +q 1=。
这里k 76k q Q Q ...Q =有8k −bits ，k 87k r R R ...R =有9k −bits ，例如076510q =Q=Q Q Q ...Q Q ，
087610r =R=R R R ...R R 。需要注意的是这里的k+12k+12k r D D 代表k+12k+12k r 4D 2+D ×+×。所以
在这个算法中我们不需要乘法和加法，取而代之的是移位和拼接，这更适合于FPGA 操作。实现结构如图3。
图3
3、FPGA实现
我们在Altera公司的QuartusⅡ5.1软件环境下使用VHDL语言完成了上述各算法，并在StratixⅡEP2S30484C5芯片中实现。下面给出了各算法的资源消耗情况，并与IP_core作了比较（如表
3）。
运算 实现方法 ALUTs ALMs LC Comb LC Reg Memory bits 输出 时延 Booth 117 59 37 96 0 37 乘法 （18*18） IP_core 287 148 287 182 0 1(0) 经典方式 399 206 393 262 0 114 除法 （56/28） IP_core 2624 1342 2615 0 0 1(0) 非冗余开方 203 103 79 198 0 32 开方 （64） IP_core 1120 562 1119
1(0)
表3
可以看出本文中提出的算法对二进制数的乘除法以及开方占用资源很少，而且保证了计算精度；IP_core所用时间最短（输出时延可调），但占用逻辑单元随着位宽的增加急剧上升。由此可见，当实际设计对逻辑单元使用要求不苛刻时，便可以使用IP_core，其设计简单且计算时 延小。若对逻辑单元使用有要求且对计算时延不敏感时，使用串行乘除法和开方是很好的选择。
4、结束语
本文给出了乘除法、开方运算的FPGA串行实现算法，与IP_core方法相比，本文中的算法占用逻辑单元少，但计算周期较长，实际应用中可以考虑采用流水线等改进办法，以进一步缩短计算周期。
参考文献
[1] 林瑶，使用VHDL语言中几个常见问题的探讨，微计算机信息：2004年20卷9期，136-137页
[2] IEEE 1995 Yamin Li ,Wanming Chu，Implementation of single precision floating point square root on FPGAs，IEEE 1997.04
[3] 竺士蒙，计算机组成原理，清华大学出版社，2004.1
创新点：本文作者创新点为根据实际情况，提出了几种常见运算的FPGA串行实现方法并给出了实现结构。虽然一定程度上增加了输出时延，但该方法大大节省了资源，具有广泛的应用价值。作者简介
陈国军：男，汉族，1981.1，解放军信息工程大学硕士研究生，主要研究方向扩频通信、卫星定位。
王大鸣：男，汉族，1971.11，解放军信息工程大学副教授，主要研究方向扩频通信、卫星定位。Brief introduction of the author:Chen guojun:male,the Han nationality，born in Jan.1981,a graduate student of Information Engineering University,majored in Spread Spectrum Commmunication and Satellite Positioning.
Wang daming:male,the Han nationality，born in Nov.1971,an associate professor of Information Engineering University,majored in Spread Spectrum Commmunication and Satellite Positioning.
通信地址：河南省郑州市1001信箱825号，陈国军收 邮编：450002
Email: ******************

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。