Automat Moore’a

Automat Moore’a – automat, którego wyjście jest funkcją wyłącznie stanu wewnętrznego (por. automat Mealy’ego).

Definicja formalnaEdytuj

Automat Moore’a jest to rodzaj deterministycznego automatu skończonego, reprezentowany przez uporządkowaną szóstkę:

 

gdzie:

  – zbiór sygnałów wejściowych,
  – zbiór stanów wewnętrznych,
  – zbiór sygnałów wyjściowych,
  – funkcja przejść,  
  – funkcja wyjść,   zależy tylko od stanu w którym znajduje się automat,
  – stan początkowy, należy do zbioru  

Automat Moore’a przedstawia się jako graf skierowany z wyróżnionym wierzchołkiem zwanym stanem początkowym. Podając sygnały na wejście automatu powodujemy zmianę bieżącego stanu i zwrócenie wartości przypisanej do nowego stanu.

Przykład automatu Moore’aEdytuj

Poniżej przedstawiony został przykładowy graf automatu Moore’a. Automat ten realizuje funkcję „zamka szyfrowego”, akceptującego w stanie   kombinację określaną przez wyrażenie regularne  

Synteza strukturalnaEdytuj

Synteza strukturalna automatu Moore’a ma na celu uzyskanie schematu logicznego. Składa się ona z pięciu etapów. Poszczególne etapy zostały przedstawione na przykładzie pokazanego wyżej grafu automatu.

Etap I – kodowanie stanów, sygnałów i wyjśćEdytuj

Przypisuje się tu stanom   sygnałom   i wyjściom   reprezentację w systemie binarnym:

  • sygnały wejściowe:  
  • wyjścia automatu:  
  • stany wewnętrzne:
stan Q1 Q2 Q3
q0 0 0 0
q1 0 0 1
q2 0 1 0
q3 0 1 1
q4 1 0 0
q5 1 0 1

Etap II – budowa tablicy wzbudzeń przerzutnikówEdytuj

W powyższym układzie użyte zostały trzy przerzutniki typu D (stany zapisane są na trzech bitach). Trzeba określić funkcje wejść przerzutników (D1, D2, D3) w zależności od przejść między stanami. Tabela przejść i wyjść automatu połączona z tabelą wzbudzeń przerzutników wygląda następująco:

z Q1 Q2 Q3 Q1(t+1) Q2(t+1) Q3(t+1) D1 D2 D3
0 0 0 0 0 1 1 0 1 1
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 1 1 1 0 1 1 0 1
0 1 0 0 0 1 1 0 1 1
0 1 0 1 1 0 1 1 0 1
1 0 0 0 0 0 1 0 0 1
1 0 0 1 0 1 0 0 1 0
1 0 1 0 1 0 1 1 0 1
1 0 1 1 1 0 0 1 0 0
1 1 0 0 0 0 1 0 0 1
1 1 0 1 1 0 1 1 0 1

Aby zrozumieć zasadę budowy tabeli, należy przynajmniej prześledzić tworzenie pierwszego wiersza: bit Q w następnym takcie zegara przechodzi w bit Q(t+1). W tablicy wzbudzeń sprawdza się wartość, którą należy podać na przerzutnik D. Przykładowo Q2=0 przechodzi w Q2(t+1)=1. Na wejście przerzutnika D2 trzeba więc podać 1.

Etap III – odczyt funkcji wzbudzeń przerzutnikówEdytuj

Ze zbudowanej w poprzednim etapie tablicy odczytuje się funkcje, które trzeba podać na wejścia odpowiednich przerzutników (przy określaniu funkcji nie bierze się już pod uwagę stanów  ):

  •  
  •  
  •  

Po minimalizacji metodą siatek Karnaugh:

  •  
  •  
  •  

Etap IV – określenie funkcji wyjścia yEdytuj

Wyjście   może się zmieniać w zależności od stanu   w którym automat się znajduje. W tym przypadku   dla automatu w stanie   Ponieważ funkcja wyjścia zwraca jeden bit, dlatego otrzymuje się jeden wzór bitu wyjścia automatu:   Wiadomo także, że automat nie posiada stanów dla   i   dlatego można wzór uprościć do  

Etap V – schemat logicznyEdytuj

Można teraz przystąpić do budowy schematu logicznego automatu Moore’a (została użyta optymalizacja zgodnie z twierdzeniem Boole’a, że suma logiczna argumentów jest równa negacji iloczynu logicznego zanegowanych argumentów, co pozwoliło na użycie wyłącznie bramek NAND):