Lecture 6 定点乘法.ppt

《Lecture 6 定点乘法.ppt》由会员分享，可在线阅读，更多相关《Lecture 6 定点乘法.ppt（38页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、问题n分析手工乘法运算方法在计算机实现时面临的困难分析手工乘法运算方法在计算机实现时面临的困难n原码一位乘中，如何把乘法运算转化为加法运算的？原码一位乘中，如何把乘法运算转化为加法运算的？n原码一位乘中，需要多次通过加法运算和移位得到部分和，原码一位乘中，需要多次通过加法运算和移位得到部分和，效率低，如何提高乘的效率？效率低，如何提高乘的效率？A=0.1101 B=0.1011AB=0.1 1 0 10.1 0 1 1定点乘法运算课程结构计算机系算机系统统计硬件硬件运算器运算器数据表示数据表示数据数据数据数据定点定点原原码反反码补码移移码浮点浮点一般表示一般表示规格化格化IEEE754非数非数

2、值数数据据字符字符汉字字BCD码校校验码奇偶校奇偶校验海明校海明校验循循环冗余冗余校校验运算方法运算方法定点数定点数补码加减加减乘除乘除原原码一位一位乘乘补码一位一位乘乘并行乘法并行乘法原原码除法除法恢复余数恢复余数加减交替加减交替浮点数浮点数加减乘除加减乘除规格化格化溢出判断溢出判断运算器运算器一般运算一般运算快速运算快速运算典型典型ALU存存储器器控制器控制器总线输入入输出出软硬件接硬件接口口软件件分析笔算乘法分析笔算乘法A=0.1101 B=0.1011AB=0.100011110.1 1 0 10.1 0 1 11 1 0 11 1 0 10 0 0 01 1 0 10.1 0 0 0

3、 1 1 1 1符号位单独处理符号位单独处理乘数的某一位决定是否加被乘数乘数的某一位决定是否加被乘数 4个位积一起相加个位积一起相加,8位加法位加法乘积的位数扩大一倍乘积的位数扩大一倍乘积的符号心算求得乘积的符号心算求得？笔算乘法改进笔算乘法改进A B=A 0.1011=0.1A+0.00A+0.001A+0.0001A=0.1A+0.00A+0.001(A+0.1A)=0.1A+0.010 A+0.1(A+0.1A)=0.11 A+0.1 0 A+0.1(1 A+0.1(1 A)=2-11A+2-1 0 A+2-1(1A+2-1(1A+0)第一步第一步 0+被乘数被乘数A第二步第二步 右移右

4、移 一一 位，得新的部分积位，得新的部分积第八步第八步 右移右移 一一 位，得结果位，得结果第三步第三步 部分积部分积+被乘数被乘数右移一位右移一位改进后的笔算乘法过程（竖式）改进后的笔算乘法过程（竖式）0.0 0 0 00.1 1 0 10.1 1 0 10.1 1 0 10.0 0 0 00.1 1 0 1初态，部分积初态，部分积=0乘数为乘数为 1，加被乘数，加被乘数乘数为乘数为 1，加被乘数，加被乘数乘数为乘数为 0，加，加 01.0 0 1 110.1 0 0 11 11.0 0 0 11 1 1乘数为乘数为 1，加，加 被乘数被乘数0.1 0 0 01 1 1 11，得结果，得结果

5、1 0 1 1=0.0 1 1 01，形成新的部分积，形成新的部分积1 1 0 1=0.1 0 0 11，形成新的部分积，形成新的部分积1 1 1 0=0.0 1 0 01，形成新的部分积，形成新的部分积1 1 1 1=部部 分分 积积 乘乘 数数 说说 明明笔算小结笔算小结 被乘数只与部分积的高位相加被乘数只与部分积的高位相加 由乘数的末位决定被乘数是否与原部分积相加，由乘数的末位决定被乘数是否与原部分积相加，然后然后 1 位形成新的部分积位形成新的部分积，同时，同时 乘数乘数 1位位（末位移丢），空出高位存放部分积的低位。（末位移丢），空出高位存放部分积的低位。硬件硬件3个寄存器（被乘数、

6、乘数、部分积），个寄存器（被乘数、乘数、部分积），具有移位功能具有移位功能1个个n位全加器位全加器 乘法乘法 运算可用运算可用 加和移位实现加和移位实现n=4，加加 4 次次，移移 4 次次例例已知已知 x=0.1110 y=0.1101 求求x y原原解：解：数值部分的运算数值部分的运算0.0 0 0 00.1 1 1 00.1 1 1 00.0 0 0 00.1 1 1 00.1 1 1 0部分积部分积 初态初态 z0=0 部部 分分 积积 乘乘 数数 说说 明明0.0 1 1 101.0 0 0 11 01.0 1 1 01 1 00.1 0 1 10 1 1 01，得得 z4逻辑右移逻

7、辑右移1 1 0 1=0.0 1 1 11，得得 z10 1 1 0=0.0 0 1 11，得得 z21 0 1 1=0.1 0 0 01，得得 z31 1 0 1=逻辑右移逻辑右移逻辑右移逻辑右移逻辑右移逻辑右移+x*+0+x*+x*数值部分按绝对值相乘数值部分按绝对值相乘 乘积的符号位乘积的符号位 x0 y0=1 0=1x*y*=0.1 0 1 1 0 1 1 0则则 x y原原 =1.1 0 1 1 0 1 1 0特点特点绝对值运算绝对值运算逻辑移位逻辑移位结果结果用移位的次数判断乘法是否结束用移位的次数判断乘法是否结束原码一位乘原码一位乘逻辑实现逻辑实现(x)(y)A的操作流程特点：符

8、号特点：符号 位参与位参与 乘法运算，运算结果用补码表示乘法运算，运算结果用补码表示补码与真值的关系补码与真值的关系设设x补补x0.x1x2xn,当真值当真值x=0时，时，x0=0 x补补x=0.x1x2xn=当真值当真值x0时，时，x0=1,x补补1.x1x2xn=2+x x=x补补21.x1x2xn2 =-10.x1x2xn-1综合：综合：x=-x0+补码一位乘法补码一位乘法设被乘数设被乘数X补补=x0.x1x2xn,乘数乘数Y补补 y0.y1y2yn，则有，则有 XY补补=X补补(-y0+)证明证明：(1)X正负任意，正负任意，Y为正数为正数 X补补=2+X=2n+1+X mod 2,Y

9、补补=Y则：则：X补补 Y补补2n+1 Y+X Y=2+X Y mod 2 所以：所以：X补补 Y补补=XY补补=X补补(0.y1y2yn)(2)X正负任意，正负任意，Y为负数为负数 X补补=x0.x1x2xn，Y补补1.y1y2yn=2+Y Y=0.y1y2yn-1 XY=X(0.y1y2yn)-X XY补补=X(0.y1y2yn)补补+-X补补 =X补补(0.y1y2yn)+-X补补 综合：综合：XY补补=X补补(-Y0+)补码一位乘法补码一位乘法 0.xxxx 10.xxxx10000.xxxx 0.yyyyyyyy0.0000设设x补补=x0.x1x2 xn y补补=y0.y1y2 y

10、nx y补补=x补补(0.y1 yn)x补补 y0=x补补(y1 2-1+y22-2+yn2-n)x补补 y0=x补补(y0+y1 2-1+y22-2+yn2-n)=x补补y0+(y1 y12-1)+(y22-1y22-2)+(yn2-(n-1)yn2-n)=x补补(y1y0)+(y2y1)2-1+(ynyn-1)2-(n-1)+(0 yn)2-n)Y020 +Y1 2-1+Yn 2-nx补补=+x补补 2-1=20 2-12-2=2-1 2-22-12-2=x补补(y1y0)+(y2y1)2-1+(yn+1yn)2-n 附加位附加位 yn+1补码一位乘运算规则（补码一位乘运算规则（Booth

11、 算法）算法）z0补补=0z1补补=2-1(yn+1yn)x补补+z0补补 yn+1=0zn补补=2-1(y2y1)x补补+zn-1补补x y补补=(y1y0)x补补+zn补补最后一步不移位最后一步不移位如何实现如何实现 yi+1yi?0 00 11 01 11+x补补 1+x补补 110 1 -1 0 yi yi+1操作操作yi+1yi 补码一位乘运算规则（补码一位乘运算规则（Booth 算法）算法）x y补补=(y1-y0)x补补+(y2-y1)x补补+(y3-y2)x补补+(yn-yn-1)x补补+(yn+1-yn)x补补+0 2-12-12-1 2-1运算规则如下：运算规则如下：符号位

12、参与运算，运算的数均以补码表示。符号位参与运算，运算的数均以补码表示。被乘数取双符号位参加运算，部分积初值为被乘数取双符号位参加运算，部分积初值为0。乘数取单符号位乘数取单符号位.乘数末位增设附加位乘数末位增设附加位yn+1，且初值为，且初值为0。按下表进行操作。按下表进行操作。(右移为算术右移右移为算术右移)按照上述算法进行按照上述算法进行n+1n+1步操作，但第步操作，但第n+1n+1步不再移位，步不再移位，补码一位乘运算规则（补码一位乘运算规则（Booth 算法）算法）例例已知已知 x=+0.0011 y=0.1011 求求xy补补解：解：0 0.0 0 0 01 1.1 1 0 11

13、1.1 1 0 10 0.0 0 1 11 1.1 1 0 10 0.0 0 1 11 1.1 1 0 11.0 1 0 100 0.0 0 0 111 1.1 1 0 11 10 0.0 0 0 11 1 11 1.1 1 0 11 1 1 1 x补补=0.0011 y补补=1.0101x补补=1.1101+x补补1 1.1 1 1 01 1 0 1 0 11+x补补0 0.0 0 0 01 1 1 0 101+x补补1 1.1 1 1 01 1 1 1 0110 0.0 0 0 0 1 1 1 1 101+x补补+x补补 xy补补 =1.11011111 最后一步不移位最后一步不移位 补码

14、补码右移右移补码补码右移右移补码补码右移右移补码补码右移右移+补码一位乘补码一位乘Booth 算法的硬件配置算法的硬件配置A、B、Q 均均 n+2 位位移位和加受末两位乘数控制移位和加受末两位乘数控制0 A部分积部分积 n+1n+2 位加法器位加法器控控 制制 门门0 B被乘数被乘数 n+10 Q乘数乘数 n n+1移位和加移位和加控制逻辑控制逻辑计数器计数器 CGM00,110110右移右移补码一位乘补码一位乘Booth 算法流程算法流程阵列乘法器不带符号二进制数 a4 a3 a2 a1 a0 b4 b3 b2 b1 b0 0 0 0 0 0 a4b0 a3b0 a2b0 a1b0 a0b0

15、 a4b1 a3b1 a2b1 a1b1 a0b1 a4b2 a3b2 a2b2 a1b2 a0b2 a4b3 a3b3 a2b3 a1b3 a0b3a4b4 a3b4 a2b4 a1b4 a0b4+阵列乘法器阵列乘法器T时刻时刻6T时刻时刻7T时刻时刻12T时刻时刻13T时刻时刻T+(n-1)6T时刻时刻T+(n-1)6T-T时刻时刻T+(n-1)6T+2T时刻时刻T+(n-1)6T+5T时刻时刻T+(n-1)6T+(n-2)2T+T时刻时刻最后一次进位：最后一次进位：2T+(n-1)6T+(n-1)2T时刻时刻乘法最高位：乘法最高位：2T+(n-1)6T+(n-1)2T+T时刻时刻 =8(

16、n-1)T+3T=(8n-5)T为什么不是加为什么不是加5T？如果与门运算需如果与门运算需要要2T，则总时延，则总时延为为(4n-2)2Tn原理：转化为两个正数乘，然后利用不带符号陈列乘法器。原理：转化为两个正数乘，然后利用不带符号陈列乘法器。结果的符号位单独求，并对结果进行求补。算前求补乘结果的符号位单独求，并对结果进行求补。算前求补乘法器算后求补法器算后求补阵列乘法器带符号二进制数E=0时，输入和输出时，输入和输出相等相等E=1时，则从数最右时，则从数最右端往左边扫描，直到端往左边扫描，直到第一个第一个1的时候，该的时候，该位和右边各位保持不位和右边各位保持不变变0A=A，左边各，左边各数

17、值位按位取反数值位按位取反1A=乛乛A可以用符号作为可以用符号作为E 的的输入输入阵列乘法器带符号的阵列乘法器(间接法)乘法小结乘法小结 原码乘原码乘 符号位符号位 单独处理单独处理 补码乘补码乘 符号位符号位 自然形成自然形成 原码乘去掉符号位运算原码乘去掉符号位运算 即为无符号数乘法即为无符号数乘法 不同的乘法运算需有不同的硬件支持不同的乘法运算需有不同的硬件支持 整数乘法与小数乘法完全相同整数乘法与小数乘法完全相同 可用可用 逗号逗号 代替小数点代替小数点小结n理解并会计算（要求过程）理解并会计算（要求过程）：定点原码一位乘，定点补码：定点原码一位乘，定点补码一位乘（一位乘（Booth 算法算法）n了解无符号阵列乘法器的原理了解无符号阵列乘法器的原理作业6n6-1.用原码一位乘计算用原码一位乘计算0.1001(-0.1011)（写出详细步骤）（写出详细步骤）n6-2.(选做）选做）用补码一位乘用补码一位乘(Booth 算法算法)计算计算0.1001(-0.1011)（写出详细步骤）（写出详细步骤）思考n原码除法中为什么需要恢复余数？在加减交替法中恢复余原码除法中为什么需要恢复余数？在加减交替法中恢复余数的机制是什么？数的机制是什么？