Algorithmic State Machines

Review: Finite State Machines (FSMs)

State machines are defined as a set of states, transitions, and outputs. You can use them to model the behavior of systems with finite, discrete states. They are pretty much the bread and butter of hardware design, but can also be used in software (e.g. state machines pattern).

Mealy vs. Moore

• Mealy: Outputs depend on both the current state and the input. This means that the output can change as soon as the input changes, even without a state transition.
• Moore: Outputs depend only on the current state. This means that the output can only change when the state changes.

Mathematical Definition

More concisely, a finite state machine is defined as a 5-tuple:

$$ FSM = (S, I, O, T, s_0) $$

Where:

• $S$ is the set of states
• $I$ is the set of inputs
• $O$ is the set of outputs
• $T$ is the transition function, which maps a state and an input to a new state
• $s_0$ is the initial state

So what is an Algorithmic State Machine?

An Algorithmic State Machine (ASM) is basically an extended framework for designing and implementing synchronous (clocked) digital systems using finite state machines. At the highest level, you divide the design two parts:

1. Control: The part that manages the state transitions and controls the flow of the algorithm.
   • This is typically implemented using a finite state machine (FSM).
   • The control unit generates control signals based on the current state and inputs.
   • It determines which operations to perform and when to perform them.
2. Data Path: The part that performs the actual computations and data manipulations.
   • This is typically implemented using combinational and sequential logic.
   • The data path consists of registers, multiplexers, arithmetic units, and other components that perform the required operations.
   • It processes the data based on the signals generated by the control unit.

For my more software-brained readers, it's sort of like the data path is the model/view of a web application, while the control unit is the frontend controller (please don't read too far into this analogy...).

Register Transfer Level (RTL) Design

• Sequential algorithms:
  • Variables used as symbolic memory locations
  • Sequential execution dictates the ordering of operations
• Hardware implementation:
  • Registers store intermediate data (variables)
  • Datapath implements all necessary register operations (computations attached to register inputs)
  • A control path FSM specifies the ordering of register operations
• This design scheme sometimes referred to as register-transfer level (RTL) design

$$ r_{\text{dest}} \leftarrow f(r_{\text{src1}}, r_{\text{src2}}, \ldots, r_{\text{srcn}}) $$

Where:

• $r_{i}$ is a register
• $f$ is some combinational function

For example:

• $r_{1} \leftarrow r_{2} + r_{3}$ means that the value in register 2 is added to the value in register 3, and the result is stored in register 1.
• $r_{1} \leftarrow 0$ means clear register 1 (set it to 0).
• $y \leftarrow a * a$ means that the value in register $a$ is multiplied by itself, and the result is stored in register $y$.

Timing Interpretation

• After the clock edge, the outputs of all registers update simultaneously and become available
• During the rest of the clock cycle, these outputs propagate through the combinational logic that performs $f$
• At the next clock edge, the result is stored into $r_{\text{dest}}$ and the process repeats

ASM Diagram (ASMD)

An ASM diagram is a graphical representation of an algorithmic state machine. It consists of:

• State boxes: Represent the different states of the machine.
  • Rectangular boxes, containing the state name and the output signals (Moore type).
• Transition arrows: Represent the transitions between states.
• Decision boxes: Represent the conditions that determine state transitions.
  • Diamond-shaped boxes, containing a condition with a $0$ and $1$ transition.
• Conditional output box: Represent the outputs that depend on the current state and the input conditions.
  • Box with rounded corners, containing the output signals (Mealy type).
  • Must be output of decision box.
• ASM Block: A rectangular box that groups together a set of states and transitions.
  • A single state box grouped with all decision and conditional output boxes that are part of the state.
  • NO overlap between ASM blocks, and NO internal feedback loops (just make the ASM block smaller so the feedback loop goes outside the box).
  • All changes happen within the ASM block in a single clock cycle, particularly at state exit rather than entrance (important!).

ASMD Design Procedure

Given some sequential algorithm:

1. Identify datapath components and operations
   • Registers, ALUs, multiplexers, etc.
   • Operations: addition, subtraction, multiplication, etc.
2. Identify states and signals that cause state transitions
   • external inputs, status signals, etc. based on sequence of operations
3. Name the control signals
   • Outputs of the control unit and inputs to the datapath

SystemVerilog Controller Module

module controller(
    input logic clk, reset, // (input signals, e.g. start)
    // input logic (status signals, e.g. x_le_y, i_eq_z)
    // output logic {status indicators, e.g. ready, done}
    // output logic {control signals, e.g. load, incr, set}
);

  // define state names (enum) and variables
  /*
  enum logic [2:0] {S0, S1, S2, S3} ps, ns;
  */

  // constoller logic with synchronous reset
  /*
  always_ff @(posedge clk)
    if (reset) ps <= S0;
    else ps <= ns;
  */

  // next state logic
  /*
  always_comb
    case (ps)
      S0:       ns = ...
      S1:       ns = ...
      S2:       ns = ...
      S3:       ns = ...
      default:  ns = ...
    endcase
  */

  // output assignment
  /*
  assign ctrl_sig_1 = (ps == Si) & (...);
  assign ctrl_sig_2 = (ps == Sj) & (...);
  ...
  */

endmodule // controller

SystemVerilog Datapath Module

module datapath #(parameter W=4)(
    input logic clk,
    // input logic (input data, e.g. [W-1:0] x)
    // output logic (output data, e.g. y)
    // input logic (control signals, e.g. load, incr, set)
    // output logic (status signals, e.g. x_le_y, i_eq_z)
);
  // internal datapath signals and regs
  /*
  logic [W-1:0] x;

  // datapath logic
  /*
  always_ff @(posedge clk) begin
    if (load) x <= ...;
    else if (incr) x <= x + 1;
    else if (set) x <= ...;
  end
  */

  // outpt assignments
  /*
  assign y = ...;
  assign x_le_y = (x <= y);
  assign i_eq_z = (i == z);
  */

endmodule // datapath