Automat Mealy’ego

Z Wikipedii, wolnej encyklopedii
(Przekierowano z Automat Mealy'ego)
Skocz do: nawigacja, szukaj
Automat Mealy’ego

Automat Mealy’egoautomat), którego wyjście jest funkcją stanu wewnętrznego i sygnałów wejściowych (por. automat Moore’a).

Definicja formalna[edytuj]

Automat Mealy’ego jest to rodzaj deterministycznego automatu skończonego, reprezentowany przez uporządkowaną szóstkę:

,
Schemat Ideowy Automatu Mealy’ego

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ść, y(t) = Ψ[q(t), z(t)], zależy od stanu, w którym znajduje się automat oraz od sygnału wejściowego,
  • q0 – stan początkowy, należy do zbioru Q.

Automat Mealy’ego 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 podanego sygnału wejściowego.

Tłumacząc to w sposób bardziej przystępny: Stan wyjść Y automatu Mealy’ego [1] zależy od stanu wewnętrznego automatu Q (stanu przerzutników / rejestrów) tak jak ma to miejsce w Moore’a ale również od stanu wejść Z. W diagramie stanów zobrazowane jest to poprzez napis (Z / Y) obok strzałek zmiany stanu (funkcji przejść Φ), czyli dla każdego stanu wejścia Z podawany jest również stan wyjścia Y. W automacie Moore’a podawany jest tylko stan wejścia Z (zob. automat Moore’a). W konsekwencji liczba stanów wewnętrznych Q automatu Mealy’ego może być mniejsza (ten sam stan Q może wystąpić dla różnych stanów wyjść Y) w porównaniu z automatem Moore’a. Okupione to jest z reguły bardziej skomplikowaną logiką Ψ sterującą stanami wyjścia Y oraz większymi czasami propagacji. Podsumowując, wybór pomiędzy automatem Mealy’ego i Moore’a zależy od konkretnego automatu i wymagań.

Przypisy

  1. Mealy, George H., A Method for Synthesizing Sequential Circuits. Bell System Technical Journal. pp. 1045–1079., 1955.