Tekst źródłowy strony Automat Moore’a

{{Dopracować|źródła=2013-09}}
'''Automat Moore’a''' – automat, którego wyjście jest funkcją wyłącznie stanu wewnętrznego (por. [[automat Mealy’ego]]).

== Definicja formalna ==
Automat Moore’a jest to rodzaj [[Deterministyczny automat skończony|deterministycznego automatu skończonego]], reprezentowany przez uporządkowaną szóstkę:
:: <math>\langle Z,Q,Y,\Phi,\Psi,q_0\rangle,</math>
[[Plik:Moore machine-diagram.svg|center|200x200px]]

gdzie:
: <math>Z = \{z_1, z_2, \dots, z_n\}</math> – zbiór sygnałów wejściowych,
: <math>Q = \{q_1, q_2, \dots, q_n\}</math> – zbiór stanów wewnętrznych,
: <math>Y = \{y_1, y_2, \dots, y_n\}</math> – zbiór sygnałów wyjściowych,
: <math>\Phi</math> – funkcja przejść, <math>q(t+1) = \Phi[q(t), z(t)],</math>
: <math>\Psi</math> – funkcja wyjść, <math>y(t) = \Psi[q(t)],</math> zależy tylko od stanu w którym znajduje się automat,
: <math>q_0</math> – stan początkowy, należy do zbioru <math>Q.</math>

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 stanu sprzed zmiany.

== Przykład automatu Moore’a ==
Poniżej przedstawiony został przykładowy graf automatu Moore’a. Automat ten realizuje funkcję „zamka szyfrowego”, akceptującego w stanie <math>q_4</math> kombinację określaną przez [[wyrażenie regularne]] <math>((z_2 z_2 z_1 + z_2 z_1)^* z_1 z_2)^*.</math>
[[Plik:Graf automatu moore.svg|center|450px]]

== Synteza strukturalna ==
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ść ===
Przypisuje się tu stanom <math>(q_1, q_2, \dots, q_n),</math> sygnałom <math>(z_1, z_2, \dots, z_n)</math> i wyjściom <math>(y_1, y_2, \dots, y_n)</math> reprezentację w systemie binarnym:
* sygnały wejściowe: <math>z_1 \to 0, z_2 \to 1;</math>
* wyjścia automatu: <math>y_1 \to 0, y_2 \to 1;</math>
* stany wewnętrzne:

{| class="wikitable" style="text-align: center"
!width="40"| stan
!width="40"| Q<sub>1</sub>
!width="40"| Q<sub>2</sub>
!width="40"| Q<sub>3</sub>
|-
! q<sub>0</sub>
| 0 || 0 || 0
|-
! q<sub>1</sub>
| 0 || 0 || 1
|-
! q<sub>2</sub>
| 0 || 1 || 0
|-
! q<sub>3</sub>
| 0 || 1 || 1
|-
! q<sub>4</sub>
| 1 || 0 || 0
|-
! q<sub>5</sub>
| 1 || 0 || 1
|}

=== Etap II – budowa tablicy wzbudzeń przerzutników ===
W powyższym układzie użyte zostały trzy [[Przerzutnik#Przerzutniki typu D|przerzutniki typu D]] (stany zapisane są na trzech bitach). Trzeba określić funkcje wejść przerzutników (D<sub>1</sub>, D<sub>2</sub>, D<sub>3</sub>) 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:
{| class="wikitable" style="text-align: center"
!width="40"| z
!width="40"| Q<sub>1</sub>
!width="40"| Q<sub>2</sub>
!width="40"| Q<sub>3</sub>
!width="50"| Q<sub>1</sub>(t+1)
!width="50"| Q<sub>2</sub>(t+1)
!width="50"| Q<sub>3</sub>(t+1)
!width="40"| D<sub>1</sub>
!width="40"| D<sub>2</sub>
!width="40"| D<sub>3</sub>
|-
| 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 [[Przerzutnik#Tablica_wzbudzeń_przerzutników|tablicy wzbudzeń]] sprawdza się wartość, którą należy podać na przerzutnik D. Przykładowo Q<sub>2</sub>=0 przechodzi w Q<sub>2</sub>(t+1)=1. Na wejście przerzutnika D<sub>2</sub> trzeba więc podać 1.

=== Etap III – odczyt funkcji wzbudzeń przerzutników ===
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 <math>q(t+1)</math>):
* <math>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,</math>
* <math>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,</math>
* <math>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.</math>

Po minimalizacji metodą [[Metoda Karnaugha|siatek Karnaugh]]:
* <math>D_1={zQ}_2+{Q}_2{Q}_3+{Q}_1{Q}_3,</math>
* <math>D_2=\overline{z}\overline{Q_2}\overline{Q_3}+z\overline{Q_1}\overline{Q_2}Q_3,</math>
* <math>D_3=Q_1+z\overline{Q_3}+\overline{Q_2}\overline{Q_3}+\overline{z}Q_2Q_3.</math>

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

=== Etap V – schemat logiczny ===
Można teraz przystąpić do budowy schematu logicznego automatu Moore’a (została użyta optymalizacja zgodnie z twierdzeniem Boole’a, że [[Alternatywa|suma logiczna]] argumentów jest równa [[Negacja|negacji]] iloczynu logicznego zanegowanych argumentów, co pozwoliło na użycie wyłącznie bramek NAND):
[[Plik:Automat moore'a uklad.png]]

[[Kategoria:Teoria automatów]]