Wikipedia

Automat Moore’a: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja przejrzana][wersja przejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
→‎Przykład automatu Moore’a: błąd merytoryczny w wyrażeniu regularnym - nieprawidłowe przejścia
Linia 1:
{{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:▼
 
▲gdzie:
* ''Z = {z<sub>1</sub>, z<sub>2</sub>, …,z<sub>n</sub>}'' – zbiór sygnałów wejściowych,
*: ''Q<math>Z = \{q<sub>1</sub>z_1, q<sub>2</sub>z_2, ''…''\dots,q<sub>n z_n\}</submath>}'' – zbiór stanówsygnałów wewnętrznychwejściowych,
*: ''Y<math>Q = \{y<sub>1</sub>q_1, y<sub>2</sub>q_2, ''…''\dots,y<sub>n q_n\}</submath>)'' – zbiór sygnałówstanów wyjściowychwewnętrznych,
: <math>Y = \{y_1, y_2, \dots, y_n\}</math> – zbiór sygnałów wyjściowych,
* ''Φ'' – funkcja przejść, ''q(t+1) = Φ[q(t), z(t)],''
*: ''Ψ''<math>\Phi</math> – funkcja wyjśćprzejść, ''y<math>q(t+1) = Ψ\Phi[q(t)],'' zależy tylko od stanu w którym znajduje się automatz(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,
*: ''q<submath>0q_0</submath>'' – 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 nowego stanu.
 
== 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<submath>4q_4</submath>'' kombinację określaną przez [[wyrażenie regularne]] <math>((z<sub>2</sub>z<sub>2</sub>z<sub>1</sub>&nbsp;z_2 z_2 z_1 +&nbsp;z<sub>2</sub>z<sub>1</sub> z_2 z_1)^*&nbsp;z<sub>1 z_1 z_2)^*.</submath>z<sub>2</sub>)*.
[[Plik:Graf automatu moore.svg|450px|center|450px]]
 
== Synteza strukturalna ==
Linia 25:
 
=== Etap I – kodowanie stanów, sygnałów i wyjść ===
Przypisuje się tu stanom (''q<sub>1</submath>(q_1, q<sub>2</sub>q_2, ''…''\dots, q_n),q<sub>n</submath>''), sygnałom (''z<sub>1</submath>(z_1, z<sub>2</sub>z_2, ''…''\dots,z<sub>n z_n)</submath>'') i wyjściom (''y<sub>1</submath>(y_1, y<sub>2</sub>y_2, ''…''\dots,y<sub>n y_n)</submath>'') reprezentację w systemie binarnym:
* sygnały wejściowe: z<SUB>1</SUBmath>z_1 →\to 0, z<SUB>2</SUB>z_2 →\to 1;</math>
* wyjścia automatu: y<SUBmath>1</SUB>→y_1 \to 0, y<SUB>2</SUB>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>
Linia 58:
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
Linia 97:
 
=== 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_3D_1=\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}Q_2Q_3+zQ_1\overline{Q_2}Q_3,</math>▼
 
* <math>D_1D_2=\overline{z}\overline{Q_1}Q_2Q_3+\overline{zQ_2}Q_1\overline{Q_2}Q_3}+z\overline{Q_1z}Q_1\overline{Q_2}\overline{Q_3}+z\overline{Q_1}Q_2Q_3+zQ_1\overline{Q_2}Q_3,</math>
* <math>D_2D_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>
▲* <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 Karnaugh|siatek Karnaugh]]:▼
 
▲Po minimalizacji metodą [[metodaMetoda KarnaughKarnaugha|siatek Karnaugh]]:
* <math>D_1={zQ}_{2}+{Q}_{2}{Q}_{3}+{Q}_{1}{Q}_{3}</math>
* <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 ===
Źródło: „https://pl.wikipedia.org/wiki/Automat_Moore’a”