《补码一位乘法的证明》由会员分享，可在线阅读，更多相关《补码一位乘法的证明（10页珍藏版）》请在金锄头文库上搜索。
1、二二二二.补码一位乘法补码一位乘法补码一位乘法补码一位乘法为了得到补码一位乘法的规律，我们先从补码和真值的转换为了得到补码一位乘法的规律，我们先从补码和真值的转换为了得到补码一位乘法的规律，我们先从补码和真值的转换为了得到补码一位乘法的规律，我们先从补码和真值的转换公式开始讨论公式开始讨论公式开始讨论公式开始讨论. .1.1.补码与真值的转换公式补码与真值的转换公式补码与真值的转换公式补码与真值的转换公式设设设设xx补补补补=x=x0 0.x.x1 1x x2 2xxn n, ,当当当当x=0x=0时时时时,x,x0 0=0,=0,nnxx补补补补=0.x=0.x1 1x x2 2xxn n=
2、 x xi i2 2-i-i=x=xi=1i=1当当当当x0x0)0，根据式（，根据式（2.31a2.31a）有）有 x(0.y x(0.y1 1y y2 2yyn n) 补补=x =x 补补(0.y(0.y1 1y y2 2yyn n) ) 所以所以 xy xy 补补=x =x 补补(0.y(0.y1 1y y2 2yyn n) + -x ) + -x 补补 (2.31b) (2.31b) （3 3）被乘数）被乘数x x和乘数和乘数y y符号都任意符号都任意. . 将式（将式（2 31a2 31a）和武（）和武（2.31b2.31b）两种情况综合起来，即）两种情况综合起来，即得补码乘法的统一
3、算式，得补码乘法的统一算式， 即即 xy xy 补补=x =x 补补(0.y(0.y1 1y y2 2yyn n) - x ) - x 补补yy0 0 =x =x 补补(-y(-y0 0+0.y+0.y1 1y y2 2yyn n) ) n n =x =x 补补(-y(-yo o + y + yi i2 2-i -i) ) i=1 i=1 证毕证毕. . 为了推出串行逻辑实现的分步算法，将上式展开加以变换为了推出串行逻辑实现的分步算法，将上式展开加以变换: :xy xy 补补=x=x 补补 -y -y0 0+ y+ y1 12 2-1-1+y+y2 22 2-2-2+y+yn n2 2-n-n
4、 =x =x 补补 -y -y0 0+(y+(y1 1-y-y1 12 2-1-1)+(y)+(y2 22 2-1-1-y-y2 22 2-2-2)+(y)+(yn n2 2-(n-1)-(n-1) - y - yn n2 2- -n n)=x =x 补补(y(y1 1-y-y0 0)+(y)+(y2 2-y-y1 1)2)2-1-1+(y+(yn n-y-yn-1n-1)2)2-(n-1)-(n-1) + (0-y + (0-yn n)2)2-n-n n n=x =x 补补 (y(yi+1i+1 - y - yi i)2)2-i -i i=1 i=1写成递推公式如下写成递推公式如下 z z0
5、 0 补补=0=0 z z1 1 补补=2=2-1-1zz0 0 补补+(y+(yn+1n+1-y-yn n)x)x 补补 (y (yn+1n+1=0)=0) z z2 2 补补=2=2-1-1zz1 1 补补+(y+(yn n - y - yn-1n-1)x )x 补补 z zi i 补补=2=2-1-1zzi-1i-1 补补+ (y+ (yn-i+2n-i+2 - y - yn-i+1n-i+1)x )x 补补 z zn n 补补=2=2-1-1zzn-1n-1 补补+ (y+ (y2 2 - y - y1 1)x )x 补补 z zn+1n+1 补补=z=zn n 补补+(y+(y1 1
6、-y-y0 0)x)x 补补=xy =xy 补补开始时，部分积为开始时，部分积为开始时，部分积为开始时，部分积为0 0，即，即，即，即zz0 0 补补补补=0=0然后每一步都是在前次部然后每一步都是在前次部然后每一步都是在前次部然后每一步都是在前次部分积的基础上，由（分积的基础上，由（分积的基础上，由（分积的基础上，由（y yi+1i+1-y-yi i) )（i=0,1,2,ni=0,1,2,n）决定对）决定对）决定对）决定对xx补补补补的操作，再右移一位，得到新的部分积的操作，再右移一位，得到新的部分积的操作，再右移一位，得到新的部分积的操作，再右移一位，得到新的部分积. .如此重复如此重复
7、如此重复如此重复n+1n+1步，步，步，步，最后一步不移位，便得到最后一步不移位，便得到最后一步不移位，便得到最后一步不移位，便得到xyxy补补补补，这就是有名的布斯公式，这就是有名的布斯公式，这就是有名的布斯公式，这就是有名的布斯公式. .实现这种补码乘法规则时，在乘数最末位实现这种补码乘法规则时，在乘数最末位实现这种补码乘法规则时，在乘数最末位实现这种补码乘法规则时，在乘数最末位y yn n后面要增加后面要增加后面要增加后面要增加一位补充位一位补充位一位补充位一位补充位y yn+1n+1。开始时。开始时。开始时。开始时y yn+1n+1=0,=0,由由由由yyn ny yn+1n+1 判断
8、第一步判断第一步判断第一步判断第一步该怎么操作；然后再由该怎么操作；然后再由该怎么操作；然后再由该怎么操作；然后再由y yn-1n-1y yn n判断第二步该怎么操作。但因判断第二步该怎么操作。但因判断第二步该怎么操作。但因判断第二步该怎么操作。但因为每作一步要右移一位，故作完第一步后，为每作一步要右移一位，故作完第一步后，为每作一步要右移一位，故作完第一步后，为每作一步要右移一位，故作完第一步后，y yn-1n-1y yn n正好移到正好移到正好移到正好移到原来原来原来原来y yn ny yn+1n+1的位置上。依此类推，所以每步都用的位置上。依此类推，所以每步都用的位置上。依此类推，所以每
9、步都用的位置上。依此类推，所以每步都用y yn ny yn+1n+1位位位位置进行判断置进行判断置进行判断置进行判断. .我们将此两位称为判断位我们将此两位称为判断位我们将此两位称为判断位我们将此两位称为判断位. .如果判断位如果判断位如果判断位如果判断位y yn ny yn+1n+1=01=01，则，则，则，则y yi+1i+1-y-yi i=1=1，做加，做加，做加，做加xx补补补补操作操作操作操作. .如果如果如果如果y yn ny yn+1n+1=10=10，则，则，则，则y yi+1i+1yyi i=-1,=-1,做减法做减法做减法做减法, ,即做加即做加即做加即做加-x-x补补补补
10、操作；操作；操作；操作；如果如果如果如果y yn ny yn+1n+1=11=11或或或或0000，则，则，则，则y yi+1i+1yyi i=0=0，z zi i加加加加0 0，即保持不变即保持不变即保持不变即保持不变. .补码一位乘法的运算规则如下（开始时补码一位乘法的运算规则如下（开始时补码一位乘法的运算规则如下（开始时补码一位乘法的运算规则如下（开始时y yn+1n+1=0=0）: :(1)(1)如果如果如果如果y yn n=y=yn+1n+1, ,部分积部分积部分积部分积Z Zi i加加加加0 0，再右移，再右移，再右移，再右移1 1位；位；位；位；（2 2）如果）如果）如果）如果y
11、 yn ny yn+1n+1=01,=01,部分积加部分积加部分积加部分积加xx补补补补，再右移，再右移，再右移，再右移1 1位；位；位；位；（3 3）如果）如果）如果）如果y yn ny yn+1n+1=10,=10,部分积加部分积加部分积加部分积加-x-x补补补补，再右，再右，再右，再右移移移移1 1位位位位. .这样重复进行这样重复进行这样重复进行这样重复进行n n1 1步，但最后一步不移位步，但最后一步不移位步，但最后一步不移位步，但最后一步不移位. .包括一包括一包括一包括一位符号位，所得乘积为位符号位，所得乘积为位符号位，所得乘积为位符号位，所得乘积为2n2n1 1位，其中位，其中
12、位，其中位，其中n n为尾数为尾数为尾数为尾数数位数位数位数位. .例例x补补=0.1101，y补补=0.1011,求求xy补补.解：解：部分积部分积乘数乘数说明说明00.00000.10110yn+1=0+11.0011ynyn+1=10,+-x补补11.001111.1001101011右移右移1位位+00.0000ynyn+1=11,+011.100111.1100110101右移右移1位位+00.1101ynyn+1=01,+x补补00.100100.0100111010右移右移1位位+11.0011ynyn+1=10,+-x补补11.011111.1011111101右移右移1位位+
13、00.1101ynyn+1=01,+x补补00.1000111101最后一步不移位最后一步不移位实现一位补码乘法的逻辑原理图与一位原码乘法的逻辑结构非实现一位补码乘法的逻辑原理图与一位原码乘法的逻辑结构非实现一位补码乘法的逻辑原理图与一位原码乘法的逻辑结构非实现一位补码乘法的逻辑原理图与一位原码乘法的逻辑结构非常类似，所不同的有以下几点常类似，所不同的有以下几点常类似，所不同的有以下几点常类似，所不同的有以下几点: : (1)(1)被乘数的符号被乘数的符号被乘数的符号被乘数的符号x x0 0和乘数的符号和乘数的符号和乘数的符号和乘数的符号y y0 0都参加运算都参加运算都参加运算都参加运算.
14、.(2)(2)乘数寄存器乘数寄存器乘数寄存器乘数寄存器RR1 1有附加位有附加位有附加位有附加位y yn+1n+1；，其初始状态为；，其初始状态为；，其初始状态为；，其初始状态为“0”.“0”.当乘当乘当乘当乘数和部分积每次右移时数和部分积每次右移时数和部分积每次右移时数和部分积每次右移时, ,部分积最低位移至部分积最低位移至部分积最低位移至部分积最低位移至RR1 1的首位位置，故的首位位置，故的首位位置，故的首位位置，故RR1 1必须是具有右移功能的寄存器必须是具有右移功能的寄存器必须是具有右移功能的寄存器必须是具有右移功能的寄存器. .(3)(3)被乘数寄存器被乘数寄存器被乘数寄存器被乘数
15、寄存器RR2 2的每一位用原码（即触发器的每一位用原码（即触发器的每一位用原码（即触发器的每一位用原码（即触发器QQ端）或反端）或反端）或反端）或反码（即触发器码（即触发器码（即触发器码（即触发器QQ端）经多路开关传送到加法器对应位的一个输端）经多路开关传送到加法器对应位的一个输端）经多路开关传送到加法器对应位的一个输端）经多路开关传送到加法器对应位的一个输入端入端入端入端. .而开关的控制信号由而开关的控制信号由而开关的控制信号由而开关的控制信号由y yn n和和和和y yn+1n+1的输出译码的输出译码的输出译码的输出译码 器产生器产生器产生器产生. .当当当当y yn ny yn+1n+
16、1=01=01时时时时, ,送送送送xx补补补补; ;当当当当y yn ny yn+1n+1=1=1时时时时, ,送送送送-x-x补补补补, ,即送即送即送即送RR2 2的的的的反码且在加法器最末位加反码且在加法器最末位加反码且在加法器最末位加反码且在加法器最末位加”1”1”（4 4）RR0 0保存部分积，它也是具有右移功能的移位寄存器，保存部分积，它也是具有右移功能的移位寄存器，保存部分积，它也是具有右移功能的移位寄存器，保存部分积，它也是具有右移功能的移位寄存器，其符号位与加法器符号位其符号位与加法器符号位其符号位与加法器符号位其符号位与加法器符号位f f始终一致始终一致始终一致始终一致.
17、 .（5 5）当计数器）当计数器）当计数器）当计数器i=n+1i=n+1时，封锁时，封锁时，封锁时，封锁LDRLDR1 1和和和和LDRLDR0 0控制信号，使控制信号，使控制信号，使控制信号，使最后一步不移位最后一步不移位最后一步不移位最后一步不移位. .执行补码一位乘法的总时间为执行补码一位乘法的总时间为执行补码一位乘法的总时间为执行补码一位乘法的总时间为ttmm=(n+1)t=(n+1)ta a+nt+ntr r（2 23333）其中其中其中其中n n为尾数位数，为尾数位数，为尾数位数，为尾数位数，t ta a为执行一次加法操作的时间，为执行一次加法操作的时间，为执行一次加法操作的时间，为执行一次加法操作的时间，t tr r为执行为执行为执行为执行一次移位操作的时间一次移位操作的时间一次移位操作的时间一次移位操作的时间. .如果加法操作和移位操作同时进行，如果加法操作和移位操作同时进行，如果加法操作和移位操作同时进行，如果加法操作和移位操作同时进行，t tr r项可省去项可省去项可省去项可省去. .
