CS274: Computer Architecture - Computer Arithmetic: Addition and Subtraction Logic Gates

Activity Goals

The goals of this activity are:

1. To design truth tables and a circuit for addition
2. To design truth tables and circuit for overflow detection
3. To generzlie overflow detection using only the carry bits

Supplemental Reading

Feel free to visit these resources for supplemental background reading material.

• The Year 2038 Problem
• To keep a Boeing Dreamliner flying, reboot once every 248 days by Engadget

The Activity

Directions

Consider the activity models and answer the questions provided. First reflect on these questions on your own briefly, before discussing and comparing your thoughts with your group. Appoint one member of your group to discuss your findings with the class, and the rest of the group should help that member prepare their response. Answer each question individually from the activity, and compare with your group to prepare for our whole-class discussion. After class, think about the questions in the reflective prompt and respond to those individually in your notebook. Report out on areas of disagreement or items for which you and your group identified alternative approaches. Write down and report out questions you encountered along the way for group discussion.

---

Model 1: Logic Gates for Adding and Subtracting

A	B	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Questions

1. Draw a truth table for addition for both sum and carry outputs.
2. Draw a circuit representing the sum and carry when adding two one-bit values.

---

Model 2: Overflow Detection

Questions

1. Given that overflow occurs when the sign bit of the sum differs from the sign bit of the two inputs.
2. Generate examples of overflow when adding values of like signs together (both positive and negative). Generate examples of non-overflow (for both positive and negative). Finally, generate an example adding a positive and negative value together. What do their carry bits have in common in the most significant bit?
3. Generalize how you can detect overflow by using only the carry in and carry out bits in the most significant digit. Now, write this down in a truth table and draw a circuit for overflow detection.
4. What is the effect of declaring a variable as an unsigned int as opposed to an int?

---

Model 3: Key Formulas and Concepts Recap

A quick-reference recap of the key rules from this activity. Try to reproduce each one from memory before peeking!

Key Rules and Formulas

• Half adder (no carry in): sum = A XOR B; carry = A AND B. Micro-example: A=1, B=1 gives sum = 1 XOR 1 = 0, carry = 1 AND 1 = 1: that is 1 + 1 = 10 binary.
• Full adder (with carry in): sum = (A XOR B) XOR carryIn; carryOut = ((A XOR B) AND carryIn) OR (A AND B). Micro-example: A=1, B=1, carryIn=1 gives sum = (1 XOR 1) XOR 1 = 1 and carryOut = (0 AND 1) OR (1 AND 1) = 1: that is 1 + 1 + 1 = 11 binary.
• Overflow by signs: overflow occurs when the sign bit of the sum differs from the (shared) sign bit of the two inputs; adding opposite-sign values never overflows.
• Overflow by carries: overflow = carryIn XOR carryOut at the most significant bit. Micro-example (4 bits): 0101 + 0110: the MSB column receives carry in 1 but produces carry out 0, and 1 XOR 0 = 1: overflow.
• Unsigned values: an unsigned int reinterprets the same n bits as 0..2^n - 1; the hardware adds identically, only the overflow interpretation changes (unsigned "rollover," like an odometer wrapping from 999999 to 000000).

Full Adder Truth Table

carryIn  A  B | sum  carryOut
   0     0  0 |  0      0
   0     0  1 |  1      0
   0     1  0 |  1      0
   0     1  1 |  0      1
   1     0  0 |  1      0
   1     0  1 |  0      1
   1     1  0 |  0      1
   1     1  1 |  1      1

Glossary

Term	Meaning
Truth table	A table listing a circuit's output for every combination of inputs
Logic gate	A circuit computing a boolean function (AND, OR, XOR, NOT, ...)
XOR	"Exclusive or": 1 exactly when the inputs differ
Half adder	Adds two 1-bit inputs, producing sum and carry
Full adder	Adds two 1-bit inputs plus a carry in, producing sum and carry out
Ripple-carry adder	A chain of full adders where each carry out feeds the next carry in
Overflow	A signed result that does not fit; detected as carryIn XOR carryOut at the MSB
Rollover	Unsigned wraparound past the maximum value, like an odometer

Questions

1. Without looking, write the full adder's sum and carryOut formulas, then verify them against the truth table row where all three inputs are 1.

---

Submission

I encourage you to submit your answers to the questions (and ask your own questions!) using the Class Activity Questions discussion board. You may also respond to questions or comments made by others, or ask follow-up questions there. Answer any reflective prompt questions in the Reflective Journal section of your OneNote Classroom personal section. You can find the link to the class notebook on the syllabus.