Automat Moore'a

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

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₁, z₂, ... ,z_n} - zbiór sygnałów wejściowych
Q = {q₁, q₂, ... ,q_n} - zbiór stanów wewnętrznych
Y = {y₁, y₂, ... ,y_n) - zbiór sygnałów wyjściowych
Φ - funkcja przejść, q(t+1) = Φ[q(t), z(t)]
Ψ - funkcja wyjść, zależy tylko od stanu w którym znajduje się automat, y(t) = Ψ[q(t)]
q₀ - stan początkowy, q₀ 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 q₄ kombinację określaną przez wyrażenie regularne ((z₁z₂z₁ + z₂z₁)* z₁z₂)*.

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]

Przypisujemy tu stanom (q₁, q₂, ... ,q_n), sygnałom (z₁, z₂, ... ,z_n) i wyjściom (y₁, y₂, ... ,y_n) reprezentację w systemie binarnym:

Sygnały wejściowe: z₁ → 0; z₂ → 1
Wyjścia automatu: y₁→ 0; y₂ → 1
Stany wewnętrzne:

stan	Q₁	Q₂	Q₃
q₀	0	0	0
q₁	0	0	1
q₂	0	1	0
q₃	0	1	1
q₄	1	0	0
q₅	1	0	1

Etap II - budowa tablicy wzbudzeń przerzutników [edytuj]

W powyższym układzie użyjemy trzech przerzutników D (stany zapisane są na trzech bitach). Musimy 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	Q₁	Q₂	Q₃	Q₁(t+1)	Q₂(t+1)	Q₃(t+1)	D₁	D₂	D₃
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 prześledźmy tworzenie pierwszego wiersza: bit Q w następnym takcie zegara przechodzi w bit Q(t+1). W tabeli wzbudzeń sprawdzamy wartość, którą należy podać na przerzutnik D. Przykładowo Q₂=0 przechodzi w Q₂(t+1)=1. Na wejście przerzutnika D₂ musimy więc podać 1.

Etap III - odczyt funkcji wzbudzeń przerzutników [edytuj]

Ze zbudowanej w poprzednim etapie tabeli odczytujemy funkcje, które musimy podać na wejścia odpowiednich przerzutników (przy określaniu funkcji nie bierzemy 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]

Wyjście Y może się zmieniać 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 otrzymamy 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}$ .