Automat Moore’a

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Automat Moore'a)
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]

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

,
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]

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]

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 (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]

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]

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 y[edytuj]

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 logiczny[edytuj]

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