Divider

• Division (x = qy + r) after “restoring algorithm”

Classic Method

• Assuming always $y_i=1$ then subtract the divisor
• If the result is positive, then move to the next digit
• If the result is negative, then set $y_i=0$ and add the divisor back (i.e. cancel the subtraction)

Array Divider

• Performs the division as a combinational circuit
• 1 subtractor (ex: ripple-borrow subtractor) is needed per row
• How to perform correction in case of negative result?
  • The result is negative when the borrow (left most bit) is equal to ‘1’
  • Feed the borrow back (right) as signal $a$
    • $a=0$ the subtraction was correct, no need to correct
    • $a=1$ instead of the difference, use the minuend
  • Special full subtractor the “D-Box”
    • 
    • $d_i=a{x}_i+\overline{a}(x_i\oplus y_i\oplus b_{i-1})$
    • $b_i=\overline{x_i}{y}_i+\overline{x_i}{b}_{i-1}+y_i{b}_{i-1}$
• 

Sequential Divider

• Quotient is computed stepwise
• Algorithm
  1. Load operand into register Y
  2. AC ← 0, Q ← X
  3. Iterate n times
     1. shift (AC, Q) one position left
     2. AC ← AC - Y
     3. If AC < 0
        1. then AC ← AC + Y
        2. else Q(0) ← 1
  4. Quotient is in Q, remainder is in AC
• Notes
  • Uses logic shift (fill left with 0)
  • AC and Y are (n+1) bit numbers in 2’s complement
•