利用矢量旋转求解平方根的算法及其FPGA实现*_电工电气_中国百科网
利用矢量旋转求解平方根的算法及其FPGA实现*
    　　引言
　　随着电子技术的不断发展，EDA技术在数字信号处理领域得到了越来越多的应用。在FPGA中，应用VHDL语言可以进行加法、减法、乘法等运算，但却不能直接进行开平方运算。传统的开平方算法主要可以分为三大类：牛顿迭代法[1~3]，SRT-冗余算法[4~5]，非冗余算法[6~7]。
　　当直接利用牛顿迭代法进行开平方运算时，涉及到复杂的除法运算。为了避免除法运算，必须首先计算出平方根的倒数，再与被开方数相乘得到平方根。利用牛顿迭代法求根的迭代次数只和初始值与被开方数之间的误差有关，而与被开方数无关。另外，运算中还涉及到查表运算，要使迭代次数降低，必须相应地增加查找表的大小。而且在每次迭代运算中都涉及到乘法、加/减法运算，为了提高乘法运算速度，经常通过采用高速并行乘法器和进位保留加法器来辅助运算，需要较高资源。
　　经典SRT-冗余算法也是基于迭代实现的，在每次迭代中都涉及到加法、乘法、条件判断转移、数值转换等运算，为了减少电路的复杂度，所有的迭代运算都共用硬件资源，因此，该算法的效率较低。
　　非冗余算法可分为恢复余数的算法和不恢复余数的算法。与SRT算法相似，这两种算法都需要复杂的迭代运算。恢复余数的算法由于存在反馈补偿机制，存在很大延时，效率低;不恢复余数的算法[9]还要采用更多加法运算。
　　本文提出了一种基于矢量旋转求三角函数进而求得任意数平方根的算法，并用VHDL语言在Altera EP2S60开发板上加以实现。该算法相比其他传统开平方算法具有处理速度更快、计算误差更小、占用资源更少的显著优势。
　　基于矢量旋转(VR)算法实现开平方的算法
　　矢量旋转算法简介
　　如图1所示，初始向量M0(x0，y0)与x轴重合，经逆时针旋转Dq角度之后得到向量M1(x1，y1)，依此类推，逆时针旋转i次之后得到向量Mi(xi，yi)。
矢量控制　　向量Mi-1(xi-1，yi-1)和Mi(xi，yi)之间的坐标满足如下关系:
　　所以(1)可化简为:
　　利用VR算法实现开平方的算法
　　图1中若令向量的模等于1，则有：
　　VR算法适于计算三角函数，在进行开平方运算时，可利用三角函数倍角之间的关系，将开平方运算转化为三角函数运算。对于t&[-1，1]，初始向量M0(x0，y0)在[0，p]内逆时针旋转，每次旋转角度Dq，经过i次旋转后，总能使得xi=cos(i&Dq)&t，Dq越小，近似程度越高。
矢量控制　　先考察在[0，1]之间的任意实数。假设待开方数为s，且s&[0，1]。有：
　　参数讨论
　　为了将该算法在FPGA上实现，需要选择合适的参数以降低实现的复杂度。在FPGA上实现加减法比较简单，而要实现乘法会比较复杂，在公式(3)中就涉及到乘法运算，要是能通过移位实现乘法将大大提高运算速度。因此Dq要尽量小，以获得更高的近似度，而且这样公式(3)中的cos(Dq)&1，由此可简化计算;另外yi-1tan(Dq)，xi-1tan(Dq)要能通过数据移位实现。因此选择合适的Dq，使得，这样公式(3)中的迭代运算就可用右移k位实现，公式(3)可以简化为：
　　但如果Dq太小，会使迭代次数增多，因此选取合适的Dq是必要的。
　　任意数的开平方算法
　　直接利用VR算法只能计算[0，1]内的平方根值，有一定的局限性。因此，设待开方数T为任意正数，当T&1时，可通过对其预处理后映射到[0，1]区间内再进行开平方运算。步骤如下：
矢量控制　　开平方算法的FPGA实现
　　该开平方算法完全由移位和相加完成，很容易在硬件上实现，而且效率较高。由于FPGA具有并行处理能力，实现开方运算，速度可以比数字信号处理芯片快，以满足某些高速度处理要求。笔者采用的FPGA芯片是Altera公司的Stratix II系列EP2S60开发板。
　　实现方法
　　(1)预处理单元
　　要利用VR算法实现开平方运算，必须对输入进行预处理，设输入为单精度浮点数据格式，在预处理单元中将输入转化成算法可以处理的格式。
　　，有，所以迭代运算时寄存器中存放的上一次旋转所得的坐标值xi，yi每次右移5位。VR算法的FPGA实现架构如图2所示。
　　(3)后处理单元
　　由VR算法得到的结果需要经后处理单元处理成单精度浮点数据格式后输出。该单元需要预处理单元传递相关参数。
矢量控制　　实验结果
　　在Quartus Ⅱ6.0环境下使用VHDL语言完成了上述算法，并在Stratix系列EP2S60开发板上实现。时钟频率为100MHz，综合和布局布线后，需要不到1%的ALUT和56个寄存器，因此实现该算法只需要占用很少的资源。仿真波形如图3所示。
　　波形图中的被开方数范围在[0，1]之间，由于以16位二进制数表示，需要对其进行归一化。如图中输入数值65000，归一化后为0.9918，实验中输出开平方值65345，归一化后为0.9971，通过计算，0.9918的理论开平方值约为0.9959，实验值和理论值之间的误差约为0.1195%。
　　由于迭代计算中没有复杂的乘法运算，每次迭代都只需要一次加法运算和一次移位操作。因此本文提出的算法只需要一个时钟周期就可以计算出结果，在理论上没有时延。图3所示的仿真图中有时延是因为为了仿真时间考虑，将循环过程以牺牲时间来实现的，因此该算法具有处理速度快的特点。
　　试验分析
　　在输入数据为16位宽，的条件下进行仿真，得到实验数据。
　　图4是实验值与理论值的比较，由此可见，笔者提出的算法可以很好地逼近理论值，计算误差非常小。
　　在相同器件和相同精度的条件下，对不同的开平方算法的性能进行比较。在输入均为16位的被开方数时，对本算法、参考文献[8]采用的牛顿迭代算法和文献[9]采用的不恢复余数的开平方算法进行比较，结果见表1。
　　在相同精度的条件下，本文算法占用资源比采用牛顿迭代算法和不恢复余数的开平方算法分别少了9%和6%，完成一次平方根运算需要的周期明显减少，只需要1个时钟周期就可以输出运算结果，以后每个时钟输出1个运算结果。而牛顿迭代算法由于需要反馈调整，需要31个时钟周期才可以完成1次开平方运算;不恢复余数的开平方算法则需要9个时钟周期才能输出第一个结果。
　　在硬件速度允许的情况下，该算法可以进一步提高以获得更好的性能，这取决于迭代计算中每次旋转角度大小的选择。
　　本文提出了一种基于矢量旋转求三角函数进而求得任意数平方根的算法，并在FPGA上加以实现。该算法没有时延，且迭代次数少;在相同的计算误差下，使用的算术逻辑单元较少，适于在FPGA上实现，满足了数据更快处理速度和芯片更少面积的要求。
　　参考文献：
　　[1] Hennessy J, Patterson D. Computer Architecture, A Quantitative Approach[M], Second Edition, Morgan Kaufmann Publishers, Inc., 1996
　　[2] Kabuo H, Taniguchi T, Miyoshi A. et al. Accurate Rounding Scheme for the Newton-Raphson Method Using Redundant Binary Representation[J], IEEE Transaction on Computers, Vol. 43, No. 1, 1994. pp43-51
　　[3] Markstein P, Computation of Elementary Functions on the IBM RISC RS6000 Processor[J]. IBM Jour. Of Res. and Dev., January, 1990. pp111-119
　　[4] Ercegovac M, Lang T, Radix-4 Square Root Without Initial PLA[J], IEEE Transaction on Computers, Vol. 39, No. 8, 1990. pp
　　[5] Lang T, Montuschi P, Very-high Radix Combined Division and Square Root with Prescaling and Selection by Rounding[J], Proc. of 12th IEEE Symposium on Computer Arithmetic, IEEE Computer Society Press, 1995. pp124-131
　　[6] Bannur J, Varma A, The VLSI Implementation of A Square Root Algorithm[J], Proc. of IEEE Symposium on Computer Arithmetic, IEEE Computer Society Press, 1985. pp159-165
　　[7] Johnson K C, Efficient Square Root Implementation on the 68000[J], ACM Transaction on Mathematical Software, Vol. 13, No. 2, 1987. pp138-151
　　[8] 王艳梅,王同杰,郑成文.用VHDL实现的开方运算[J].沈阳工业学院学报,): 3
　　[9] 林志谋，卢贵主.一种适合FPGA实现的开平方算法[J].厦门大学学报,):119-201
Copyright by ；All rights reserved.& & &移位累加乘法器的计算过程类似手算十进制乘法的过程。具体细节可参见中文版《数字设计---原理与实践(第3版)》P316 组合乘法器一节。
& & &现以4位无符号数乘法为例加以说明。
& & &两个无符号的4位数相乘结果为8位数。因此先定义两个8位的变量 a,c, 用来缓存被加数和输出结果，定义一个4位变量 b 来缓存加数。
& & &常规的计算过程是：将4位被加数赋值给 a 的低四位，然后与 b 的最低位相乘，接着a 左移一位后与b的第2位相乘，再与之前的结果相加，依次进行下去，直到计算完成为止。4位数据相乘需要做3次移位和3次加法。
& & &这里需要用到verilog的移位运算符，当将一个数移位后再赋值给一个相同位宽的变量时（比如这里的a移位后再赋值给a）,如果使用左移&&运算，则移出的最高位被截掉，最低位补0；若使用右移&&运算，则移出的最低位被截掉，最高位补0 。
& & &因为这里的移位相加没有严格的顺序要求，因此既可以使用左移，也可以使用右移，当然左移位更符合我们的思维。
& & &Verilog代码：
module multi44(dina,dinb,dout,clk,rst);input clk,input [3:0] dina,output [7:0]reg [7:0]reg [7:0] a,reg [3:0]reg [1:0]regalways @ (posedge clk or negedge rst)begin
a&=0; b&=0; c&=0;
state&=0; dout&=0;
case(state)
1'b0: //初始化和输出结果
a[4:1]&= //装载被乘数dina（相当于已经左移1位）
b&= //乘数dinb缓存
//初始化输出中间结果
if(dinb[0]==1)
c&={4'b0,dina};
1'b1: //移位-相加
if(b[i]==1)
//与上一次移位后的a相加
a&=(a&&1); //左移一位，下次使用
default: dout&=0;
endendmodule
& &用Modelsim仿真结果如下：
& & &由此可以看出，4位的乘法需要4个时钟周期。选择spartan&xc3s400综合后的最小时钟周期如下：
& & &占用资源情况如下：
阅读(...) 评论()第31卷第5期；2008年10月；电子器件；ChineseJournalOfElectron；Vol.31No.5Oct.2008；A32bitMultiplierDesignBa；LIUXue2yong,LIXiao2jiang；(TheInstituteofMicroelec；Abstract:Themultiplieris；Keywords:switc
第31卷　第5期
2008年10月
ChineseJournalOfElectronDevices
Vol.31　No.5Oct.2008
A32bitMultiplierDesignBasedonSwitch&Shift
LIUXue2yong,LIXiao2jiang,MACheng2yan
(TheInstituteofMicroelectronics,CAS,Hangzhou310053,China)
Abstract:ThemultiplierisanimportantandcomplexpartintheALUdesignofCPU,ittakesuparelativelargerareaandlongerdelay.Accordingtothedifferentrequirementsofsystem,wecandesignoutvariousmultipliers.Thispapermakesacompromisebetweensystemclockandarea,bringingoutanonesingleclockmultiplierdesignbasedonswitchandshiftoperation.AtlastbyusingtoolsitgivesoutthesynthesisreportandsimulatingwavetodrawaparallelthistheonegeneratedfromSYNOPSYSdesign_ware.
Keywords:multi2shiftEEACC:6230
一种开关移位式32位乘法器的设计
刘学勇,李晓江,马成炎3
(杭州中科微电子有限公司,杭州310053)
摘　要:乘法器在CPU的ALU设计中是很重要,也是较为复杂的一部分,它占据大的面积和较长的延时。根据系统不同的
要求,我们可以设计出不同的乘法器。本文是在系统时钟要求和面积两方的限制下做了折衷,提出了一种基于开关和移位工作方式的多时钟周期乘法器的设计。最后用DC进行综合,并经VCS仿真得到结果与SYNOPSYS公司design_ware里的乘法器进行比较,指出其优缺点。
关键词:开关;移位;多周期;乘法器中图分类号:TN402　　
文献标识码:A　　文章编号:08)
面积和延时的目的。其具体思路是把2个32bit分
解成为4个16bit的数来进行操作。其分解出来的16×16位的无符号数乘法属于一个原子操作,用一个组合逻辑在一个clock内完成。
　　乘法器的代价很高并且运算很慢,许多计算问题的性能常常是由乘法运算所能执行的速度决定的[3]。在CPU的运算功能块ALU设计中,根据系统不同的要求,我们又可以设计单时钟周期或者多时钟周期的乘法器。有关单周期和多周期乘法器稍微系统一点的阐述,可以参考文献[7]。一般说来直接在verilog代码“×”号会使DC直接调用design2ware里的单时钟乘法器进行综合,此乘法器的面积和延时都比较大。如果需要降低延时并且减小面积的情况下,我们要对乘法操作时钟数进行牺牲。为此,针对小面积小延时的情况,作者采用分解成原子操作的方法来实现32带符号位数的乘法,达到减小
1　原子乘法的实现
乘法原子操作是16×16位乘法的一个时钟实现,是整个32位乘法器的关键。此实现基于开关移位原理。考虑到图的表示过于复杂,暂用8×8的原子操作来图解原理,以此达到理会16×16的原子操作过程。
先给出A=,B=。如图1,
作者简介:刘学勇(19842),男,现为中国科学院微电子研究所2005级硕士研究生,主要研究方向为数字SOC设计;
李晓江,男,现为中国科学院微电子研究硕士生导师,主要研究方向为数字SOC设计;
马成炎,男,研究员,中国科学院微电子研究所博士生导师,研究方向模拟射频芯片设计,machengyan@。
圆圈里的数字表示乘数B,如果为1则表示开关打开,选择A;如为0则不打开选择0
图1　原子操作原理解析
考虑对称性,把B的8bit4,
两两相邻为一组,每组2bit传递A。位方框L1),,如图形成了A1,S1,0和A。再把这四个数据重新分组,此时移位为移2位。最后得出来的数据只有一组,左边移4位与右边相加就得到乘法原子操作的结果S3。下面给出每步操作的中间结果,如图2
bit乘法整合实例
。通常的做法是在写代码时分为正数
乘正数,负数乘负数等[6]。这样比较麻烦,本文干脆直接先把两个乘数转换成绝对值后再根据原来两数的最高位符号位来判断乘积结果是否要由补码转成原码。这只需要用A[31]和B[31]相异出来的结果用来选择乘积和补码就行了。图中的trans以及trans64都是进行补码转换。
3　进位问题的说明
由于两个32位乘数的最高位都为0,所以最终乘积一定是62位的。分解的乘数中得到的4个子乘积项依次为32位,31位,31位,30位。要考虑进位问题,我们只需要拿最大的数去相乘,如果最大的数都没有发生进位,则其他数据更不可能有进位问题。选取最大的数7FFF_FFFF和它自己7FFF_FFFF相乘。以此来考虑进位问题。下面分时钟来说明子乘积项如何相加。
(1)第1个CLK后,得到32位乘积FFFE20001。
(2)第2个CLK后,得到31位乘积7FFE28001。把它与第一个乘积的高16位FFFE进行相加,得到31位(而不是32位)和7FFF_7FFF。所以
图2　原子操作数据运算说明
2　32位乘法器的整合
有了16×16位乘法原子操作,我们可以由它构
造多周期32位乘法器。两个32位乘数都是被转换成了绝对值的,所以最高位都为0,这样2个32位乘数实质上分解成2个15位数和2个16位的数。这样也有一个好处就是可以消除一些乘积间有进位的问题。
还是用图来说明问题,取A=F5D8_C3D5,B=7DF8_FA1B。先把它们转换成补码即绝对值,分别为0A27_3C2B和7DF8_FA1B。再对这两个补码进行乘数分解,如图3。
这个流程图很明朗,BEHAVIOR一栏用箭头指出各步骤操作的意义。在经过4个clock后已经可以得到一个乘法结果,但其还不是最终结果,
此31位加法操作没有进位。
(3)第3个CLK后,得到31位乘积7FFE28001,然后在加上第2个CLK后得到的和7FFF27FFF得到FFFE_0000,此时两个31位数相加发生
了进位但最后结果没有超过32位。
(4)第4个CLK后,子乘积结果为30位的3FFF20001,加上上个CLK得到的和的高16位FFFE得到30位的3FFF_FFFF,无加法进位。这
说明,这步操作最多就是产生30位的和。
通过以上4个CLK的运算,我们可以看到,最
长的是31位加31位得到32位的数据,我们就可以通过资源复用,用一个32位的半加器用来完成上述全部操作,其中位数不够的高位填补0。这样在最大的数都只采用一个32位加法器和4个时钟周期完成了乘法操作,我们可以推测出其他数据一样满足这样的要求。
本设计用了4个时钟周期来完成一次带符号32位数据乘法运算,虽然时钟周期多,但换来的是面积的减少。这在面积要求比较严格而时钟数不太紧的情况下是很有利的。
作者完成乘法器verilog[]且使用SYNOPSYS工具到数据如下:
m　面积:35700μm×最大延时:15.18ns
而如果调用用SYNOPSYS自身design_ware的乘法器(单时钟周期)我们得到数据如下:
μm×μm　面积:64440最大延时:25.24ns对于design_ware里的乘法器,它本身是采用
了Wallacetree或者基于Booth编码等途径优化过的[5],所以相对作者自己直接用32位(即一个clock做完)做原子操作得出的面积和延时来说是比较好的。所以要想进一步减少延时和面积,只有通过牺牲时钟数来获取。
由数据可见,本设计要求的面积减少了近一半,由于设计中多出了许多不必要的控制,如果是单纯乘法内核的话可以使面积更加少。再者最大延时缩短了不少,使得系统工作频率得到提高。如果对16位原子操作进行进一步的优化,比如深入研究使其中一个乘数和积的部分寄存器共用[1],还可以使面积和延时更加小,不过鉴于这是新提出的一种基于开关移位的乘法器,故不做优化保持原样,目的是使读者知道这么一种思路。　　用SYNOPSYS的VCS仿真器仿真,得到如下波形,结果正确,注意第一个时钟周期是用来装载数据用,故共5个CLOCK出结果
图4　仿真波形
,。这种设计,但是也开拓了设计思路。另位乘法分解这一操作对于减小面积也是种有效的方法。再者进位的考虑使用了最大数据来衡量其他数据也是可行的。最后把带符号数相成转换成绝对值后再转换回来也是本文的一个特点。参考文献:
[1]　puterOrganization
&Design:TheHardware/Software[M].Interface(SecondE2dition).郑纬民,等译.第二版,清华大学出版社,]　SamirPalnitkar.VerilogHDLAGuidetoDigitalDesignand
Synthesis[M].(SecondEdition).夏宇闻,胡燕详,刁岚松等
译,第二版,电子工业出版社,2004,11.
[3]　RabaeyJamM,ChandrakasanAnatha,DigitalIntegratedCir2
cuitsADesignPerspective(secondEdition).周润德等译,第
二版,电子工业出版社,2005,7.
[4]　HennessyJohnL,PattersonDavidA,ComputerArchitecture:
AQuantitativeApproach[M].(ThirdEdition),机械工业出版
社,2002.9.
[5]　王彬,任艳颖编著.数字IC系统设计[M].西安电子科技大学
出版社,2005,9.
[6]　朱子玉,李亚民,CPU芯片逻辑设计技术[M].清华大学出版
社,2005,1.
[7]　CilettiMichaelD,AdvancedDigitalDesignwiththeVerilog
HDL[M].张雅绮,李锵等译,电子工业出版社,2005,1.
包含各类专业文献、行业资料、专业论文、中学教育、幼儿教育、小学教育、高等教育、生活休闲娱乐、外语学习资料、一种开关移位式32位乘法器的设计_图文93等内容。　
　设计内容:设计一个 6*6 串行乘法器 设计要求: (...开关级基本结构模型,例如 p m o s 和 n m o ...常见的有移位相加法,加法树 法,查表法,混合法等等... 　南昌航空大学实验报告 课程名称:EDA 技术实验 学号: 指导教师评定:___ 实验名称:移位相加 8 位硬件乘法器电路设计 姓名: 签名: 一、实验目的: 1、 学习移位... 　12 第一章 前言 1.1 设计概述 1.1.1 问题提出与原理 采用元件例化的设计方法,设计一个移位相加型 8 位硬件乘法器设计。下图 所示为一个基于时序结构的 8 ... 　VLSI电路系统与设计_32bit移位相加乘法器_信息与通信...个部分: 右移寄存器, 位加法器, 32 32 乘 1 ... 　学号: 课程名称: 题目: 学生姓名: 学 FPGA 设计 移位相加 8 位硬件乘法器电路设计 院(系):信息科学与工程学院 专业班级: 一、 产品设计需求说明 本产品实现... 　设计任务与要求 1.内容: 由 8 位加法器构成的以时序逻辑方式设计的 8 位乘法器乘法通过逐向 移位加原理来实现,从被乘数的最低位开始,若为 1,则乘数左移与 ... 　位乘法器逻辑原理图 三.8 位移位相加乘法器运算逻辑波形图 8 位移位相加乘法器运算逻辑波形图 四.实验总结通过这次设计,进一步加深了对 EDA 的了解,让我对它有... 　移位相加乘法器_信息与通信_工程科技_专业资料。vhdl语言程序设计实实例一、 设计目标: 设计一个 8 位二进制乘法电路,采用移位相加的方法实现八位二进制数相乘。 ... 　移位累加乘法器_电子/电路_工程科技_专业资料。研究...2013年注会设计统考真题及答案68份文档 新市场营销法则...一种开关移位式32位乘法... 3页 2下载券 移位相加...当前位置： >
假定一次ALU运算用1个时钟周期，移位一次用1个时钟周期，则最快的32位原码一位乘法所需要的时钟周期数大约为（）。
所属学科：
试题类型：客观题
所属知识点：
试题分数：1.0 分
暂未组卷。
暂无学习笔记。
&&&&&&&&&&&&&&&长沙希赛教育科技有限公司 版权所有 & &&