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

2021年计算机组成原理第5讲_定点除法第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.
1
2021/1/16
计算机组成原理第5讲_定点除法
补码一位乘法
Tow’s complement Multiplication
Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's 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 two's complement representation. That forces the multiplication process to be adapted to handle two's complement numbers, and that complicates the process a bit more.
2
2021/1/16
计算机组成原理第5讲_定点除法
补码一位乘法
设 [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页
3
2021/1/16
计算机组成原理第5讲_定点除法
[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]
=