计算机组成原理第5讲_定点除法.ppt

* * 计算机组成原理 Principles of Computer Organization 广义双语教学课程 09/skyclass25/ 青岛理工大学 校级精品课程 /ec/C84/ 第3章 运算方法和运算部件 ( 4 ) Several algorithms exist to perform division in digital designs. These algorithms fall into two main categories: slow division and fast division. Slow division algorithms produce one digit of the final quotient per iteration. Examples of slow division include restoring, non-performing restoring, non-restoring, and SRT division. Fast division methods start with a close approximation to the final quotient and produce twice as many digits of the final quotient on each iteration. Newton-Raphson and Goldschmidt fall into this category. 补码一位乘法 Tow’s complement Multiplication Booths multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in twos complement notation. The algorithm was invented by Andrew Donald Booth in 1951 . 比较法（又称Booth法）是实现补码一位乘法的一种方案。 Modern computers embed the sign of the number in the number itself, usually in the twos complement representation. That forces the multiplication process to be adapted to handle twos complement numbers, and that complicates the process a bit more. 补码一位乘法 设 [X]补= X0 .X1X2……Xn-1Xn ，[Y]补= Y0 .Y1Y2……Yn-1Yn 根据校正法 [X·Y]补 = [X]补·（0. Y1Y2……Yn-1Yn）+ [-X]补·Y0 =[X]补·（-Y0 +Y12-1＋Y22-2＋……＋Yn 2-n） 式中，Y0是符号位（“0”为正，“1”为负），Yn+1是在乘数最低位Yn后增设的附加位，初值为0。 =[X]补·[-Y0+(Y1-Y12-1)+(Y22-1-Y22-2)+…+( Yn 2－(n-1)-Yn 2-n)] =[X]补·[(Y1-Y0)+( Y2-Y1)2-1+…+（Yn-Yn-1）2-（n-1） +(0-Yn) 2-n] =[X]补·[(Y1－Y0)+( Y2－Y1)2-1+…+( Yn+1－Yn) 2-n] =[X]补· 则 [X·Y]补 = [X]补·（－Y0 + ) 48页 [P0]补 ＝0 开始时，部分积为0， 然后在上一步的部分积上加 ( Yi+1－Yi) ·[X]补（i=n,…,2,1,0），再右移一位，得到新的部分积。如此重复n+1步，最后一次不移位，得到[X·Y]补。 从该递推公式可归纳出补码一位比较乘法的运算规则 递推公式（ Booth公式）: [P1]补 ＝{[P0]补+( Yn+1－Yn)·[X]补}·2－1 [P2]补 ＝{[P1]补+( Yn－Yn－1)·[X]补}·2－1 … [Pi]补 ＝{[Pi－1]补+( Yn－i+2－Yn－i+1)·[X]补}·2－1 … [Pn]补 ＝{[Pn－1]补+( Y2－Y1)·[X]补}·2－1 [Pn+1]补 ＝[Pn]补+( Y1－Y0)·[X]补 [X·Y]补=[X]补·[(Y1－Y0)+( Y2－Y1)2-1+…+( Yn+1－Yn) 2-n] =[X·Y]补 部分积的初值＝0 位积+部分积 然后