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ę:

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

gdzie:

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

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

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

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

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

$q_{0}$ – 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 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 $q_{4}$ kombinację określaną przez wyrażenie regularne $((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 $(q_{1},q_{2},\dots ,q_{n}),$ sygnałom $(z_{1},z_{2},\dots ,z_{n})$ i wyjściom $(y_{1},y_{2},\dots ,y_{n})$ reprezentację w systemie binarnym:

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

• $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},$
• $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_{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:

• $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_{2}Q_{3}.$

Etap IV – określenie funkcji wyjścia y

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

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):