CN1122024A - 一种任意字长、任意精度的乘法运算方法及乘法器 - Google Patents
一种任意字长、任意精度的乘法运算方法及乘法器 Download PDFInfo
- Publication number
- CN1122024A CN1122024A CN 94114858 CN94114858A CN1122024A CN 1122024 A CN1122024 A CN 1122024A CN 94114858 CN94114858 CN 94114858 CN 94114858 A CN94114858 A CN 94114858A CN 1122024 A CN1122024 A CN 1122024A
- Authority
- CN
- China
- Prior art keywords
- circuit
- multiplier
- decoding
- product
- operand
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/38—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
- G06F7/48—Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation using non-contact-making devices, e.g. tube, solid state device; using unspecified devices
- G06F7/52—Multiplying; Dividing
- G06F7/523—Multiplying only
- G06F7/525—Multiplying only in serial-serial fashion, i.e. both operands being entered serially
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- Complex Calculations (AREA)
Abstract
本发明提供了一种有任意长度、任意精度的乘法运算方法及乘法器。该乘法运算的操作数以任意长度,各取一位成对由高位到低位有规律顺序输入,通过转换电路、进位电路、个位电路、累加器逐位计算,乘积从高位到低位有序输出,运算由高位开始,可以在任意位终止,因而具有任意精度,提高处理速度。可代替目前使用的浮点乘法器和定点乘法器,运算不需操作数全部位到齐就开始进行,利于多级连乘的并行运算。
Description
本发明涉及一种计算机中心处理单元中的算术运算器。
传统的定点乘法器是一种采用n位移位寄存器和n位加法器,重复n次位移和n次n位加法,实现n位整数相乘,这种乘法器速度较慢。另一种采用阵列乘法器,采用n(n-1)个一位全加器和n2个“与”门,实现n位数乘以n位数,这种在位数增多时,线路复杂。还有一种采用ROM查表法,这种在位数增多时,空间需要很大。这几种乘法器线路实现都受到运算器字长的限制,不可能做到任意长度的两操作数相乘。线路上需设置专门机构检测溢出。传统的浮点乘法器比定点乘法器可实现大范围数的乘积,线路比定点乘法器复杂,操作数大时,精度降低。上述乘法器在数的表示范围和精度上受到结构限制。传统的乘法器把两个操作数一次存入两个n位寄存器,进行运算,这种需要等到全部都到齐才开始运算,用于流水处理或多处理机并行处理时,进行多于两个操作数连续相乘,下一级运算必须等到上一级运算的全部2n位结果都出来才能开始,增加了等待时间。
本发明的目的在于避免上述现有技术不足之处,提供一种可以实现两操作数有任意长度,任意精度的乘法运算方法及乘法器;在运算时从高位到低位逐位计算,乘积从高位到低位得出;在不需要绝对精度时,舍去对低位处理,加快运算速度;用一个乘法器既可作为浮点乘法器又可作为定点乘法器;运算不需操作数全部位到齐就开始进行,利于多级连乘运算的并行处理。
附图的图面说明:
图1.乘法运算流程图
图2.乘法器结构图
图3.控制逻辑电路图
图4.五进制电路图
图5.进位电路图
图6.个位电路图
本发明的目的可以通过以下措施来达到:
该乘法器包括操作数寄存器、控制逻辑电路、五进制转换电路、进位电路、个位电路、缓存器、累加器、寄存器、乘积寄存器堆;乘法器操作数以任意长度,成对由高位到低位顺序输入,通过转换电路、进位电路、个位电路、累加器逐位运算,将乘积由高位到低位有序输出;
任意字长、任意精度的乘法运算流程为:
——输入运算的控制参数:位数n、精度p
——操作数按规律每次从A、B队列中各取一位:Ai、Bj
——将Ai、Bj分别转换成五进制表示
——分别求Ai、Bj的进位和Ai、Bj的个位
——根据进位和个位的有序累加(参数k)得出一位乘积Cm
参看乘法流程图,A、B是二个任意多位的二—十进制或二—十六进制的操作数(为叙述方便,假设为等长度n位)。p是所需计算精度位数。
A=A1A2A3……An
B=B1B2B3……Bn其中位Ai、Bj(1≤i,j≤n)。计算A*B=C的过程即求
C=C1C2C3……C2n-1位Cm(1≤m≤2n-1)与Ai、Bj有如下对应关系:
C1: A1B1
C2: A2B1 A1B2
C3: A3B1 A2B2 A1B3
… … …
Cn: AnB1 An-1B2 … … A1Bn
Cn+1: AnB2 An-1B3 … A2Bn
… … …
C2n-2: AnBn-1 An-1Bn
C2n-1: AnBnAi、Bj以固定周期时钟读入,则Cm输出的周期为:
Cm :C1、C2、C3、…Cn、Cn+1、…、C2n-1
周期:1、 2、 3、 …n、 n-1、 …、1
结合图2进一步详述乘法运算方法,A寄存器堆、B寄存器堆分别以高位到低位的顺序存放二—十进制或二—十六进制n位操作数A、B,其中的位表示为Ai、Bj(1≤i,j≤n),位数n、运算精度p和时钟信号ck送入控制逻辑电路,由此产生读取操作数的时钟ck1和输出乘积位的时钟ck2,并在达到所需精度的第p位时停上后续位的计算。
使用五进制在于简化进位、个位运算时的线路。数的五进制表示为,二—十进制或二—十进制数a0a1a2a3
小于5时: a0a1a2取0…4,a3=0
大于5时:取a0a1a2a3-5的倍数,另有三位表示数的大小:
大于5: a3=1 反之为零。
大于10:a4=1 …
等于15:a5=1 …以Ai为例:
Ai(a0a1a2a3a4a5) Ai(a0a1a2a3a4a5)
3 ( 1 1 0 0 0 0 ) 2 ( 0 1 0 0 0 0 )
8 ( 1 1 0 1 0 0 ) 7 ( 0 1 0 1 0 0 )
C ( 1 1 0 1 1 0 ) B ( 0 1 0 1 1 0 )
进位电路由五进制数直接输出其乘积的百位和十位数值。求Ai*Bj的进位
Cmk=Cmk11Cmk10Cmk9Cmk8Cmk7Cmk6Cmk5Cmk4。基于五进制求进位规律为:((Ai*Bj)的进位表示为(Ai*Bj)进)
(1)Ai、Bj皆小于5: (Ai*Bj)进=1或者0
(2)一大于5、一小于5: [(Ai+5)*Bj]进
(3)两皆大于5、小于10:[(Ai+5)*(Bj+5)]进
(4)一大于10、一小于5:[(Ai+10)*Bj]进
(5)一大于10、一小于5:[(Ai+10)*(Bj+5)]进
(6)二大于10: [(Ai+10)*(Bj+10)]进
经过对输入数据译码,并把各分解运算的进位相加,可求出任意二数相乘进位。表示为高位的Cmk进高和低位Cmk进,第m个乘积位第k个节拍的进位高位和低位。
求Ai*Bj的个位指其乘积中小于10(十进制)的部份,输入操作数的五进制数和原二—十进制或二—十六进制的最低位ao、bo,具体如下:个位对操作数译码真值表如下左二图,将Ai、Bj译码输出相加,作为乘积译码的输入,输出乘积的五进制数。按照ao、bo的乘法规则,若满足乘法奇偶性,则乘积译码输出即为(Ai*Bj)个,否则加5后作为(Ai*Bj)个。
Ai的真值表
Bj的其值表
乘积译码真值表记为:Cmk个,第m个乘积位第k个节拍的个位。
输入 | 输出 |
01234 | 01243 |
输入 | 输出 |
01234 | 00132 |
输入 | 输出 |
01234567 | 01243124 |
m=2n-1(精度到最低位)或m=p(精度到所需位)。乘积根据需要可为二—十进制或二—十六进制数,提高实用性。
这样的单元乘法器重复设置,可实现乘法运算的两操作数并行运算,或多操作数并行连乘的功能。
本发明相比现有技术有如下优点:
由于本发明基于操作数位的运算,位数增加仅仅意味重复运算次数,因而可以做到无限字长,不会产生溢出。乘积的个位,进位独立地求出,可以并行化,运算由高位开始,可以在任意位终止,因而具有任意精度,可以牺牲精度赢来处理速度,把精度、数表示范围大小对线路结构复杂度的依赖变为对运行时间快慢的依赖,而且可由应用程序直接控制。实现可用一个乘法器既取代目前的定点乘法器,同时又代替浮点乘法器。把单个乘法单元重复设置可多位操作数并行处理,甚至可对连乘高度并行,更体现速度的提高。
下面将结合附图实施例进一步详述:
参看图2,A寄存器堆、B寄存器堆分别以高位到低位的顺序存放二—十进制或二—十六进制n位操作数A、B,其中的位表示为Ai、Bj(1≤i,j≤n),位数n和运算精度p、时钟信号ck送入控制逻辑电路,由此产生读取操作数的时钟ck1和输出乘积位的时钟ck2,并在达到所需精度时停止后续位的计算。两个五进制译码电路,分别将上述Ai、Bj转换成进位电路、个位电路易于处理的五进制数。进位电路由两个五进制数直接输出其乘积的百位、十位数值。个位电路输出个位数值。缓存器作用是对数据延迟一个ck1时钟。进位缓存器对进位数缓冲一拍,两个位缓存器对个位数据各缓冲一拍。三个缓存器先将原有数据输出到下一级,然后再接收新数据。累加器先后将原有数据和乘积Cmk-2的个位相加,再和Cmk-1的进位相加,再和Cmk的较高进位相加,累加器的位数决定操作数至少允许最大的位数:
每增加4位长度,操作数位数扩大十倍。累加器在ck2的控制下,结束上述过程。与寄存器左移4位(二进制)后的数据累加,并将结果送回寄存器。上述寄存器左移即可送出一位乘积给乘积寄存器堆,完成一位乘积。只要m≤2n-1或m≠p,这过程就继续下去。
累加器长度(二进制) | 最少位数可达(十进制) |
8 位 | 12 位 |
12 位 | 125 位 |
16 位 | 1250 位 |
20 位 | 12500 位 |
下面对本乘法器电路所采用的控制逻辑电路,五进制电路、进位电路、个位电路加以更详细说明:
参看图3,控制逻辑电路由减计数器1、加计数器2、与门3、辅助计数器4、5和加法器6、比较器7、8、9、与门10组成。作用是控制Ai、Bj的输入顺序和Cm输出顺序,根据输入的控制参数n、p和时钟信号ck,产生读入数据的固定时钟信号ck1,产生乘积输出时钟ck2、运算结束信号stop。具体是:减计数器1对i计数,加计数器2对j计数,m(n时,辅助计数器4由与门3控制设置i的初值(即j的末值),辅助计数单元5由与们10控制设置i的末值(即j的初值,当m≥n时,辅助计数单元4设置i的末值(j的初值),辅助计数单元5设置j的末值(i的初值)。当p≥n时,加法单元6将n和i的末值相加输出,与p比较产生停止信号stop。当p<n时,i的末值直接与p比较产生信号stop。
参看图4,五进制电路由数值判定电路11,加法单元12组成。四位二进制a3a2a1a0送入数值判定电路11,决定a5a4a3,然后经控制门13选择5或10的补码,送加法单元12和原数相加,得到数的五进制表示a5a4a3a2a1a0。
参看图5,进位电路由译码电路14、15、16、17加法单元18、19、20组成。译码电路对输入的Ai、Bj的五进制数译码,输出
(15*15)进, (10*10)进, (5*10)进,(5*5)进,
(3*3)进, (4*4)进, (d*5)进(d小于5)。根据两数相乘的六种情况,由加法器18、19、20相加,加法器输出即是乘积的百位十位的值。
参看图6.个位电路由译码电路21、22和加法器23、26、与门组成。译码电路21、22分别对输入的Ai、Bj的五进制译码,(见前真值表)加法器23的输出由译码电路(见前真值表),译码后输出,由原操作数的最低位经与门25相”与”,决定是否由加法器26“加”5。
如果N个结构完全相同的完整单乘法器并行,就能够实现N+1个操作数连乘的并行处理,A*B*C*D*…的计算,其中A、B、C、D等都是多位数,利用前述的本乘法器的运算特点,将本级的乘积寄存器堆和下级的A寄存器堆相连接,便能实现当A*B的高位结果一出来就可以立即着手处理乘C的高位,其乘积高位一出来,就可以立即着手乘以D的高位,达到A*B的较低位同A*B*C的较高位,和A*B*C*D*…的更高位同时处理。
Claims (7)
1.一种任意字长、任意精度的乘法运算方法,其特征在于乘法操作数以任意长度,成对由高位到低位顺序输入,通过转换电路、进位电路、个位电路、累加器逐位运算,将乘积由高位到低位有序输出;
乘积Cm(1≤m≤2n-1)与操作数Ai、Bj有如下对应关系:
C1: A1B1
C2: A2B1 A1B2
C3: A3B1 A2B2 A1B3
… … …
Cn: AnB1 An-1B2 … … A1Bn
Cn+1: AnB2 An-1B3 … A2Bn
… … …
C2n-2: AnBn-1 An-1Bn
C2n-1: AnBn
操作数寄存器堆以高位到低位的顺序存放二—十进制或二—十六进制n位操作数;
控制逻辑电路根据输入位和要求运算精度产生读取操作数的时钟ck1和输出乘积位的时钟ck2,并在达到所需精度时停止后续位的计算;
五进制转换电路将成对输入的每位操作数转成五进制数;
进位电路将两个十或者十六进制数相乘的进位简化为两个五进制相乘的进位与五进制数乘与5、10的进位的和,直接输出其乘积的十位数值;
个位电路对输入Ai、Bj直接译码:
Ai: 01234 Bj: 01234
译码: 01243 译码: 00132译码输出相加后再译码输出个位数值:
相加:01234567
译码:01243124
缓存器、累加器根据逻辑电路的控制时钟进行有序累加,将乘积从高位到低位输出,累加器的位数决定操作数至少允许最大位数;
乘法运算可两操作数并行运算,或多操作数并行连乘。
2.一种根据任意字长、任意精度的乘法运算方法而设计的乘法器,其特征在于乘法器由操作数寄存器、控制逻辑电路、五进制转换电路、进位电路、个位电路、缓存器、累加器、寄存器、乘积寄存器堆组成。
3.根据权利要求2所述的根据任意字长、任意精度的乘法运算方法而设计的乘法器,其特征在于控制逻辑电路由减计数器[1]、加计数器[2]、与门[3]、辅助计数器[4]、[5]和加法器[6]、比较器[7]、[8]、[9]、与门[10]组成,控制Ai、Bj的输入顺序,Cm输出顺序,根据输入的控制参数n、p和时钟信号ck产生输入数据的固定时钟信号ck1、乘积位输出时钟ck2和计算结束信号stop。
4.根据权利要求2或3所述的根据任意字长、任意精度的乘法运算方法而设计的乘法器,其特征在于五进制电路由数值判定电路[11]、加法单元[12]和控制门[13]组成,把四位二进制a3a2a1a0送入数值判定电路[11],决定a5a4a3,然后选择5或10的补码,送加法单元[12]与原数相加,得到数的五进制表示a5a4a3a2a1a0。
5.根据权利要求4所述的根据任意字长、任意精度的乘法运算方法而设计的乘法器,其特征在于进位电路由译码电路[14]、[15]、[16]、[17]、加法电路[18]、[19]组成。译码电路对输入的Ai、Bj五进制数译码,输出乘积的百位十位的值。
6.根据权利要求4所述的根据任意字长、任意精度的乘法运算方法而设计的乘法器,其特征在于个位电路由译码电路[21]、[22]和加法电路[23]组成,译码电路[21]、[22]分别对输入的Ai、Bj的五进制译码,加法器[23]的输出经由译码电路[24]译码,由原操作数的最低位的”与”,决定是否由加法器[26]加5后输出。
7.根据权利要求5或6所述的根据任意字长、任意精度的乘法运算方法而设计的乘法器,其特征在于所述乘法单元重复设置,将上级乘积寄存器堆和下一级中的一个操作数寄存器堆互联达到多于两个操作数连乘的并行处理。
Priority Applications (2)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN 94114858 CN1122024A (zh) | 1994-08-15 | 1994-08-15 | 一种任意字长、任意精度的乘法运算方法及乘法器 |
PCT/CN1995/000064 WO1996005554A1 (fr) | 1994-08-15 | 1995-08-15 | Procede et unite de multiplication |
Applications Claiming Priority (1)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
CN 94114858 CN1122024A (zh) | 1994-08-15 | 1994-08-15 | 一种任意字长、任意精度的乘法运算方法及乘法器 |
Publications (1)
Publication Number | Publication Date |
---|---|
CN1122024A true CN1122024A (zh) | 1996-05-08 |
Family
ID=5037230
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
CN 94114858 Pending CN1122024A (zh) | 1994-08-15 | 1994-08-15 | 一种任意字长、任意精度的乘法运算方法及乘法器 |
Country Status (2)
Country | Link |
---|---|
CN (1) | CN1122024A (zh) |
WO (1) | WO1996005554A1 (zh) |
Cited By (4)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN100356314C (zh) * | 2003-01-06 | 2007-12-19 | 上海奇码数字信息有限公司 | 可控制锁存累加器的系统与方法 |
CN103853524A (zh) * | 2012-11-30 | 2014-06-11 | 安凯(广州)微电子技术有限公司 | 一种乘法器装置和实现乘法运算的方法 |
CN111091190A (zh) * | 2020-03-25 | 2020-05-01 | 光子算数(北京)科技有限责任公司 | 数据处理方法及装置、光子神经网络芯片、数据处理电路 |
CN111988031A (zh) * | 2020-08-28 | 2020-11-24 | 华中科技大学 | 一种忆阻存内矢量矩阵运算器及运算方法 |
Families Citing this family (2)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN111475135B (zh) * | 2019-01-23 | 2023-06-16 | 阿里巴巴集团控股有限公司 | 一种乘法器 |
CN112416294B (zh) * | 2020-11-20 | 2022-09-16 | 安谋科技(中国)有限公司 | 处理器及其二进制累加方法和计算机可读介质 |
Family Cites Families (3)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JP2838326B2 (ja) * | 1991-04-16 | 1998-12-16 | 三菱電機株式会社 | ディジタル乗算器 |
JPH0820942B2 (ja) * | 1991-09-26 | 1996-03-04 | インターナショナル・ビジネス・マシーンズ・コーポレイション | 高速乗算器 |
DE69329260T2 (de) * | 1992-06-25 | 2001-02-22 | Canon K.K., Tokio/Tokyo | Gerät zum Multiplizieren von Ganzzahlen mit vielen Ziffern |
-
1994
- 1994-08-15 CN CN 94114858 patent/CN1122024A/zh active Pending
-
1995
- 1995-08-15 WO PCT/CN1995/000064 patent/WO1996005554A1/zh active Application Filing
Cited By (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
CN100356314C (zh) * | 2003-01-06 | 2007-12-19 | 上海奇码数字信息有限公司 | 可控制锁存累加器的系统与方法 |
CN103853524A (zh) * | 2012-11-30 | 2014-06-11 | 安凯(广州)微电子技术有限公司 | 一种乘法器装置和实现乘法运算的方法 |
CN103853524B (zh) * | 2012-11-30 | 2017-02-08 | 安凯(广州)微电子技术有限公司 | 一种乘法器装置和实现乘法运算的方法 |
CN111091190A (zh) * | 2020-03-25 | 2020-05-01 | 光子算数(北京)科技有限责任公司 | 数据处理方法及装置、光子神经网络芯片、数据处理电路 |
CN111988031A (zh) * | 2020-08-28 | 2020-11-24 | 华中科技大学 | 一种忆阻存内矢量矩阵运算器及运算方法 |
CN111988031B (zh) * | 2020-08-28 | 2022-05-20 | 华中科技大学 | 一种忆阻存内矢量矩阵运算器及运算方法 |
Also Published As
Publication number | Publication date |
---|---|
WO1996005554A1 (fr) | 1996-02-22 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
Ma et al. | Multiplier policies for digital signal processing | |
Erle et al. | Decimal multiplication with efficient partial product generation | |
Trivedi et al. | On-line algorithms for division and multiplication | |
JP3244506B2 (ja) | 小型乗算器 | |
CN1503938A (zh) | 乘法逻辑电路 | |
CN1402843A (zh) | 在一个周期内处理乘累加运算 | |
CN87100346A (zh) | 最佳分区再生先行进位加法器 | |
WO2010049218A1 (en) | A high radix digital multiplier | |
CN1020806C (zh) | 使用跳跃阵列和变形华莱士树的并行乘法器 | |
CN1108558C (zh) | 面向算术/移位操作的单指令多数据校正电路 | |
Gnanasekaran | On a bit-serial input and bit-serial output multiplier | |
CN1781076A (zh) | 组合多项式和自然乘法的乘法器架构 | |
CN1786900A (zh) | 基于改进的蒙哥马利算法的模乘器 | |
CN1731345A (zh) | 可扩展高基蒙哥马利模乘算法及其电路结构 | |
CN1122024A (zh) | 一种任意字长、任意精度的乘法运算方法及乘法器 | |
CN1075646C (zh) | 一种高速乘法器 | |
CN1234065C (zh) | 微控制器ip核的处理方法 | |
CN1437155A (zh) | 可以减小误差的平方根计算器 | |
Rezai et al. | Algorithm design and theoretical analysis of a novel CMM modular exponentiation algorithm for large integers | |
Privat | A novel class of serial-parallel redundant signed-digit multipliers | |
CN1290002C (zh) | 高速加法器 | |
CN1180427A (zh) | 以单精度或双精度进行算术运算的系统 | |
RU2638724C1 (ru) | Устройство для коррекции порядка при нормализации чисел | |
CN1085862C (zh) | 高速模乘法装置 | |
CN1591824A (zh) | 40位带舍入功能的快速累加累减器电路实现结构 |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
C06 | Publication | ||
PB01 | Publication | ||
C10 | Entry into substantive examination | ||
SE01 | Entry into force of request for substantive examination | ||
C02 | Deemed withdrawal of patent application after publication (patent law 2001) | ||
WD01 | Invention patent application deemed withdrawn after publication |