PL

Automaty stanów (Moore i Mealy)

Od grafu stanów do tablicy i równań przerzutników, na przykładzie detektora sekwencji

Projektowanie detektora sekwencji

Automat

Graf stanów

Każda strzałka ma wartość wejścia x, które ją wywołuje; w automacie Mealy'ego także wytwarzane wyjście („wejście/wyjście”). W automacie Moore'a wyjście jest wpisane w stan, a stany z podwójnym okręgiem dają z = 1.

Tablica stanów

Równania z przerzutnikami D

Symulacja

Wejście

Czym jest automat stanów

Automat skończony to układ sekwencyjny, który w każdej chwili znajduje się w jednym z ograniczonej liczby stanów. Stan streszcza wszystko, co istotne z przeszłości. Przy każdym zboczu zegara przechodzi do nowego stanu, zależnego od stanu bieżącego i wejść. Buduje się go z rejestru przerzutników, który przechowuje stan, oraz dwóch bloków logiki kombinacyjnej: jeden oblicza stan następny, drugi wyjścia.

To uporządkowany sposób projektowania każdej automatyki sekwencyjnej: sygnalizacji świetlnej, sterowania drzwiami automatycznymi, automatu sprzedającego, protokołu portu szeregowego czy etapów cyklu prania. W sterowniku PLC programuje się go tak samo w GRAFCET lub krokami w drabince, a w mikrokontrolerze instrukcją switch na zmiennej stanu.

Moore i Mealy

MooreMealy
Wyjście zależy odTylko stanuStanu i wejść
Gdzie rysuje się wyjścieW każdym stanieNa każdej strzałce, „wejście/wyjście”
Liczba stanówZwykle kilka więcejZwykle mniej
ReakcjaWyjście zmienia się przy następnym zboczu zegaraWyjście zmienia się, gdy tylko zmieni się wejście
WyjścieStabilne przez cały takt, bez szpilekMoże mieć szpilki, jeśli ma je wejście

Porównaj oba typy w symulatorze na tej samej sekwencji: detektor Mealy'ego daje z = 1 w tym samym takcie, w którym przychodzi ostatni bit, a detektor Moore'a takt później, po wejściu w stan końcowy. Jeśli wyjście automatu Mealy'ego trafia do innego układu synchronicznego, to opóźnienie i tak pojawia się przy jego zatrzaśnięciu.

Etapy projektu

  1. Graf stanów. Opisuje się zachowanie: jakie są stany, do którego przechodzi się przy każdym wejściu i jakie wyjście powstaje. W detektorze sekwencji każdy stan oznacza „odebrałem pierwsze k bitów sekwencji”.
  2. Tablica stanów. To samo co graf, w postaci tabeli: stan bieżący i wejście po lewej, stan następny i wyjście po prawej.
  3. Kodowanie. Każdemu stanowi przypisuje się kod binarny. Przy S stanach potrzeba ⌈log₂ S⌉ przerzutników. Kodowanie binarne wymaga najmniej przerzutników; kodowanie „one-hot” (jeden przerzutnik na stan) wymaga ich więcej, ale bardzo upraszcza równania i jest typowe w układach FPGA.
  4. Równania. Przy przerzutnikach D wejście D każdego z nich to wprost odpowiedni bit stanu następnego. Nieużywane kody są stanami obojętnymi i pomagają w minimalizacji na siatce Karnaugha. Przy przerzutnikach JK korzysta się z tablicy wzbudzeń zamiast przepisywać stan następny.
  5. Stany nieużywane. Trzeba sprawdzić, dokąd przejdzie automat, jeśli wystartuje z nieużywanego kodu przez zakłócenie lub po włączeniu zasilania, i przewidzieć reset, który sprowadzi go do stanu początkowego.

Nakładanie

Z nakładaniem ostatnie bity wykrytej sekwencji mogą być początkiem następnej: szukając 1011 w 1011011, wykrywa się ją dwa razy. Bez nakładania po każdym wykryciu automat zaczyna od nowa i znajduje tylko jedną. Aby zdecydować, do którego stanu wrócić, gdy przyjdzie niepasujący bit, szuka się najdłuższej części odebranego ciągu, która zgadza się z początkiem sekwencji; to ta sama idea, co w algorytmie wyszukiwania tekstu KMP.

Przykład: sygnalizacja świetlna

Sygnalizator dla samochodów z przyciskiem dla pieszych to automat Moore'a: światła zależą tylko od stanu. Licznik czasu daje sygnał „czas upłynął”, a naciśnięcie przycisku jest zapamiętywane do chwili obsłużenia.

StanŚwiatła dla samochodówŚwiatła dla pieszychPrzechodzi dalej, gdy
S0 ZieloneZieloneCzerwonePieszy nacisnął przycisk i minął minimalny czas zielonego
S1 ŻółteŻółteCzerwoneMinął czas żółtego
S2 CzerwoneCzerwoneZieloneMinął czas przejścia pieszych
S3 EwakuacjaCzerwoneZielone migająceMinął czas ewakuacji; powrót do S0

Cztery stany koduje się dwoma przerzutnikami. Wyjścia są funkcjami Q1 i Q0, np. zielone dla samochodów = Q1'·Q0', a czerwone dla pieszych = Q1'.

Zobacz też: przerzutniki, siatka Karnaugha, symulator bramek logicznych i symulator drabinkowy.