To study and simulate the Restoring Division Algorithm for unsigned binary integers. The simulator visualizes the repetitive process of left-shifting, subtracting the divisor, and conditionally restoring the partial remainder to calculate both the quotient and the final remainder.
Theory
What is Restoring Division?
Restoring division is an algorithm used in digital logic to divide two unsigned binary numbers. It mimics the traditional "paper-and-pencil" long division method but relies strictly on shifts, subtractions, and additions. It is called "restoring" because if a subtraction results in a negative partial remainder, the algorithm "restores" the previous remainder by adding the divisor back.
Registers Used
M (Divisor): Holds the divisor (n bits).
Q (Dividend / Quotient): Initially holds the dividend. During execution, it gradually accumulates the quotient bits.
A (Accumulator / Remainder): Initially 0. Holds the partial remainder during division and the final remainder at the end.
Count: Counter initialized to n (the number of bits in Q).
The Algorithm Steps
For an n-bit division, perform the following steps n times:
Shift Left AQ: Shift the combined A and Q registers left by 1 bit.
Subtract: A = A - M (using two's complement addition: A = A + M' + 1).
Check Sign of A:
If A < 0 (Sign bit is 1): The subtraction was invalid (we tried to subtract a divisor larger than the current partial remainder). Set the quotient bit Q0 = 0, and Restore A by adding M back (A = A + M).
If A ≥ 0 (Sign bit is 0): The subtraction was valid. Set the quotient bit Q0 = 1. (No restoration needed).
Decrement Count: Reduce count by 1. If Count > 0, repeat from Step 1.
Worked Example: 7 ÷ 3
Let n = 4. Dividend Q = 7 (0111). Divisor M = 3 (0011). A = 00000.
In restoring division, what does it mean to "restore" A?
a) Setting A to zero
b) Adding the divisor (M) back to A
c) Shifting A to the right
d) Inverting all bits in A
Answer: b) If A - M is negative, we "restore" the previous value of A by doing A + M.
Question 2
When is the restoration step performed?
a) Only on the last iteration
b) Whenever A >= 0 after subtraction
c) Whenever A < 0 after subtraction
d) Before shifting AQ
Answer: c) The restore step (A = A + M) happens when the result of A - M is negative, indicating the divisor is larger than the partial remainder.
Question 3
What determines the value of the quotient bit Q0 in each iteration?
a) The sign bit of A after subtraction
b) The LSB of the divisor M
c) Whether the counter is even or odd
d) The sign bit of Q
Answer: a) If A < 0 (sign bit is 1), Q0 is set to 0. If A >= 0 (sign bit is 0), Q0 is set to 1.
Question 4
What registers hold the final quotient and remainder, respectively?
a) A holds Quotient, Q holds Remainder
b) Q holds Quotient, M holds Remainder
c) Q holds Quotient, A holds Remainder
d) M holds Quotient, A holds Remainder
Answer: c) At the end of the algorithm, the Q register holds the quotient and the A register holds the final remainder.
Question 5
If dividing an n-bit dividend by an n-bit divisor, how many iterations does restoring division take?
a) n - 1
b) n
c) n + 1
d) 2n
Answer: b) The cycle of Shift-Subtract-Restore/SetQ is repeated exactly n times.
Procedure
Follow these steps to operate the Restoring Division Simulator:
1
Navigate to the Simulation tab to see the restoring division datapath.
2
Set Divisor (M): Click the bit buttons (M3–M0) to enter the 4-bit unsigned divisor. Ensure the divisor is not zero.
3
Set Dividend (Q): Click the bit buttons (Q3–Q0) to enter the 4-bit unsigned dividend.
4
Run the Simulation: Click the "Divide" button. The simulator will automatically calculate the result.
5
Observe Iteration Steps: The Iteration Table on the right will populate with the steps: Left Shift, Subtract, and Restore/Set.
6
Follow the Animation: The circuit diagram will visually highlight the active operation. Notice when the Adder/Subtractor turns red (Subtract) versus green (Restore Add).
7
Final Result: The final Quotient (in Q) and Remainder (in A) are displayed at the bottom right.