Màquina de Moore
Una màquina de Moore en teoria de la computació és un autòmat d'estats finits on les sortides estan determinades per l'estat actual únicament (i no depèn directament de l'entrada).[1] El diagrama d'estats per a una màquina Moore inclourà un senyal de sortida per a cada estat. Comparada amb la Màquina de Mealy, la qual mapeja transicions a la màquina a sortides.
El nom Moore machine ve del seu promotor: Edward F. Moore, un pioner de les màquines d'estats, el qual va escriure Gedanken-experiments on Sequential Machines, pp 129-153, Estudis d'Autòmats, Anales dels Estudis Matemàtics, no. 34, Princeton University Press, Princeton, N. J., 1956.[2]
La majoria de les electròniques estan dissenyades com a sistemes seqüencials síncrons. Els sistemes seqüencials síncrons són una forma restringida de màquines de Moore on l'estat canvia només quan el senyal de rellotge global canvia. Normalment l'estat actual s'emmagatzema en Flip-flops, i el senyal de rellotge global està connectada a l'entrada "clock" dels flip-flops. Els sistemes seqüencials síncrons són una manera de resoldre problemes de metaestabilitat.
Una màquina electrònica de Moore típica inclou una cadena de Lògica combinacional per descodificar l'estat actual en sortides (lambda). L'instant en el qual l'estat actual canvia, aquells canvis es propaguen a través de la cadena. i gairebé instantàniament les sortides canvien (o no canvien). Hi ha tècniques de disseny per assegurar que no es produeixin errors de curta durada a les sortides durant el breu període mentre aquests canvis s'estan propagant a través de la cadena, però la majoria dels sistemes estan dissenyats perquè els glitches durant el breu temps de transició siguin ignorats. Les sortides llavors romanen igual indefinidament (per exemple, els LEDs estan brillants, la bateria està connectada als motors, etc.), fins que la màquina de Moore canvia d'estat una altra vegada.
Definició formal modifica
Una màquina de Moore pot ser definida com una 6 - tupla
{S, S 0 , S,?, T , G } consistent de
- Un conjunt finit d'estats ( S )
- Un estat inici (també anomenat estat inicial) S 0 el qual és un element de ( S )
- Un conjunt finit anomenat alfabet entrada (S)
- Un conjunt finit anomenat l'alfabet sortida (?)
- Una funció de transició ( T : S × S? S ) mapejant un estat i una entrada al següent estat
- Una funció sortida ( G : S ??) Mapejant cada estat a l'alfabet sortida.
El nombre d'estats en una màquina de Moore serà major o igual al nombre d'estats a la Màquina de Mealy corresponent.
Referències modifica
- ↑ David A. Patterson, John L. Hennessy. Estructura y diseño de computadores (en castellà). Reverte, 2000, p. 110. ISBN 9788429126181.
- ↑ Moore, Edward F «Gedanken-experiments on Sequential Machines». Automata Studies, Annals of Mathematical Studies. Princeton University Press [Princeton, N.J.], 34, 1956, pàg. 129–153.