Automat Moore'a

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Definicja intuicyjna:

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

Schemat ideowy automatu Moore'a

Automat Moore'a – jest to rodzaj deterministycznego automatu skończonego, reprezentowany przez uporządkowaną szóstkę 
\langle Z,Q,Y,\Phi,\Psi,q_0\rangle
, gdzie:

  • Z = {z1, z2, ... ,zn} – zbiór sygnałów wejściowych
  • Q = {q1, q2, ... ,qn} – zbiór stanów wewnętrznych
  • Y = {y1, y2, ... ,yn) – zbiór sygnałów wyjściowych
  • Φ – funkcja przejść, q(t+1) = Φ[q(t), z(t)]
  • Ψ – funkcja wyjść, zależy tylko od stanu w którym znajduje się automat, y(t) = Ψ[q(t)]
  • q0 – stan początkowy, q0 należy do zbioru Q

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'a[edytuj | edytuj kod]

Poniżej przedstawiony został przykładowy graf automatu Moore'a. Automat ten realizuje funkcję "zamka szyfrowego", akceptującego w stanie q4 kombinację określaną przez wyrażenie regularne ((z1z2z1 + z2z1)* z1z2)*.

Graf automatu moore.svg

Synteza strukturalna[edytuj | edytuj kod]

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 | edytuj kod]

Przypisujemy tu stanom (q1, q2, ... ,qn), sygnałom (z1, z2, ... ,zn) i wyjściom (y1, y2, ... ,yn) reprezentację w systemie binarnym:

  • Sygnały wejściowe: z1 → 0; z2 → 1
  • Wyjścia automatu: y1→ 0; y2 → 1
  • 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ów[edytuj | edytuj kod]

W powyższym układzie użyjemy trzech przerzutników D (stany zapisane są na trzech bitach). Musimy 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 prześledźmy tworzenie pierwszego wiersza: bit Q w następnym takcie zegara przechodzi w bit Q(t+1). W tabeli wzbudzeń sprawdzamy wartość, którą należy podać na przerzutnik D. Przykładowo Q2=0 przechodzi w Q2(t+1)=1. Na wejście przerzutnika D2 musimy więc podać 1.

Etap III – odczyt funkcji wzbudzeń przerzutników[edytuj | edytuj kod]

Ze zbudowanej w poprzednim etapie tabeli odczytujemy funkcje, które musimy podać na wejścia odpowiednich przerzutników (przy określaniu funkcji nie bierzemy już pod uwagę stanów q(t+1)).

  • D_1=\overline{z}\overline{Q_1}Q_2Q_3+\overline{z}Q_1\overline{Q_2}Q_3+z\overline{Q_1}Q_2\overline{Q_3}+z\overline{Q_1}Q_2Q_3+zQ_1\overline{Q_2}Q_3
  • D_2=\overline{z}\overline{Q_1}\overline{Q_2}\overline{Q_3}+\overline{z}Q_1\overline{Q_2}\overline{Q_3}+z\overline{Q_1}\overline{Q_2}Q_3
  • D_3=\overline{z}\overline{Q_1}\overline{Q_2}\overline{Q_3}+\overline{z}\overline{Q_1}Q_2Q_3+\overline{z}Q_1\overline{Q_2}\overline{Q_3}+\overline{z}Q_1\overline{Q_2}Q_3+z\overline{Q_1}\overline{Q_2}\overline{Q_3}+z\overline{Q_1}Q_2\overline{Q_3}+zQ_1\overline{Q_2}\overline{Q_3}+zQ_1\overline{Q_2}Q_3

Po minimalizacji metodą siatek Karnaugh:

  • D_1={zQ}_{2}+{Q}_{2}{Q}_{3}+{Q}_{1}{Q}_{3}
  • D_2=\overline{z}\overline{Q_2}\overline{Q_3}+z\overline{Q_1}\overline{Q_2}Q_3
  • D_3=Q_1+z\overline{Q_3}+\overline{Q_2}\overline{Q_3}+\overline{z}Q_2Q_3

Etap IV – określenie funkcji wyjścia y[edytuj | edytuj kod]

Wyjście Y może się zmieniać od stanu Q, w którym automat się znajduje. W tym przypadku Y=1 dla automatu w stanie Q=100. Ponieważ funkcja wyjścia zwraca jeden bit, dlatego otrzymamy jeden wzór bitu wyjścia automatu: y=Q_1\overline{Q_2}\overline{Q_3}. Wiadomo także, że automat nie posiada stanów dla Q_1=1 i Q_2=1, dlatego można wzór uprościć do y=Q_1\overline{Q_3}.

Etap V – schemat logiczny[edytuj | edytuj kod]

Możemy już przystąpić do budowy schematu logicznego automatu Moore'a:

Automat moore'a uklad.png