COA — STEP 7 NOTES: COMPUTER ARITHMETIC

Common to ECE 231EC5E04 and CSE 231CS5002 (based on Mano, Chapter 10/7)
Unit placement
• ECE Unit-3 (Computer Arithmetic)
• CSE Unit-III (Computer Arithmetic)
One set of notes serves both.
Sourcing note: This step is covered in the project file
6__COAUNITIIIPART2_COMPUTER_ARITHMETICS.pdf. The algorithms, rules, and
flowchart logic below are taken from that file — marked [Certain]. The step-by-step
numerical register traces (sequential multiply, Booth's, restoring division) appear in the
file only as figures with no text layer, so the traces shown here were independently
recomputed and verified rather than copied from the figures.
File-label caution: The source file is internally headed "Unit-IV." Per the syllabi,
Computer Arithmetic is ECE Unit-3 / CSE Unit-III. Content is correct; only the
file's own label differs.

7.1 Introduction
Data in a computer is manipulated using arithmetic instructions. The four basic
operations are addition, subtraction, multiplication, and division; all other operations
are derived from these. A separate arithmetic processing unit inside the CPU carries
them out, working on fixed-point (integer/fraction) or floating-point data. A clear set of
well-defined steps to solve a problem is called an algorithm. [Certain]

7.2 Addition and Subtraction

Signed-Magnitude Add/Subtract
When numbers are in signed-magnitude form, the sign is handled separately from the
magnitude. The eight cases of add/subtract reduce to a simple rule: [Certain]
• Compare the two signs with an XOR gate: output 0 = signs identical, output 1 =
signs different.
• For ADD: identical signs → add the magnitudes; different signs → subtract them.
• For SUBTRACT: different signs → add the magnitudes; identical signs → subtract
them.
The rule table (A = first operand, B = second): [Certain]
 Operation When A > B When A < B When A = B
Add magnitudes ± (A + B) — —
Subtract + (A − B) − (B − A) + (A − B)
magnitudes

Algorithm details: [Certain]

• Magnitudes are added with EA ← A + B, where E (a carry flip-flop) combines with
A as register EA. A carry of 1 in E after addition is an overflow, transferred to the
add-overflow flip-flop AVF.
• When magnitudes are subtracted, A is added to the 2's complement of B. No
overflow can occur in subtraction, so AVF is cleared to 0.
• E = 1 means A ≥ B → the result in A is correct. (If the result is zero, force the sign
positive to avoid "negative zero.")
• E = 0 means A < B → take the 2's complement of A (microoperation A ← A' + 1)
and complement the sign.

Signed 2's-Complement Add/Subtract

Much simpler — no sign comparison needed: [Certain]
• Addition: AC ← AC + B, then check V (overflow).
• Subtraction: AC ← AC + B' + 1 (add the 2's complement of B), then check V.
This is why modern hardware prefers 2's complement: one adder + one complementer
handle both add and subtract.

7.3 Multiplication Algorithm (Sequential, Signed-Magnitude)

Setup: multiplicand in B, multiplier in Q, their signs in Bs and Qs. The product is double-
length, stored in registers A and Q. Registers A and E are cleared, and the sequence counter
SC is set to the number of bits in the multiplier. The product sign = Bs XOR Qs. [Certain]
Algorithm (repeat until SC = 0): [Certain]
1. Test the low-order bit of the multiplier, Qn.
2. If Qn = 1, add the multiplicand B to the partial product A (A ← A + B).
3. If Qn = 0, do nothing (just shift).
4. Shift register EAQ right by one (forming the new partial product).
5. Decrement SC by 1. If SC ≠ 0, repeat from step 1; if SC = 0, stop.
Worked example — multiply 5 (multiplicand) × 3 (multiplier), 4-bit: [Likely —
canonical method; file shows the trace only as a figure]
B = 0101 (5), Q = 0011 (3), SC = 4, A = 0000, E = 0.
 Step E A Q SC Action
init 0 0000 0011 4 —
Qn=1 → 0 0101 0011 add B
A=A+B
shr EAQ 0 0010 1001 3 shift right
Qn=1 → 0 0111 1001 add B
A=A+B
shr EAQ 0 0011 1100 2 shift right
Qn=0 → 0 0011 1100 —
no add
shr EAQ 0 0001 1110 1 shift right
Qn=0 → 0 0001 1110 —
no add
shr EAQ 0 0000 1111 0 shift right,
stop

Product = A,Q = 0000 1111 = 15 (= 5 × 3). ✓ [Likely]

7.4 Booth's Algorithm (Signed 2's-Complement Multiplication)

Booth's algorithm multiplies binary integers in signed-2's-complement form. Its insight:
a string of 0's in the multiplier needs only shifting, and a string of 1's from bit weight 2^k
down to 2^m can be treated as 2^(k+1) − 2^m. [Certain]
File's example of the idea: the number 001110 (+14) has a run of 1's from 2³ to 2¹ (k = 3,
m = 1), so it equals 2⁴ − 2¹ = 16 − 2 = 14. Thus M × 14 = M×2⁴ − M×2¹ — shift M left four
times, subtract M shifted left once. [Certain]
The rules — inspect the two bits Qn (current) and Qn+1 (the bit to its right, initially 0):
[Certain]

Qn Qn+1 Meaning Action

10 first 1 in a string of 1's Subtract multiplicand
from partial product
(AC ← AC − B)
01 first 0 in a string of 0's Add multiplicand to
partial product (AC ←
AC + B)
00 string of 0's continues no change
11 string of 1's continues no change
After each step, arithmetic-shift-right AC, Qn, Qn+1. Repeat for n bits. The algorithm
works for positive and negative multipliers because a negative multiplier ends in a string
of 1's, making the last operation a correct subtraction. [Certain]
Worked example — multiply (+5) × (−3) using Booth's, 5-bit: [Verified by
recomputation; the file shows its own trace only as a figure]
Multiplicand M = 00101 (+5), so −M = 11011. Multiplier Q = 11101 (−3 in 5-bit 2's
complement). Qn+1 starts at 0. AC = 00000, repeat 5 times. Inspect the pair (Qn, Qn+1)
each step, act, then arithmetic-shift-right AC-Q-Qn+1 together.

(Qn,
Step Qn+1) Action AC Q Qn+1
init — — 00000 11101 0
1 10 AC = AC − 11011 11101 0
M
ashr 11101 11110 1
2 01 AC = AC + 00010 11110 1
M
ashr 00001 01111 0
3 10 AC = AC − 11100 01111 0
M
ashr 11110 00111 1
4 11 shift only 11110 00111 1
ashr 11111 00011 1
5 11 shift only 11111 00011 1
ashr 11111 10001 1

Result AC,Q = 11111 10001 = −15 in 2's complement. (+5 × −3 = −15.) ✓

Note how the algorithm handles the negative multiplier automatically: the run of 1's in −3
(11101) produces the right mix of subtract/add operations, and the final result is correct
without any special end-correction. [Method [Certain] from source; this specific trace
verified by recomputation]
The exact register width and intermediate bits depend on the textbook's
convention; the method and rules are [Certain], the specific trace is [Likely].

7.5 Division Algorithm (Restoring, Signed-Magnitude)

Binary division is done by successive compare, shift, and subtract. It is simpler than
decimal division because each quotient digit is only 0 or 1 — no guessing how many times
the divisor fits. [Certain]
Paper method: compare the divisor with the most-significant bits of the dividend. If the
partial remainder ≥ divisor, the quotient bit is 1 and the divisor is subtracted; if smaller, the
quotient bit is 0 and no subtraction. The divisor shifts right each time. [Certain]
Hardware method (what we implement): instead of shifting the divisor right, shift the
dividend (partial remainder) left. Subtraction is done by adding the 2's complement of
B; the end carry E tells the relative magnitude. Register EAQ shifts left, 0 inserted into Qn,
old E lost. Divisor in B, double-length dividend in A and Q. [Certain]
The restoring-division algorithm (repeat n times): [Certain on method]
1. Shift EAQ left by one.
2. Subtract divisor: A ← A + B' + 1 (i.e. A − B).
3. Examine E (the end carry):
– E = 1 → A ≥ B → set quotient bit Qn = 1 (keep the subtraction).
– E = 0 → A < B → set quotient bit Qn = 0, and restore by adding B back (A ←
A + B).
4. Decrement SC; repeat until done. At the end, A holds the remainder, Q holds the
quotient.
Worked example — divide 7 ÷ 3 (n = 4): [Verified by recomputation]
Dividend = 0000 0111 in registers A,Q (A = 0000, Q = 0111 = 7); Divisor B = 0011 (3); 2's
complement of B = 1101. Repeat 4 times: shift A,Q left → subtract (A = A + B' + 1) → test
E → set Qn or restore.

Step Operation A Q E
init — 0000 0111 —
1 shl A,Q 0000 1110
A=A−B 1101 1110 0
E=0→ 0000 1110
restore
(A+B), Qn =
0
2 shl A,Q 0001 1100
A=A−B 1110 1100 0
E=0→ 0001 1100
restore, Qn =
0
3 shl A,Q 0011 1000
A=A−B 0000 1000 1
E = 1 → Qn = 0000 1001
1 (no
restore)
 Step Operation A Q E
4 shl A,Q 0001 0010
A=A−B 1110 0010 0
E=0→ 0001 0010
restore, Qn =
0

Final: Q = 0010 = quotient 2, A = 0001 = remainder 1. Check: 7 = 3×2 + 1. ✓

(Note: each "shl A,Q" shifts the double-length register left by one and brings the just-
decided quotient bit into the low end of Q on the next cycle's setup; the quotient builds up
in Q from the right.) [Method [Certain] from source; this trace verified by
recomputation]

7.6 Floating-Point Arithmetic

A floating-point number has a mantissa m and an exponent e, representing m × r^e. The
mantissa may be a fraction or integer; the radix point and radix r are not stored. [Certain]
Example: decimal 537.25 is stored as m = 53725, e = 3, meaning .53725 × 10³. A number
is normalized when the most significant mantissa digit is non-zero (maximum significant
digits). Zero cannot be normalized — it is all 0's in mantissa and exponent. [Certain]
Biased exponent advantage: it stores only positive numbers, so exponents are easy to
compare without worrying about signs; the smallest biased exponent is all zeros, making
the floating-point zero a zero mantissa with the smallest exponent. [Certain]

Addition / Subtraction (four parts) — [Certain]

1. Check for zeros — if either operand is 0, handle specially (a normalized number
can't be 0).
2. Align the mantissas — make the two exponents equal by shifting the smaller
number's mantissa right while incrementing its exponent.
3. Add or subtract the mantissas (same as fixed-point).
4. Normalize the result — if the MSB position A1 is 0, shift the mantissa left and
decrement the exponent, repeating until A1 = 1.
Worked alignment example (from the file): to add .5372400 × 10² and .1580000 ×
10⁻¹, the exponents differ by 3, so shift the second mantissa right 3 places to make both
exponents 10², then add the mantissas. [Certain]

Multiplication / Division — [Certain]

• Multiplication: no alignment needed — multiply the mantissas and add the
exponents.
• Division: no alignment needed — divide the mantissas and subtract the
exponents.
The mantissa operations reuse the same fixed-point registers and circuits; exponent
operations are compare/increment (align), add/subtract (multiply/divide), and decrement
(normalize). [Certain]
Register configuration: mantissa in signed-magnitude with biased exponent. AC = (As, A,
a); BR = (Bs, B, b); QR = (Qs, Q, q). A1 is the MSB of A, which must be 1 to be normalized. A
parallel adder handles mantissas (sum to A, carry to E); a separate adder + comparator
handles exponents. [Certain]

7.7 Decimal Arithmetic (brief)

Decimal arithmetic uses BCD (binary-coded decimal). Each decimal digit needs 4 bits.
Decimal addition requires a correction step: if a BCD digit sum exceeds 9 (1001), add 6
(0110) to correct it. Signed decimal numbers use signed-magnitude or 10's-complement
(the 10's complement of a BCD number = 9's complement + 1 at the LSD). [Certain — from
Part B / data-rep file; syllabus lists Decimal Arithmetic Unit & Operations]

Key Points — Step 7 (Computer Arithmetic)

• Four basic operations (add, subtract, multiply, divide); all else derived. A separate
arithmetic unit handles them.
• Signed-magnitude add/subtract: XOR the signs to decide add-vs-subtract
magnitudes; overflow → AVF. Signed 2's complement is simpler: add = AC+B,
subtract = AC + B' + 1.
• Sequential multiplication: test Qn; if 1 add B; shift EAQ right; repeat SC times.
Product in A,Q.
• Booth's algorithm (2's complement): inspect Qn Qn+1 → 10 subtract, 01 add,
00/11 no change; then arithmetic-shift-right. Works for negative multipliers. Idea: a
run of 1's = 2^(k+1) − 2^m.
• Restoring division: shift EAQ left, subtract divisor (A + B' + 1), check E — E=1 →
quotient bit 1; E=0 → quotient bit 0 and restore (add B back). Ends with remainder
in A, quotient in Q.
• Floating-point add/sub (4 steps): check zeros → align mantissas (equalize
exponents) → add/subtract mantissas → normalize. Multiply: multiply mantissas,
add exponents. Divide: divide mantissas, subtract exponents. No alignment for
×/÷.
• Normalized = MSB of mantissa non-zero; biased exponent keeps exponents
positive and easy to compare.
• Decimal (BCD): add 6 correction when a digit sum exceeds 9.

Reminder on sourcing: Algorithms and rules are [Certain] (from the file's text).
The step-by-step register traces (sequential multiply 5×3, Booth's +5×−3,
restoring division 7÷3) appear in the file only as figures, so they were
independently recomputed and verified for these notes. The final answers —
5×3 = 15, +5×−3 = −15, 7÷3 → Q = 2, R = 1 — are all correct.