Automat Moore'a
Z Wikipedii
Definicja intuicyjna:
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.
Automat Moore'a - jest to rodzaj deterministycznego automatu skończonego, reprezentowany przez uporządkowaną szóstkę 
, gdzie:
- Z = {z1, z2, ... ,zn} - zbiór sygnałów wejściowych
- Q = {q1, q2, ... ,qn} - zbiór stanów wewnętrznych
- Y = {y1, y2, ... ,yn) - 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)]
- q0 - stan początkowy, q0 należy do zbioru Q
Spis treści |
[edytuj] 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 q4 kombinację określaną przez wyrażenie regularne ((z1z2z1 + z2z1)* z1z2)*.
[edytuj] 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.
[edytuj] Etap I - kodowanie stanów, sygnałów i wyjść
Przypisujemy tu stanom (q1, q2, ... ,qn), sygnałom (z1, z2, ... ,zn) i wyjściom (y1, y2, ... ,yn) reprezentację w systemie binarnym:
- Sygnały wejściowe: z1 → 0; z2 → 1
- Wyjścia automatu: y1→ 0; y2 → 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 |
[edytuj] Etap II - budowa tablicy wzbudzeń przerzutników
W powyższym układzie użyjemy trzech przerzutników D (stany zapisane są na trzech bitach). Musimy określić funkcje wejść przerzutników (D1, D2, D3) 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 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 Q2=0 przechodzi w Q2(t+1)=1. Na wejście przerzutnika D2 musimy więc podać 1.
[edytuj] Etap III - odczyt funkcji wzbudzeń przerzutników
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]). Znak # oznacza tu negację.
- D1 = #z #Q1Q2Q3 + #z Q1#Q2Q3 + z #Q1Q2#Q3 + z #Q1Q2Q3 + z Q1#Q2Q3
- D2 = #z #Q1#Q2#Q3 + #z Q1#Q2#Q3 + z #Q1#Q2Q3
- D3 = #z #Q1#Q2#Q3 + #z #Q1Q2Q3 + #z Q1#Q2#Q3 + #z Q1#Q2Q3 + z #Q1#Q2#Q3 + z #Q1Q2#Q3 + z Q1#Q2#Q3 + z Q1#Q2Q3
Po minimalizacji metodą siatek Karnaugh:
- D1 = z Q2 + Q2Q3 + Q1Q3
- D2 = #z #Q2#Q3 + z #Q1#Q2Q3
- D3 = Q1 + z #Q3 + #Q2#Q3 + #z Q2Q3
[edytuj] Etap IV - określenie funkcji wyjścia y
Należy tu określić funkcję wyjścia w zależności od stanu, w którym się znajdujemy. W rozpatrywanym automacie bit Y wyjścia y przyjmie wartość Y=1 jedynie w stanie q4 zakodowanym jako Q1=1, Q2=0, Q3=0. Wynika stąd, że y = Q1#Q2#Q3
[edytuj] Etap V - schemat logiczny
Możemy już przystąpić do budowy schematu logicznego automatu Moore'a:
