湘潭大学 刘福贵 计算机组成原理课件.ppt

数据校验 概述在计算机系统中 数据在存取和传递过程中可能会产生错误 为减少和避免错误 一方面是要精心设计各种电路 提高计算机硬件的可靠性 另一方面是在数据编码上找出路 即采用带有某种特殊能力的编码法 通过少量的附加电路 使之能发现某些错误 甚至能确定错误的性质和准确的出错位置 进而实现自动改错功能数据校验码就是一些具有发现某些错误或带有自动改错能力的数据编码方法 其编码分别称为检错码 能够发现某些错误的数据编码 和纠错码 不仅能够发现某些错误 而且具有确定的错误自动纠正能力的数据编码 它们的实现原理是在合法的数据编码之间 加进一些不允许出现的 非法的 编码 使合法数据编码出错时 就成为非法编码 这样就可以通过检测编码的合法性来达到发现错误 和 或自动纠正错误 的目的 数据校验 概述合理安排非法编码数量和编码规则 就可以提高发现错误的能力 甚至达到自动改正错误的目的 这里用到一个码距的概念 码距是指任意两个合法码之间至少有几个二进制位不同 仅有一位不同称其码距为1 例如用四位二进制表示16种状态 则16种编码都用到了 此时码距为1 即任何一个状态的四位码中的一位或几位出错 就变成了另一个合法码 此时无查错能力 若用四位二进制表示8个状态 就可以只用其中八种编码 而把另8种编码作为非法编码 此时可使合法码的码距为2 一般来说 合理地增大合法码的码距 就能提高发现错误的能力 但由此将会使得表示一定数量的合法码所使用的二进制位数增多 增加了数据存储的容量或数据传送的数量 硬件 常用的数据校验码是奇偶校验码 海明校验码和循环冗余校验码 CRC 数据校验 奇偶校验奇偶校验是最简单 应用最广泛且开销最小的一种校验方式奇偶校验码的实现原理是使原来合法编码码距由 增加到 实现的具体方法是为一个信息补充一个二进制位 称为奇偶校验位 用该位的值为 或 使信息和该校验位一起含有 值的个数为奇数 称为奇校验 或偶数 称为偶校验 形成奇偶校验位的值和进行校验 是由专设的硬件线路实现的 何种门电路 奇偶校验又分为垂直奇偶校验 水平奇偶校验和水平垂直奇偶校验三种垂直 纵向 奇偶校验 针对一个数据对象增设一个奇偶校验位 使得n位长的数据字被加长到n 1位 例如 用七单位ASCII码表示的数字0 9在增设一个奇偶校验位后形成的垂直奇偶校验码如表一所示 数据校验 奇偶校验 数据校验 奇偶校验水平奇偶校验 对于数据传送来说 成组传送是一种高效的数据传输方式 在数据的成组传送中 被传送的数据具有相同的数据类型 为了有效地检测数据成组传送过程中可能出现的数据错误 可以考虑针对这一组数的每一位 而不是每个数据 设置一个奇偶校验位 如果每个数据含10个二进制位 就设置10个奇偶校验位 而不管这组数据包含多少个元素 由此形成的校验方式即是 水平奇偶校验 设被传送的数据是由七位ASCII字符组成的数据组 每次传送10个数据 按照水平奇偶校验的方式形成数据的校验码基于水平奇偶校验的校验码形成方式 可设7个校验位 相应示例数据及其校验码如表二所示 数据校验 数据校验 奇偶校验水平垂直奇偶校验 同时进行水平和垂直奇偶校验的方式称为水平垂直奇偶校验水平垂直奇偶校验通常用在成组数据传送时的数据校验上 它在两个方向上对数据进行校验 对成组传送的数据的每一个数据元素按垂直奇偶校验方法形成一个校验位对各数据的同一位按水平奇偶校验方法形成一个校验位设被传送的数据是由七位ASCII字符组成的数据组 每次传送10个数据 相应校验码示于表三水平奇偶校验码和垂直奇偶校验码只能发现奇数个错 不能发现偶数个错 水平垂直奇偶校验码具有较强的检错能力 它不但能发现所有一位 二位和三位错误 而且能改正一位错误 数据校验 数据校验 海明校验码海明校验码 其实现原理是在数据中加入几个校验位 将数据代码的码距较均匀地拉大 并把数据的每一个二进制位分配在几个奇偶校验组中 当某一位出错后 就会引起有关几个奇偶校验位的值发生变化 这不但可以发现错误 还能指出是哪一位出错 为进一步自动纠错提供了依据为了简单起见 在此仅介绍能够自动纠正一位错误的海明校验码海明校验码是用r个奇偶校验位附加到具有k个二进制数位的数据上 形成一个长度为M r k 位的新代码 海明校验码 因为要校正一位错误 附加的校验位就要有指示错误出在哪一位的能力 就是说 校验位的状态应当有M 1种 含无错的情况 以便能指出n个海明码代码位中的任何一位有错或无错 数据校验 数据校验 海明校验码若海明码的最高位号为m 最低位号为1 即设相应形成的海明校验码为HmHm 1 H2H1 则其编码规则是 校验位与数据位之和为m 每个校验位Pi在海明码中被分在位号2i 1的位置 其余各位为数据位 并按从低位向高位依次排列的关系分配各数据位海明码的每一位Hi 包括数据位和校验位本身 由多个校验位校验 其关系是被校验的每一位位号要等于校验它的各校验位号之和在增大合法码的码距时 使所有码的码距尽量均匀地增大 以保证对所有码的检错能力平衡提高在下面的讨论中 我们将以一个字节数据作为被校验的数据来系统地介绍用海明校验码实现校验的全过程 问题要求被设定为 检测与自动校正一位错 并发现两位错 数据校验 海明校验码每个字节由8个二进制位组成 此处k为8 根据表2 6可知 校验位数r应为5 故海明码的位数为13 可表示为 H13H12H11H10H9H8H7H6H5H4H3H2H1五个校验位P5 P1对应的海明码位号 按2i 1的原则确定 分别为 H13 H8 H4 H2 H1由此 可得到13位的海明码组织形式为 P5D8D7D6D5P4D4D3D2P3D1P2P1注意 数据位 D8 D1 的位号根据向前的相关讨论 每个海明码的位号要等于参与校验它的几个校验位的位号之和的关系 可以相应得出如表2 6 1的结果 数据校验 数据校验 海明校验码应当注意 这里的P5与P1 P4不同 可被认为是由 海明校验 这种校验方法所确定的 由此可使相应的 码距 被拉大 相应的 校正一位错误 发现两位同时出错 的目标得以实现在这种安排下 每一数据位至少出现在3个Pi值的形成关系中当任一数码位发生变化时 必将引起3个或4个Pi值跟着变化 因此 该海明码的码距大于等于4在发送或存入数据时 相应的校验电路基于上述5个表达式根据具体的数据值产生P1 P5 连同数据值一起按照上述数位编排方式发送或存储在数据的接收方 或者数据被读出时 由对应的校验电路按照同样的方式产生校验码 若记相应产生的校验码对应地为S1 S5 则可达到检错和纠错的目的 数据校验 海明校验码在进行错误检测时 相应的关系式为 S1 P1 D1 D2 D4 D5 D7S2 P2 D1 D3 D4 D6 D7S3 P3 D2 D3 D4 D8S4 P4 D5 D6 D7 D8S5 P5 P4 P3 P2 P1 D1 D2 D3 D4 D5 D6 D7 D8 在发生一位数据错的情况下 相应地 有 S5S4S3S2S1 10011 D1错10101 D2错10110 D3 其它数据位错依此类推 无错时S5S4S3S2S1 00000若出现两位错 S5 0 不能确定错误位置 数据校验 海明校验码下面假设被校验的数据值是英文字母 C 的ASCII值 用一个字节 8位二进制 表示 以之来进一步具体化地说明海明校验的相关过程 被测数据值的二进制描述为 D8D7D6D5D4D3D2D1 01000011基于被测数据的值可得出13位海明码为 P50100P4001P31P2P1可相应求得P1 P5的值分别为 P1 D1 D2 D4 D5 D7 1P2 D1 D3 D4 D6 D7 0P3 D2 D3 D4 D8 1P4 D5 D6 D7 D8 1P5 0 数据校验 海明校验码由此可知 相应的海明码为 0010010011101设其中有一个数据位D2出错 接收到的编码为 P5D8D7D6D5P4D4D3D2P3D1P2P10010010001101此时 相应形成的S1 S5分别为 S1 P1 D1 D2 D4 D5 D7 1S2 P2 D1 D3 D4 D6 D7 0S3 P3 D2 D3 D4 D8 1S4 P4 D5 D6 D7 D8 0S5 1即有S5 S1 10101 数据校验 海明校验码由于S5 0 且S4 S1 0101 0000 使得如教材P43图2 8所示的电路产生 一位错 的指示由于有S1 1 S3 1 它们的表达是分别为 S1 P1 D1 D2 D4 D5 D7S3 P3 D2 D3 D4 D8同时出现在这两个表达式中的仅有D2和D4 但D4还出现在S2的表达式中 但S2 0 这就是说 此时的错误只可能是因D2出错引起的 或者说 由S5 S1 10101即可断言 唯一的可能是D2出错 基于前面的讨论可知 可由相应的硬件根据该值确认是D2出错 相应地将D2取反即可自动纠正该错误 数据校验 数据校验 数据校验 数据校验 循环冗余 CRC 校验为了引入CRC校验码 可将一个k位的二进制数以多项式形式表示为 M X CK 1XK 1 CK 2XK 2 C1X C0例如 对于4位的二进制数1101 可相应地表示为 M X x3 x2 1由于CRC校验码是在k位的被校验数据后加上r位的校验码 若记相应校验码的多项式形式表示为S X 相应形成的CRC编码的多项式表示形式为C X 则有 C X M X Xr S X 其中 M X Xr即是被校验数据的多项式形式表示在左移r位后得到的结果的多项式表示形式 这样 r位的校验码即可简单地接续在其后 形成一个完整的k r位的二进制数的多项式表示 数据校验 循环冗余 CRC 校验CRC校验码的产生 CRC校验位的产生方法是 用M X Xr按模2除法的规则除以一个r 1位的生成多项式G X 得到一个商和一个r位的余数 此余数就是所得的 校验码 在发送数据时 先发送M X 对应的待传输数据 接着发送按上述规则求得的 校验码 由此组成一个完整的CRC编码 即前面已讨论的C X 在接收数据时 将相应收到的k r位代码按模2除法的规则除以发送时使用的生成多项式G X 并将所得余数与发送时产生的 校验码 进行 比较 若两者一致 表明相应数据传送过程无错 若两者不同 则表明数据传送过程发生了某种错误 可采取相应的措施对错误进行修正或者发送一个信号给数据的发送者 要求其将数据重发 由此使可能发生的错误被检测并得以纠正 数据校验 循环冗余 CRC 校验设M X Xr G X 的余数为R X 商为Q X 则有 Q X R X G X M X Xr G X Q X M X Xr G X R X G X M X Xr G X R X G X 模2运算 M X Xr R X G X 由前面的相关讨论可知 M X Xr R X 就是相应被传送数据的CRC编码 因此 被传送数据的CRC编码在除以生成多项式G X 时 其余数应当为0这也就是说 实行CRC校验时 接收方在收到相应数据的CRC编码后 只需检查 M X Xr R X G X 的余数是否为0 若为0 则表明相应数据传送过程无错 否则 表明数据传送过程发生了某种错误 数据校验 数据校验 循环冗余 CRC 校验CRC码的译码与纠错 将收到的循环校验码用约定的生成多项式G X 去除 如果码字无误 余数应为0 如果有某一位出错 则余数不为0 不同数位出错余数不同 可以证明 余数与出错位的对应关系是不变的 只与码制和生成多项式有关如上述给定的例子所示的 7 4 码 发送数据的CRC编码为1100010 生成多项式为1011 数据接收方在收到相应的7位代码 记作A1A2A3A4A5A6A7 后 即以之按模2除法除以1011 得到一个3位的余数 在假定同时只有一位出错的情况下 有 1100010 余数0001100011 余数0011100000 余数0101100110 余数1001101010 余数0111110010 余数1101000010 余数1110100010 余数101 数据校验 数据校验 循环冗余 CRC 校验基于以上讨论可知 如果收到的CRC代码中有某一位出错 则当用其按模2除法的规则除以生成多项式G X 时 所得的余数必然不等于0 如果将所得余数补0继续做模2除法 即 若得余数110 补0 使成为1100 继续作模2除法 所得的余数将会是表2 7中的下一个余数 也就是说 由此将会使各次的余数按表2 7中给定的顺序 循环 110 111 101 001 010 100 011 110 这就是人们称其为 循环码 的原因如果在求出余数不为0后 一边对余数补0继续做模2除 同时让被测CRC码循环左移 基于表2 7 当出现余数 101 时 出错位也移到了A1位置 可通过异或门将它纠正后在下一次移位是送回A7 继续移满一个循环 对于 7 4 码共移7次 就得到一个纠正后的CRC码 数据校验 循环冗余 CRC 校验关于生成多项式 并不是任何一个r 1位多项式都可以作为生成多项式的 从检错及纠错的要求出发 生成多项式应能满足下列要求 任何一位发生错误都应使余数不为0不同位发生错误应使余数不同对余数继续作模2除 应使余数循环将这些要求反映为数学关系是较复杂的 对一个 n k 码来说 可将 Xn 1 分解为若干质因子 注意是模 运算 根据编码要求的码距选取其中的因式或若干因式的乘积作为生成多项式表2 8给出了部分生成多项式 运算方法及运算部件 定点加 减运算定点数乘法运算定点数除法运算浮点数的运算方法运算部件 定点加 减运算 定点加 减运算 定点加 减运算 定点加 减运算 定点加 减运算 定点加 减运算 二进制加法器加法器加速方法 在计算机技术的发展过程中 人们提出了各种各样提高运算速度的方法 从大的方面讲有三个 从系统结构角度 提出了并行处理 流水线等方式运算电路特别是加法和移位用逻辑电路的高速化运算方法和逻辑结构的高速化这些方法是互相联系的 可以并行采用 这里主要讲述第三种方法前面讲过 串行进位并行加法器的速度受进位影响 围绕进位信号的快速处理 提出了许多方法 如正负逻辑交替法 进位信号检测法 跳跃进位法 先行进位法等 在此重点介绍先行进位法 定点加 减运算 二进制加法器先行进位法的基本思想是 考虑任一位进位时 把比它低的所有各位的两个相加数可能对本位进位的影响一并考虑而形成一个统一的进位逻辑 从而使较高位的进位能与比它低的所有各位的进位同时形成诚然 能做到全字长同时进位是最理想的了 但不难想象 对最高位来说 构成同时进位逻辑的门数要很多 以致在实际构成时发生困难因此 一般都分为适当位数的组 组内各位做到完全先行进位即同时进位 组与组之间可以采用串行进位或并行进位 下面主要以 位一组为例 讲述组内并行进位 其余的大家可以类推 定点加 减运算 二进制加法器先行进位的逻辑原理 由前述的进位表达式Ci AiBi Ai Bi Ci 1设Pi Ai Bi Gi AiBi则相应地有Ci Gi PiCi 1称G 为第 位的生成进位 称P C 为第 位的传递进位 时 低位来的进位可以通过第 位传向高位 时 低位来的进位不能通过第 传向高位 有时称 为进位传递函数或进位传递条件 相应地 称为进位生成函数或进位生成条件 上述公式表示 进位由生成进位和传递进位两部分组成 定点加 减运算 定点加 减运算 定点加 减运算 二进制加法器定点加减法的实现 二进制定点加法是计算机中实现算术运算的基础前面已经讲过 采用补码方案时 加减法可用统一的方式处理 因此下面讨论用补码实现加减法对运算器的要求由前面的相关内容可知 可有下列公式 X Y 补 X 补 Y 补 X Y 补 X 补 Y 补 MOD2 若已知 Y 补求 Y 补 则可用把 Y 补的每一位 包括符号位和数值位 取反 再在最低位加 来实现由此可得如图3 1所示的补码加减法运算逻辑电路框图图中F代表多位并行加法器 它的功能是 接收参加运算的两个数X和Y 实现加法运算 并在输出端给出本次运算结果 定点加 减运算 定点加 减运算 定点加 减运算 定点加 减运算 二进制加法器图3 1给出的是实现定点补码加减运算最简化的原理性框图 仍需要从多个方面进行完善才能使之满足实用的要求 主要应考虑的是 溢出问题及其处理应当考虑对运算结果给出一些整体性的标志 如结果是否为0等 这样 可以简化人们的程序设计在实际机器的运算器中 有着多个寄存器 应使运算的操作数和结果可在多个寄存器中选择为使计算机能够高效地工作 应当考虑使运算结果的2倍值 1 2倍结果的自动求取问题 因为 在这里 要实现这一要求是不困难的下面 分别对之作简要讨论 所关注的主要问题是溢出的识别与处置问题 定点加 减运算 二进制加法器 溢出问题及其处置策略由前面的相关讨论可知 仅当运算不产生溢出时 两数和 差 的补码等于两数补码之和 差 溢出 运算结果超出机器数所能表示的范围 对于加减运算来说 仅当相加两数同号或者相减两数异号时 才有发生溢出的可能 下面来看几个相应的示例 定点加 减运算 二进制加法器 溢出问题及其处置策略在上例中 和 得出正确结果 和 为 溢出 情况若以fA fB分别表示两个操作数 A B 的符号位 fS为结果的符号位 符号位fA fB直接参与运算 它所产生的进位以Cf表示 则在以2n 1为模的补码运算中 符号位有进位并不一定表示溢出 上例中的 和 即是这种情况若用C来表示数值最高位产生的进位 则C 1也并不表示一定发生了溢出 上例中的 和 属于这种情况如何判断运算是否发生了溢出 实现时有多种方法可供选择 采用其中一种即可下面将概要介绍判别溢出的几种方法 定点加 减运算 定点加 减运算 二进制加法器 多个寄存器问题在实际的计算机中 尤其是现代计算机中 其运算器中通常包含多个寄存器 它们可被用来保存参与运算的操作数 X 补和 Y 补 也可被用来保存结果 X Y 补或者 X Y 补 完成相应运算操作的指令将会相应地指出参与运算的操作数所关联的寄存器 保存结果的寄存器 参见 指令系统 一章的相关讨论 控制器在分析了相应的指令后将给出相应的内部控制信号 通知运算器 哪两个寄存器被用来保存参与运算的操作数 哪个寄存器被用来保存结果图3 1中的控制门A B C将被相应的以一个控制机构来取代 使得适应于多寄存器的环境 定点加 减运算 二进制加法器 给出结果标志问题除了求得二进制补码形式的加减法运算结果外 为了方便于人们的编程 通常还要求定点加法器给出关于结果的一些特征指示 这些特征指示被以相应的标志触发器保存 通常使用的标志触发器有 零标志触发器Z 若运算结果为0 则Z被置1溢出标志触发器V 若运算产生溢出 则V被置1负标志触发器N 若运算结果的最高位为1 则N被置1 注意 N的值固定地与结果最高位一致 进位 借位标志触发器C 若加法运算的最高位上产生进位或者减法运算的最高位上产生借位 则C被置1这些标志触发器在机器内部按固定规则与数据总线的相应数据位连接 组成一个程序可访问的 逻辑意义上的 标志寄存器 定点加 减运算 二进制加法器 运算结果的移位问题数据的移位操作 2 X 补 X X 2 X 寄存器间的数据传送操作 X Y 通常也是经过加法器来完成的 下图所示电路在加到图3 1电路后即可达到相应目标这也为基于加法器实现乘 除法运算提供了方便 使得相应处理 如 X Y 2 X 可简便 高效地完成 图四实现移位功能的逻辑电路 定点数乘法运算 原码一位乘法所谓 原码一位乘法 就是指参与运算的数和运算结果都使用原码表示 运算一位一位地进行两个原码数相乘 其乘积的符号为相乘两数符号的异或值 数值则为两数绝对值之积设 X 原 XS X1X2X3 Xn Y 原 YS Y1Y2Y3 Yn其中XS YS为符号位 则有 X Y 原 X 原 Y 原 XS YS X1 X2X3 Xn Y1Y2Y3 Yn 符号 表示把符号位和数值邻接起来 定点数乘法运算 定点数乘法运算 原码一位乘法在手工计算时 有 依乘数 绝对值 每一位的取值为1还是为0 决定相加数取被乘数的值还是取零值各相加数是从乘数的最低位求起 逐位变高 相加时逐个左移一位 最后一并求和 乘积的符号位按 正乘正 负乘负结果的符号位为正 正乘负 负乘正结果的符号位为负 的方案求出在计算机中 若完全按上述方法做会存在一些问题 在运算器中是很难实现多个数据同时相加的 通常只能完成对两数的求和运算 其解决方法是 每求得一个相加数 一位积 就同时完成与上一次部分积相加的操作 定点数乘法运算 原码一位乘法在手工计算时 各加数逐位左移 最终相加位数为相乘二数位数 若它们的长度一致 的两倍 而在计算机中 加法器的位数一般与寄存器位数相同 而不是寄存器位数的两倍其解决方法为 每次相加得到的部分积右移一位后再与求得的相加数 位积 相加 因为在求本次部分积之和时 前一次部分积的最低一位不再与任何数值相加手工计算时乘数每一位的值是0还是1都直接看得见 而在计算机内采用由存放乘数寄存器中每一位直接决定本次相加数是被乘数还是零很不方便的若采用由该寄存器的最低一位来执行这种判别 以确定本次的位积 就简便多了基于人们的手工乘法 考虑到计算机实现的简便性 即形成了适合计算机执行的原码一位乘法 定点数乘法运算 原码一位乘法设 X 原 XS X1X2 Xn Y 原 YS Y1Y2 Yn 则原码乘法的规则为 积的符号位 XS YS 积的绝对值 X Y X Y X 0 Y1Y2Y3 Yn X Y1 2 1 Y2 2 2 Yn 2 n X 2 1 Y1 2 1 Y2 2 1 Y 0 其递推公式为 P0 0P1 2 1 P0 X Y P2 2 1 P1 X Y 1 P3 2 1 P2 X Y 2 P 2 P 1 X Y1 X Y 定点数乘法运算 定点数乘法运算 原码一位乘法乘法运算开始时 有 A寄存器被清为0 作为初始部分积被乘数放在B寄存器中乘数放在C寄存器中实现部分积和被乘数相加是通过给出A F命令和B F命令实现的部分积的右移是通过把经过F求得的结果右斜一位 用F 2 BUS控制 送入BUS 并用BUS A命令将结果接收到A寄存器中的C寄存器是用移位寄存器实现的 本身能在移位命令C 2 C控制下自行移位 其最低位的值可用作B F的控制命令 定点数乘法运算 原码一位乘法注意 加法器F最低一位的值 右移时移入C寄存器的最高数值位 使积的低位部分保存在C寄存器中 原来的乘数在逐位右移过程中丢失了图中还给出了一个计数器Cd 用来控制逐位相乘的次数 它的初值经常存放乘数位数的补码值 以后每完成一次乘计算就使其计数一次 待计数到0时 给出结束乘运算的控制信号为了简化描述 图中未画出求结果的符号位的电路 结果符号位的求取是很简单的 可以通过对相乘二数的符号执行异或操作完成应当特别注意 原码一位乘法的主体部分 求结果的数值部分 是绝对值计算 因为 与补码不同 原码是将数符和数值部分分别编码形成的机器数原码一位乘法的控制流程可示意于图二 定点数乘法运算 原码一位乘法从流程图上可以清楚地看到 这里原码一位乘法是通过循环迭代的方法实现的 即按一定的时间顺序重复地使用最少量的硬件 寄存器 加法器 移位器 和传送门等 把整个乘法过程变成为数据经过门和加法器实现相加 移位和寄存器接收的时序控制过程由于其与人们的手工乘法运算具有基本相同的过程特性 因此 原码一位乘法具有简单 易于掌握等特点由前面的相关讨论可知 为了方便加减运算 使其实现简单高效 计算机中的定点数值数据通常用补码表示 对之 若使用原码一位乘法来完成乘法计算 首先要将补码形式的数据转换为原码表示 同时 在求得结果后 应将结果转换为补码表示 定点数乘法运算 补码一位乘法若计算机中的数是用补码表示的 可以把补码转换成原码 相乘后再把原码转换为补码 这样做 码制变换比较麻烦 而且影响速度可以直接用补码来完成一位乘法运算 以解决上述问题 不过 应当注意 与原码不同 补码是将数符和数值一起编码而产生机器数的 因此 不能简单套用原码乘法的运算规则下面讨论两种实现补码一位乘法的方法 修正法 基于原码乘法的规则执行相应补码乘法 在此基础上 考虑原码与补码间的差异 对求得的结果进行修正 使满足补码运算的规则要求布斯法 比较乘法 是基于修正法产生的方法在这两种方法中 布斯法应用更为广泛 定点数乘法运算 补码一位乘法 校正法校正法是将 X 补与 Y 补按原码运算规则运算 求得相应结果 再根据情况对结果加以校正 进而得到所需 X Y 补的方法为此 下面分两种情况来讨论如何基于原码一位乘法规则得到补码一位乘法的结果 被乘数为任意值 乘数大于或等于0 此时 乘数的原码表示与补码表示是一致的被乘数为任意值 乘数小于0 此时 乘数的原码表示与补码表示是不同的被乘数 X 补的符号任意 乘数Y 0 相应地 有 当被乘数为正 X 0 时 有 X 补 X 原 X Y 补 Y 原 Y所以乘法过程与原码乘法相同 且符号位可以参加运算 定点数乘法运算 补码一位乘法 校正法当被乘数为负 X 0 用模4补码 则有 X 补 22 X mod4 2n 2 X mod4 由于Y 0 Y 0故 Y 补 Y 0 Y Y2 Y Y1 2 Y2 2 2 Yn 2 n X 补 Y 补 X 补 Y 2n 2 X Y 2n 2 Y X Y2n 2 Y 2n 2 Y1 2 1 Y2 2 2 Y 2 n Y1 2n 1 Y2 2n 2 Yn 1 21 Yn 22 22 mod4 X 补 Y 补 2n 2 Y X Y 22 X Y X Y 补综合而论 当 X 补为任意符号数 Y 0时 X Y 补 X 补 Y 补 定点数乘法运算 补码一位乘法 校正法被乘数 X 补符号任意 乘数Y为负数 相应地 有 因为 Y 0 故有 Y 补 1 Y Y Yn mod2 由补码与其真值间的关系可知Y Y 补 2 0 Y Y Yn 1因此 X Y 补 X 0 Y Y Yn 1 补 X 0 Y Y Yn 补 X 补 X 补 0 Y Y Yn X 补综合上述讨论 可以得到结论 X Y 补 X 补 0 Y Y Yn X 补 Y 其中 Y0为 Y 补的数符位 定点数乘法运算 补码一位乘法 校正法若设 Y 补 Y0 Y1Y2 Yn 1Yn 则按校正法执行补码一位乘法 其相应的递推公式为 P0 补 0 P1 补 2 P0 补 X 补 Y P2 补 2 P1 补 X 补 Y Pn 补 2 Pn 1 补 X 补 Y Pn 1 补 Pn 补 X 补 Y0校正法的补码一位乘法的规则可用文字归纳为 如原码一位乘法那样完成乘法过程 但相应的加法为带二位符号的补码加法 移位按补码移位执行若乘数为负 最后一次执行 X 补操作 不移位若乘数有n位 含一位符号位 执行n步操作 定点数乘法运算 补码一位乘法 布斯 BOOTH 乘法布斯法是基于校正法形成的 它克服了校正法最后一步处理不规则的问题设 X 补 X X X Xn Y 补 Y Y Y Yn 其中 X Y 为符号位 求 C 补 X Y 补 基于补码乘法的校正法 有 C 补 X Y 补 X 补 0 Y Y Yn Y X 补 X 补 Y 2 Y 2 Yn 2 n Y X 补 Y Y Y Y 2 Y Y 2 2 Yn Y 2 n Y 2 n X 补 Y Y Y2 Y 2 Y Y 2 Y Y 2 n Y Y 2 n Y 0 定点数乘法运算 补码一位乘法 布斯 BOOTH 乘法由以上讨论可以看出 布斯法克服了校正法存在的控制不规范问题 这使得此方法得到了广泛应用布斯法基于两个相邻的乘数数位的比较结果确定当前这一步具体执行的操作 因而是一种比较法布斯法求取补码一位乘法的递推公式为 P0 补 0 Y 0 P1 补 2 P0 补 X 补 Y Y P2 补 2 P1 补 X 补 Y Y Pn 补 2 Pn 1 补 X 补 Y2 Y Pn 1 补 Pn 补 X 补 Y Y 定点数乘法运算 补码一位乘法 布斯 BOOTH 乘法布斯乘法的规则有 基于比较形成n个部分积 P1 Pn 的规则 判别YiYi 1 i n n 1 2 1 有 若YiYi 1 00或11 上次部分积右移一位得到新部分积若YiYi 1 01 则上次部分积加上 X 补 然后右移一位得到新部分积若YiYi 1 10 则上次部分积加上 X 补 然后右移一位得到新部分积n n 1当i 0 判断Y0Y1 其运算规则同上 只是不移位 最后一步的运算 定点数乘法运算 补码一位乘法 布斯 BOOTH 乘法布斯乘法的要点 布斯乘法的要点可被归纳为 部分积的初始值 P0 被设置为0 乘数的补充位 Yn 1 被设置为0乘数采用一位符号位 被乘数和部分积采用两位符号位 即求部分积的加法按模4补码规则进行 乘数的最后一位减去其相邻的前一位 乘以被乘数 再加上上一次的部分积 右移一位得到新的部分积同原码乘法一样 在每次将部分即进行移位时 移出位被移到乘数 乘数寄存器 的最高位 或者说 部分分积连同乘数一起按补码右移的规则右移一位 重复第2步到第4步的操作n 1次 但最后一次不执行移位操作 定点数乘法运算 补码一位乘法 布斯 BOOTH 乘法下面来看三个较为典型的示例 例1 一个正数乘以一个负数例2 两个负数相乘例3 两个 1相乘例1 设X 0 1101 Y 0 1011 用布斯乘法计算X Y解 X 补 00 1101 Y 补 1 0101 X 补 11 0011 X Y 补 11 01110001X Y 0 10001111相关过程如下 定点数乘法运算 定点数乘法运算 定点数乘法运算 定点数乘法运算 定点数乘法运算 定点数乘法运算 原码两位乘法按乘数每两位的取值情况 一次求出对应于该两位的部分积 此时 只要增加少量逻辑电路 就可使乘法速度提高一倍原码两位乘法 乘数和被乘数都用原码表示 同原码一位乘法 分别计算结果的数符和数值 数值部分采用绝对值计算两位乘数有四种可能的组合 每种组合对应于以下操作 00 相当于0 X 部分积Pi右移2位 不进行其他运算 01 相当于1 X 部分积Pi X 右移2位 10 相当于2 X 部分积Pi 2X 右移2位 11 相当于3 X 部分积Pi 3X 右移2位 定点数乘法运算 原码两位乘法将原码两位乘法与一位乘法相比 可以发现 在运算规则上 多了两种情况 2X 对应于当前两位乘数为10的情况 3X 对应于当前两位乘数为11的情况在这其中 要实现 2X是不困难的 问题在于 3X不便于一次完成解决的办法是 以 4X X 来代替3X 本次运算只执行 X 将 4X归并到下一步执行由于部分积已右移了两位 所欠下的 4X已变成 X 为此 增设一个触发器C 称为 欠位 触发器 记录是否欠下 4X因此 实际操作用Yi 1 Yi C三位来控制 运算规则如表3 1所示 表中2 2为右移2位 定点数乘法运算 定点数乘法运算 定点数乘法运算 补码两位乘法下面讨论基于布斯法的补码两位乘法若将一位补码乘法的布斯方法中的连续两步运算进行合并 即可得到补码两位乘法的布斯方法的计算公式 假设上一步的部分积为 Pi 补 则求 Pi 1 补的公式为 Pi 1 补 Pi 补 Yn i 1 Yn i X 补 2 1相应地 基于 Pi 1 补求 Pi 2 补的公式为 Pi 2 补 Pi 1 补 Yn i Yn i 1 X 补 2 1将前一公式中的 Pi 1 补代入 Pi 2 补的公式中 得 Pi 2 补 Pi 补 Yn i 1 Yn i X 补 2 1 Yn i Yn i 1 X 补 2 1 Pi 补 Yn i 1 Yn i X 补 2 Yn i Yn i 1 X 补 2 2 Pi 补 Yn i 1 Yn i 2Yn i 1 X 补 2 2 定点数乘法运算 补码两位乘法上述公式表明 在已知 P0 补 0时 若要求第一步的部分积 P1 补 则需要考察补充位Yn 1 Yn和Yn 1这三位间的关系 并取 P1 补 P0 补 Yn 1 Yn 2Yn 1 X 补 2 2要求第二步的部分积 P2 补 则有 P2 补 P1 补 Yn 1 Yn 2 2Yn 3 X 补 2 2 Yn i 1 Yn i 2Yn i 1 可有8种组和情况 相应的组合值及其对应的操作如表3 2所示 表3 2中的2 2表示按补码右移规则右移两位 定点数乘法运算 补码两位乘法 定点数乘法运算 补码两位乘法从表3 2可以看出 对于补码两位乘法来说 在乘法执行过程中 有五种不同的操作 分别是 Pi 2 补 Pi 补 0 2 2 Pi 2 补 Pi 补 X 补 2 2 Pi 2 补 Pi 补 X 补 2 2 Pi 2 补 Pi 补 2 X 补 2 2 Pi 2 补 Pi 补 2 X 补 2 2相应地 加法器所接收的来自被乘数寄存器的数据有 X 补 直接取置被乘数寄存器的值2 X 补 被乘数寄存器值左斜一位的值 X 补 取自被乘数寄存器反相的输出 12 X 补 左斜一位的被乘数寄存器反相输出 2 定点数乘法运算 补码两位乘法为了实现部分积 乘数的右移两位 2 2 的操作 加法器的输出需要右斜两位传送到部分积寄存器 同时 乘数寄存器的最高两位应连接到加法器的最低两位且乘数寄存器每次应具有右移两位的特性加法器需使用三位符号位 即执行模8加法 以免 X 补左斜两位送加法器时运算结果出现溢出的情形发生补码两位乘法运算中的求部分积的次数和右移操作的控制问题 当乘数由1位符号位和n 奇数 位数据位组成时 求部分积的次数为 1 n 2 且最后一次的右移操作只右移一位 若数值位本身为偶数 则可采取下述两种方法之一 在乘数的最后补一个0 再加补充位 使数据位为奇数且其值不变 求部分积的次数为1 n 1 2 最后一次右移操作也只右移一位 定点数乘法运算 补码两位乘法乘数增加一位符号位 使总位数仍为偶数 此时求部分积的次数为n 2 1 最后一次不再执行右移操作无论采用哪一种方法 其答案是相同的 设X 0 1101 Y 0 1011 求 X Y 补解 X 补 1 0011 111 00112 X 补 110 0110 X 补 000 11012 X 补 001 1010 定点数乘法运算 定点数乘法运算 定点数除法运算 原码一位除法原码一位除法 有 恢复余数法 和 加减交替法 不恢复余数法 两种方法 在计算机中常用的是 加减交替法 因为 它的操作步骤少 也不复杂 一位 除法 基于加法器 通过一个算法 过程 来完成两个数的除法操作 算法的基本步骤是一位一位地求得作为结果的 商 类似于乘法 也可一次求得多位商 鉴于其复杂性 不予讨论 原码除法 基于 原码 的编码规则 把除法分为两项工作 一是求商的绝对值 二是求商 和余数 的符号 也可以说 原码除法 是基于绝对值运算的除法除法算法在本质上是一种试探法对于除法 总是假定 被除数 除数 对十进制除法 其每位商为 中之一 但对二进制除法 其每位商只可能为 或 定点数除法运算 定点数除法运算 原码一位除法 恢复余数法手工计算存在的问题及解决方法 手工计算的方法要求加法器的位数必须为除数位数的两倍 实现起来不合理 通过分析发现右移除数 可以通过左移被除数 余数 的方案替代 左移出去的被除数高位都是0 对计算不会产生任何影响手工计算除法时 上商0还是1是计算者用观察比较的办法确定 而在计算机中 只能用做减法判结果为正还是为负来确定在计算机中 比较除数与被除数大小是通过做减法实现的 除数乘以1 2与余数比较 可以等效于除数不动 而使余数左移一位来实现 减除数的绝对值 Y 可通过加 Y 补来实现 上商可通过在商寄存器末位置 商 或置 商 来实现 上商的同时使商寄存器与余数寄存器一起左移一位等 定点数除法运算 原码一位除法 恢复余数法用 恢复余数法 实现原码一位除法 相应地 有 设被除数 X 原 X0 X1X2X3 X 除数 Y 原 Y0 Y1Y2Y3 Y 商 C 原 C0 C1C2C3 C 余数 R 原 R0 R1R2R3 R 则 X 原 Y 原 C 原 R 原 2 n用 恢复余数法 实现原码一位除法的基本方略是 符号位单独处理商的数值部分 变成两正数相除 即 X Y X Y 定点数除法运算 原码一位除法 恢复余数法每一步除法通过2R Y i 0 1 2 R X 来实现比较若2R Y Ri 1 0 即余数为正 则商上 1 若2R Y Ri 1 0 即余数为负 则商上 0 但此时Ri 1实际上不是余数 称为假余数 本次不应该做减法 为比较而做的减法 所以必须加上 Y 恢复成此前的余数 恢复余数法 即由此而得名示例 设X 0 1001 Y 0 1011 用恢复余数法求X Y 相应地 有 X 原 1 1001 Y 原 0 1011 X 0 1001 Y 0 1011 Y 补 1 0101 定点数除法运算 原码一位除法 恢复余数法上例所示除法的相应结果为 商的绝对值 C 原 0 1101机器余数的绝对值 在相应除法运算结束时 余数寄存器 其初始值为被除数 的值 它是经过了确定次数左移后得到 形式上的余数 R4 原 0 0001商的数符Cf Xf Yf 1 0 1商的原码表示为 C 原 1 1101机器余数的原码表示为 R 原 1 0001实际余数 R 原真 2 4 R 原 1 00000001原码恢复余数除法一般很少采用 原因是每次恢复余数时多做了一次加法 使除法时间变长 同时造成除法步骤不固定 控制上也复杂一些 上商和左移还必须分成两步来完成 定点数除法运算 原码一位除法 加减交替法加减交替法 不恢复余数法 是基于恢复余数法形成的 设恢复余数法在运算过程中的第i步得到的余数Ri是假余数 即Ri 0 在此基础上 要得到下一步除法的新余数Ri 1 首先要恢复余数 然后左移一位 再减去除数 Y 才能得到新余数Ri 1 即有 Ri 1 2 Ri Y Y 2Ri Y 由此可见 在得到并确知Ri 0的情况下 要得到新余数Ri 1 不必恢复余数 只要将Ri视为余数 左移一位后再加上 Y 就可得到新余数Ri 1当然 若最后一步除法得到余数Rn为假余数 Rn 0 而又要保留结果余数时 则仍然需要恢复余数 注意 仅在最后一步 定点数除法运算 定点数除法运算 原码一位除法 加减交替法加减交替法以被除数的绝对值作为初始的余数开始除法运算 并以之减去除数的绝对值 形成第一步的余数之后 每一步均取余数的数符的反作为商 商0则做加法 商1则做减法 这就是称其 加减交替法 的原因示例 X 0 1001 Y 0 1011 求X Y解 根据题意 有 X 原 1 1001 Y 原 0 1011 X 0 1001 Y 0 1011 Y 补 1 0101结果 X Y 原 1 1101 R4 原 1 0001 R4 原真 2 4 R4 原 1 00000001 定点数除法运算 定点数除法运算 定点数除法运算 定点数除法运算 原码一位除法 加减交替法可以把定点原码一位除法的实现方案归纳如下 对定点小数除法 首先要比较除数和被除数的绝对值大小 防止出现数值溢出的错误商的符号位为相除二数的符号的半加和计算机中用加减交替法实现除法时 被除数的位数可以是除数的两倍 其低位的数值部分开始时放在商寄存器中 运算过程中 存放被除数和商的寄存器同时移位 由于商是逐位形成的 因此 不会影响除法过程的正确性计算机中 求差和移位是在同一操作步骤中完成的 而不是像例中所写的用两个步骤完成原码一位除法的加减交替法的运算过程的详细控制流程如图二所示 定点数除法运算 定点补码一位除法补码除法和其它补码运算一样 符号位也应与数值位一样参与运算补码一位除法的基本问题 比较 上商 获得新余数比较 绝对值大小的比较 因参加除法运算的两个数是带符号的数 判别是否够减 就不能再简单地用被除数 余数 减去除数 而是要比较它们绝对值的大小 所以 当两数同号时应作减法 两数异号时应作加法设被除数为 X 补 XS X X2 X R0 补除数为 Y 补 YS Y1Y2 Yn第i步的余数为 Ri 补 RS R1R2 Rn i 0 1 n 其中XS YS和RS是相应数据的数符位 定点数除法运算 定点补码一位除法在进行被除数与除数间绝对值大小的比较中 由相应数学知识可知 有 若XS YS 则 X 补 Y 补 R1 补 若新余数的符号位 RS 与XS相同 说明够减 否则说明不够减 商为正若XS YS 则 X 补 Y 补 R1 补 若新余数的符号位 RS 与XS相同 说明够减 否则说明不够减 商为负第一次计算后 由于结果送到存放被除数的寄存器 余数寄存器 中 可能会将被除数的符号改变 这样一来 再按照上述方法去确认是否 够减 难以形成正确的结论 然而 除数寄存器的内容在完成上述操作时是不变的 所以 应当将上述确认第一次比较结果的原则在表述形式上作些调整 改为基于YS进行 定点数除法运算 定点补码一位除法基于上述讨论 在进行被除数与除数间绝对值大小的比较中 应有 若XS YS 则 X 补 Y 补 R1 补 若新余数的符号位 RS 与YS相同 说明够减 否则说明不够减 商为正若XS YS 则 X 补 Y 补 R1 补 若新余数的符号位 RS 与YS不相同 说明够减 否则说明不够减 商为负上商 对于补码除法来说 由于商可正可负 需要区别对待 当商为正时 若比较确认被除数 余数 的绝对值较大 相应位的商为1 反之 相应位的商为0 而当商为负时 基于补码与反码的关系 当比较确认被除数 余数 的绝对值较大时 相应位的商为0 反之 相应位的商为1 为降低误差 将商的最低位恒置1 定点数除法运算 定点数除法运算 定点补码一位除法上表所列的结论告诉我们 在形成补码商的过程中 若对于负商 在约定末位置1 按照反码上商的条件下 则正商和负商的上商规则可一致性地表述为 若余数与除数同号 商为1 余数与除数异号 商为0溢出检测与商的符号位产生 对于第一步运算 有 若XS YS 则 X 补 Y 补 R1 补 若新余数的符号位 RS 与YS相同 说明够减 商为1 由于是第一次上商且本应上的商为正 0 而现在的值说明商为负 1 故产生溢出 否则 商0 为正确的符号位若XS YS 则 X 补 Y 补 R1 补 若新余数的符号位 RS 与YS不相同 说明够减 商为0 由于是第一次上商且本应上的商为负 1 而现在的值说明商为正 0 故产生溢出 否则 商1 为正确的符号位 定点数除法运算 定点补码一位除法综上所述 在没有溢出的情况下 符号位参与运算 得到商的符号位是正确的这样做还有一个好处 第一步除法 求商的符号位时 可利用余数来判断除法的溢出对于除法 若 X Y 产生溢出 而补码除法的第一步操作是 X 补 Y 补 R1 补 这样 可以如下规则判定补码除法是否产生了溢出 在XS YS时 若有RS YS 则除法产生溢出在XS YS时 若有RS YS 则除法产生溢出在按照上述规则确认产生了溢出时 将溢出标志触发器置 结果不必左斜送到余数寄存器形成新余数 除法至此结束 而这时被除数和除数均未被破坏 定点数除法运算 定点补码一位除法求新余数的一般规则 下面分几种情况来讨论 若XS YS 商为正 对之 有 若余数 Ri 补的符号位与YS相同 说明 够减 商为 得到的余数 Ri 补为真余数 下一步计算为 Ri 1 补 2 Ri 补 Y 补若余数 Ri 补的符号位与YS相异 说明 不够减 商为0 所得余数 Ri 补为假余数 下一步要恢复余数 之后再左移一位与除数比较 相应计算为