Lecture 3: Sequential Logic

What this lecture covers

This lecture finishes the combinational-logic material from Lecture 2 and then introduces sequential logic, the concept that gives circuits memory. It opens by proving logical completeness (that AND, OR, and NOT — or NAND alone — can implement any Boolean function), then covers a handful of practical combinational building blocks: equality checkers, an arithmetic logic unit (ALU), tri-state buffers, and a simplification technique called the uniting theorem, illustrated with a priority circuit.

The second half is the core of the lecture: how to build a circuit that remembers a value. Mutlu builds up from cross-coupled inverters (which store a bit but can't be controlled) to the RS latch, the gated D latch, registers, a small memory array, and finally the D flip-flop, motivated by the need for synchronous, clock-driven state changes. The lecture ends by introducing finite state machines, the framework the course will use to describe and design a microprocessor's control logic.

Key ideas

• Logical completeness: any Boolean function can be built from AND, OR, and NOT gates alone (and, separately, from NAND gates alone, or NOR gates alone), because these can implement the canonical sum-of-products form.
• ALU (arithmetic logic unit): a single module that performs one of several arithmetic or logic operations, chosen by a function-select input, by routing operand values through adders and multiplexers.
• Tri-state buffers: a switch-like gate whose output is either the input value or a floating (undriven) state, used to let multiple components share a single bus wire without conflict.
• Uniting theorem: if an input variable's value doesn't change the output across a set of truth-table rows, that variable can be eliminated from the simplified equation — the basis of the "don't care" (X) notation.
• Cross-coupled inverters: the simplest storage element, with two stable states, but with no way to set or change the stored value.
• RS latch: two cross-coupled NAND gates with set (S) and reset (R) inputs that let you write a bit, but whose forbidden input combination (S = R = 0) can cause metastability.
• Gated D latch: adds a write-enable and single data input to the RS latch design, guaranteeing S and R are never simultaneously zero.
• D flip-flop: two D latches wired to opposite clock phases so that the output only changes on the clock's rising edge, holding its value for the entire clock cycle — the storage element synchronous circuits actually use.
• Finite state machine (FSM): a system with a finite set of states, inputs, outputs, a next-state function, and an output function, built from a state register (sequential) plus next-state and output logic (combinational).

Walkthrough

Recap and logical completeness (2:57)

Mutlu reviews the combinational logic covered so far — decoders, multiplexers, full adders, canonical SOP/POS forms, and programmable logic arrays (PLAs) — then formalizes logical completeness: since a PLA can implement any truth table's sum-of-products form using only AND, OR, and NOT gates, that gate set is logically complete. He notes, without proof, that NAND alone (and NOR alone) is also logically complete.

Comparators and the arithmetic logic unit (9:01)

The lecture builds a bitwise equality checker from XNOR gates and an AND gate, then introduces the arithmetic logic unit (ALU) as the module that combines several arithmetic and logic operations — AND, OR, addition, subtraction, and others — into one circuit, selected by a function-select input. Mutlu traces through the ALU's internal multiplexers and an adder to show how selecting different function codes produces addition or, using two's-complement negation, subtraction.

Tri-state buffers and shared buses (15:06)

A tri-state buffer either passes its input through or leaves its output floating (undriven), controlled by an enable signal. Mutlu explains why this matters: multiple components such as a CPU and memory can be connected to the same shared bus, and control logic ensures only one tri-state buffer drives the bus at any time, avoiding a short circuit. He shows how tri-state buffers can also implement multiplexers and gives a transistor-level implementation of the buffer itself.

Boolean simplification and priority circuits (25:16)

The lecture introduces the uniting theorem: if a variable doesn't affect the output across two truth-table rows, it can be dropped from the simplified expression, which motivates the "don't care" (X) notation. Mutlu applies this to design a priority circuit that grants a shared bus to one of several requesters based on a fixed priority order, showing how don't-care simplification makes the resulting equations much shorter than the full truth table.

From cross-coupled inverters to the RS latch (38:27)

Mutlu introduces the simplest sequential element: two cross-coupled inverters, which have two stable states (and an undesirable third, oscillating "metastable" state) but no way to set their value. Adding control turns this into the RS latch, built from two cross-coupled NAND gates with set (S) and reset (R) inputs. He works through why holding both S and R at one preserves the stored value, why driving one low sets or resets it, and why driving both low at once is forbidden — it violates the assumption that Q and its complement are opposite, and can lead to metastability.

Registers and a small memory array (1:05:28)

Building on the gated D latch (which fixes the RS latch's forbidden-input problem with a single data and write-enable input), the lecture assembles multiple D latches in parallel into a register, then combines several registers with an address decoder and multiplexer into a small addressable memory array. Mutlu works through reading and writing a two-location, three-bit memory in detail, showing how the decoder selects a location and the multiplexer routes the correct stored value to the output, and notes the same idea scales to lookup tables used inside FPGAs.

Clocks, D flip-flops, and finite state machines (1:28:49)

Using a traffic light as an example, Mutlu introduces the idea of state and the clock signal that synchronizes when a system moves from one state to the next, contrasting synchronous design (state changes only at clock edges, easier to design correctly) with asynchronous design (state changes whenever inputs change, prone to race conditions). He shows why a simple gated D latch can't serve as a state register, because its output changes as soon as its input changes while the clock is high, and fixes this by chaining two D latches on opposite clock phases into a D flip-flop, which only updates on the clock's rising edge. The lecture closes by defining a finite state machine as a state register plus next-state logic and output logic, setting up the design of a full FSM in the next lecture.

Before you watch

• Watch Lecture 1 and Lecture 2 first; this lecture assumes you know CMOS gates, truth tables, SOP/POS forms, decoders, and multiplexers.
• Being comfortable with truth tables and basic Boolean simplification will make the uniting theorem and priority-circuit sections easier to follow.

Check your understanding

1. Why is the set {AND, OR, NOT} logically complete, and why is NAND alone also logically complete?
2. How do tri-state buffers let a CPU and memory share a single bus wire without conflict?
3. Why is the input combination S = R = 0 forbidden in an RS latch, and what can happen if it occurs?
4. Explain why a plain gated D latch cannot be used as a synchronous state register, and how chaining two latches into a D flip-flop solves the problem.
5. What are the five elements of a finite state machine, and which parts are combinational versus sequential?