Lecture 2: Combinational Logic

What this lecture covers

This lecture continues directly from Lecture 1's transistor-level introduction to CMOS gates. It first closes out the device-level material — explaining why an AND gate needs a NAND gate plus an inverter rather than a more "obvious" six-transistor circuit, and covering dynamic and static power consumption and Moore's law — before moving up a level of abstraction into Boolean algebra and combinational logic design.

The second half builds the vocabulary and tools used throughout the rest of the course: sum-of-products (SOP) and product-of-sums (POS) canonical forms, and the standard combinational building blocks — decoders, multiplexers, adders, and programmable logic arrays (PLAs) — that will reappear when the course constructs a microprocessor. After this lecture you should be able to derive a truth table's canonical Boolean form and explain what a decoder, multiplexer, or adder does at both the functional and gate level.

Key ideas

• Why AND needs NAND + inverter: p-type transistors pull up voltage well but pull down poorly, and n-type transistors do the opposite, so a "naive" AND gate built from mixed series/parallel transistors would not switch reliably.
• Dynamic vs. static power: dynamic power is capacitance * voltage^2 * frequency, consumed when signals switch; static power comes from transistor leakage even when nothing is switching.
• Moore's law: the number of transistors that can be manufactured at minimum cost on a chip has grown exponentially, from thousands in the 1960s to tens of billions today.
• Sum of products (SOP): a Boolean function written as the OR of minterms (AND terms) for every input combination that makes the output true — a canonical, if often unminimized, way to specify any function from its truth table.
• Product of sums (POS): the dual representation, built from maxterms — the AND of OR terms for every input combination that makes the output false.
• De Morgan's law and bubble pushing: NOR is equivalent to AND with inverted inputs, and NAND is equivalent to OR with inverted inputs, which lets you redraw a circuit using whichever gate type is cheaper to build.
• Decoders: an n-input, 2^n-output circuit that raises exactly one output line based on the input bit pattern, used for tasks like memory address decoding or instruction opcode decoding.
• Multiplexers: select one of several data inputs based on a select input, and can also implement arbitrary logic functions as lookup tables — the same principle FPGAs use.
• Ripple-carry vs. carry-lookahead adders: chaining one-bit full adders is simple but slow because the carry must propagate through every bit; carry-lookahead logic computes carries faster using dedicated Boolean equations.

Walkthrough

Recap and finishing the AND gate question (3:50)

Mutlu recaps the transistor-level CMOS material from Lecture 1 — the inverter, NAND gate, and the general pull-up/pull-down network structure — then answers a question raised the day before: why can't you build an AND gate directly with two n-type and two p-type transistors, instead of a NAND followed by an inverter? He sketches the naive circuit on the board and explains that p-type transistors pass "ones" well but "zeros" poorly (and vice versa for n-type), so a directly wired AND gate would output unreliable intermediate voltages. This is why AND gates cost six transistors rather than four.

Power consumption (20:01)

The lecture introduces dynamic power, given by capacitance times voltage squared times switching frequency, and static power, caused by transistor leakage current even when a circuit is idle. Since voltage affects power cubically once its effect on achievable frequency is included, reducing supply voltage is one of the most effective ways to cut power consumption, which is why modern chips run at low voltages. Total energy consumed is the integral of both power components over time.

Moore's law and manufacturing (28:10)

Mutlu walks through Gordon Moore's original observation that the number of transistors manufacturable at minimum cost per chip grows exponentially over time, illustrating it with Moore's own plots from the 1960s. He connects this to the physical challenges of shrinking transistors further today — structures only a few atoms across, extreme ultraviolet lithography, and the search for new device materials — and assigns Moore's 1965 paper as optional reading, framing continued innovation "at the bottom" of the stack as a prerequisite for progress "at the top," including AI.

Boolean algebra: axioms, theorems, and De Morgan's law (38:17)

The lecture reviews Boolean algebra as the formal theory behind combinational circuit design: axioms such as identity and distributive laws, the principle of duality (swapping AND/OR and 0/1 preserves truth), and simplification theorems like XY + XY' = X. It then covers De Morgan's law and demonstrates "bubble pushing" — redrawing a NOR gate as an AND gate with inverted inputs, or a NAND gate as an OR gate with inverted inputs — which is useful when one gate type is cheaper or faster to fabricate than another.

Canonical forms: sum of products and product of sums (46:21)

Mutlu defines minterms (products including every input variable) and maxterms (sums including every input variable), then shows how any truth table can be written as a sum of products — the OR of all minterms where the output is 1 — or a product of sums — the AND of all maxterms where the output is 0. He introduces the compact minterm/maxterm summation notation (for example, F = Σm(3,4,5,6,7)) and stresses that while SOP and POS are guaranteed, standardized starting points, they are not minimal circuits; Boolean algebra rules are then used to simplify them into cheaper two-level logic.

Decoders and multiplexers (1:16:23)

The lecture introduces decoders as pattern detectors: an n-input decoder raises exactly one of 2^n outputs corresponding to the input bit pattern, which is the mechanism behind memory address decoding and instruction opcode decoding. It then covers multiplexers, which select one of several data inputs based on a select line, and shows how multiplexers can implement arbitrary logic functions by wiring constant 0s and 1s to their data inputs — the same lookup-table principle FPGAs use to make hardware reconfigurable.

Adders and programmable logic arrays (1:36:39)

Mutlu derives the one-bit full adder's truth table and its SOP-based logic, then chains full adders into a ripple-carry adder, noting its latency downside: the most significant bit's sum can't be computed until the carry has rippled through every earlier bit. He briefly introduces carry-lookahead addition as a way to compute carries faster using dedicated logic rather than waiting for each bit in sequence. The lecture closes with programmable logic arrays (PLAs), which implement any sum-of-products function by programming connections between an AND-gate array and an OR-gate array, illustrated by wiring a PLA to implement the full adder.

Before you watch

• Watch Lecture 1 first, since this lecture builds directly on the CMOS transistor and inverter/NAND/AND gate material introduced there.
• Basic Boolean algebra and binary number representation, as covered in the assigned readings, make the canonical-forms section easier to follow.

Check your understanding

1. Why does a "naive" four-transistor AND gate fail, and how does the standard six-transistor NAND-plus-inverter design avoid the problem?
2. Write the sum-of-products and product-of-sums forms for a function and explain what a minterm and a maxterm represent.
3. How does bubble pushing let you rewrite a NAND gate as an OR gate with inverted inputs?
4. Explain how a decoder can be used to decode a memory address or a processor instruction opcode.
5. Why is a ripple-carry adder slower for wide operands, and what problem does a carry-lookahead adder try to solve?