ES

Máquinas de estados (Moore y Mealy)

Del diagrama de estados a la tabla y a las ecuaciones de los biestables, con un detector de secuencia

Diseñador de detector de secuencia

Máquina

Diagrama de estados

Cada flecha lleva el valor de la entrada x que la provoca; en Mealy, también la salida que se produce («entrada/salida»). En Moore la salida va dentro del estado, y los estados con doble círculo son los que dan z = 1.

Tabla de estados

Ecuaciones con biestables D

Simulación

Entrada

Qué es una máquina de estados

Una máquina de estados finitos es un circuito secuencial que en cada momento está en uno de un número limitado de estados. El estado resume todo lo que importa del pasado. Con cada flanco de reloj pasa a un estado nuevo, que depende del estado actual y de las entradas. Se construye con un registro de biestables, que guarda el estado, y dos bloques de lógica combinacional: uno calcula el estado siguiente y otro las salidas.

Es la forma ordenada de diseñar cualquier automatismo con secuencia: un semáforo, el control de una puerta automática, una máquina expendedora, el protocolo de un puerto serie o las etapas de un ciclo de lavado. En un PLC se programa igual con GRAFCET o con pasos en ladder, y en un microcontrolador con un switch sobre una variable de estado.

Moore y Mealy

MooreMealy
La salida depende deSolo del estadoDel estado y de las entradas
Dónde se dibuja la salidaDentro de cada estadoEn cada flecha, «entrada/salida»
Número de estadosSuele necesitar alguno másSuele necesitar menos
RespuestaLa salida cambia en el flanco de reloj siguienteLa salida cambia en cuanto cambia la entrada
SalidaEstable durante todo el ciclo, sin glitchesPuede tener glitches si la entrada los tiene

Compara los dos tipos en el simulador con la misma secuencia: el detector de Mealy da z = 1 en el mismo ciclo en que llega el último bit, y el de Moore un ciclo después, cuando ya ha entrado en el estado final. Si la salida de un Mealy se lleva a otro circuito síncrono, ese retraso aparece igualmente al registrarla.

Pasos del diseño

  1. Diagrama de estados. Se describe el comportamiento: qué estados hay, a cuál se pasa con cada entrada y qué salida se produce. En un detector de secuencia, cada estado significa «llevo recibidos los primeros k bits de la secuencia».
  2. Tabla de estados. Lo mismo que el diagrama, en forma de tabla: estado actual y entrada a la izquierda, estado siguiente y salida a la derecha.
  3. Codificación. Se asigna un código binario a cada estado. Con S estados hacen falta ⌈log₂ S⌉ biestables. La codificación binaria usa el mínimo de biestables; la «one-hot» (un biestable por estado) gasta más biestables pero simplifica mucho las ecuaciones, y es habitual en FPGA.
  4. Ecuaciones. Con biestables D, la entrada D de cada uno es directamente el bit correspondiente del estado siguiente. Los códigos que no se usan son indiferentes y ayudan a simplificar en el mapa de Karnaugh. Con biestables JK se usa la tabla de excitación en lugar de copiar el estado siguiente.
  5. Estados sobrantes. Hay que comprobar a dónde va la máquina si arranca en un código no usado, por un ruido o al encender, y prever un reset que la lleve al estado inicial.

Solapamiento

Con solapamiento, los últimos bits de una secuencia detectada pueden ser el principio de la siguiente: buscando 1011 en 1011011, se detecta dos veces. Sin solapamiento, tras cada detección la máquina vuelve a empezar y solo encuentra una. Para decidir a qué estado volver cuando llega un bit que no encaja, se busca la parte más larga de lo recibido que coincide con el comienzo de la secuencia; es la misma idea que usa el algoritmo de búsqueda de texto KMP.

Ejemplo: un semáforo

Un semáforo para coches con pulsador de peatones es una máquina de Moore: las luces dependen solo del estado. Un temporizador da la señal de «tiempo cumplido» y el pulsador queda memorizado hasta que se atiende.

EstadoLuces cochesLuces peatonesPasa al siguiente cuando
S0 VerdeVerdeRojoHa pulsado un peatón y ha pasado el tiempo mínimo de verde
S1 ÁmbarÁmbarRojoTiempo de ámbar cumplido
S2 RojoRojoVerdeTiempo de paso de peatones cumplido
S3 DespejeRojoVerde intermitenteTiempo de despeje cumplido; vuelve a S0

Cuatro estados se codifican con dos biestables. Las salidas son funciones de Q1 y Q0, por ejemplo verde de coches = Q1'·Q0' y rojo de peatones = Q1'.

Relacionado: biestables y flip-flops, mapa de Karnaugh, simulador de puertas lógicas y simulador ladder.