CS Notes

05 Sequential Logic Design II & Hardware Description Languages and Verilog

Apr 02, 202518 min read

Lecture from: 09.03.2023 | Video: YT

Sequential Logic Design II - Finite State Machines

We Covered A Lot of Sequential Logic

In the previous lecture, we delved into sequential logic, covering circuits capable of storing information. These included:

  • Cross-coupled inverter: The fundamental building block for memory elements.
  • R-S Latch: A basic latch with Set and Reset inputs.
  • Gated D Latch: A latch controlled by a clock or enable signal.
  • D Flip-Flop: An edge-triggered storage element, crucial for synchronous circuits.
  • Register: A collection of D flip-flops for storing multi-bit data.
  • Memory: A larger structure built from storage elements to hold data.

We also discussed:

  • Sequential logic circuits: Circuits whose outputs depend on both current and past inputs, requiring state and a clock for synchronization in synchronous systems. We contrasted asynchronous and synchronous sequential circuits.
  • Finite State Machines (FSMs): A mathematical model of computation used to design sequential logic circuits. Today, we will focus on how to design FSMs in detail.

Recall: Sequential Circuits

Sequential circuits are characterized by their ability to produce outputs based on both current and past input values. This “memory” aspect is what distinguishes them from combinational circuits.

As depicted above, a sequential circuit fundamentally comprises:

  • Combinational Circuit: Processes the inputs and the current state to generate outputs and the next state.
  • Storage Element: Stores the current state, providing feedback to the combinational circuit.

To illustrate the difference between combinational and sequential circuits, consider these analogies:

  • Combinational Lock (Left): Similar to a combinational circuit, it only depends on the current input combination. If you enter the correct combination, it opens immediately.
  • Sequential Lock (Right): Like a sequential circuit, it depends on the sequence of past inputs. You need to dial the correct numbers in the correct order to open it. This lock has memory of the dials’ positions.

We modeled the sequential lock using a state diagram to fully describe its operation. This diagram visually represents the states of the lock and the transitions between them based on input sequences.

This diagram is a graphical representation of a Finite State Machine.

Recall: Finite State Machines (FSMs)

FSMs are discrete-time models of stateful systems, defined by five key elements:

  1. A finite number of states: Each state represents a “snapshot” of the system at a given time, capturing all relevant information.
  2. A finite number of external inputs: The signals that drive the FSM’s behavior.
  3. A finite number of external outputs: The signals produced by the FSM to interact with its environment.
  4. An explicit specification of all state transitions: Rules defining how the FSM moves from one state to another based on current state and inputs.
  5. An explicit specification of what determines each external output value: Rules defining how outputs are generated, which can depend on the current state (Moore FSM) or both current state and inputs (Mealy FSM).

Every FSM can be conceptually divided into three main parts:

  • Next State Logic (Combinational Circuit): Determines the next state of the FSM based on the current state and inputs.
  • State Register (Sequential Circuit): Stores the current state of the FSM. Implemented using flip-flops to ensure state changes occur synchronously with the clock.
  • Output Logic (Combinational Circuit): Generates the FSM’s outputs based on the current state (Moore) or current state and inputs (Mealy).

The clock (CLK) synchronizes the operation. At the beginning of each clock cycle, the next state calculated by the next state logic is latched into the state register, becoming the current state for the next cycle.

We can further break down the FSM block diagram:

  • Sequential Circuits - State Register(s):

    • Composed of flip-flops (typically D flip-flops).
    • Store the current state (S).
    • Provide the next state (S’) at the clock edge.

  • Combinational Circuits:

    • Next State Logic: Determines the next state based on the current state and inputs.
    • Output Logic: Generates the outputs based on the current state (Moore) or current state and inputs (Mealy).

To implement the state register, we require storage elements with specific properties:

  1. Data Storage at Clock Beginning: The state must be updated only at the beginning of each clock cycle, triggered by a clock edge.
  2. Data Availability Throughout Clock Cycle: The stored state must be stable and available for the entire duration of the clock cycle, allowing the combinational logic to operate correctly.

There are two types of FSMs:

Recall: The Problem with Latches: Transparency

Simple latches, like the Gated D Latch, are not suitable for state registers due to their transparency.

When the clock (or Write Enable - WE) is high, the output Q directly follows the input D. This transparency leads to issues in synchronous sequential circuits, where we need state changes to be strictly controlled by the clock edge.

We need a storage element that is not transparent, changing its output only at specific clock transitions.

Recall: The D Flip-Flop

The D Flip-Flop solves the transparency problem by using two latches in a master-slave configuration.

  • D Latch (First) - Master: Captures the input D when the clock is low.
  • D Latch (Second) - Slave: Latches the output of the first latch when the clock is high.

Behavior:

  • Clock Low: The first latch is transparent, propagating D. The second latch is disabled, holding its previous value (Q unchanged).
  • Clock High: The first latch is disabled. The second latch becomes transparent and latches the value that was present at the input of the first latch just before the clock transitioned high.
  • Rising Clock Edge (0 → 1): Q gets assigned the value of D that was sampled by the master latch.
  • All Other Times: Q remains unchanged.

The D Flip-Flop is an edge-triggered storage element, as state changes occur only at the clock edge. This behavior is ideal for building state registers in synchronous FSMs.

Symbol:

  • The triangle inside the flip-flop symbol indicates edge-triggering.

Behavior Summary:

  • Rising edge of clock (0 → 1): Q is assigned D.
  • All other times: Q remains unchanged.

Therefore, D Flip-Flops are used to implement state registers in synchronous sequential circuits and FSMs, ensuring synchronized state updates.

Register, based on D Flip-Flop

A register is built by combining multiple D flip-flops in parallel, each storing one bit of a multi-bit value.

  • Multiple Parallel D Flip-Flops: For an N-bit register, use N D flip-flops.
  • Shared Clock: All flip-flops are clocked by the same clock signal (CLK), ensuring simultaneous updates.
  • Condensed Symbol: For multi-bit registers, a condensed symbol is often used with a slash and a number indicating the bus width (e.g., D[3:0] and Q[3:0]).

This slide shows the internal structure of a 4-bit D flip-flop-based register, visually demonstrating the parallel arrangement of D flip-flops and the shared clock signal.

FSM Design Procedure

  1. Determine all possible states: Identify all relevant states your machine can be in based on the problem specification.
  2. Develop a state transition diagram:
    • Based on textual description of desired behavior.
    • Determine inputs and outputs for each state.
    • Figure out transitions between states based on inputs and current state.
  3. Approach:
    • Start by defining the reset state.
    • Add transitions and states iteratively.
    • Choose good state names for clarity.
    • Building an FSM is like programming, but fundamentally is not programming in the traditional software sense.
    • FSMs have a sequential “control-flow” with conditionals and “goto’s”.
    • If-then-else constructs are controlled by inputs.
    • Outputs are controlled by state or state and inputs.
    • In hardware, complex systems consist of many concurrent FSMs.

Hardware Description Languages and Verilog

This lecture note summarizes the key concepts discussed in Lecture 5b, focusing on Hardware Description Languages (HDLs) and the Verilog HDL in particular.

What We Will Cover Soon: LC-3 Processor & Datapath

We are building towards designing a complete computer system, like the LC-3 processor. HDLs are essential tools for describing and implementing such complex hardware.

Transistor Counts Are Growing

Transistor counts are rapidly increasing, especially in memory chips. Memory chips often have orders of magnitude more transistors than computation chips.

How to Deal with This Complexity? - Hardware Description Languages

To manage the design complexity of modern hardware, we use Hardware Description Languages (HDLs).

HDLs are essential for:

  • Describing (Specifying) Complex Designs: Handling the intricate details of billions of transistors.
  • Simulating Their Behavior: Verifying functional and timing correctness before fabrication.
  • Synthesizing (Automatically Designing) Portions of It: Automating the translation from high-level descriptions to gate-level implementations.

HDLs enable an error-free path to implementation by providing tools for specification, simulation, and synthesis. They are languages specifically designed to describe hardware, with Verilog and VHDL being two prominent examples. Learning one HDL makes it easier to learn others, as the fundamental concepts are similar.

Hardware Description Languages - Two Well-Known Languages

Two major HDLs are widely used in the industry:

  • Verilog:

    • Developed in 1984, standardized in 1995 (IEEE 1364).
    • More popular in the US.

  • VHDL (VHSIC Hardware Description Language):

    • Developed in 1981 by the US Department of Defense, standardized in 1987 (IEEE 1076).
    • More popular in Europe.

In this course, we will focus on Verilog.

Why Specialized Languages for Hardware?

HDLs are specialized for hardware description because:

  • Easy Description of Hardware Structures: HDLs provide built-in constructs to represent hardware elements like wires, gates, registers, flip-flops, clocks, and combinational/sequential logic elements.
  • Seamless Expression of Parallelism: HDLs naturally capture the inherent parallelism of hardware, where all hardware logic operates concurrently.

These features ease specification, simulation, and synthesis of complex digital circuits.

Key Design Principle: Hierarchical Design

Hierarchical design is a fundamental principle in hardware engineering.

  • Design a Hierarchy of Modules: Break down complex systems into smaller, manageable modules.
  • Primitive Gates: Start with predefined “primitive” gates (AND, OR, NOT, etc.).
  • Simple Modules: Build simple modules by instantiating these primitive gates (e.g., multiplexers, decoders).
  • Complex Modules: Construct complex modules by instantiating and interconnecting simpler modules.
  • Hierarchy Controls Complexity: Analogous to function/method abstraction in programming.

Top-Down Design Methodology

Top-down design starts with the high-level system specification and progressively decomposes it into smaller modules.

  1. Define Top-Level Module: Start with the overall system functionality.
  2. Identify Sub-Modules: Determine the necessary components (sub-modules) to build the top-level module.
  3. Subdivide Sub-Modules: Continue breaking down sub-modules until you reach “leaf cells”—basic, indivisible components like logic gates or library elements.

Bottom-Up Design Methodology

Bottom-up design starts with available basic building blocks and combines them to create larger modules.

  1. Identify Building Blocks (Leaf Cells): Determine the primitive components available (e.g., from a standard cell library).
  2. Build Bigger Modules: Combine leaf cells to create simple modules with specific functionalities.
  3. Build Top-Level Module: Assemble higher-level modules from these simpler modules until the complete system (top-level module) is built.

In practice, hardware designers often use a combination of both top-down and bottom-up approaches.

Defining a Module in Verilog

In Verilog, a module is the fundamental building block. To define a module, you need to specify:

  • Name of the module: A unique identifier for the module.
  • Directions of its ports: Specify whether each port is an input or output.
  • Names of its ports: Give names to each input and output port for referencing them within and outside the module.
  • Functionality of the module: Describe the behavior or structure of the module using Verilog constructs.

Implementing a Module in Verilog

Here’s an example of a Verilog module definition:

module example (a, b, c, y);
  input a;
  input b;
  input c;
  output y;
 
  // Circuit description goes here
 
endmodule
  • module example (a, b, c, y);: Declares a module named example with ports a, b, c, and y.
  • input a; input b; input c;: Declares a, b, and c as input ports.
  • output y;: Declares y as an output port.
  • // here comes the circuit description: Comment indicating where the module’s functionality is described.
  • endmodule: Marks the end of the module definition.

A Question of Style (and Consistency)

Verilog offers flexibility in syntax. Port name and direction declarations can be combined for a more compact style.

Both code snippets are functionally identical, but the second one combines the port direction and name in the module port list itself. Consistency in style is crucial for code readability and maintainability.

What If We Have Multi-bit Input/Output?

Verilog allows defining multi-bit inputs and outputs, known as buses.

  • [range_end : range_start]: Syntax to declare a bus. range_end is typically the Most Significant Bit (MSB), and range_start is the Least Significant Bit (LSB).
  • Number of bits: range_end - range_start + 1.

Example:

input [31:0] a;     // 32-bit input bus 'a' (a[31] is MSB, a[0] is LSB)
output [15:8] b1;   // 8-bit output bus 'b1' (bits 15 down to 8 of a larger bus)
output [7:0] b2;    // 8-bit output bus 'b2' (bits 7 down to 0 of a larger bus)
input c;          // 1-bit input 'c' (single signal)

It’s good practice to be consistent with bus ordering (e.g., always [31:0] or always [0:31]). [31:0] is generally preferred as it is more common and less array-like.

Manipulating Bits

Verilog provides mechanisms for manipulating bits within buses:

  • Bit Slicing: Extract a subset of bits from a bus.

    wire [15:0] longbus;
wire [7:0] shortbus;
assign shortbus = longbus[12:5]; // Assign bits 12 to 5 of longbus to shortbus

  • Concatenation: Combine multiple bits or buses into a larger bus using curly braces {}.

    assign y = {a[2], a[1], a[0], a[0]}; // Concatenate bits a[2], a[1], a[0], and a[0]

  • Duplication: Replicate bits or buses using the duplication operator {repetitions{value}}.

    assign x = {4{a[0]}}; // Replicate bit a[0] four times

Basic Syntax

  • Case Sensitive: Verilog is case-sensitive (e.g., SomeName and somename are different).
  • Names: Names cannot start with numbers (e.g., 2good is invalid).
  • Whitespaces: Whitespaces are ignored.
  • Comments:
    • Single-line comments: // comment
    • Multi-line comments: /* comment */

Two Main Styles of HDL Implementation

There are two primary styles for implementing hardware descriptions in HDLs like Verilog:

  1. Structural (Gate-Level):

    • Describes the circuit in terms of interconnected gates and modules.
    • Specifies how modules are connected.
    • Low level of abstraction, close to hardware implementation.

  2. Behavioral:

    • Describes the functionality of the circuit using high-level constructs like logical and mathematical operators, conditional statements (if-else, case).
    • Abstracts away gate-level details.
    • Allows for more concise and readable code, especially for complex logic.

Many practical designs use a combination of both styles, leveraging structural for performance-critical parts and behavioral for complex control logic.

Structural (Gate-Level) HDL

Structural HDL focuses on describing the hardware structure explicitly.

Behavioral HDL

Behavioral HDL describes the functionality of a circuit at a higher level of abstraction, without explicitly specifying gates.

Bitwise Operators in Behavioral Verilog

Behavioral Verilog supports bitwise operators that operate on individual bits of buses.

![image depecting Behavioral Verilog - Bitwise Operators Example on slide number 43]

module gates(input [3:0] a, b, output [3:0] y1, y2, y3, y4, y5);
 
  assign y1 = a & b;  // Bitwise AND
  assign y2 = a | b;  // Bitwise OR
  assign y3 = a ^ b;  // Bitwise XOR
  assign y4 = ~(a & b); // Bitwise NAND
  assign y5 = ~(a | b); // Bitwise NOR
 
endmodule
  • &, |, ^, ~&, ~|: Bitwise AND, OR, XOR, NAND, NOR operators.
  • These operators perform bit-by-bit operations on the input buses a and b, resulting in output buses y1 to y5.

Reduction Operators in Behavioral Verilog

Reduction operators perform operations across all bits of a bus, resulting in a single-bit output.

module and8(input [7:0] a, output y);
 
  assign y = &a; // Reduction AND
 
endmodule
  • &a: Reduction AND operator. It performs a bitwise AND operation across all bits of bus a, resulting in a 1-bit output y that is 1 only if all bits of a are 1.

Conditional Assignment in Behavioral Verilog

Conditional assignment allows assigning values based on conditions, similar to if-else statements.

module mux2(input [3:0] d0, d1, input s, output [3:0] y);
 
  assign y = s ? d1 : d0; // Conditional assignment (ternary operator)
 
endmodule
  • s ? d1 : d0: Ternary operator. If s is true (1), y is assigned d1; otherwise, y is assigned d0.

More Complex Conditional Assignments

Conditional assignments can be nested to create more complex logic, like a 4-to-1 multiplexer.

module mux4(input [3:0] d0, d1, d2, d3, input [1:0] s, output [3:0] y);
 
  assign y = s[1] ? (s[0] ? d3 : d2) : (s[0] ? d1 : d0); // Nested ternary operators
 
endmodule

This example uses nested ternary operators to select one of four inputs based on the 2-bit select input s.

Precedence of Operations in Verilog

Understanding operator precedence is crucial for writing correct Verilog code.

The table shows the precedence of Verilog operators, from highest to lowest. Operators at the top have higher precedence and are evaluated before operators lower in the table. Parentheses () can be used to override precedence and explicitly control the order of operations.

How to Express Numbers?

Verilog uses a specific format to express numbers, allowing you to specify the size, base, and value.

Format: N'Bxx

  • N (Number of bits): Specifies the bit-width of the number.
  • B (Base): Indicates the number base:
    • b (binary)
    • h (hexadecimal)
    • d (decimal)
    • o (octal)
  • xx (Number): The value of the number expressed in the specified base.

Example: 8'b0000_0001 - An 8-bit binary number with the value 1.

Verilog also supports X (invalid) and Z (floating) values and underscores _ for readability.

Reminder: Floating Signals (Z)

Floating signals (Hi-Z or Z) represent a disconnected or high-impedance state, not driven by any circuit.

![image depecting Verilog Floating Signals (Z) and Tri-State Buffer Example on slide number 54]

  • 4'bz: Represents a 4-bit bus with all bits in the Hi-Z state.

Tri-State Buffer Example:

module tristate_buffer(input [3:0] a, input en, output [3:0] y);
  assign y = en ? a : 4'bz; // Conditional assignment for Tri-State buffer
endmodule

If en (enable) is high, y is assigned the value of a. If en is low, y is assigned 4'bz, making the output float (Hi-Z).

Truth Table for AND Gate with Z and X

Verilog’s logic gates can handle Z and X inputs, with specific truth tables that define their behavior in these cases.

For example, in an AND gate:

  • If any input is 0, the output is 0, even if the other input is Z or X.
  • If one input is 1 and the other is Z or X, the output is X (unknown).
  • If both inputs are 1, the output is 1.

What Happens with HDL Code? - Synthesis & Simulation

Once you write HDL code, two primary processes are involved:

  • Synthesis (Hardware Synthesis):

    • Translates synthesizable HDL code into a gate-level netlist (gates and wires).
    • Performed by synthesis tools (e.g., Vivado).
    • Applies optimizations for area, performance, power, etc.
    • Cannot guarantee optimal solutions due to complexity.

  • Simulation:

    • Verifies the behavior of the described circuit without building actual hardware.
    • Performed by simulators (e.g., ModelSim, Vivado Simulator).
    • Works on both structural and behavioral HDL.
    • Essential for functional and timing verification.

A Note on Hardware Synthesis

It’s crucial to remember that HDL code describes hardware, not just a software program. Thinking in terms of hardware blocks (combinational logic, registers, FSMs) is essential for writing efficient and synthesizable HDL code.

Writing More Reusable Verilog Code

To make Verilog code more reusable and adaptable to different bit widths, we use parameterized modules.

Parameterized Modules

Parameterized modules allow you to define modules with parameters that can be customized when the module is instantiated.

module mux2
 #(parameter width = 8) // Parameter declaration with default value
 (input [width-1:0] d0, d1, input s, output [width-1:0] y);
 
  assign y = s ? d1 : d0;
 
endmodule
  • #(parameter width = 8): Declares a parameter named width with a default value of 8.
  • [width-1:0] d0, d1, output [width-1:0] y: Uses the width parameter to define the bit widths of the input and output buses.
Instantiating Parameterized Modules

When instantiating a parameterized module, you can either use the default parameter values or override them with specific values.

// Using default parameter width (8 bits)
mux2 i_mux (d0, d1, s, out); 
 
// Overriding parameter width to 12 bits
mux2 #(12) i_mux_b (d0, d1, s, out); 
 
// Verbose version with named parameter assignment
mux2 #(.width(12)) i_mux_b (.d0(d0), .d1(d1), .s(s), .out(out));

What About Timing?

Verilog allows you to specify timing relationships for simulation purposes, but these are not synthesizable and are only used for modeling delays.

`timescale 1ns/1ps  // Time units for simulation
 
module simple (input a, output z1, z2);
  assign #5 z1 = ~a;  // Inverted output after 5ns delay
  assign #9 z2 = a;   // Output after 9ns delay
endmodule
  • “timescale 1ns/1ps`: Specifies the time unit (1 nanosecond) and time precision (1 picosecond) for simulation.
  • #5, #9: Delay specifications in time units. They indicate that the assignments to z1 and z2 should be delayed by 5ns and 9ns, respectively, in simulation.

Good Practices

Adhering to good coding practices improves Verilog code readability, maintainability, and reduces errors.

  • Develop/Use a Consistent Naming Style: Follow a clear and consistent naming convention for signals, modules, and instances.
  • Use MSB to LSB Ordering for Buses: Prefer [31:0] over [0:31] for bus declarations for consistency.
  • Define One Module per File: Improves code organization and management.
  • Use a File Name That Matches Module Name: Makes it easier to locate module definitions.
  • Always Keep in Mind That Verilog Describes Hardware: Think in hardware terms when writing Verilog code for efficient and synthesizable designs.

Continue here: 06 Hardware Description Languages and Verilog II, Timing

Graph View