Finite State Machine (FSM)

Een FSM is een controle structuur die zich in een eindig aantal toestanden kan bevinden. Onder invloed van ingangssignalen kan een FSM overgaan naar één bepaalde toestand één andere toestand. In elke toestand wordt er een waarde toegekend aan de uitgangssignalen. De toestand wordt opgeslagen in een toestandsregister.

Voorbeeld FSM

De meest eenvoudige FSM is een teller. Er is geen enkel ingangssignaal en de uitgang is de waarde van de toestand.

Een eerste ingangssignaal dat de telcyclus kan beïnvloeden, is een enable signaal.

Een ander ingangssignaal zou een up/down (UD) signaal kunnen zijn.

Werkelijke toestandsdiagrammen kunnen heel wat complexer zijn.

Aanpak van een digitaal ontwerp

  • Opdelen in functionele bouwblokken.

    • Onderscheid maken tussen datapad en controle.
    • Steeds dieper verfijnen tot basisblokken.
    • Duidelijk beschrijven wat elk bouwblok moet doen.
    • Duidelijk beschrijven welke signalen toekomen en vertrekken.

Na deze stap kan de entity van de verschillende bouwblokken geschreven worden. Wanneer het ontwerp met meerdere personen zal gemaakt worden, is dit het moment om de taken te verdelen.

  • Datapad opsplitsen in registers en combinatorische blokken.
  • Controle implementeren als FSM.

Het datapad

Entity van het datapad

Ingangssignalen zijn:

  • data ingangen (te verwerken)
  • controle signalen (bepalen wat er moet gebeuren met de ingangsdata)

Uitgangssignalen zijn:

  • data uitgangen
  • status signalen (zijn nodig voor het controleblok om beslissingen te nemen)

Uitwerken van het datapad

De bouwblokken van het datapad zijn vaak goed gekende blokken:

  • combinatorische blokken (optellers, decoders, multiplexers, comparators, …)
  • registers

Combinatorische blokken kunnen snel ontworpen worden op basis van Booleaanse vergelijkingen.

Het Controlepad

Entity van de controle

Ingangssignalen zijn:

  • status signalen (zijn nodig voor het controleblok om beslissingen te nemen)
  • controle ingangen (controle van een ander controleblok)
    • Het kloksignaal hoort hier ook bij.

Uitgangssignalen zijn:

  • controle signalen (bepalen wat er moet gebeuren met de ingangsdata)
  • controle uitgangen (controle voor een ander controleblok)

Controle a.d.h.v. een FSM

  • Teken het bouwblok met alle signalen.

  • Teken het toestandsdiagramma.

    • Elk van de verschillende stappen die ondernomen worden, vormen een verschillende toestand.
    • Indien de uitgang verschillend is, moet de toestand zeker verschillen.

  • Minimaliseer het aantal toestanden.

    • Twee toestanden kunnen samengenomen worden als hun uitgangssignalen gelijk zijn en als de volgende toestand gelijk is.

  • Controleer de volledigheid van het toestandsdiagramma.

    • Alle mogelijke combinaties van ingangssignalen zijn in principe mogelijk in elke toestand.
    • Voorzie wat er vanuit elke toestand moet gebeuren onder alle mogelijke combinaties.
    • Voorkom dubbele toewijzingen.

  • Bepaal de next state functie in functie van de huidige toestand en alle ingangssignalen (behalve de klok).

    • Het resultaat van de next state functie wordt in de volgende klokpuls opgeslagen in het state register. De next state functie is een combinatorisch bouwblok.

  • Bepaal de output functie in functie van de huidige toestand (en eventueel de ingangssignalen).

    • De output functie is al dan niet afhankelijk van de ingangssignalen. De output functie is een combinatorisch bouwblok.

Moore en Mealy FSM

Het is belangrijk een onderscheid te maken tussen een Moore en een Mealy FSM.

  • Een Moore FSM heeft een output functie die enkel afhangt van de toestand.
  • Een Mealy FSM heeft een output functie die afhangt van de toestand en de ingangen.
    • Mealy FSMs mogen niet rondgekoppeld worden.

Moore FSM

Mealy FSM

Toestandsencodering

Encoderen van de toestanden in een FSM:

  • willekeurig
    • bv. 000, 111, 011, 110, 101
  • minimale bitverandering (= Gray encodering)
    • bv. 00, 01, 11, 10
  • one-hot
    • bv. 0001, 0010, 0100, 1000

FSM in VHDL

Definieer de toestand als een opsommingstype en maak twee signalen aan van dit type. Deze signalen vormen de ingang en de uitgang van het state register.

type my_state is (rst_state, green_state, yellow_state, red_state);
signal next_state, state: my_state;

Ontwerp de next state functie, het state register en de output functie in drie verschillende processen. Voorzie alle mogelijkheden in de next state functie en de output functie, anders ontstaan er latches in deze bouwblokken.