7.3 Combinational Circuits

This chapter under major construction.

Domino adder. This video shows a 4-bit ripple-carry adder that was implemented using 10,000 dominoes.

Exercises.

Design a circuit to control a single light bulb by three switches. The circuit has three inputs (the switch settings x, y, and z) and one output (the light control). At any time, you should be able to turn the light off (if on) or on (if off) by changing the position of any one of the three switches. When all three switches are 0 (down position), the light control is 0 (light off).
Which of the following TOY machine components are not combinational circuits?
1. Control
2. Counter
3. Registers
4. Main memory
5. Adder

Creative Exercises.

Sum-of-products. Disjunctive normal form. Algebraic properties: sum and product are commutative and associative, distributive property, etc.
Product-of-sums. Conjunctive normal form. Include a term for each 0 in the truth table trow.
Consensus theorems. Verify that (a+b)(a'+c)(b+c) = (a+b)(a'+c) and (ab) + (a'c) + (bc) = (ab) + (a'c).
Duality. The dual of any boolean identity is obtained by exchanging OR with AND and 0 with 1.
DeMorgan laws.
XOR using NAND. Implement an XOR gate using only NAND gates. Assume you can have inputs that are 0 or 1.
XOR using NAND. Implement an XOR gate using only 4 NAND gates. Assume you can have inputs that are 0 or 1. Answer: XOR(a, b) = NAND(d, e), where c = NAND(a, b), d = NAND(a, c), and e = NAND(b, c).
OR and NAND using NOR. Implement OR using NOR gates. Implement NAND using NOR gates. Don't assume that you can use inputs that are 0 or 1.
Universality. Prove that the following combinations of gates are universal:
- { AND, NOT }
- { OR, NOT }
- { NAND }
- { NOR }
- { XOR, AND }
Non-universality. Prove that the following gates are not universal:
- { AND }
- { OR }
- { XOR }
AND from XOR. Prove that you can't make an AND gate out of XOR gates.
Solution. As above { XOR, AND } is universal. So if you could make an AND gate out of XOR gaets, { XOR } would be univeral. But in the previous question, you proved that it was not universal.
The 2-NOTs problem. Give three inputs a, b, and c, design a circuit that outputs a', b', and c'. You may use as many AND and OR gates as you like, but at most two NOT gates. Warning: high degree of difficulty.
Flat computer. Show that, in principle, you can draw and circuit in the plane. Assume two input AND, OR, and NOT can be drawn in the plane. It suffices to draw a crossover circuit. planar cross-over circuit.
Comparator circuit.
At least k. A n-way majority circuit takes n inputs and returns 1 if and only if at least strictly more of its inputs are 1 than 0. Given an n-way majority circuit, describe how to build an At-Least-k circuit that returns 1 if and only if at least k of its inputs are 1. Answer: consider a 2n-way majority circuit. Make n-k+1 of the inputs 1, k-1 of the inputs 0, and the original n inputs.
Exactly k circuit. Describe how to build a circuit that outputs 1 if and only if exactly k of its inputs are 1. Answer: If k = n, use an n-way and gate. Otherwise build up an At-least-k circuit and an At-least-k+1 circuit as in the previous exercise. It has exactly k inputs that are 1 if the first circuit outputs 1, but the second one outputs 0.
Odd parity from majority gates. Describe how to build an n-way odd parity circuit using only majority gates. You may assume that you have 0s and 1s as inputs.
Odd parity. Describe how to build an N-way odd parity circuit using only AND, OR, NOT. Hint: build a tree of 3-way odd parity gates, using ceil(2.5(N-1)) total gates.
What is the smallest such circuit you can build for N = 2 to 6? The 3-way XOR tree construction is optimal for N = 2 to 5: 3 gates, 5 gates, 8 gates, and 10 gates respectively. The answer is unknown for N = 6 (but is known to be either 12 or 13). (Ingo Wegener, 1991)
XOR from AND. Design an XOR circuit using only AND and NOT. Use as few AND gates as possible. Min = 3.
MAJ from AND. Design a 3-way MAJ circuit using only AND and NOT. Use as few AND gates as possible. Min = 4.
Adder from majority gates. Describe how to build an n-bit ripple-carry adder circuit using only majority gates. You may assume that you have 0s and 1s available as inputs. Hint: build up a 3-way odd parity circuit out of 3-way majority circuits. Note that MAJ(x, y) = AND(x, y) and MAJ(x, y, 1) = OR(x, y).
Boolean logic puzzle. You must transport a wolf, a goat, and a cabbage to the other side of the river using a boat. Due to natural predator relationships, you cannot leave the goat and the wolf alone on the same side of the river at the same time. Nor can you leave the goat and the cabbage together.
Overflow of two's complement adder. How to detect overflow of two's complement adder? Subtractor? Answer If the carry out of the leftmost bit is different from the carry in.
Boolean functions and circuits. Let f be a boolean function on n input bits. Prove that for most functions f, the number of AND, OR, and NOT gates needed to implement f is at least 2^(n/3). Hint: prove that the number of circuits with m gates is at most 2^m and compare this quantity to the number of boolean functions on n inputs.