Maquinas de estado

Maquinas de estado

• Definición• Clasificación• Maquinas de estado síncronas– Análisis – Diseño

Definición

• Son ciertos circuitos secuenciales que tienen un número determinado de estados (2n).

• Pueden ser:– retroalimentados (flip flops, biestables) o– máquinas sincrónicas temporizadas cuando utilizan

las primeras para crear circuitos cuyas entradas son examinadas y cuyas salidas cambian con respecto a una señal de reloj controlada.

• En cualquier caso, se tienen unas entradas, unas salidas y unos estados.

Estructura

Lógica de estado

siguiente

F

Memoria de estado

Entrada reloj

Lógica de salida

G

Señal de reloj

Excitación Estado presente

Salidas

Estructura

• Lógica de estado siguiente(F): Una función de las entradas y del estado actual.

• Memoria de estados: Es un conjunto de n flip-flops que almacenan el estado presente de la máquina, que tiene 2n estados diferentes. La señal de reloj controla el cambio de estado en tales flip flops.

• La señal de reloj: dispone el funcionamiento de los flip-flops ya sea por disparo de flanco o por disparo de pulso

• Lógica de salida(G): Una función del estado actual y/o de las entradas

Clasificación

• Sincrónicas vs Asincrónicas• Máquinas de Moore• Máquina de Mealy

Maquina de Moore• Es la máquina de estado en la cual las salidas solo

dependen del estado presente

Lógica de estado

siguiente

F

Memoria de estado

Entrada reloj

Lógica de salida

G

Señal de reloj

ExcitaciónEstado presen

te

Salidas

Máquina de Mealy

• Es la máquina de estado en la cuál la salida depende tanto del estado presente como de las entradas externas

Máquina de Mealy

Lógica de estado

siguiente

F

Memoria de estado

Entrada reloj

Lógica de salida

G

Señal de reloj

Excitación Estado presente

Salidas

Maquinas de estado sincrónicas

• Las que poseen entrada de reloj en la memoria de estado

Análisis

• Asumiendo la definición formal de máquina de Mealy:– Estado siguiente = F(estado actual, entrada)– Salida = G(estado actual, entrada)

• La primera ecuación dice que el estado siguiente estará determinado por la entrada presente y el estado presente del circuito.

• La segunda precisa que la salida de la máquina la determinan las dos mismas variables.

• El propósito del análisis de los circuitos secuenciales es determinar el estado siguiente y las funciones de salida para poder predecir el comportamiento del circuito.

Análisis

• Determinar el estado siguiente y las funciones de salida F y G.

• Usar F y G para construir una tabla de estados/salidas que especifique por completo el estado siguiente y la salida del circuito para cada combinación posible de estado actual y entrada.

• Diagrama de estados que presente en forma gráfica la información anterior(opcional).

Diseño

• Construir una tabla de estado/salida correspondiente a la descripción o especificación, mediante nombres mnemotécnicos para los estados. (Puede partirse del diagrama de estados correspondiente.

• Minimizar el número de estados en la tabla de estado/salida(opcional)

• Elegir un conjunto de variables de estado y asignar combinaciones de variables de estado a cada uno de los estados.

Diseño• Sustituir las combinaciones de variable de estado

en la tabla de estado/salida para crear una tabla de transición/salida que muestre la combinación de variable de estado siguiente y la salida para cada combinación de estado/salida

• Elegir el tipo de flip flop que hará la memoria de estado.

• Construir una tabla de excitación que muestre los valores de excitación requeridos para obtener el estado siguiente deseado para cada combinación de estado/entrada.

Diseño

• Derivar las ecuaciones de excitación de la tabla de excitación

• Derivar las ecuaciones de salida de la tabla de transición/salida

• Dibujar el diagrama lógico que muestre los elementos de almacenamiento de las variables de estado y realice las ecuaciones requeridas de excitación y salida.

Ejemplo 1

• Enunciado del problema: En una señal, detectar tres “1” seguidos

utilizando una máquina de Moore y biestables tipo D– Construir una tabla de estado/salida

correspondiente a la descripción o especificación, mediante nombres mnemotécnicos para los estados. (Puede partirse del diagrama de estados correspondiente)• Construir plantilla para la tabla de estado.

Tres unos seguidos

SIGNIFICADO S A Z

0 1

Estado inicial INI INI UNO 0

Tres Unos seguidos

SIGNIFICADO S A Z

0 1

Estado inicial INI INI UNO 0

Ha ingresado un 1 UNO INI DOS 0

Tres unos segudos

SIGNIFICADO S A Z

0 1

Estado inicial INI INI UNO 0

Ha ingresado un 1 UNO INI DOS 0

Han ingresado dos 1s

DOS INI TRES 0

Tres unos seguidos

SIGNIFICADO S A Z

0 1

Estado inicial INI INI UNO 0

Ha ingresado un 1 UNO INI DOS 0

Han ingresado dos 1s

DOS INI TRES 0

Han ingresado tres 1

TRES INI CUATRO

1

Tres unos seguidos

SIGNIFICADO S A Z

0 1

Estado inicial INI INI UNO 0

Ha ingresado un 1 UNO INI DOS 0

Han ingresado dos 1s

DOS INI TRES 0

Han ingresado tres 1

TRES INI CUATRO

1

Han ingresado 4 “1s”

CUATRO INI TRES 1

Tres unos seguidos

• Diagrama de estados

INI UNO

DOS

TRES

CUATRO

1

1

11

0

0

0

1

Tres Unos seguidos

– Minimizar el número de estados en la tabla de estado/salida(opcional)

SIGNIFICADO S A Z

0 1

Estado inicial INI INI UNO 0

Ha ingresado un 1 UNO INI DOS 0

Han ingresado dos 1s

DOS INI TRES 0

Han ingresado tres 1

TRES INI CUATRO

1

Han ingresado 4 “1s”

CUATRO INI TRES 1

Tres Unos seguidos

SIGNIFICADO S A Z

0 1

Estado inicial INI INI UNO 0

Ha ingresado un 1 UNO INI DOS 0

Han ingresado dos 1s

DOS INI TRES 0

Han ingresado tres 1

TRES INI TRES 1

Han ingresado 4 “1s”

TRES INI TRES 1

Tres Unos seguidos

SIGNIFICADO S A Z

0 1

Estado inicial INI INI UNO 0

Ha ingresado un 1 UNO INI DOS 0

Han ingresado dos 1s

DOS INI TRES 0

Han ingresado tres 1

TRES INI TRES 1

Tres Unos seguidos

INI UNO

DOS

TRES

1

1

1

0

0

0

1

Tres Unos seguidos

• Elegir un conjunto de variables de estado y asignar combinaciones de variables de estado a cada uno de los estados.• Estado inicial solo 000 o solo 111 (estados repetitivos)• minimizar el número de variables de estado que cambian • maximizar el número de variables de estado que no

cambian en un grupo de estados relacionados • facilita el análisis del circuito.

Tres Unos seguidos

Nombre del

estado

AsignaciónEl más simple

Compuesta

Q1-Q3

Un solo uno

Q1-Q5

Casi un 1Q1-Q4

INIUNODOSTRES

00011011

00011110

0001001001001000

000001010100

Tres Unos seguidos

• Sustituir las combinaciones de variable de estado en la tabla de estado/salida para crear una tabla de transición/salida que muestre la combinación de variable de estado siguiente y la salida para cada combinación de estado/salida

Tres Unos seguidos

SIGNIFICADO S A Z

0 1

Estado inicial 00 INI UNO 0

Ha ingresado un 1 01 INI DOS 0

Han ingresado dos 1s

11 INI TRES 0

Han ingresado tres 1

10 INI TRES 1

Tres Unos seguidos

SIGNIFICADO S A Z

0 1

Estado inicial 00 00 01 0

Ha ingresado un 1 01 00 11 0

Han ingresado dos 1s

11 00 10 0

Han ingresado tres 1

10 00 10 1

Tres Unos seguidos

• Elegir el tipo de flip flop que hará la memoria de estado.– Para este caso es D por solicitud del ejercicio

• Construir una tabla de excitación que muestre los valores de excitación requeridos para obtener el estado siguiente deseado para cada combinación de estado/entrada.

Tres Unos seguidos

• Resumen de tablas de excitación

Tres Unos seguidos

• Derivar las ecuaciones de excitación de la tabla de excitación

SIGNIFICADO S

Q2Q1

A

0Q2

*Q1*

1Q2

*Q1*

Estado inicial 00 00 01

Ha ingresado un 1 01 00 11

Han ingresado dos 1s 11 00 10

Han ingresado tres 1 10 00 10

Tres Unos seguidos

A’ A

D2‘D1' mo m1

D2'D1 m2 m3

D2D1 m6 m7

D2D1' m4 m5

Para Q1* = Q1A+Q2A

Tres Unos seguidos

• Para Q2* = Q2´A

A’ A

D2‘D1' mo m1

D2'D1 m2 m3

D2D1 m6 m7

D2D1' m4 m5

Tres Unos seguidos

• Derivar las ecuaciones de salida de la tabla de transición/salida

SIGNIFICADO S

Q2Q1

Z

Estado inicial 00 0

Ha ingresado un 1 01 0

Han ingresado dos 1s

11 0

Han ingresado tres 1 10 1

Z= D2D1´

Tres Unos seguidos

• Dibujar el diagrama lógico que muestre los elementos de almacenamiento de las variables de estado y realice las ecuaciones requeridas de excitación y salida.

Tres Unos seguidos

Nombre del

estado

AsignaciónEl más simple

Compuesta

Q1-Q3

Un solo uno

Q1-Q5

Casi un 1Q1-Q4

INIUNODOSTRES

00011011

00011110

0001001001001000

000001010100

• Elegir un conjunto de variables de estado y asignar combinaciones de variables de estado a cada uno de los estados.

Tres Unos seguidos• tabla de excitación con los valores de excitación

para obtener el estado siguiente

SIGNIFICADO S

Q2Q1

A Z

0Q2

*Q1*

1Q2

*Q1*

Estado inicial 00 00 01 0

Ha ingresado un 1 01 00 10 0

Han ingresado dos 1s

10 00 11 0

Han ingresado tres 1

11 00 11 1

• Derivar las ecuaciones de excitación de la tabla de excitación

SIGNIFICADO S

Q2Q1

A

0Q2

*Q1*

1Q2

*Q1*

Estado inicial 00 00 01

Ha ingresado un 1 01 00 10

Han ingresado dos 1s

10 00 11

Han ingresado tres 1

11 00 11

• Para Q2* = Q1A+Q2A

A’ A

Q2‘Q1' mo m1

Q2‘Q1 m2 m3

Q2Q1 m6 m7

Q2Q1' m4 m5

• Q1* = Q1´A+Q2A

A’ A

Q2‘Q1' mo m1

Q2‘Q1 m2 m3

Q2Q1 m6 m7

Q2Q1' m4 m5

Ecuación de salida

SIGNIFICADO S

Q2Q1

Z

Estado inicial 00 0

Ha ingresado un 1 01 0

Han ingresado dos 1s

10 0

Han ingresado tres 1 11 1

Z= Q2Q1

Diagrama