第三章_运算方法与运算部件(第二讲)

1、第三章 运算方法与运算部件(2)3.3 二进制乘法运算3.3.1 定点数一位乘法 （1）1. 原码定点一位乘法 两个原码数相乘，其乘积的符号为相乘两数的异或值，数值两数绝对值之积。 假设 X原=X0 X1 X2 Xn Y原=Y0 Y1 Y2 Yn XY原=X原Y原 = (X0Y0)(X1 X2 Xn)(Y1 Y2 Yn)符号表示把符号位和数值邻接起来。 3.3.1 定点数一位乘法 （2）例：X=0.1101，Y=0.1011计算XY 解： 0.1101 0.1011 1101 1101 0000 1101 0.10001111 XY=0.10001111, 符号为正3.3.1 定点数一位乘法

2、（3） 分解乘法操作，两个n位数相乘，结果是2n位。 1101 1011 1101 1101 0000 1101 10001111 积有8位，我们把积的中间形式称为部分积。 00000000 第0步 部分积 + 1101 00001101 第1步 部分积 + 1101 00100111 第2步 部分积 + 0000 00100111 第3步 部分积 + 1101 10001111 第4步 部分积3.3.1 定点数一位乘法 （4） 重复执行下列操作n次： （1）加被乘数或0（由乘数的相应位决定）到部分积； （2）部分积右移1位。 由于乘数的各个位决定加被乘数或0，我们采用值判断乘数最低位，每次判

3、断完毕，右移1位的方法。而且由于乘数右移空出的高位可以留给部分积的低位。 所以，保存乘数的寄存器，最后保存部分积的低n位。 因此，最后的乘法规则是： 部分积（只占n位）初始值为0 重复执行下列操作n次： （1） 由乘数的最低位的值决定：1，加被乘数；0，加0； （2） 部分积连同乘数一道右移1位。3.3.1 定点数一位乘法 （5）A 部分积计数器n 位 加法器B 被乘数CyCdC 乘数A, C 联合右移 1 位3.3.1 定点数一位乘法 （6） 部分积 乘数 00 0000 1011 +X 1101 00 1101右移1位 00 0110 1101 +X 1101 01 0011右移1位 00

4、 1001 1110 +0 0000 00 1001右移1位 00 0100 1111 +X 1101 01 0001右移1位 00 1000 11113.3.1 定点数一位乘法 （7）2. 定点补码一位乘法 有的机器为方便加减法运算，数据以补码形式存放。乘法直接以补码进行，以减少转换次数。 证明略。 具体规则如下： XY补=X补（Y0 + 0. Y1 Y2 Yn ）Y为正数：XY补=X补（ 0. Y1 Y2 Yn ）Y为负数：XY补=X补（ 0. Y1 Y2 Yn ）+-X补3.3.1 定点数一位乘法 （8） 部分积 乘数 X=-0.1101, Y=0.1011 00 0000 1011 X

5、补=11.0011，Y补=0.1011 +X补 11 0011 11 0011 右移1位 11 1001 1101 +X补 11 0011 10 1100 右移1位 11 0110 0110 +0 00 0000 11 0110 右移1位 11 1011 0011 +X补 11 0011 10 1110 右移1位 11 0111 0001 Y0=0 XY补=11.01110001 12343.3.1 定点数一位乘法 （9） 部分积 乘数 X=-0.1101, Y=-0.1011 00 0000 0101 X补=11.0011，Y补=11.0101 +X补 11 0011 11 0011 右移1

6、位 11 1001 1010 +0 00 0000 11 1001 右移1位 11 1100 1101 +X补 11 0011 10 1111 右移1位 11 0111 1110 +0 00 0000 11 0111 右移1位 11 1011 1111 Y0=1 +-X补 00 1101 00 1000 1111 XY补=0.1000111112343.3.1 定点数一位乘法 （10） “布斯公式”：在乘数Yn后添加Yn+1=0。按照Yn+1 ，Yn相邻两位的三种情况，其运算规则如下：（1） Yn+1 -Yn =0（ Yn+1 Yn =00或11），部分积加0，右移1位;（2） Yn+1 -Y

7、n =1（ Yn+1 Yn =10） ，部分积加X补，右移1位；（3） Yn+1 -Yn =-1（ Yn+1 Yn =01） ，部分积加X补，右移1位 最后一步不移位。3.3.1 定点数一位乘法 （11）X=-0.1101, Y=0.1011 部分积 乘数 Yn Yn+1 00 0000 01011 0 +-X补 00 1101 Yn+1Yn=01,+-X补 00 1101 右移1位 00 0110 10101 1 +0 00 0000 Yn+1Yn=00,+0 00 0110 右移1位 00 0011 01010 1 +X补 11 0011 Yn+1Yn=10,+X补 11 0110 右移1

8、位 11 1011 00101 0 +-X补 00 1101 Yn+1Yn=01,+-X补 00 1000 右移1位 00 0100 00010 1 +X补 11 0011 Yn+1Yn=10,+X补 11 0111 0001 XY=-0.1000111112343.3.2 定点数两位乘法 （1）1原码两位乘 乘数和被乘数都用原码表示。 两位乘数有四种可能组合，每种组合对应于以下操作： 00相当于0X。部分积 Pi 右移2位，不进行其他运算； 01相当于1X。部分积 Pi + X，右移2位； 10相当于2X。部分积 Pi + 2X，右移2位； 11相当于3X。部分积 Pi+3X，右移2位。 同

9、前述的一位乘法比较，多出了+2X和 +3X两种情况。把调左移1位即得2X，在机器内采用向左斜送1位来实现。 可是 +3X一般不能一次完成，如分成两次进行，又降低了运算速度。解决问题的办法是：以（4X-X)来代替3X运算，在本次运算中只执行一次-X，而+4X归并到下一次执行。 此时部分积已右移了两位，上一步欠下的+4X已变成X，在实际线路中要用一个触发器C来记录是否欠下+4X，若是，则1C。3.3.2 定点数两位乘法 （2） 因此实际操作用Yi-1、Yi、C三位来控制，运算规则如下：Yi-1 Yi C操作 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1

10、 1 +0， 右移2位 0C +X， 右移2位 0C +X， 右移2位 0C +2X，右移2位 0C +2X，右移2位 0C -X， 右移2位 1C -X， 右移2位 1C +0， 右移2位 1C 3.3.2 定点数两位乘法 （3） X=0.100111, Y=0.100111 部分积 乘数 Yi-1Yi,欠位 C 00 000000 100111 0 +-X补 11 011001 110: -X, 1C 11 011001 右移2位 11 110110 011001 1 +2X 01 001110 011: +2X，0C 01 000100 右移2位 00 010001 000110 0 +

11、2X 01 001110 100: +2X，0C 01 011111 右移2位 00 011111 110001 0 1233.3.2 定点数两位乘法 （4） 2补码两位乘 根据前述的布斯算法，将两步合并成一步，即可推导出补码两位乘的公式。Yn-i-1 Yn-i Yn-i+1Pi+2补 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 +0， 右移2位 +X补， 右移2位 +X补， 右移2位 +2X补，右移2位 -2X补，右移2位 -X补， 右移2位 -X补， 右移2位 +0， 右移2位 3.3.2 定点数两位乘法 （5） 当乘数由1位符号位和以n

12、（奇数）位数据位组成时，求部分积的次数为（1n）2，而且最后一次的右移操作只右移一位。 若数值位本身为偶数n，可采用下述两种方法之一：（1）可在乘数的最后一位补一个0，乘数的数据位就成为奇数，而且其值不变，求部分积的次数为1+(n+l)/2，即n/21，最后一次右移操作也只右移一位。（2）乘数增加一位符号位，使总位数仍为偶数，此时求部分积的次数为n/2+1，而且最后一次不再执行右移操作。3.3.2 定点数两位乘法 （6）X=-0.1101,Y=-0.1011；X补=1.0011,Y补=1.0101乘数的最低位补0，Y补=1.01010 部分积 乘数，附加位 000 0000 101010 0

13、+2-X补 001 1010 100: +2-X补 001 1010右移2位 000 0110 101010 1 +-X补 000 1101 101: +-X补 001 0011 右移2位 000 0100 111010 1+-X补 000 1101 101: +-X补 001 0001右移1位 000 1000 111101 0 1233.3.2 定点数两位乘法 （6）乘数增加1位符号位，Y补=11.0101 部分积 乘数，附加位 000 0000 110101 0 +X补 111 0011 010: +X补 111 0011右移2位 111 1100 111101 0 +X补 111 00

14、11 010: +X补 110 1111 右移2位 111 1011 111111 0+-X补 000 1101 110: +-X补 000 1000 111111 0 123 3.7 数据校验码（1） 计算机系统中的数据，在读写、存取和传送的过程中不可避免地产生错误。 为减少和避免错误，一方面是精心设计各种电路，提高计算机硬件的可靠性； 另一方面是在数据编码的方法减少出错的可能性，即采用某种编码法，通过少量的附加电路，使之能发现某些错误，甚至能确定出出错的位置，进而实现自动改错的能力。 3.7 数据校验码（2） 数据校验码是一种常用的带有发现某些错误或自动改错能力的数据编码方法。其实现原理，

15、是加进一些冗余码，使合法数据编码出现某些错误时，就成为非法编码。 这样，可以通过检测编码的合法性来达到发现错误的目的。合理地安排非法编码数量和编码规则，可以提高发现错误的能力，或达到自动改正错误的目的。 3.7 数据校验码（3） 这里用到一个码距码距的概念。码距码距根据任意两个合法码之间至少有几个二进制位不相同而确定的，仅有一位不同，称其码距码距为1。 例如，用四位二进制表示16种状态，则16种编码都用到了，此时码距为1，就是说，一个状态的四位码中的一位或几位出错，就变成另一个合法码，此时无查错能力。 若用二进制位表示8个状态，就可以只用其中的8种编码，而把另8种编码作为非法编码，码距为2。

16、一般来说，合理地增大码距，就能提高发现错误的能力，但码所使用的二进位变多，增加了数据存储的容量或数据传送的数量。常用的数据校验码有： 奇偶校验码奇偶校验码、海明校验码海明校验码和循环冗余校验码循环冗余校验码。 3.7.1 奇偶校验码(1) 它的实现原理，是使码距由1增加到2。 若编码中有1位二进制数出错了，即由1变成0，或者由0变成1。这样出错的编码就成为非法编码，就可以知道出现了错误。 在原有的编码之上再增加一位校验位，原编码n位，形成新的编码为n+1 位。 增加的方法有2种： 奇校验：增加位的0或1要保证整个编码中1的个数为奇数个。 偶校验：增加位的0或1要保证整个编码中1的个数为偶数个。

17、 3.7.1 奇偶校验码(2)+D D7 7D D6 6D D5 5D D4 4D D3 3D D2 2D D1 1D D0 0偶校验位偶校验位奇校验位奇校验位形成+D D校校偶校验错偶校验错奇校验错奇校验错检验 3.7.1 奇偶校验码(3)下面给出对几个字节值的奇偶校验的编码结果： 数据 奇校验的编码 偶校码的编码 00000000 100000000 000000000 01010100 001010100 101010100 01111111 001111111 101111111 其中，最高一位为校验位，其余低八位为数据位。从中可以看到，校验位的值取0还是1，是数据位中1的个数决定的。

18、 这种方案只能发现一位错或奇数个位错，但不能确定是哪一位错，也不能发现偶数个位错。 3.7.2 海明校验码(1) 这是由Richard Hamming于1950年提出的、目前还被广泛采用。 它的实现原理，是在数据中加入几个校验位，并把数据的每一个二进制位分配在几个奇偶校验组中。当某一位出错就会引起有关的几个校验组的值发生变化，这不但可以发现出错，还能指出是哪一位出错，为自动纠错提供了依据。 假设校验位的个数为r，则它能表示2r个信息，用其中的一个信息指出“没有错误”，其余2r-1个信息指出错误发生在哪一位。然而错误也可能发生在校验位，因此只有k=2r-1-r个信息能用于纠正被传送数据的位数，也

19、就是说要满足关系： 2r=k+r+1 3.7.2 海明校验码(2) 海明码中，r位奇偶校验位与k位数据位合在一起，形成k+r位新的数据。使用1到k+r为新的数据编号，并在编号为2的幂次方的位置安排奇偶校验位。剩余的位置上安排数据位。 数据位的长度可以是任意的。我们以11位数据为例，说明海明码的产生及纠错方法。假设这11位数据是 01110011010 我们使用4位奇偶校验位，把它们插入上面的数据中，并对每位数据及每位奇偶校验。 数据位用Db命名，校验位用Pb命名，数据位和校验位混合统一编号，号码从1到15。其中收据11位，校验位4位，总共15位。 3.7.2 海明校验码(3) 2 23 3 2

20、 22 2 2 21 1 2 20 0 0 1 1 1 0 0 1 P4 1 0 1 P3 0 P2 P1H15 H14 H13 H12 H11 H10 H9 H8 H7 H6 H5 H4 H3 H2 H1 D11 D10 D9 D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1 H3(D1): 1,2H5(D2): 1,4H6(D3): 2,4H7(D5): 1,2,4H9(D5): 1,8H10(D6): 2,8H11(D7): 1,2,8H12(D8): 4,8H13(D9): 1,4,8H14(D10): 2,4,8H15(D11): 1,2,4,8 3.7.2 海

21、明校验码(4)P P1 1=H=H1515 H H1313 H H1111 H H9 9 H H7 7 H H5 5 H H3 3= =0 1 0 1 1 1 0=0 P P2 2=H=H1515 H H1414 H H1111 H H1010 H H7 7 H H6 6 H H3 3= =0 1 0 0 1 0 0=0 P P3 3=H=H1515 H H1414 H H1313 H H1212 H H7 7 H H6 6 H H5 5= =0 1 1 1 1 0 1=1 P P4 4=H=H1515 H H1414 H H1313 H H1212 H H1111 H H1010 H H9

22、9= =0 1 1 1 0 0 1=0 所以，得到的海明码是： 01110010 01011 100000 3.7.2 海明校验码(5) 检查时，我们做如下的运算，并称得到的C3C2C1C0为检查码C。C C0 0=H=H1515 H H1313 H H1111 H H9 9 H H7 7 H H5 5 H H3 3 P P1 1 C C1 1=H=H1515 H H1414 H H1111 H H1010 H H7 7 H H6 6 H H3 3 P P2 2 C C2 2=H=H1515 H H1414 H H1313 H H1212 H H7 7 H H6 6 H H5 5 P P3 3

23、 C C3 3=H=H1515 H H1414 H H1313 H H1212 H H1111 H H1010 H H9 9 P P4 4 C= C3C2C1C0 3.7.2 海明校验码(6) 如果所有位均没有出错，则C= C3C2C1C0=0000。 假设H H6出错，因为C3和C0的表达式中不含有H H6，因此C3=C0=0。但C2和C1的表达式中含有H H6，因此C2=C1=1。即C3C2C1C0=0110=6。指出H H6出错。把H H6求反，即得到正确结果。这就是一位错的纠错。 如果只是一位奇偶校验位出错，检查码C也能把它指出来。 3.7.2 海明校验码(7) 传统的海明码到此为止，它只能纠正一位错。以下描述对海明码的扩展，它不但能纠正一位错，而且能检测出多位错。 如果是两位出错的话，传统的海明码将会出现怎样的一种情况呢？ 假设H H9和H H10两位出错， C0中包含H H9，故C0=1； C1中包含H H10，故C1=1； C2中不包含H H9、H H10，故C20； C3中既包含H H9，也包含H H10，故C3=0。 即C3C2C1C0=0011=3，指出H H3出错。如果我们对H H3求反，不但没有把错误的H H9和H H10