From More to Moore: Breakthrough FPGA State Machines with Category Theory

In digital design, engineers have traditionally utilized VHDL and Verilog to construct state machines, reminiscent of the simple tools used by early artisans. Yet, as technology advances, there is a call for a shift towards a more mathematical paradigm: Moore machines. Traditional state machines, defined by binary constants and conditional statements, often fail to capture the increasingly sophisticated nuances of everyday devices such as traffic lights, elevators, vending machines, washing machines, microwaves, digital watches, automatic doors, ATMs, etc. Moore machines refine this concept with mathematical constructs, sets, functions, and tuples, facilitating a formal definition characterized by a sextuple (S,S0,Σ,Λ,T,G).

The Quirky Quirks of Conventional State Machines

Regrettably, as my patient readers have come to expect, I must once again highlight the frequent lack of elegance and solid engineering in much of today's tech landscape. An industry where naivety or, worse yet, overengineering, often become the norm—this is the realm of the so-called PIT (Private IT industry).

The field of FPGA design is no exception. Today, we bring to light another example of naivety and ad-hoc solutions that unravel into a tangle of spaghetti code as the demands of use cases begin to scale. The usual implementation of state machines in FPGA technology often resembles a game of digital Jenga: engineers stacking logic blocks upon logic blocks, hoping against hope that their precarious tower won't topple when the clock ticks. Let's take a humorously serious glance at the traditional methods most FPGA engineers employ and ponder why these might be due for a mathematical metamorphosis.

The Predominant Naive Approach to State Machines in the FPGA Industry:

We dive straight into action without further delay, considering the classic Turnstile model as our elementary example.

In Verilog, we encounter a delightful little module that, much like a toddler's initial steps, hesitantly oscillates between states with the guileless charm of a novice's endeavor. It possesses a quaint allure, truly:

-- Naive State Machine Implementation in Verilog

module Turnstile_Example (
  input i_Reset,
  input i_Clk,
  input i_Coin,
  input i_Push,
  output o_Locked
);
  localparam LOCKED = 1'b0;
  localparam UNLOCKED = 1'b1;
  reg r_Curr_State, r_Next_State;
  // Current state register
  always @(posedge i_Clk or posedge i_Reset) begin
    if (i_Reset)
      r_Curr_State <= LOCKED; // Oh look, it's trying to be secure!
    else
      r_Curr_State <= r_Next_State; // A wild guess appears!
  end
  // Next state determination
  always @(r_Curr_State or i_Coin or i_Push) begin
    r_Next_State <= r_Curr_State; // I guess we're staying put?
    case (r_Curr_State)
      LOCKED:
        if (i_Coin)
          r_Next_State <= UNLOCKED; // Cha-ching! Freedom!
      UNLOCKED:
        if (i_Push)
          r_Next_State <= LOCKED; // Pushed back to square one.
    endcase
  end
  assign o_Locked = (r_Curr_State == LOCKED); // It's a lock!
endmodule
        

And then there's VHDL's take on the Turnstile_Example, with its delightful attempt to be both sophisticated and straightforward. It's as though the language itself is trying to wear a top hat while riding a unicycle:

-- same naivety this time with the more serious VHDL :)
library ieee;
use ieee.std_logic_1164.all;
entity Turnstile_Example is
  port (
    i_Reset  : in std_logic;
    i_Clk    : in std_logic;
    i_Coin   : in std_logic;
    i_Push   : in std_logic;
    o_Locked : out std_logic
  );
end entity Turnstile_Example;

architecture RTL of Turnstile_Example is
  type t_State is (LOCKED, UNLOCKED);
  signal r_Curr_State, r_Next_State : t_State;
begin
  -- Current state register
  process (i_Clk, i_Reset) is
  begin
    if i_Reset = '1' then
      r_Curr_State <= LOCKED; -- Reset with flair!
    elsif rising_edge(i_Clk) then
      r_Curr_State <= r_Next_State; -- Decisions, decisions.
    end if;
  end process;
  -- Next state determination
  process (r_Curr_State, i_Coin, i_Push)
  begin
    r_Next_State <= r_Curr_State; -- Stability or stagnation?
    case r_Curr_State is
      when LOCKED =>
        if i_Coin = '1' then
          r_Next_State <= UNLOCKED; -- Pay to play.
        end if;
      when UNLOCKED =>
        if i_Push = '1' then
          r_Next_State <= LOCKED; -- Pushing boundaries, are we?
        end if;
    end case;
  end process;
  o_Locked <= '1' when r_Curr_State = LOCKED else '0'; -- Binary simplicity.
end RTL;
        

These code examples, though workable, are simplistic and predate the complexities of real-world systems, assuming that simple solutions can resolve the complex challenges of synthesis and timing closure.

But fear not, for the Moore machine model, with its mathematical might, is here to save the day. It strides in, a knight in algebraic armor, ready to bring order to chaos with a 6-tuple that would make Pythagoras himself nod in approval :)

FIRST, TRY TO IMPROVE THE NAIVE spaghetti-code:

Here it starts the funny part of the article, explaining how to transform that ordinary state machine into a golden state machine capable of fitting into any use case, regardless of its complexity, thanks to the miraculous assistance of Category Theory. In this formalized mathematical framework, we abstract the concepts of states, inputs, and transitions into functions and types that reflect the structure of a Moore machine

But, what the heck is a Moore Machine ?

A Moore machine is a 6-tuple (S,S0,Σ,Λ,T,G), encompassing a finite set of states, an initial state, input and output alphabets, and functions that dictate state transitions and outputs. This model excels in its mathematical precision, allowing for an abstract yet precise definition of a state machine's behavior.

The Moore machine formalization challenges the typical hardware description by introducing a level of abstraction that captures the essence of the state machine's operation in a type-theoretic and categorical framework. It promotes a more functional design perspective, focusing on the mappings between sets — the very nature of computation and state transitions.

In applying this method to our VHDL and Verilog snippets, we unveil the limitations of the traditional approach. Where the hardware description languages use enumerated types and case statements to describe state transitions, the Moore machine employs a transition function T:S×Σ→S that offers a clear and concise mathematical representation. It replaces the often verbose and error-prone procedural blocks with a pure function that is easier to reason about and verify.

Moreover, the output function G:S→Λ of the Moore machine delineates a clear separation between the state of the system and the output it produces. This separation is not inherently apparent in the traditional VHDL snippets, where the output logic is often intermingled with the state transition logic, potentially leading to less maintainable and verifiable designs.

In conclusion, by using the mathematical formalism of Moore machines, we can refine our understanding and implementation of state machines in digital designs.

And now, enough with theory and hands-on with the code and how we can attempt to refactor the Verilog and VHDL code to align it with the mathematical definition of a Moore machine:

1. State Type Definition:

- Instead of using simple localparam or type declarations for states, define a new type that encapsulates all possible states of the machine.

2. Initial State:

- Define a constant or signal that represents the initial state (S0) of the machine in a way that it's clear it's an element of the defined state set S.

3. Input Alphabet:

- Abstract the inputs ( i_Coin, i_Push) into a type that represents the input alphabet Σ.

4. Output Alphabet:

- Abstract the output (o_Locked) into a type that represents the output alphabet Λ.

5. Transition Function:

- Refactor the transition logic into a formal function that maps a state and an input from the input alphabet to the next state.

6. Output Function:

- Define an output function that maps each state to an element of the output alphabet.

Here is an example of how the VHDL code might be refactored:

library ieee;

use ieee.std_logic_1164.all;

entity Turnstile_Example is

  port (

    i_Reset  : in std_logic;

    i_Clk    : in std_logic;

    i_Coin   : in std_logic;

    i_Push   : in std_logic;

    o_Locked : out std_logic);

end entity Turnstile_Example;

architecture RTL of Turnstile_Example is

  -- Define the state type as a set of states S

  type t_State is (LOCKED, UNLOCKED);

  -- Define the initial state S0

  constant c_Initial_State : t_State := LOCKED;

  -- Define the input alphabet Σ

  type t_Input_Alphabet is (COIN, PUSH, NONE);

  -- Define the output alphabet Λ

  type t_Output_Alphabet is ('0', '1');

  -- Declare signals for the current and next states

  signal r_Curr_State, r_Next_State : t_State;

  -- Transition function T : S × Σ → S

  function transition(s : t_State; input : t_Input_Alphabet) return t_State is

  begin

    -- Transition logic here

  end function;

  -- Output function G : S → Λ

  function output(s : t_State) return t_Output_Alphabet is

  begin

    -- Output logic here

  end function;

begin

  -- State register process

  process(i_Clk, i_Reset) is

  begin

    if i_Reset = '1' then

      r_Curr_State <= c_Initial_State;

    elsif rising_edge(i_Clk) then

      -- Use the transition function

      r_Curr_State <= transition(r_Curr_State, ...);

    end if;

  end process;

  -- Output assignment

  o_Locked <= output(r_Curr_State);

end RTL;        

This pseudocode aligns the VHDL representation closer to the mathematical definition of a Moore machine, with explicitly defined types and functions for the state transitions and outputs. The actual implementation of the transition and output functions would need to follow the logic specific to the turnstile state machine.

A PAUSE TO BRIEFLY DIVE INTO THE CATEGORY THEORY BEHIND THE REFACTORING

As we have already seen with the naive approach to state machines commonly employed by most FPGA-related companies, this state machine model is merely a handful of signals and processes, reminiscent of the rudimentary tools used by early artisans. Consider the turnstile at a subway station, a rite of passage for every commuter and every novice state machine enthusiast. In the VHDL and Verilog documentation, its essence is captured using binary constants and conditional statements—a method that is effective but falls short in capturing the increasingly sophisticated nuances of daily-used devices. But what if we could capture not just the mechanics but also the very essence of the turnstile's logic or that of any other machine?

For that we are using the higher plane of abstraction devised by Moore and described not by mere signals and transitions, but by sets, functions, and tuples that sing the songs of states and inputs in harmony. Here, the turnstile is not a mere collection of gates and triggers but a mathematical entity defined by the sextuple (S,S0,Σ,Λ,T,G) a beacon of formalism in the fog of pragmatism.

In this enlightened model, the initial state S0 , the input alphabet Σ , and the set of states S are not just notations but the foundation of a system that can be prodded, poked, and proven with the rigor of mathematical theorems. The transition function T and the output function G provide a lexicon for computation that is as precise as a Swiss watch, where every tick is a function call and every tock a well-defined result.

The parallels with folds in functional programming are unmistakable. The foldl function, a staple in the functional programmer's pantry, mirrors the transition function T of our Moore machine. It takes an accumulator and an input, and it weaves a new accumulator, step by deterministic step. The extract function, often the identity in simpler folds, in the Moore machine becomes a lens through which we observe the output Λ from the current state.

As we translate these concepts into code, we no longer speak in the imperative but in the declarative. The VHDL and Verilog state machines, with their if and case constructs, give way to data types and functions that express the transition and output logic with mathematical grace. Let's briefly utilize Haskell as the formal language for defining the constructors (data and type) of such a Moore machine:

data Moore s a b = Moore s (s -> b) (s -> a -> s)        

Here, s is the state, a is the input, and b is the output. Our humble turnstile is now a Moore machine, where the outputs are as predictable as the orbits of the planets, and the transitions as logical as the theorems of Euclid

data TurnstileState = Locked | Unlocked
data TurnstileInput = Coin | Push
data TurnstileOutput = Alarm | ThankYou

transitionFn :: TurnstileState -> TurnstileInput -> TurnstileState
transitionFn Locked Coin = Unlocked
transitionFn Unlocked Push = Locked
transitionFn state _ = state
        

Same with any other devices, for instance, an OVEN:

transitionFn :: OvenState -> InputSignal -> OvenState

transitionFn Off BakePressed = Bake

transitionFn Bake OffPressed = Off

outputFn :: OvenState -> Heat

outputFn Off = HeatOff

outputFn Bake = HeatOn        

In this world, every state machine is a Moore machine, every fold a step in its computation, and every engineer a mathematician at heart. By embracing this formalism, we transcend the limitations of the past, crafting designs that are not only efficient and effective but also elegant and exact.

BACK TO OUR STATE MACHINE, now with an OVEN for baking a cake, for Moore :)

Translating the concepts of a Moore machine from Haskell into VHDL requires us to map the functional constructs into the imperative world of VHDL. Here’s how the Haskell data type and functions can be represented in VHDL:

Just remember how we had coded the Moore data type in Haskell:

data Moore s a b = Moore s (s -> b) (s -> a -> s)        

In VHDL, we’ll need to define equivalent constructs for the state (s), input (a), and output (b). We’ll use enum types for the state and input, and the output will be a signal.

First, we’ll define the states and input signals as enumerated types:

-- again from here on with VHDL only..

type State_Type is (Off, Bake, Idling);

type Input_Type is (BakePressed, OffPressed, TooHot, TooCold);        

Next, we’ll define the signals to hold the current state, next state, and output:

signal Current_State: State_Type;

signal Next_State: State_Type;

signal Output_Signal: Heat_Type; -- Assuming Heat_Type is defined elsewhere        

The transition function in Haskell, which takes a state and an input to produce a new state, would be mapped to a process in VHDL that updates the Next_State based on Current_State and the input.

process(Current_State, Input_Signal)

begin

    case Current_State is

        when Off =>

            if Input_Signal = BakePressed then

                Next_State <= Bake;

            else

                Next_State <= Current_State;

            end if;

        when Bake =>

            if Input_Signal = OffPressed then

                Next_State <= Off;

            elsif Input_Signal = TooHot then

                Next_State <= Idling;

            else

                Next_State <= Current_State;

            end if;

        when Idling =>

            if Input_Signal = TooCold then

                Next_State <= Bake;

            elsif Input_Signal = OffPressed then

                Next_State <= Off;

            else

                Next_State <= Current_State;

            end if;

    end case;

end process;        

For the output function in Haskell (`outputFn`), we can create a concurrent statement in VHDL that assigns the output based on the current state

with Current_State select

    Output_Signal <=

        HeatOff when Off,

        HeatOn when Bake,

        HeatOff when Idling;        

Finally, we would have the VHDL architecture that ties together the state updating logic and the output logic:

architecture Behavioral of OvenControl is

    signal Current_State, Next_State: State_Type;

    signal Output_Signal: Heat_Type; -- Defined as an enumeration type elsewhere

begin

    -- State transition logic

    State_Transition: process(Current_State, Input_Signal)

    begin

        -- Transition logic as shown above

    end process State_Transition;

    -- Output logic

    Output_Logic: process(Current_State)

    begin

        -- Output logic as shown above

    end process Output_Logic;

    -- Update the current state at every rising edge of the clock

    -- and reset logic

    State_Register: process(Clock, Reset)

    begin

        if Reset = '1' then

            Current_State <= Off; -- Assuming Off is the initial state

        elsif rising_edge(Clock) then

            Current_State <= Next_State;

        end if;

    end process State_Register;

end Behavioral        

This VHDL code provides a structural framework equivalent to the Moore machine in Haskell, maintaining the formal properties of state machines while working within the imperative paradigm of VHDL.

CONCLUSIONS:

And that is all folks, just the beginning of a new journey from the rudimentary flip-flops to the sophistication of Moore machines in FPGA development, that is not just a leap in technology—it's a transformative shift in the fabric of our daily lives. The devices that surround us, from the phone in your pocket to the car that drives you home, are becoming not just smarter, but also more integrated into our existence. They are becoming extensions of our will, interpreters of our desires, and guardians of our safety.

The breakthrough in state machine design that we've pioneered is far more than an academic exercise—it's the cornerstone of this new reality. By levering the power of category theory and abstract algebra, we've given engineers the tools to design systems with an unprecedented level of precision and predictability. Our method isn't merely a different way to code—it's a different way to think, to design, to innovate.

Consider the turnstile, a simple gatekeeper, transformed by our approach into a model of efficiency and reliability. Now extrapolate that to autonomous vehicles, whose intricate state machines must navigate the chaos of the roads with unerring accuracy. Picture smart grids that balance the whims of energy supply and demand with Moore-like prescience. Imagine healthcare devices that monitor and adjust to a patient's condition with the subtlety and nuance of a human caregiver.

Our breakthrough reaches beyond the confines of FPGA boards and design software; it influences the very way we interact with technology. Devices are no longer just tools; they are partners, collaborators, and protectors. In a world that demands smarter, safer, and more responsive technology, the Moore method for FPGA state machine design is not just an innovation—it is a necessity.

Lets continue to push the boundaries of what's possible, armed with the certainty that the systems we create are built on the most solid mathematical foundations. The impact of our work today will echo through the smart devices of tomorrow, shaping a future where technology and humanity evolve in concert.

For in the alignment of mathematics, engineering, and imagination lies the key to unlocking a world where technology fulfills its greatest promise: to serve humanity with Moore intelligence, Moore empathy, and Moore grace.

#FutureOfTechnology #MooreMachines #FPGARevolution #DigitalTransformation #SmartDevices #EngineeringExcellence