定点乘除法运算市公开课一等奖百校联赛获奖课件.pptx

2.3 二进制乘法运算1.软件编程方法实现软件编程方法实现(时序控制乘法器）时序控制乘法器）由手算到机器实现，要处理三个问题：符号问题、由手算到机器实现，要处理三个问题：符号问题、部分积相加进位问题、移位问题。部分积相加进位问题、移位问题。原码乘法是先取绝对值相乘，再依据同号相乘为原码乘法是先取绝对值相乘，再依据同号相乘为正、异号相乘位负，单独决定符号位。补码乘法则让正、异号相乘位负，单独决定符号位。补码乘法则让符号位直接参加运算，算法将会复杂一些。符号位直接参加运算，算法将会复杂一些。2.硬件快速乘法器实现硬件快速乘法器实现 利用中大规模集成电路芯片，在一拍节中实现多项利用中大规模集成电路芯片，在一拍节中实现多项部分积相加，成为阵列乘法器。部分积相加，成为阵列乘法器。第1页3.3.1 定点数一位乘法定点数一位乘法1.定点原码一位乘定点原码一位乘规则规则:在机器中采取在机器中采取A,B,C存放器来分别存放部分积，被存放器来分别存放部分积，被乘数和乘数乘数和乘数 （1）在机器内一次加法操作只能求出两数之和，所以）在机器内一次加法操作只能求出两数之和，所以每求得一个相加数时，就得与上次部分积相加。每求得一个相加数时，就得与上次部分积相加。（2）人工计算时，相加数逐次向左偏移一位，因为最）人工计算时，相加数逐次向左偏移一位，因为最终乘积位数是乘数（或被乘数）两倍终乘积位数是乘数（或被乘数）两倍.因为在求此次部因为在求此次部分积时，前一次部分积最低位，不再参加运算，所以可分积时，前一次部分积最低位，不再参加运算，所以可将其右移一位。相加数可直送而无须偏移，于是用将其右移一位。相加数可直送而无须偏移，于是用N位位加法器就可实现两个加法器就可实现两个N位数相乘。位数相乘。（3）部分积右移时乘数存放器同时右移一位，这么能）部分积右移时乘数存放器同时右移一位，这么能够用乘数存放器最低位来控制相加数（取被乘数或零），够用乘数存放器最低位来控制相加数（取被乘数或零），同时乘数存放器最高位可接收部分积右移出来一位，所同时乘数存放器最高位可接收部分积右移出来一位，所以，完成乘法运算后，以，完成乘法运算后，A存放器中保留乘积高位部分，存放器中保留乘积高位部分，乘数存放器乘数存放器C中保留乘积低位部分。中保留乘积低位部分。第2页例例:设设X=0.1101,Y=0.1011,求求XY.其中存放器其中存放器B=X ,Cd=4.流程图流程图3.6 计算过程以下计算过程以下:0 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 10 0 0 1 1 0 1 1 0 10 0 1 1 0 10 1 0 0 1 10 0 1 0 0 1 1 1 1 00 0 0 0 0 00 0 1 0 0 10 0 0 1 0 0 1 1 1 10 0 1 1 0 10 1 0 0 0 10 0 1 0 0 0 1 1 1 1 +x右移一位+x右移一位+0右移一位+x右移一位部分积 A 乘数 C 乘积高位 乘积低位1(丢失)1(丢失)0(丢失)1(丢失)XY=0.10001111第3页 注意：注意：两操作数绝对值相乘，两操作数绝对值相乘，符号位单独符号位单独处理。处理。存放器存放器A.B均设置双符号位，第均设置双符号位，第1符符号位一直是部分积符号，决定在右号位一直是部分积符号，决定在右移时第移时第1符号位补符号位补0操作步数由乘数尾数位数决定，用操作步数由乘数尾数位数决定，用计数器计数器Cd来计数。即作来计数。即作n次累加和移次累加和移位。位。最终是加符号位，依据最终是加符号位，依据Sx Sy决定。决定。第4页2.定点补码一位乘法定点补码一位乘法 实现补码乘法有两种方法，现在广泛使用是实现补码乘法有两种方法，现在广泛使用是Booth算法，也称为比较法。这种方法在机器实算法，也称为比较法。这种方法在机器实现中要在乘数末位现中要在乘数末位Yi之后再增加一个附加位之后再增加一个附加位Yi+1,并令其初始值为并令其初始值为0。然后依据比较。然后依据比较Yi、Yi+1值决定值决定下一步操作，规则以下：下一步操作，规则以下：(部分积初始为部分积初始为0)Yi Yi+1 操操 作作 0 0 原部分积右移一位原部分积右移一位 0 1 原部分积加原部分积加X补补后再右移一位后再右移一位 1 0 原部分积加原部分积加-X补补后再右移一位后再右移一位 1 1 原部分积右移一位原部分积右移一位第5页例例3.35:设设X=-0.1101,Y=0.1011,即即X补补=11.0011,Y补补=0.1011 ,-X=00.1101 求求XY补补.计算过程以下计算过程以下:0 0 0 0 0 0 0.1 0 1 1 0 初始值,最终一位补0 0 0 1 1 0 1 Y5Y4=01 +-X补0 0 1 1 0 10 0 0 1 1 0 1 0 1 0 1 1 右移一位0 0 0 0 0 0 Y4Y3=11 +00 0 0 1 1 00 0 0 0 1 1 0 1 0 1 0 1 右移一位1 1 0 0 1 1 Y3Y2=10 +X补1 1 0 1 1 01 1 1 0 1 1 0 0 1 0 1 0 右移一位 0 0 1 1 0 1 Y2Y1=01 +-X补0 0 1 0 0 00 0 0 1 0 0 0 0 0 1 0 1 右移一位1 1 0 0 1 1 Y1Y0=10 +X补1 1 0 1 1 1 0 0 0 1+部分积 乘数Y Yi Yi+1 说明乘积高位 乘积低位XY补=1.01110001,XY=-0.10001111第6页 初始值与符号位：初始值与符号位：A存放器存放部分累加和，存放器存放部分累加和，初始为初始为0，采取双符号位。第，采取双符号位。第1符号位指示累符号位指示累加和正负，以控制右移时补加和正负，以控制右移时补0或补或补1。B中存中存放被乘数补码，双符号位。放被乘数补码，双符号位。基本操作：用基本操作：用C存放器最末两位作判断位，存放器最末两位作判断位，决定下一步操作。决定下一步操作。移位移位:在右移时，第在右移时，第2符号位值移入位数最高符号位值移入位数最高位，第位，第1符号位值不变且移入第符号位值不变且移入第2符号位，而符号位，而A存放器末位移入存放器末位移入C存放器。存放器。步数与最终一步操作步数与最终一步操作:乘数有效位是乘数有效位是4位，共位，共作作5步。注意，最终一步不移位因为这一步步。注意，最终一步不移位因为这一步是用来处理符号位。是用来处理符号位。第7页2.4.1 定点除法运算 1.定点原码一位除法 有恢复余数法和不恢复余数法（加减交替法），计算机中常用后者。因为它操作步骤少，而且也不复杂。其处理思想是：先减后判，如减后发觉不够减，则在下一步改作加除数操作。这么操作步骤固定易于编程。其关键点如下：(1)要求被除数|X|除数|Y|,并取原码尾数绝对值相除；符号位单独处理，商符号为相除两数符号半加和。（2）被除数位数能够是除数两倍，其低位数值部分开始时放在商存放器中。运算中，放被除数和商A、C存放器同时移位，并将商存放器C中最高位移到被除数存放器A最低位中。（3）每步操作后，可根据余数Ri符号来判断是否够减：Ri位正表明够减，上商Q为1。Ri为负表明不够减，上商Q为0。（4）基本操作可用通式描述为：Ri=2Ri+(1-2Qi)Y (5原码除思想是先当成正数相除，若最终一步所得余数为负，则应恢复余数，但不移位，以保持Ri为正。举比如下：第8页例例3.39:设被乘数设被乘数X=0.1011,Y=0.1101,用加减交替法求用加减交替法求X/Y.-Y补补=11.0011,计算过程以下计算过程以下:0 0 1 0 1 1 0 0 0 0 0 开始情形1 1 0 0 1 1 +-Y补1 1 1 1 1 0 0 0 0 0 0 不够减,商上01 1 1 1 0 0 0 0 0 0 0 左移0 0 1 1 0 1 +Y0 0 1 0 0 1 0 0 0 0 1 够减,商上10 1 0 0 1 0 0 0 0 1 0 左移1 1 0 0 1 1 +-Y补0 0 0 1 0 1 0 0 0 1 1 够减,商上10 0 1 0 1 0 0 0 1 1 0 左移 1 1 0 0 1 1 +-Y补1 1 1 1 0 1 0 0 1 1 0 不够减,商上01 1 1 0 1 0 0 1 1 0 0 左移0 0 1 1 0 1 +Y0 0 0 1 1 1 0 1 1 0 1 够减,商上1+)+)+)+)+)被除数(余数R)（被除数)(商）操作说明余数 商X/Y=0.1101,余数=0.0111第9页A存放器中开始时存放被除数绝对值，以后将存放存放器中开始时存放被除数绝对值，以后将存放各次余数，取双符号位。各次余数，取双符号位。B存放器存放除数绝对值，存放器存放除数绝对值，取双符号位。取双符号位。C存放器同来存放商，取单符号位。存放器同来存放商，取单符号位。第一步操作：将被除数第一步操作：将被除数X视为初始余数视为初始余数R0,依据依据R0符符号位正（绝对值），令商符为号位正（绝对值），令商符为0，正是商符以后再置，正是商符以后再置入。第一步为入。第一步为-Y。商值则依据余数商值则依据余数R0符号来决定，正则商上符号来决定，正则商上1，求下一，求下一位商方法是余数左移一位再减去除数；当余数为负位商方法是余数左移一位再减去除数；当余数为负则商上则商上0，求下一位商方法是余数左移一位再加上除，求下一位商方法是余数左移一位再加上除数。左移位时末位补数。左移位时末位补0。操作步数与最终一步操作：假如要求得操作步数与最终一步操作：假如要求得n位商（不含位商（不含符号位），则需作符号位），则需作n步步“左移左移-加减加减”循环；若第循环；若第n步余数为负，则需增加一步恢复余数，这增加一步步余数为负，则需增加一步恢复余数，这增加一步不移位。不移位。第10页2.定点补码一位除法（加减交替法）补码除法规则表：补码除法规则表：X补、补、Y补、补、r补补分别为被除数、除数和余数分别为被除数、除数和余数 X补Y补数 符商符第一步操作r补 Y补数 符 上商 下一步操作同号 0 减法同号（够减）异号（不够减）1 02ri补-Y补2ri补+Y补异号 1 加法同号（不够减）异号（够减）1 02ri补-Y补2ri补+Y补第11页 以上是在以上是在|X|Y|即不溢出前提下；即不溢出前提下；（1）第一步假如被除数与除数同号，用被除数减去除数；）第一步假如被除数与除数同号，用被除数减去除数；若两数异号，用被除数加上除数。假如所得余数与除数若两数异号，用被除数加上除数。假如所得余数与除数同号上商同号上商1，若余数与除数异号，上商，若余数与除数异号，上商0，该商即为结果，该商即为结果符号位。符号位。（2）求商数值部分）求商数值部分 假如上次上商假如上次上商1，将余数左移一位后，将余数左移一位后减去除数；假如上次上商减去除数；假如上次上商0，将余数左移一位后加上除，将余数左移一位后加上除数。然后判断此次操作后余数，假如余数与除数同号上数。然后判断此次操作后余数，假如余数与除数同号上商商1；若余数与除数异号上商；若余数与除数异号上商0。如此重复执行。如此重复执行 n-l次（设数值部分有次（设数值部分有n位）。位）。（3）商最终一位普通采取恒置）商最终一位普通采取恒置1方法，井省略了最低位方法，井省略了最低位+1操作，此时最大误差为士操作，此时最大误差为士2-n.假如对商精度要求较高假如对商精度要求较高则可按规则（则可按规则（2）再进行一次操作以求得商第）再进行一次操作以求得商第n位。当除位。当除不尽时若商为负，要在商最低一位加不尽时若商为负，要在商最低一位加 1，使商从反码值，使商从反码值转变成补码值转变成补码值;若商为正最低位不需要加若商为正最低位不需要加1。第12页例例3.40:设设X补补=1.0111,Y补补=0.1101,求求X/Y补补.-Y补补=11.0011,计算过程以下计算过程以下:X/Y补=1.01011 1 0 1 1 1 0 0 0 0 0 开始情形0 0 1 1 0 1 两数异号+Y补？书0 0 0 1 0 0 0 0 0 0 1 余数与除数同号,商上10 0 1 0 0 0 0 0 0 1 0 左移1 1 0 0 1 1 上次商1,+-Y补1 1 1 0 1 1 0 0 0 1 0 余数与除数异号,商上01 1 0 1 1 0 0 0 1 0 0 左移0 0 1 1 0 1 上次商0,+-Y补0 0 0 0 1 1 0 0 1 0 1 余数与除数同号,商上10 0 0 1 1 0 0 1 0 1 0 左移 1 1 0 0 1 1 上次商1,+-Y补1 1 1 0 0 1 0 1 0 1 0 余数与除数异号,商上01 1 0 0 1 0 1 0 1 0 1 左移,商最低位恒置1+)+)+)+)被除数(余数)商 操作说明余数 商第13页 例例3.40最低位恒置最低位恒置1，余数不正确。，余数不正确。A存放器存放被除数（补码），以后存放余数，存放器存放被除数（补码），以后存放余数，取双符号位。取双符号位。B存放器存放除数（补码），双存放器存放除数（补码），双符号位。符号位。C存放器存放商，初始值为存放器存放商，初始值为0（未考（未考虑商符之前），单符号位。虑商符之前），单符号位。如余数为如余数为0，则表示除尽。例，则表示除尽。例3.41如采取商最如采取商最低位恒置低位恒置1方法，其误差为方法，其误差为2-n=2-4。补码除法规则表补充说明：补码除法规则表补充说明：1、表中、表中i=0n-1.2、上采取末位恒置、上采取末位恒置1方法，操作简便。如要方法，操作简便。如要提升精度，则要提升精度，则按上述规则多提升精度，则要提升精度，则按上述规则多求一位，再采取以下方法对商进行处理：求一位，再采取以下方法对商进行处理：两数两数能除尽时，如除数为正，商无须加能除尽时，如除数为正，商无须加2-n,如除数为负，商加如除数为负，商加2-n；两数除不尽时，如商为正，商无须加；两数除不尽时，如商为正，商无须加2-n,如商为负，商加如商为负，商加2-n。第14页 例例3.42 X补补=1.0111,Y补补=1.0011,则则-Y补补=0.1101。求。求X/Y补补=？被除数（余数）被除数（余数）商商 操作说明操作说明 11。0111 +00。1101 两数同号，+-Y补 00。0100 0 余数与除数异号，商0 左移 00。1000 +11。0011 +Y 补 11。1011 01 同号，商1 左移 11。0110 +00。1101 +-Y 补 00。0011 010 异号，商0 左移 00。0110 +11。0011 +Y 补 11。1001 0101 同号，商1 左移 11。0010 +00。1101 +-Y 补 11。1111 01011 同号，商1X/Y补=0.1011 余数补=1。1111x2-4 第15页