Automat Moore’a

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 deterministycznego automatu skończonego, reprezentowany przez uporządkowaną szóstkę:

${\displaystyle \langle Z,Q,Y,\Phi ,\Psi ,q_{0}\rangle ,}$

gdzie:

${\displaystyle Z=\{z_{1},z_{2},\dots ,z_{n}\}}$ – zbiór sygnałów wejściowych,

${\displaystyle Q=\{q_{1},q_{2},\dots ,q_{n}\}}$ – zbiór stanów wewnętrznych,

${\displaystyle Y=\{y_{1},y_{2},\dots ,y_{n}\}}$ – zbiór sygnałów wyjściowych,

${\displaystyle \Phi }$ – funkcja przejść, ${\displaystyle q(t+1)=\Phi [q(t),z(t)],}$

${\displaystyle \Psi }$ – funkcja wyjść, ${\displaystyle y(t)=\Psi [q(t)],}$ zależy tylko od stanu w którym znajduje się automat,

${\displaystyle q_{0}}$ – stan początkowy, należy do zbioru ${\displaystyle 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 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 ${\displaystyle q_{4}}$ kombinację określaną przez wyrażenie regularne ${\displaystyle ((z_{2}z_{2}z_{1}+z_{2}z_{1})^{*}z_{1}z_{2})^{*}.}$

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 ${\displaystyle (q_{1},q_{2},\dots ,q_{n}),}$ sygnałom ${\displaystyle (z_{1},z_{2},\dots ,z_{n})}$ i wyjściom ${\displaystyle (y_{1},y_{2},\dots ,y_{n})}$ reprezentację w systemie binarnym:

• sygnały wejściowe: ${\displaystyle z_{1}\to 0,z_{2}\to 1;}$
• wyjścia automatu: ${\displaystyle y_{1}\to 0,y_{2}\to 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

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 (D₁, D₂, D₃) 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 Q₂=0 przechodzi w Q₂(t+1)=1. Na wejście przerzutnika D₂ 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 ${\displaystyle q(t+1)}$):

• ${\displaystyle D_{1}={\overline {z}}{\overline {Q_{1}}}Q_{2}Q_{3}+{\overline {z}}Q_{1}{\overline {Q_{2}}}Q_{3}+z{\overline {Q_{1}}}Q_{2}{\overline {Q_{3}}}+z{\overline {Q_{1}}}Q_{2}Q_{3}+zQ_{1}{\overline {Q_{2}}}Q_{3},}$
• ${\displaystyle 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},}$
• ${\displaystyle D_{3}={\overline {z}}{\overline {Q_{1}}}{\overline {Q_{2}}}{\overline {Q_{3}}}+{\overline {z}}{\overline {Q_{1}}}Q_{2}Q_{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:

• ${\displaystyle D_{1}={zQ}_{2}+{Q}_{2}{Q}_{3}+{Q}_{1}{Q}_{3},}$
• ${\displaystyle D_{2}={\overline {z}}{\overline {Q_{2}}}{\overline {Q_{3}}}+z{\overline {Q_{1}}}{\overline {Q_{2}}}Q_{3},}$
• ${\displaystyle D_{3}=Q_{1}+z{\overline {Q_{3}}}+{\overline {Q_{2}}}{\overline {Q_{3}}}+{\overline {z}}Q_{2}Q_{3}.}$

Etap IV – określenie funkcji wyjścia y

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

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 suma logiczna argumentów jest równa negacji iloczynu logicznego zanegowanych argumentów, co pozwoliło na użycie wyłącznie bramek NAND):