UNIDAD VI: CIRCUITOS
LÓGICOS SECUENCIALES
Maquinas de
Estados Finitos I
MAQUINA DE ESTADOS FINITOS
(FSM)
 La gran mayoría de algoritmos son
implementados en software, esto se debe
principalmente a la flexibilidad y facilidad de
programación de los microprocesadores.
 Algunos algoritmos no pueden implementarse
solo en software. Las razones pueden variar de
acuerdo a la aplicación pero frecuentemente
hacen referencia a una capacidad de
procesamiento que NO PUEDE obtenerse con
microprocesadores
Maquinas de Estado Finito I
MAQUINA DE ESTADOS FINITOS
(FSM)
 La solución para implementar estos algoritmos
es utilizar hardware.
 Cuando un algoritmo se implementa en
hardware, las maquinas de estado se emplean
para acompañar la tarea (control).
 Una maquina de estados puede ser de la
complejidad que se quiera y funciona de forma
similar al software.
 La forma más simple de maquina de estados
es un contador.
Maquinas de Estado Finito I
MAQUINA DE ESTADOS FINITOS
(FSM)
 Una FSM descompone un algoritmo en pasos
(estados).
 Las transiciones entre estado pueden
depender de una condición o evento, o pueden
producirse en forma incondicional.
 Las condiciones y eventos están asociados a las
entradas del circuito.
 Las maquinas de estado se representan por
medio de Diagramas de Estados y Tablas de
Transición de Estados.
Maquinas de Estado Finito I
EJERCICIO 1
 Especificar en lenguaje natural el funcionamiento
de una maquina expendedora de tiquetes por
medio de estados …
Sencillo
Par
Multiviaje
Maquinas de Estado Finito I
EJERCICIO 1 – SOLUCIÓN
 Paso 0 – Sistema en espera, permanece en este
paso mientras el usuario no presione un botón de
selección de tiquete.
 Paso 1 – El sistema despliega valor de tiquete
seleccionado y queda en un estado de espera a que
usuario ingrese el dinero.
 Paso 2 – Cuando el usuario termina de ingresar dinero,
el sistema verifica que tenga la devuelta para el valor
ingresado, sino la tiene devuelve el dinero ingresado por
el usuario y retorna al paso 0. Si la tiene entrega el
tiquete seleccionado
 Paso 3 – Finalmente el sistema entrega la
devuelta y agradece la compra.
 Paso 4 – Regresar a estado de Espera
Maquinas de Estado Finito I
DIAGRAMA DE ESTADOS
 El Diagrama de Estados describe el
comportamiento de un circuito secuencial en
forma gráfica. Una FSM siempre tendrá un
diagrama de estados asociado.
 Los Estados del circuito se simbolizan como
círculos y se etiquetan con letras mayúsculas.
 Las transiciones entre estados se representan
con flechas. Estas se rotulan con las entradas y
el valor de estas que produjo la transición.
 Las salidas pueden aparecer ya sea en las
flechas o en los círculos.
Maquinas de Estado Finito I
DIAGRAMA DE ESTADOS
 Ejemplos de Diagramas de Estado
entrada/salida
5 estados
0
1 salida
A
1 entrada
1 entrada
0/0
1 salida
(0)
A
4 estados
1
1/0
B
1/1
(0)
E
0
(1)
1
0
1/0
B
0/0
C
(1)
0
0/0
1
D
D
C
0/1
(0)
1
Maquinas de Estado Finito I
1/1
DIAGRAMA DE ESTADOS
 Es muy importante tener en cuenta que si se tiene una
variable de entrada simple, cada estado en el diagrama
debe tener dos flechas salientes, una que corresponde
a la entrada en un valor ‘1’ y otra en un valor ‘0’.
 Si fueran dos variables de entrada, deben salir de cada
estado cuatro flechas que corresponderían a todas las
posibles combinaciones entre las entradas: 00, 01, 10 y
11.
00/0
xx/0
xx/1
01/0
10/1
A
10/1
01/0
C
D
11/0
00/0
Maquinas de Estado Finito I
11/0
B
TABLA DE TRANSICION DE
ESTADOS
 La tabla de transición de estados es otra forma de
representar circuitos secuenciales y FSMs. Es utilizada
principalmente en el algoritmo de diseño del sistema
secuencial. 0
ESTADO
ACTUAL
A
(0)
1
B
(0)
E
0
(1)
1
0
C
(1)
0
1
D
(0)
1
Maquinas de Estado Finito I
ESTADO
SIGUIENTE
SALIDA
Ent=0
Ent=1
A
A
B
0
B
C
D
0
C
B
D
1
D
E
D
0
E
A
A
1
CIRCUITOS MOORE
 Los circuitos cuyas
salidas solamente
son funciones del
estado se
denominan
Circuitos Moore.
 En los Circuitos
Moore las salidas
se introduce dentro
del estado, ya que
la salida depende
solamente del
estado.
Maquinas de Estado Finito I
0
A
(0)
1
B
(0)
E
0
(1)
1
0
C
(1)
0
1
D
(0)
1
CIRCUITOS MEALY
 Si las salidas de un
circuito dependen del
estado actual y de
las entradas se
denominan Circuitos
Mealy.
 Estando en un estado
si preguntamos por el
valor de la salida,
podemos no tener
respuesta hasta que
no se especifique el
valor de la entrada en
el siguiente intervalo.
Maquinas de Estado Finito I
0/0
A
1/0
1/1
1/0
B
0/0
1/1
0/0
D
C
0/1
CIRCUITOS MEALY
 Tabla de transición de estados en un circuito
mealy.
0/0
A
ESTADO
ACTUAL
1/0
1/1
1/0
B
0/0
1/1
0/0
D
C
0/1
Maquinas de Estado Finito I
ESTADO SIGUIENTE
0
1
A
A/0
B/0
B
D/0
C/1
C
B/0
A/0
D
D/1
A/1
MOORE vs. MEALY
 En el sistema de Moore la
independencia de las
salidas de las entradas
hace más fácil seguir la
operación del sistema en
pasos a través de sus
estados y por tanto hace
mucho más fácil la
detección de errores.
 Menos propenso a
glitches en las salidas.
Maquinas de Estado Finito I
 En forma general la
versión de Mealy de un
circuito secuencial será
más económica en
componentes físicos que
la versión de Moore.
 Debido a la dependencia
de las salidas respecto a
entradas, los circuitos
Mealy pueden presentar
glitches.
MOORE vs. MEALY
 NOTA:
 Cualquier Sistema secuencial se puede implementar
con alguna de los dos tipos de circuitos moore ó
mealy.
 Incluso es posible hacer combinaciones de ambos
tipos de circuitos en un solo diseño.
Maquinas de Estado Finito I
EJERCICIO 2
 Dibuje el diagrama de estados y la tabla de
transición de estados de un circuito secuencial el
cual da una salida Z = 1 solamente cuando la
entrada X es igual 1 durante 3 o más intervalos
consecutivos de reloj.
 Utilice un circuito tipo Moore
 Utilice un circuito tipo Mealy
Maquinas de Estado Finito I
EJERCICIO 2 – SOLUCIÓN
MOORE
0
A
(0)
1
B
1
C
(0)
1
D
(1)
1
Maquinas de Estado Finito I
ESTADO
SIGUIENTE
SALIDA
0
1
A
A
B
0
B
A
C
0
C
A
D
0
D
A
D
1
0
(0)
0
ESTADO
ACTUAL
0
EJERCICIO 2 – SOLUCIÓN MEALY
0/0
A
1/0
0/0
0/0
B
1/0
C
Maquinas de Estado Finito I
1/1
ESTADO
ACTUAL
ESTADO
SIGUIENTE
0
1
A
A/0
B/0
B
A/0
C/0
C
A/0
C/1
EJEMPLO – DETECTOR DE SECUENCIA

Dibuje el diagrama de estados y la tabla de
transición de estados de un circuito secuencial
el cual da una salida Z = 1 cuando por una
entrada X a ingresado la secuencia de bits
1101. Para un circuito secuencial tipo:
a. Moore
b. Mealy
X
Maquinas de Estado Finito I
Circuito
Secuencial
Z
EJEMPLO – DETECTOR DE SECUENCIA

Circuito Moore
0
0
S0
0
1
E.A
S0
S0
S1
0
S1
0
S1
S0
S2
0
S2
S3
S2
0
S3
S0
S4
0
S4
S0
S2
1
1
1
S2
0
1
S3
0
1
S4
1
Maquinas de Estado Finito I
X=0
0
0
0
E.S
X=1
SALIDA
Z
EJEMPLO – DETECTOR DE SECUENCIA
 Circuito Mealy
0/0
E.A
S0
0
1/1
X=1
S0
S0/0
S1/0
S1
0
1/0
S1
S0/0
S2/0
S2
S3/0
S2/0
S3
S0/0
S1/1
S2
0
0/0
S3
0
Maquinas de Estado Finito I
X=0
1/0
0/0
1/0
E.S
0/0
Descargar

`0`.