Automat Moore'a

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Definicja formalna[edytuj | edytuj kod]

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,
Moore machine-diagram.svg

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ść, y(t) = Ψ[q(t)], zależy tylko od stanu w którym znajduje się automat,
  • q0 – stan początkowy, 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]

Przypisuje się 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ż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ów[edytuj | edytuj kod]

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 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ć w zależności 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 otrzymuje się 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ż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): Automat moore'a uklad.png