关键字 |
Radix2, Radix4 Booth乘数,Booth算法 |
介绍 |
乘法是一种基本的算术运算,它的应用可以追溯到几十年前。早期ALU的加法器最初用于执行乘法运算。随着阵列乘法器的应用,时钟速率增加,时间约束变得严峻。从那时起,实现乘法的方法被提出,这是更复杂的[1-4]。众所周知,乘法运算在数字计算和数字电子学中的应用非常广泛,特别是在多媒体和数字信号处理(DSP)应用领域。乘法运算主要分为三个阶段:第一阶段主要是通过与门数组生成部分乘积;第二阶段采用部分积减积方案减积部分积;最后将偏积[5]相加得到乘积。乘法可以执行:1)有符号的数字;2)无符号数字。 Signed multiplication a binary number of either sign (two numbers whose sign may are not necessarily positive) may be multiplied. But, in signed multiplication the sign-extension for negative multiplicands is not usable for negative multipliers and there are large numbers ofsummands due to the large sequence of 1’s in multiplier. Unsigned multiplication binary number (whose sign is positive) is multiplied. Continuous advances of microelectronic technologies make better useof energy, encode data more effectively, transmit information more reliable, etc. Particularly, many of these technologies address low-power consumption to meet the requirements of various portable applications [7]. In these application systems, a multiplier is a fundamental arithmetic unit andwidely used in circuits. VHDL is one of the commontechniques for the digital system emergent process. The technique is done by program using certain software which performs simulation and examination of the designed system. The designer only needs to describe his digital circuit design in textual form which can remove without the effort to alter the hardware. VHDL is more preferred because this technique can reduce cost and time, easy to troubleshoot, portable, a lot of platform software support the VHDL function and high references availability. All the processes will be running using Xilinx- Quartus software which means the process is simulated only without any hardware implementation .Multiplication is a fundamental operation in most signals processing algorithms. Multipliers have large area, long latency and consume considerable power. Therefore low-power multiplier design has been an important part in low- power VLSI system design. Fast multipliers are essential parts of digital signal processing systems. The speed of multiplier operation is of great importance in digital signal processing as well as in the general purpose processors today. The basic multiplication principle is twofold i.e., evaluationof partial products and accumulation of the shifted partial products. |
文献综述及相关工作 |
乘法器是许多高性能系统的关键部件,如FIR滤波器、[9]、微处理器、数字信号处理器等。系统的性能通常由乘数的性能决定,因为乘数通常是系统[10]中最慢的。此外,它通常是消耗[11]最多的区域。因此,优化乘数的速度和面积是一个主要的设计问题。然而,面积和速度通常是相互冲突的约束,因此提高速度的结果主要是在更大的区域。因此,设计了一个具有不同面积-速度约束的全频谱乘法器,在频谱的一端是完全并行的乘法器,在另一端是完全串行的乘法器。介于两者之间的是数字串行乘法器,其中操作的是由几个位组成的单个数字。 |
这些倍增器在速度和面积上都有适度的表现。然而,现有的数字串行乘法器一直受到复杂的交换系统和/或设计不规范的困扰。Radix- 2n[12]乘法器以并行方式操作数字,而不是位,将流水线化到数字级别,避免了上述大部分问题。他们是由M. K. Ibrahim在1993年介绍的 |
补充表示 |
在补码表示法中,数字在二进制部分中用二的补码表示。在这种方法中,正数的表示方法与符号幅度法相同。它是使用最广泛的表示法。正数简单地表示为以“0”为符号位的二进制数。为了得到负数,把所有0都转换成1,所有1都转换成0,然后加上1。假设,一个数字是2的补体形式,我们必须用二进制来求它的值,那么如果数字以“0”开头,那么它是一个正数,如果数字以“1”开头,那么它是一个负数。如果,number是负的取2的补,我们将得到普通二进制形式的number。以1101为例。取2的补,就得到0011。因为,数字以“1”开头,它是负数,0011是正3的二进制表示。 So, the number is -3. Similarly, we are representing other negative numbers in 2’s complement representation. |
假设我们把小数点后的+5和-5相加,结果是0。现在,用2的补式表示这些数字,然后我们得到+5为0101,-5为1011。这两个数相加得到10000。丢弃进位,则数字表示为' 0 '。在这个带符号的乘法中,我们修改了复杂乘法策略。 |
A.布斯的重新编码算法 |
利用基本的Booth 's Recoding算法进行并行乘法,生成高效的部分积。这些偏积的比特数总是比输入的比特数大。部分积的宽度通常取决于用于重新编码的基数方案。这些产生的部分产物由压缩机添加。因此,该方案使用的部分产品少,功耗低,面积小。 |
有两种类型的算法为乘法生成有效的部分积。首先我们将解释Booth 's Recoding算法的基本技术,然后对Booth 's Recoding算法进行了改进。Radix- 2n[12]乘法器以并行方式操作数字,而不是位,将流水线化到数字级别,避免了上述大部分问题。他们是由M. K. Ibrahim在1993年介绍的。 |
这些结构是迭代的和模块化的。在数字级别上进行的流水线操作带来了恒定的运算速度,而不受乘数大小的影响。时钟速度仅由数字大小决定,而数字大小在设计实现之前已经确定。 |
booth基2编码算法的基本技术 |
Booth算法提供了一个用带符号2的补式表示[8]乘二进制整数的过程。根据乘法程序,乘数中0的字符串不需要加法,只需要移位,乘数中1的字符串从比特权重2k到权重2m可以被视为2k+1 - 2m。 |
布斯算法首先要对乘法器进行编码。在重新编码的格式中,乘数中的每一位都可以取三个值中的任何一个:0、1和-1。假设我们想要将一个数字乘以01110(十进制14)。这个数字可以被认为是10000(十进制16)和00010(十进制2)之间的差值。乘以01110可以通过以下乘积的和来实现: |
I) 24乘以乘数(24 = 16) |
Ii) 2的21乘以乘数的补数(21 = 2)。 |
在标准的乘法运算中,由于字符串中有三个1,所以需要进行三次加法运算。这可以用一个加法和一个减法代替。通过使用表1中总结的下列规则重新编码乘法器01110来识别上述需求。 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-1252-t001.gif) |
状态图 |
基-2布斯乘法器的状态图如图1所示。这里我们有四种不同的状态。对于00,有11个状态我们可以用零来做乘法。对于01个状态,我们可以用1乘以乘法,而对于10个状态,我们可以用-1乘以乘法。 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-1252-g001.gif) |
ASM图 |
图2为基数-2展位乘数的ASM图。它代表了与机器状态相关的各种操作的常规程序。在这里,我们用基基-2展台编码器生成部分产品。利用该方法可以减少部分积的产生,并且计算时间延迟小于普通乘法。 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-1252-g002.gif) |
要为基数-2生成重新编码的乘数,需要执行以下步骤。 |
i)在LSB边附加一个0的给定乘数。 |
ii)用重叠的方式将两位数组合成一组,用上表重新编码。 |
考虑一个8位乘数为11011001,乘数为011100010的例子。 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-1252-e001.gif) |
其中Vdd为电源电压,idd (t)为电路在某一时刻所吸取的电流。 |
根据这个方程,在给定时间内峰值功率的最小值与该时间内引出的电流成正比。由于电流只有在电路有源时才理想流动,因此通过最小化同时有源元件的数量,我们可以减少从电源中抽取的电流尖峰,从而减少ir电压降。 |
为了优化电路的峰值功率,必须减少同时开关的电路元件的数量。 |
在本文的工作中,实现高速乘法器是为了提高并行性,这有助于减少后续计算阶段的数量。布斯算法的原始版本(基数-2)有两个缺点。 |
它们是:1)加减运算和移位运算的次数变多,在设计并行乘法器时变得不方便。(2)当存在孤立的1时,算法效率降低。通过使用改良的radix4克服了这些问题。Booth算法扫描三个比特的字符串:1)必要时扩展符号位1的位置,以确保n为偶数。2)在乘法器的LSB右侧追加一个0。3)根据每个向量的值,每个偏积将为0、+M、-M、+2M或-2M。 |
B的负值由取2的补项得到,本文采用进位前推(CLA)快速加法器。M的乘法是通过将M向左移动一位来完成的。因此,在任何情况下,在设计nbit并行乘法器时,只产生n/2个部分积。部分积按以下规则计算 |
Zn= -2×Bn+1 +Bn +Bn-1 --------- (2) |
其中B是乘数。 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-1252-t002.gif) |
B. base -4的Booth乘法算法 |
实现高速乘法器的解决方案之一是提高并行性,从而减少后续计算阶段的数量。布斯算法的原始版本(基数-2)有两个缺点。它们是: |
(i)加减运算和移位运算的次数变多,在设计并行乘法器时变得不方便。(ii)当存在孤立的1时,算法效率低下。采用改进的base -4布斯乘法算法克服了这些问题。用状态图和ASM图的图形视图描述了base -4算法的设计方法。该算法扫描3位字符串的过程如下: |
1)必要时扩展符号位1的位置,以确保n是偶数。 |
2)在乘数的LSB右边加一个0。 |
3)根据每一个向量的值,每一个偏 |
生成物是0 +y -y +2y或-2y。基-4 booth编码器根据乘法器位对乘法器进行编码。它将用重叠技术一次比较3位。分组从LSB开始,第一个块只使用乘数的两个位,并假设第三位为零。base -4型展位编码器的功能操作如表2所示。基-4布斯乘法器的状态图如图3所示。它由八种不同类型的状态组成,在这些状态中我们可以得到结果,即乘数与0、-1和-2连续相乘。状态图的图示视图根据所采用的编码技术,给出了在不同状态下进行基-4布斯乘法运算的各种逻辑。 |
状态图 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-1252-g003.gif) |
ASM图 |
base -4展台乘法器ASM图如图4所示。这代表了在各种状态下,base -4展台乘法器所需的常规操作流程。在这里,我们可以用base -4展台编码器生成部分产品。利用该方法可以进一步减少部分积的产生和计算时间延迟,比根号2乘法的计算时间延迟要小。 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-1252-g004.gif) |
以基数4为例: |
乘以1 0 0 0 0 0 0 1 |
乘数0 1 1 1 1 1 1 0 0 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-1252-e003.gif) |
结果 |
我们评估了基-2和基-4展台乘法器的性能,并在FPGA上实现。对于Design Entry,我们使用ModelSim 6.3f并使用VHDL进行设计。为了得到功率报告和延迟报告,我们使用Xilinx ISE 9.1i综合了这些乘法器。基基-2和基基-4布斯乘法器合成报告对比见表3。 |
![图像](//www.cheescube.com/articles-images/IJAREEIE-1252-t003.gif) |
结论 |
本文采用VHDL语言设计了基-2和基-4展台乘法器。改进后的基-4布斯乘法器与基-2布斯乘法器相比,延迟和功耗更小。在FPGA上实现后,发现基4乘法器的功耗比基2乘法器低。此外,估计延迟更少的基数-4展位乘数。 |
参考文献 |
- 叶伟昌,任志伟,â '  '高速展位编码并行乘法器设计,â ' ”IEEE计算机学报,第49卷,第1期。7,第692-701页,2000年7月。
- 匡尚容,王俊平,郭苍元,â ' ”基于正则偏积阵列的改进展台乘法器,â ' ”电路与系统学报,vol 56, No 5, 2009年5月。
- 王立荣,shh - jyejou和Chung-Len Lee, â '  '一个结构良好的改进展位倍增器Designâ '  ' 978-1-4244-1617-2/08/$25.00 à ©2008 IEEE。
- 金soojin Kim和Kyeongsoon Cho â '  '工作在GHz的高速改进型展台乘法器的设计Rangesâ '  '世界科学,工程与技术学院61 2010。
- Shiann-RongKuang,成员,IEEE, junun - ping Wang,和Cang-Yuan Guoâ ' ”用正则部分积修改的展台乘法器Arrayâ ' ”IEEE电路交易和SYSTEMSâ '  - II:快速摘要,第56卷,NO. 1。5 2009年5月1549-7747
- Ravindra P Rajput和M. N ShanmukhaSwamyâ '  '用于签名和未签名的高速修改展台编码器乘法器numbersâ '  ', 2012第14届建模与仿真国际会议978-0-7695-4682-7/12 à ©2012 IEEE。
- A. P. Chandrakasan和R. W. Brodersen,低功耗CMOS设计。皮斯卡塔韦,新泽西州:IEEE出版社,1998年。
- A. D. Booth, â '  '有符号的二进制乘法技术,â '  '季刊J.力学在数学中的应用。,第4卷,第2部分,第236-240页,1951。
- John G. proakis, Dimitris G. Monolakis, â '  '数字信号处理,原理,算法和Applicationsâ '  ',第四版。
- Dandapat, S. Ghosal, P. Sarkar, D. Mukhopadhyay (2009), Ã① '  ' A 1.2-ns16à  16位二进制乘法器的使用。高速CompressorsÃⅱ ' ”,电子工程学报,2009,234-239。
- 顾昌华(2003),ÃⅰÂ ' Â '超低压低功率4-2高速压缩机multiplicationsÃⅰÂ ' Â]。电路与系统,2003。在ISCAS A¢03。国际学术研讨会论文集,第5卷,2003年5月,321-324。
- Israel Koren,计算机算术算法A.K.Peters有限公司。ISBN 1568811608。
- 张昌华,谷俊杰,张敏(2004),ÃⅰÂ ' Â]用于快速计算的超低电压低功耗CMOS 4-2和5-2压缩circuitsÃⅰÂ ' Â],电路与系统学报,1985- 1997,卷:51,Issue: 10, 2004年10月。Rashmi Ranjan等/国际计算机科学与工程技术杂志(IJCSET)
|