Lecture 4: Sequential Logic II, Labs, and Verilog

What this lecture covers

The lecture answers a practical question: given a textual description of a controller, how do you turn it into working hardware? It walks through designing a traffic-light controller as a Moore finite state machine (FSM), deriving the transition table, next-state equations and output equations, then compares different ways of encoding FSM states. It also introduces the semester's FPGA lab sequence and gives a first look at Verilog, the hardware description language the labs use.

This is the second lecture on sequential logic in the course, following directly on synchronous vs. asynchronous circuits from the previous session. After watching, you should be able to derive an FSM's state transition table and equations from a word description, explain the trade-offs between binary, one-hot and output state encoding, and recognize the difference between Moore and Mealy machines in a circuit diagram.

Key ideas

• Moore FSM: an FSM whose outputs depend only on the current state, not on the inputs, which makes outputs stable and glitch-free.
• Mealy FSM: an FSM whose outputs depend on both state and input, which needs fewer states but produces less stable outputs and longer combinational paths.
• Transition table: a table of current state and inputs mapped to next state, used to derive don't-care simplifications and next-state equations.
• State encoding: binary/full encoding minimizes flip-flops; one-hot encoding uses one bit per state and simplifies logic at the cost of more flip-flops; output encoding embeds the Moore machine's outputs directly in the state bits.
• Asynchronous reset: a reset signal that takes effect immediately rather than waiting for a clock edge, used because reset is often safety-critical.
• FPGA: a reconfigurable chip built from lookup tables (LUTs) and configurable switch boxes that can implement any circuit that fits its resources.
• CAD flow: the sequence of logic synthesis, placement and routing, and bitstream generation that turns a Verilog description into a working FPGA configuration.
• Verilog module: the basic building block of a Verilog design, defined by a name, a port list, and a description of functionality between module and endmodule.

Walkthrough

Designing the traffic-light controller as a Moore FSM (0:00)

The lecture opens mid-discussion of scheduling fairness, then sets up the running example: a traffic-light controller with two avenues (A and B) as inputs and two lights as outputs, plus clock and reset. The instructor draws the four-state Moore FSM by hand: state S0 (A green, B red) holds while there is traffic on A, then moves through a yellow intermediate state S1, to S2 (A red, B green), through yellow state S3, and back to S0. Because the outputs are attached to states rather than transitions, this is identified as a Moore machine.

Deriving next-state and output equations (4:03)

The states are encoded with two bits, and a transition table is built from the state diagram, with don't-care entries where an input does not affect the next state. From this table the lecture derives Boolean equations for the next-state bits (one of which simplifies to an XOR of the current state bits) and, separately, equations for the two-bit-encoded outputs LA and LB, since a Moore machine's output logic depends only on the state. A timing diagram is then used to show how the state register, next-state logic and asynchronous reset interact with real (non-ideal) clock and reset edges, including propagation delay.

State encoding schemes: binary, one-hot, and output encoding (20:15)

Using a four-state traffic-light example, the lecture contrasts three encodings. Binary (full) encoding uses log2(states) bits and minimizes flip-flops but not necessarily the logic. One-hot encoding uses one bit per state, which makes the design process simple and automatable at the cost of more flip-flops. Output encoding, only possible for Moore machines, sets each state bit to directly match an output signal (for example, one bit per light color), eliminating separate output logic entirely. The choice between them is presented as a designer's trade-off among flip-flop count, logic complexity, area, and performance.

Moore vs. Mealy trade-offs using a pattern-detector snail (23:19)

A second example, a "snail" that reacts to the bit pattern 1101, is designed first as a Moore machine and then as a Mealy machine, showing that the Mealy version needs one fewer state because it can signal detection on a transition rather than by entering an extra state. Class discussion draws out the trade-offs: Moore machines need more states but have more stable, glitch-free outputs and shorter combinational paths, while Mealy machines can be more compact but their outputs depend on inputs that may not be stable, and chaining several Mealy machines lengthens the combinational path from input to output.

FSM design procedure and its role in system design (32:26)

The lecture closes the FSM topic with a general procedure: enumerate all states from a textual description, build the state transition diagram, define inputs and outputs for each state, and figure out the transitions, typically starting from the reset state. It notes that real systems use many communicating FSMs (for processor control, memory controllers, caches, and other controllers) rather than one enormous state machine.

Lab logistics and the FPGA lab sequence (48:36)

After a break, the lecture switches to introducing the ten-lab FPGA sequence, which counts for 30 of 100 course points, worked in pairs on a Basys 3 FPGA board. It previews the ten labs in order: a basic comparison circuit, an adder mapped to the FPGA, seven-segment display output, a turn-signal FSM, an ALU, ALU verification via testbenches, MIPS assembly, a two-part processor integration culminating in running a program on the built processor, and finally a performance-improvement lab. The instructor also shows research examples (DRAM-Bender, RowHammer, RowPress, flash memory studies) where FPGAs were used for memory characterization research, to motivate why FPGA skills matter beyond the course.

Inside an FPGA: LUTs, switches, and the CAD flow (1:02:44)

The lecture explains FPGA internals: configurable logic blocks built from lookup tables (a LUT with n inputs can implement any n-input function), switch boxes that route connections between blocks, and I/O blocks connecting to board pins. It covers the advantages of FPGAs (direct hardware implementation, high performance and energy efficiency relative to general-purpose processors, low development cost relative to ASICs) and disadvantages (lower performance and efficiency than custom ASICs, area and reliability overhead from reconfigurability). It then walks through the CAD design flow used to program an FPGA: writing Verilog, logic synthesis, placement and routing, and bitstream generation, using Xilinx Vivado as the tool for the course.

Introduction to hardware description languages and Verilog modules (1:20:59)

In the final segment, the lecture motivates hardware description languages (HDLs) by pointing to transistor counts in real chips (from roughly 1.75 billion in 2017 to over 100 billion in recent designs), arguing that manual transistor-level design is infeasible at this scale. It contrasts HDLs with sequential languages like C, noting that hardware is inherently concurrent, and introduces Verilog's hierarchical design principle (top-down decomposition into modules down to primitive gates, or bottom-up composition from basic building blocks). It ends with the syntax of a Verilog module: naming the module, declaring input/output ports, and using bit-range notation such as [31:0] A to declare multi-bit signals.

Before you watch

• Review the previous lecture's material on synchronous vs. asynchronous circuits and the distinction between combinational and sequential logic.
• Be comfortable reading a truth table and simplifying Boolean expressions (sum-of-products form), since the FSM equations build directly on this.
• Knowing what a lookup table (LUT) is will make the FPGA architecture section easier to follow.

Check your understanding

1. Why does a Moore machine's output logic depend only on the current state, while a Mealy machine's output logic also depends on the current input?
2. For the traffic-light FSM, why can the next state be "don't care" with respect to traffic on Avenue B while the controller is in state S0?
3. What is the trade-off between one-hot encoding and binary encoding of FSM states?
4. Why is output encoding only usable for Moore machines and not Mealy machines?
5. Why do hardware description languages exist instead of just using a language like C to describe circuits?