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ę:
center|200x200px
gdzie: – zbiór sygnałów wejściowych, – zbiór stanów wewnętrznych, – zbiór sygnałów wyjściowych, – funkcja przejść, – funkcja wyjść, zależy tylko od stanu w którym znajduje się automat, – stan początkowy, należy do zbioru
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 kombinację określaną przez wyrażenie regularne center|450px
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 sygnałom i wyjściom reprezentację w systemie binarnym: sygnały wejściowe: wyjścia automatu: 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 (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, 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 Q2=0 przechodzi w Q2(t+1)=1. Na wejście przerzutnika D2 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 ):
Po minimalizacji metodą siatek Karnaugh:
Etap IV – określenie funkcji wyjścia y Wyjście może się zmieniać w zależności od stanu w którym automat się znajduje. W tym przypadku dla automatu w stanie Ponieważ funkcja wyjścia zwraca jeden bit, dlatego otrzymuje się jeden wzór bitu wyjścia automatu: Wiadomo także, że automat nie posiada stanów dla i dlatego można wzór uprościć do
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): Plik:Automat moore'a uklad.png
Kategoria:Teoria automatów