Finite State Machine (FSM)

Bij het ontwerp van een digitaal systeem wordt typisch een opdeling gemaakt in datapad en controlepad. Het datapad is het deel van het design dat (zoals de naam doet vermoeden) de data afhandelt. Het controlepad is het deel van het design dat (weeral, zoals de naam doet vermoeden) controle signalen genereert en absorbeerd.

Wanneer deze opsplitsing gemaakt zou worden voor de RISC-V implementatie, zijn enkele componenten voor de hand liggend:

De geheugens worden typisch ook onder het datapad thuisgebracht: Instructie memory en Data memory.

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)

Een FSM is hét tekstboek-voorbeeld van controle structuur. De FSM kan zich in een eindig aantal toestanden kan bevinden. Onder invloed van ingangssignalen kan een FSM overgaan van één bepaalde toestand naar één andere toestand. De toestand wordt opgeslagen in een toestandsregister.

In elke toestand wordt er een specifieke waarde toegekend aan ELK uitgangssignaal.

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.

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.