cap9

1

Profesor Leopoldo Silva Bijit 19-01-2010

Capítulo 9

Sistemas secuenciales

9.1. Definiciones

Evento

Se denomina evento al cambio de valor de una señal en un instante de tiempo. Pasar de nivel

lógico 1 a 0 se denomina canto de bajada. Un canto de subida se produce cuando la señal pasa

de nivel lógico 0 a 1.

A un evento también se lo denomina mensaje; en un caso más general cuando se tienen varias

señales, los valores que toman los eventos suelen interpretarse como símbolos pertenecientes a

un alfabeto.

Máquina abstracta.

Una máquina abstracta es un modelo de computación que establece cómo se generan las

acciones, o eventos de salida, a partir de los mensajes o eventos de entrada.

Figura 9.1 Máquina abstracta.

Existen sistemas o máquinas que pueden cambiar sus atributos en función del tiempo, se

denominan dinámicos.

Estado.

Se denomina estado al conjunto de atributos que representan las propiedades de un sistema u

objeto en un determinado instante de tiempo.

En el caso de componentes digitales que tienen dispositivos que pueden almacenar valores, se

denomina estado al contenido de la memoria.

El estado refleja la condición en que se encuentra el sistema o máquina digital.

Máquina

Acciones Mensajes

2 Sistemas Digitales


Máquinas de estados.

Se denominan máquinas de estados a aquellas cuyas salidas, en un instante de tiempo,

dependen de los valores que toman las entradas y el estado en ese instante de tiempo. Lo cual

puede describirse por una función de transición que especifique los valores de las salidas y del

próximo estado para cada una de las combinaciones posibles de las entradas y del estado

presente. Las computaciones comienzan a partir de un estado inicial y de una secuencia de

valores de la entrada.

Transición.

Se denomina transición al cambio de estado del sistema, y ésta debe indicar cómo se pasa de un

estado a otro.

Un modelo matemático adecuado para la función de transición es una matriz, en la cual los

renglones y columnas representan los diferentes estados internos y los eventos de entrada,

respectivamente. El contenido de la matriz especifica el próximo estado.

Diagrama de estados.

Se denomina diagrama de estados a una representación gráfica de la matriz de transiciones, en

la cual los estados se representan como círculos (o rectángulos) y las transiciones como líneas

orientadas, que conectan los estados, y que representan los eventos de entrada.

Si puede describirse un sistema mediante un diagrama de estados o a través de las matrices de

transiciones y de salida se dice que el sistema es secuencial. En un sistema secuencial las

salidas dependen de las entradas presentes y de los valores de las entradas anteriores, mientras

que en un sistema combinacional las salidas sólo dependen de las entradas presentes o actuales.

Autómata de estados finitos determinista.

Si el número de estados es finito, se denominan máquinas de estados finitos. Si el próximo

estado queda unívocamente determinado por un solo evento se denominan determinísticas.

Si hay transiciones sin un evento de entrada o más de una transición para un par determinado

entrada-estado, se denominan no determinísticas.

Es posible generar un autómata de estados finitos determinista que tenga las mismas salidas,

para iguales entradas, que uno no determinista.

Tipos de máquinas.

Existen varios tipos de máquinas. Se denominan de Mealy aquéllas cuyas salidas se producen

en las transiciones entre estados; y Moore a aquéllas en las cuales las salidas están asociadas al

estado. Existen procedimientos para convertir un modelo de Mealy en uno de Moore.

Un diagrama de la estructura interna de la máquina abstracta que se ilustra en la Figura 9.1, se

muestra en la Figura 9.2.

Una máquina de estados finitos puede definirse según:

Capítulo 9. Sistemas secuenciales 3


MEF(x, y, z, FPE, FS)

Donde:

x es el conjunto finito de valores que puede tomar la entrada, que se define como el alfabeto de

entrada.

y es el conjunto de estados internos,

z es el alfabeto de salida. El conjunto finito de valores que puede tomar la salida,

FPE es la función de próximo estado, determina mediante una matriz el próximo estado Y,

dependiendo del valor que tenga la entrada x, y el estado presente y. Los renglones suelen ser

los diferentes estados internos y las columnas los diferentes valores que puede tomar la entrada.

Y = FPE(x, y)

FS es la función de salida. En el caso de máquinas de Moore: z=FS(y), este caso se ilustra en la

Figura 9.2; en el modelo de Mealy: z=FS(x, y).

Y

Reset

y

x

z

FPE M FS

Figura 9.2 Modelo de Moore.

Las funciones de próximo estado y de salida son funciones combinacionales. La Figura 9.2,

muestra un bloque de memoria M, que sostiene durante un tiempo el valor del estado presente y,

una vez calculado el próximo estado Y, éste se registra como el nuevo estado actual.

Reloj.

Si las transiciones ocurren en determinados instantes de tiempo se denominan sincrónicas. Los

instantes en que se producen los cambios de estado están asociados al canto de subida, o al de

bajada, de una señal denominada reloj.

Máquinas secuenciales.

Las máquinas de estados finitos suelen denominarse máquinas secuenciales ya que a partir de

un estado inicial y de una secuencia ordenada de eventos de entrada, generan una secuencia de

estados por los que pasa la máquina, y a su vez una secuencia de acciones de salida.

Las máquinas secuenciales son un poderoso modelo para implementar esquemas de control

secuencial (dependientes de la historia pasada), tanto en hardware como en software. El modelo



de máquina secuencial también facilita el diseño de la programación de sistemas multitareas, en

tiempo real, utilizando microcontroladores.

El modelo de máquina secuencial se emplea en Teoría de lenguajes formales y tiene importantes

aplicaciones en reconocimiento de patrones y analizadores léxicos y sintácticos, por mencionar

algunas.

Máquinas secuenciales sincrónicas.

Si la memoria está formada por un conjunto de flip-flops comandados por el mismo reloj, la

actualización del estado se produce en instantes sincronizados por el reloj. La Figura 9.3

muestra el diagrama general de Moore de una máquina secuencial sincrónica.

D Q

Clk

Y

Reset’

y

x

z

FPE M FS

Figura 9.3 Modelo de Moore sincrónico.

Si en la Figura 9.2, el bloque de memoria M, está formado por unidades de retardo se tiene un

modelo de representación de máquinas secuenciales asincrónicas.

Síntesis lógica.

Se denomina síntesis lógica al procedimiento por el cual a partir de la descripción de una

máquina de estados finitos: MEF(x, y, z, FPE, FS) se obtiene un circuito digital C(G, W), donde

G es un conjunto de compuertas y flip-flops y W es un conjunto de alambres que interconectan

las componentes de G. El circuito C también se denomina red booleana.

Figura 9.4 Circuito digital C(G, W).



9.2. Secuencias.

En caso de existir múltiples variables lógicas de entrada, al valor de la combinación (o vector)

se lo denomina palabra de entrada; y más simplemente: entrada.

Los distintos valores que toma la entrada, a medida que transcurre el tiempo, se denomina

secuencia temporal de entrada. En forma análoga se define una secuencia temporal de salida y

de estados internos.

Una secuencia de valores puede anotarse:

0 1 2( ) = ( ), ( ), ( ), ..., ( ),... ( )...i i i i i k i nx t x t x t x t x t x t

Con: 0kt t k t , los valores de la secuencia temporal se asocian a una secuencia de enteros.

Si t es constante, se denomina secuencia sincrónica al caso anterior.

Si t es variable, entonces kt describe los valores que toma una variable aleatoria; en este caso se

dice que la secuencia es asincrónica.

Las variables ix , toman valores discretos (0 y 1); el tiempo también puede considerarse una

variable discreta. Por ejemplo, podría ser de interés conocer el tiempo cuando se producen

cambios (en secuencias asincrónicas) o a intervalos regulares (intervalos de reloj, en secuencias

sincrónicas).

Una manera simplificada de anotar una secuencia es identificar sus valores en los diferentes

tiempos de interés.

( ) (0), (1), (2), ..., ( ),... ( )...i i i i i ix k x x x x k x n

Ejemplos de secuencias.

a) Sincrónica de nivel.

Figura 9.5. Secuencia sincrónica de niveles.

Se dice que la señal xn es una secuencia sincrónica de niveles, con respecto a un reloj, ya que

ésta sólo cambia en cantos de bajada (o de subida) del reloj, y además permanece constante el

nivel de la señal entre cantos de bajada (o de subida) del reloj.

La Figura 9.5, muestra una secuencia sincronizada por los cantos de bajada del reloj.

xn = { 0 1 0 0 1 1 0 1 0 0 ... }

...

0 1 2 3 4 5 6 7 8 9 (valores de k)

t0



b) Sincrónica de pulsos

Figura 9.6. Secuencia sincrónica de pulsos.

xp es una secuencia sincrónica de pulsos. Los valores de la secuencia se interpretan cuando el

reloj está alto. No toma valores entre pulsos.

c) Asincrónica de nivel

xa = { 0 1 0 1 0 1 ...}

t0 t1 t2 t3 t4 t5

Figura 9.7. Secuencia asincrónica de niveles.

Los intervalos ti tienen una duración aleatoria.

d) Asincrónica de pulsos.

t t t t t t t

0 1 2 3 4 5 6

Figura 9.8. Secuencia asincrónica de pulsos.

Los pulsos, de igual ancho, se presentan con intervalo aleatorio.

9.3. Modelo Secuencial

En un sistema combinacional, la salida es generada simultáneamente; es decir, en forma

concurrente o paralela y sólo depende de la entrada. Los cambios individuales de cada una de

las señales se producen en una secuencia temporal, también se dice serial en el tiempo, y pueden

contener perturbaciones antes de estacionarse en valores estables. Las redes combinacionales se

dice que no tienen memoria, y no deben tener realimentaciones; es decir que algunas salidas

estén conectadas a las entradas.

reloj

xp = { 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, ... }



En un sistema secuencial, para poder generar la salida en un tiempo dado, es preciso conocer

valores previos de algunas variables. No bastan los valores presentes de la entrada. Es decir,

debe almacenarse información concerniente a los valores de las entradas pasadas, para poder

generar la salida a partir de la entrada presente y los valores almacenados. La información

anteriormente mencionada, se almacena en estados internos.

Los valores que deben registrarse para recordar la situación, debida a los valores de las entradas

pasadas, se almacenan en variables de estado. Podemos considerar que las variables de estado

son salidas de elementos con memoria (flip-flops, registros, latches, retardos).

En cualquier instante, una máquina secuencial está en uno de un número finito de estados; éstos

quedan determinados por el valor de las variables de estado. Por ejemplo, si hay cuatro estados,

se requieren 2 variables de estado para registrar que el sistema se encuentra en uno de los cuatro

estados posibles: 00, 01, 10, 11.

La secuencia de estados internos resume la historia temporal del sistema secuencial.

A veces se emplea el término: estado total, para referirse a la combinación de los estados

internos con la entrada.

Si se aplica una secuencia de entrada, la máquina generará una secuencia de salida, y pasará por

una secuencia de estados internos.

En la Figura 9.2, la memoria puede ser modelada por:

)() ( tYtty

Es decir, en un intervalo de tiempo después, la salida de la memoria y tomará el valor actual de

la entrada a la memoria Y. Puede representarse la secuencia de valores temporales, de cada uno

de los estados, en términos de números enteros, según:

( 1) = ( )j jy k Y k

La memoria debe ser capaz de almacenar los Yj (k) y sostener estos valores durante el intervalo

(k+1). Debe notarse que los valores ( 1) jy k son estables, pero los valores ( )jY k , en el

intervalo anterior, pueden presentar perturbaciones al inicio para estabilizarse hacia el final del

intervalo. En el intervalo k-ésimo, la entrada a la memoria j-ésima es ( )jY k ; la salida de esa

memoria, en el mismo intervalo, es ( )jy k .

k k+1

Y(k) y(k+1)

Y(k) y(k)

Figura 9.8. a. Modelo de memoria.



En el modelo planteado, la salida y el próximo estado interno son funciones del estado total. A

estas máquinas se las denomina determinísticas.

Es decir, con n entradas, m variables de estado, y p variables de salida, se tienen:

1 1

1 1

( ,.., , ,.. ) (1.. )

( ,.., , ,.. ) (1.. )

i i n m

j j n m

z FS x x y y i p

Y FPE x x y y j m

Ecuaciones que indican que tanto la salida como el próximo estado dependen de la entrada y el

estado actual.

Empleando el modelo de memoria, puede eliminarse la variable Y, se logra:

1 1( 1) ( ( ),... ( ), ( ),... ( ))j j n my k FPE x k x k y k y k

Ecuación de recurrencia que permite determinar el próximo estado, a partir de la entrada y el

estado presente.

Para resolverla, es preciso conocer el valor del estado inicial y la secuencia de entrada a partir

del tiempo inicial.

Gráficamente:

(0) (1) (2) (3) ....... ..

(0) (1) (2) (3)

y y y y

x x x x

Para conocer y(1) se requiere conocer y(0) y x(0). Para conocer y(2) se requiere conocer y(1) y

x(1). Para conocer y(3) se requiere conocer y(2) y x(2). Y así sucesivamente.

Si el próximo estado es igual al actual, se dice que es un estado estable:

( 1) = ( )y k y k

Si el próximo estado es diferente al actual, se dice que habrá una transición o cambio de estado.

Ese estado actual se denomina inestable:

( 1) ( )y k y k

Lo anterior implica que una de las variables de estado conmuta, o cambia, su valor lógico.

Los elementos de almacenamiento pueden ser simplemente líneas de realimentación, las que

tienen asociado un retardo entre la entrada y la salida, en este caso se tienen sistemas

secuenciales asincrónicos.



En sistemas secuenciales sincrónicos los elementos de almacenamiento serán flip-flops,

comandados por un reloj.

9.4. Representación de máquinas secuenciales

Se entiende por representación la descripción de cómo se pasa de un estado a otro, debido a los

cambios de las entradas. Las representaciones deben describir en forma precisa y completa a la

máquina. Además, deben ser adecuadas para una manipulación formal.

9.4.1. Modelo de Mealy

Es un modelo secuencial en el cual la salida está asociada a las transiciones entre estados. Las

salidas cambian instantáneamente con los cambios de las entradas; el cambio de estado, se

produce sincronizadamente con el reloj. El diagrama se muestra en la Figura 9.9.

D Q

Clk

Y

Reset’

y

x z

FPE

M FS

Figura 9.9. Modelo de Mealy.

i) Diagrama de estados

Un diagrama de estados es un grafo en el cual, los estados se representan mediante círculos, y

por líneas rotuladas y orientadas las transiciones. El rótulo indica la entrada y la salida que

provoca la transición. Se separan con una pequeña barra diagonal (slash, en inglés).

En general:

Figura 9.10. Diagrama de estados de Mealy.

El diagrama anterior puede leerse: Estando en el estado 1y , cuando llega la entrada x se pasa al

estado 2y , con salida z.

y1

y2

x/z



Si el sistema es sincrónico la transición entre estados se produce en el instante en el cual se

produce el canto sincronizante del reloj.

Si el sistema es asincrónico, la transición se produce debida a un evento de la entrada; por

ejemplo cuando ocurre un canto de subida o de bajada de alguna de las entradas.

ii) Tabla de transición de estados

A esta tabla también se la llama matriz de transiciones.

En las columnas se indican los diferentes valores que puede tomar la entrada. En los renglones

se indican los estados internos actuales. En cada casillero de la matriz, se indica el próximo

estado y la salida asociada. La matriz suele representarse como un mapa de Karnaugh.

Esquemáticamente:

Figura 9.11. Tabla de transición de estados de Mealy. FPE.

Las representaciones son equivalentes, puede lograrse una a partir de la otra. Es decir, la matriz

de transiciones y el diagrama de estado suministran la misma información.

Pueden emplearse tablas separadas para la salida z y para el próximo estado Y.

Figura 9.12. Matriz de transiciones y matriz de salida.

9.4.2. Modelo de Moore

Modelo secuencial en el cual la salida sólo está asociada al estado presente. Las salidas y el

estado cambian sólo en los cantos de sincronización del reloj.

x

y Y/z

x

y Y

Y(x,y) Matriz Transiciones

x

y z

z(x,y) Matriz de salida



D Q

Clk

y(k+1)

Reset’

y(k)

x(k)

z(k)

FPE M FS

Figura 9.13. Modelo de Moore

i) Diagrama de estados

Figura 9.14. Diagrama de estados de Moore.

El diagrama anterior, puede leerse: Estando en estado 1y , con salida 1z ; cuando ocurre la entrada

x se pasa al estado 2y , con salida 2z .

La salida no cambia en la transición; por esta razón, las salidas se asocian a los estados.

ii) Tabla de transiciones

Figura 9.15. Tabla de transiciones modelo de Moore.

El modelo de Mealy es más general que el de Moore. Este último es un caso particular del

primero.

Las representaciones anteriores permiten analizar una máquina dada.

Entendemos por análisis, al proceso de determinar el funcionamiento de la máquina a partir del

diagrama de estados o de su tabla de transiciones.

y2/z2

x y1/z1

Y

x

y z y



El análisis de una máquina secuencial permite obtener la secuencia de salida a partir de la

secuencia de entrada; y también determinar la secuencia de estados internos.

Ejemplo 9.1

Determinar la secuencia de salida para la siguiente matriz de transiciones:

A

B

C

D

X 1 0

Estado

D/0 B/1

C/1

A/0

C/1

A/0

D/0

B/1

Secuencia de Entrada ={0,1,1,0,1,0,1,1,0,0,0,...}

Estado inicial = A

Próximo estado/z

Figura 9.16. Matriz de transiciones ejemplo 9.1.

La lectura de algunas transiciones:

Estando en A, con entrada 0, se pasa al estado D con salida 0.

Estando en D, con entrada 1, se pasa al estado B con salida 1.

Procediendo en forma similar, se logra:

Secuencia 0 1 2 3 4 5 6 7 8 9 10

Entrada 0 1 1 0 1 0 1 1 0 0 0

Estado actual A D B A D B B A C C C

Próximo estado D B A D B B A C C C C

Salida 0 1 0 0 1 1 0 1 1 1 1

Figura 9.17. Secuencia de salida y de estados.

La máquina de Mealy anterior, se comporta como un generador de secuencias.

Figura 9.18. Esquema generador de secuencias.

Se ingresa la secuencia de valores: x0, x1, x2,… y se genera la secuencia de valores de salida: z0,

z1, z2, ...

Puede obtenerse el diagrama de estados, a partir de la matriz de transiciones:

012... 0123..

... ...

x z



0/1

0/1

1/1

A C

B D

1/0 1/0

1/1

0/0

0/0

Figura 9.19. Diagrama de Estados ejemplo 9.1.

Ejemplo 9.2.

Determinar la secuencia de estados para la siguiente máquina de Moore:

Figura 9.20. Diagrama de estados de Ejemplo 9.2.

Con estado inicial C y secuencia de entrada: {0, 0, 0, 1, 1, 1,...}

Se obtiene:

i 0 1 2 3 4 5

Entrada 0 0 0 1 1 1

Estado presente C B A A B C

Estado próximo B A A B C A

Salida 0 0 1 1 0 0

Figura 9.21. Secuencia de salida Ejemplo 9.2.

Las máquinas de Moore suelen emplearse como reconocedores de secuencias. Es decir, que

entreguen una salida cuando ocurre una determinada secuencia en la entrada.

Pueden obtenerse la tabla de transiciones y la tabla con la lógica de salida, a partir del diagrama

de estados:

1

C/0 A/1

B/0

1

1

0

0 0



Figura 9.22. Tabla de transiciones Ejemplo 9.2

Existen procedimientos sistemáticos para representar un diagrama de Mealy mediante uno de

Moore. Debe considerarse la representación de Mealy como más general que la de Moore.

Ejemplo 9.3.

Obtener el diagrama de estados de un sistema secuencial sincrónico que es capaz de detectar

la secuencia 110 cada vez que ésta se presente. Determinar la secuencia de salida, cuando se

aplica en la entrada la secuencia: 011011..

Como puede observarse en la Figura 9.23, el diagrama de Moore, requiere 4 estados:

Figura 9.23. Diagrama de Moore Ejemplo 9.3.

Moore 0 1 2 3 4 5

Entrada 0 1 1 0 1 1

Estado presente Inicio Inicio Est0 Est1 Est2 Est0

Estado próximo Inicio Est0 Est1 Est2 Est0 Est1

Salida 0 0 0 0 1 0

Figura 9.23a. Secuencia de salida modelo de Moore Ejemplo 9.3.

El diagrama de Mealy requiere tres estados:

Estado

actual

Entrada x

0 1

A A B

B A C

C B A

Próximo

Estado

Estado Salida

A 1

B 0

C 0

Inicio

0

Estado0

0

Estado1

0

Estado2

1

1 1 0

0

0

0

1

1

reset



Figura 9.24 Diagrama de Mealy Ejemplo 9.3.

Mealy 0 1 2 3 4 5

Entrada 0 1 1 0 1 1

Estado presente Inicio Inicio Est0 Est1 Inicio Est0

Estado próximo Inicio Est0 Est1 Inicio Est0 Est1

Salida 0 0 0 1 0 0

Figura 9.24a. Secuencia de salida modelo de Mealy Ejemplo 9.3.

Algunas observaciones sobre las representaciones:

Las salidas de Moore son sincrónicas con el reloj, las de Mealy son asincrónicas; es decir,

apenas ocurre una transición en la entrada, se genera el próximo estado y se produce la salida

sin esperar el canto del reloj.

En general los modelos de Mealy pueden generar las mismas secuencias de salidas que una

máquina de Moore, pero con menos estados. Nótese que las salidas de Mealy ocurren un

intervalo de tiempo antes que las de Moore.

En las máquinas de Mealy, las salidas z pueden cambiar inmediatamente cuando ocurre un

cambio en las entradas, y éstas pueden cambiar entre pulsos del reloj. Si esto no se desea,

pueden sincronizarse las salidas asincrónicas, de una máquina de Mealy, pasándolas por un flip-

flop. Esto se muestra en la Figura 9.24b, donde la salida rz , tiene sus cambios sincronizados por

el reloj. Esto aumenta el número de flip-flops requeridos para la implementación y además se

posterga la salida hasta el próximo canto del reloj. Ver Capítulo 11.9.

1 / 0

0 / 0

0 / 0

0 / 1

Inicio

Estado 0

Estado 1

1 / 0

1 / 0

reset



D Q

Clk

y(k+1)

Reset’

y(k)

x(k) z(k+1)

FPE

M FS

zr(k)

Figura 9.24b. Salidas registradas en modelo de Mealy.

En el modelo de Moore, el circuito combinacional de salida puede generar perturbaciones, éstas

pueden evitarse si las salidas se generan en función del estado próximo. Ver Capítulo 11.9.

D Q

Clk

y(k+1)

Reset’

y(k)

x(k)

FPE

M FS

zr(k)

Figura 9.24c. Modelo de Moore. Salida registrada.

En diseños de máquinas secuenciales de estados finitos completamente sincrónicas, debe

preferirse el modelo de Moore. Así también cuando se empleen dispositivos lógicos

programables (PLD o FPGA) para la implementación.

Ejemplo 9.4.

Los siguientes diagramas ilustran la diferencia entre el número de estados, requeridos para cada

uno de los modelos de máquina, para un detector de la secuencia de dos unos seguidos, cada vez

que ésta se presente.



Figura 9.25. Diagramas de Mealy y Moore ejemplo 9.4.

Ejemplo 9.5. Modelado de diagrama de estados. Lavadora.

En situaciones reales puede concebirse el funcionamiento de un sistema mediante la elaboración

de un diagrama de estados.

Supongamos que disponemos de una lavadora, que externamente tiene tres botones: Encender,

Detener, Lavar; de un indicador luminoso L, y de un interruptor ubicado en la puerta.

La Figura 9.26 ilustra un esquema de los controles e indicadores de la máquina lavadora.

Figura 9.26. Lavadora.

Se consideran eventos (entradas) la activación de los botones de la consola y del interruptor de

la puerta. El indicador luminoso es una acción (salida) que debe ejecutarse.

Se visualizan tres estados asociados a la lavadora: apagada, detenida y lavando. La detección de

cuáles son los estados, está basada en la visualización de situaciones distinguibles que se

mantienen un determinado tiempo.

S0/0

reset

0

S1/0

S2/1

1

1

1

0

0

S0

reset

0/0

S1

1/0 0/0

1/1

encender detener lavar

puerta

L



Los eventos producen cambios de estado.

Estando apagada, el evento encender dispara una transición al estado detenida (o encendida).

Estando en el estado detenida, la ocurrencia del evento lavar produce la transición al estado

lavando.

Si está lavando, la presión del botón detener gatilla la conmutación al estado detenida.

Al producirse el evento abrir la puerta, la lavadora debe pasar al estado apagada.

La luz L debe encenderse cuando hay potencia aplicada a la lavadora. Es decir, desde que se

pasa de apagada a encendida y mantenerse iluminada hasta que se abra la puerta, cuando se pasa

a apagada.

Las especificaciones anteriores permiten dibujar un diagrama de estados, el que se muestra en la

Figura 9.27.

Los eventos producen cambios de estado. Cada transición o cambio de estado, está asociada a

un (y sólo un) evento. Un evento puede desencadenar varias transiciones, en el ejemplo, la

entrada o evento puerta produce dos transiciones, dependiendo del estado en que se encuentra la

lavadora.

La única acción de salida L se ilustra asociada a las transiciones (Mealy). También es posible

asociarla a los estados (Moore): la luz L debe estar encendida mientras la lavadora esté

encendida o lavando; debe apagarse cuando esté en el estado apagada.

Figura 9.27. Diagrama de estados de la Lavadora.

El estado inicial para esta máquina es el estado apagada.

Sub-máquinas.

La descripción de la lavadora puede seguir especificándose con mayor detalle, si se define con

mayor precisión el estado lavando. Esto significa observar señales internas de la lavadora.

Si se define el evento rotar, que produce que el motor de una vuelta, y de la señal de salida giro

(G=1 a la izquierda, y G=0 a la derecha) y se define que el proceso de lavar sea dar dos vueltas

a la izquierda seguidas por dos vueltas a la derecha, en el diagrama aparecen cuatro nuevos

estados para describir el estado lavando.

Apagada Encendida Lavando

Encender/ L Lavar/ L

Detener/ L Puerta/ L’

Puerta/ L’



Figura 9.28. Diagrama de estados ampliado de la Lavadora.

La descripción permite diferentes niveles de abstracción, en el ejemplo, lavando se ha descrito

como una sub-máquina digital.

9.4.3. Transformación de Mealy a Moore.

a) En el diagrama de Mealy deben separarse aquellos estados, para los cuáles existan

transiciones con diferentes valores de salida, para igual entrada:

Figura 9.29. Separación de estados.

Luego cada estado tendrá sólo un valor de salida asociado, y se transforma a representación de

Moore, según:

x/1

Sa

x/0

Sa0

Sa1

x/0

x/1

Apagada

Encendida

Izquierda/ G

Encender/ L

Lavar/ L Detener/ L

Puerta/ L’ Puerta/ L’

Izquierda 1/ G

Derecha 1/ G’

Derecha/ G’

Rotar

Rotar

Rotar

Rotar

Puerta/ L’

Puerta/ L’ Puerta/ L’



Figura 9.30. Conversión a Moore.

b) Una vez agotado el paso a), para el estado inicial pueden presentarse dos casos:

b1) Estado inicial con salida 0. No requiere modificación.

Figura 9.31. Estado inicial con salida cero.

b2) Estado inicial con salida diferente de cero.

Figura 9.32. Estado inicial con salida uno.

En este caso debería haber salida, sin haber aplicado una entrada. Se corrige agregando un

estado adicional:

Figura 9.33. Agregar estado inicial.

Sa0/0

Sa1/1

x

x

S/0 reset

S/1 reset

S/1

Si/0

reset



Ejemplo 9.6.Transformación para el reconocedor de dos unos seguidos.

Al modificarse el estado S1 del diagrama de Mealy, resulta:

Figura 9.34. Separación de estado S1.

No es necesario corregir el estado inicial. Luego puede asociarse la salida al estado y no a la

transición hacia el estado.

Figura 9.35. No es necesario corregir S0.

Finalmente puede plantearse:

S0

reset

0/0

S10

S11

1/1

1/1

1/0

0/0

0/0 S0

reset

0/0

S1

1/0 0/0

1/1

S0

reset

0/0

S10

S11

1/1

1/1

1/0

0/0

0/0



Figura 9.36. Diagrama de Moore ejemplo 9.6.

Que resulta igual al diagrama de Moore planteado antes, en el ejemplo 9.4.

El proceso de transformación explica el mayor número de estados que tiene generalmente un

diagrama de Moore, respecto a uno de Mealy.

Ejemplo 9.7.

Detector de las secuencias 01 ó 10, cada vez que se presenten.

Para un modelo de Moore, se especifican las salidas asociadas al estado.

Figura 9.37. Representación de Moore Ejemplo 9.7.

En un diagrama de Mealy, se especifican las salidas asociadas a las transiciones.

S0/0

reset

0

S10/0

S11/1

1

1

1

0

0

D/1

E/1

B/0

A/0

C/0

1

0

0

0

0

1

1

1

1

0

reset

reset entrada estado

actual

próximo

estado

salida

1 - A - 0

0 0 A B 0

0 1 A C 0

0 0 B B 0

0 1 B D 0

0 0 C E 0

0 1 C C 0

0 0 D E 1

0 1 D C 1

0 0 E B 1

0 1 E D 1



Figura 9.38. Representación de Mealy Ejemplo 9.7.

9.5. Tipos de máquinas secuenciales

Si bien existen innumerables formas que pueden tomar los diagramas de estados, pueden

describirse algunos tipos que se presentan frecuentemente.

Máquinas que analizan secuencias de largo fijo con un recorrido fijo. Por ejemplo:

adquirir 5 valores de la secuencia y tomar una acción, de acuerdo a los valores.

Máquinas que analizan secuencias de largo fijo con un recorrido fijo, con reintento en

caso de falla. Si una subsecuencia no es correcta, vuelven al estado inicial; o a un estado

previo.

Reconocedores continuos. Se genera una salida cada vez que se detecta una secuencia

dada. En estas máquinas, cada estado recuerda una secuencia previa de la entrada. En

este caso, se habla de estado inicial sólo cuando la máquina comienza a funcionar.

9.6 Síntesis de Diagramas de Estado. Modelado

Se desea obtener el diagrama de estados a partir de una descripción en lenguaje natural.

Nuestro lenguaje común suele ser impreciso y a veces redundante. Por esta razón es conveniente

emplear las construcciones estructuradas de los lenguajes de programación. Ver Apéndice 5,

sobre Uso de Verilog.

En general, el paso de una descripción en lenguaje natural a la tabla de estados, se efectúa por

pasos tentativos, hasta asegurar que el modelo formal obtenido cumple las especificaciones

dadas.

Veremos algunos ejemplos.

reset entrada Estado

actual

próximo

estado

salida

1 - A - -

0 0 A B 0

0 1 A C 0

0 0 B B 0

0 1 B C 1

0 0 C B 1

0 1 C C 0

B

A

C

0/1

0/0

0/0

1/1

1/0

1/0

reset



9.6.1 Reconocedor de secuencias de largo fijo. Verificador BCD

La máquina reconoce si una secuencia de cuatro bits, en serie, es BCD.

Tenemos una máquina con una entrada y una salida:

Figura 9.39 Diagrama en bloque verificador BCD.

Tenemos que interpretar cuando se genera la salida. Como para cada valor i de la secuencia de

entrada debe existir un valor de la secuencia de salida; debemos decidir qué salida generar

cuando han llegado uno, dos o tres valores de la entrada. En estos casos asumiremos salida cero,

dejando salida uno si los cuatro bits no pertenecen al código BCD. El bit más significativo es el

primero.

Figura 9.40 Diagrama de estados verificador BCD.

Cada estado representa una subsecuencia previa de la entrada. Por ejemplo, en el estado l se ha

recibido la secuencia 100. En el estado d se ha recibido 00.

Este primer diseño es muy sistemático; se forma un árbol de decisión. De cada estado, se pasa a

dos próximos con entrada cero y uno respectivamente.

Estos problemas no tienen una solución única. Puede encontrarse un diagrama de estados más

simple. Por ejemplo:

Estado Inicial

a

d

i h

0/0 1/0

0/0

0/0 1/0

1/0

e

k j

0/0 1/0

0/0

0/0 1/0

1/0

f

m l

0/0 1/0

0/0

0/1 1/1

1/0

g

o n

0/1 1/1

0/0

0/1 1/1

1/0

b 0/0 1/0

c 0/0 1/0

0/0 1/0

M.S.

x z



Figura 9.41 Diagrama de estados reducido del verificador BCD.

Se emplea para indicar que con entrada cero o uno, se pasa al próximo estado. Este segundo

diagrama requiere tres flip-flops para representar los siete estados. El anterior requiere 4 flip-

flops para identificar 15 estados.

Existen procedimientos sistemáticos para encontrar estados equivalentes y removerlos de los

diagramas, esto se desarrolla en el Capítulo 12.

9.6.2. Reconocedor continuo.

Se desea obtener el diagrama de estados de una máquina secuencial que produzca una salida alta

cada vez que se detecta la secuencia 0101 en la entrada; la salida debe ser cero en el resto de los

casos.

Si por ejemplo la entrada es: 0, 1, 0, 1, 0, 1, ...

la salida debe ser: 0, 0, 0, 1, 0, 1, ...

A partir de un estado inicial A, se plantea el diagrama para la secuencia que se desea reconocer:

Figura 9.42 Reconocedor de secuencia 0101.

Luego, lo que resta es completar las transiciones que faltan. Desde cada estado deben salir dos

transiciones; en este caso, sólo hay una entrada, y ésta puede tomar valores 0 y 1.

1/1

A B C D

0/0 1/0 0/0

/0 /0

/0

/0

a

b

c

d

e

f g

h

/1

/0

/0

0/0 1/0

1/0

0/0

1/0

0/0



Es recomendable conceptualizar el significado de los estados, del siguiente modo:

A: inicial, se espera un cero.

B: después de haber aceptado un cero.

C: después de haber aceptado la secuencia 01.

D: después de haber aceptado la secuencia 010.

Observaciones:

Estando en D, si llega un cero, debe ir al estado B, pues ya tendría el primer cero de la

secuencia.

Estando en B, debe permanecer en B mientras lleguen ceros.

Permanece en A, mientras lleguen unos.

Estando en C, si llega un uno, debe ir al estado inicial.

Estando en D, si llega un uno, se reconoce secuencia correcta; y debe ir a C. Ya que tiene los

dos primeros bits reconocidos.

Resulta el siguiente diagrama de estados:

Figura 9.43 Diagrama de estados completo del reconocedor continuo.

9.6.3. Reconocedor continuo con reintento en caso de falla

Diseñar máquina secuencial que reconozca con salida uno, cada vez que se presente en la

entrada, la secuencia de exactamente dos ceros, seguida de 10. En caso contrario debe generar

salida cero.

La siguiente secuencia de entrada: 001001000010010...

debe generar la siguiente salida: 000100100000001...

Un esquema de la “columna vertebral” del diagrama es:

1/0

1/0

0/0 1/0

1/1

0/0 A B C D

0/0

B B

0/0

1/0 1/0

0/0

0/0 A B C D B

0/1



Figura 9.44 Diagrama de estados inicial.

A, es el estado inicial: en él se espera por un cero.

Si en B o D falla la secuencia se retorna al estado inicial.

Estando en C, si llega un cero debe pasarse a un estado E; en el cual deben descartarse todos los

ceros que lleguen.

El diagrama completo:

Figura 9.45 Diagrama de estados completo.

9.6.4. Reconocedor continuo de códigos BCD válidos.

En este ejemplo se ilustra la importancia de darle un nombre simbólico adecuado a cada estado.

Si la entrada presente y las tres anteriores forman un código válido BCD, entonces la salida

permanece en 0; en caso contrario la salida debe ser uno.

Si asignamos el nombre del estado tal que éste sea la secuencia previa de 3 bits de la entrada,

para construir el diagrama basta obtener los estados próximos a cualquier estado.

Por ejemplo, a partir del 001, se llega a los estados 011 y 010, con entradas uno y cero

respectivamente.

Esto se ilustra en el siguiente diagrama:

Figura 9.46 Estados siguientes al estado 001.

Los dos últimos bits de 001, forman los dos primeros de 011 y 010.

De esta forma es sencillo plantear, el diagrama completo, que se muestra en la Figura 9.47.

001

011 010

1 0

A B C D 0/0

1/0

1/0

1/0 0/0

E

0/1

1/0 0/0

1/0

0/0



Figura 9.47 Diagrama de estados completo, sin salida.

Para completar el diagrama deben indicarse las salidas asociadas a las transiciones.

Las secuencias: 1010, 1011, 1100, 1101, 1110, 1111 son las que tienen asociada una salida uno.

La función de salida puede describirse por la siguiente tabla de verdad, y con ésta completar el

diagrama.

Figura 9.48 Tabla de verdad de la función de salida.

9.6.5. Del diagrama a la especificación.

Dado el siguiente diagrama de estados, describir qué efectúa la máquina.

Estado x

0 1

000 0 0

001 0 0

010 0 0

011 0 0

100 0 0

101 1 1

110 1 1

111 1 1

z

0 1

1 1

1 0

0

0

1 000

001 100

010

101

011 110

111

0

0

0

1

1

1

0



Asumir estado 1 como estado inicial.

Figura 9.49 Diagrama de estados Ejemplo 9.6.5.

Observando que en 1 se espera un cero; y que 2 simboliza que ha llegado un cero.

Se tiene que es un reconocedor continuo de las secuencias 01110 y 01111 con salida uno.

La salida es cero en el resto de los casos.

Cuando reconoce una de las secuencias anteriores vuelve a comenzar de nuevo.

9.6.6. Determinar conducta de la máquina secuencial

Figura 9.50 Diagrama de estados ejemplo 9.6.6.

Asumiendo que el estado inicial es el A, y observando cuando se produce la única salida con

valor 1, y que además después de cuatro transiciones se retorna al estado inicial: se obtiene que

analiza secuencias de largo cuatro. Si la secuencia es 1111 genera salida 1; en el resto de las

secuencias la salida es cero.

1/0 1/0

0/0

1/0

1/0 1 2 3 4 5

0/0

0/0 0/1, 1/1

0/0

1/0 0/0

A

1/0 0/0

/0

/0

/0 0/0

B C

D

F G 0/0

1/0

1/0

E

1/1



Problemas resueltos.

Problema 9.1. Cerebro de Hormiga. (Ant Brain. Propuesto en el MIT).

Se desea diseñar una máquina secuencial cuyo objetivo es permitir a la hormiga encontrar la

salida del laberinto.

La hormiga dispone de dos sensores en las antenas izquierda y derecha (I y D), que están en 1 si

la antena respectiva entra en contacto con las paredes del laberinto; y se colocan en cero si dejan

de estar en contacto. Son las entradas a la máquina de estados finitos.

La hormiga también dispone de tres señales de actuación, que son las salidas de la máquina, una

señal para avanzar hacia delante A; otra para doblar levemente hacia la izquierda DI; y otra para

doblar levemente hacia la derecha DD.

La estrategia para diseñar el cerebro de la hormiga es mantener la pared a la derecha de la

hormiga.

Figura P9.1 Laberinto.

Para desarrollar el diagrama de estados, se elige emplear el modelo de Moore. Es decir, las

salidas estarán asociadas al estado.

Se definen los estados posibles, y en cada uno de éstos debe observarse los valores de las

entradas que llevan a otros estados. Debe notarse que se tienen cuatro combinaciones posibles

para los valores permitidos a las entradas, esto implica dibujar 4 transiciones a estados

próximos. Sin embargo es posible simplificar el diagrama rotulando las transiciones como una

expresión lógica de las entradas.

Ejemplos:

Si debe pasarse a cierto estado cuando cualesquiera de las antenas tocan una pared, la transición

puede rotularse ( I + D).



Si debe pasarse a cierto estado cuando ambas antenas no tocan a alguna pared, la transición

puede rotularse ( I ' D'). Es decir, que ambas no toquen. Si la transición es cuando la izquierda

no toque y la derecha entre en contacto con la pared, la transición se anota: (I' D).

Para encontrar los estados debe analizarse las diversas situaciones en que se puede encontrar la

hormiga en su recorrido del laberinto. Observando las entradas, y las acciones que ésta puede

realizar, a continuación se plantean algunas de las situaciones:

Figura P9.2 Esquema de situaciones. Definición de estados.

A: Siguiendo la muralla y tocándola: Avanzar, doblando levemente a la izquierda, hasta llegar a B:

B: Siguiendo la muralla y no tocándola: Avanzar, doblando levemente a la derecha. O se vuelve a A, o se pasa a C.

C: Se acaba la pared: Avanzar, doblando levemente a la derecha, hasta llegar a D:

D: Vuelve a tocar la muralla, con la Antena derecha: Es la situación A.

E: Pared al frente: Mientras toque con alguna antena: Doblar levemente a la izquierda hasta pasar a F:

F: Igual situación que en el estado B.

G: Tocando la pared con la izquierda. Doblar a la derecha hasta no tocar la pared. Es la situación B.

H:Perdido: Avanzar hasta tocar algo.



No se encuentran otras situaciones que no se hayan planteado, entonces se procede a conectar

los diferentes estados, mediante el siguiente diagrama:

I’ D I + D

D’ C

(DD, A)

D’

I’ D’

B

(DD, A)

I’ D’

I

D

A

(DI, A)

D

E/G

(DI)

I + D Perdido

(A)

I’ D’

Figura P9.3 Diagrama de estados para el cerebro de la hormiga.

Nótese que los estados E y G se tratan como si fuera un solo estado. En ambos se toca con la

antena izquierda, y el objetivo (local, para cumplir la estrategia) es dejar de tocar la pared.

El diagrama muestra que los estados B y C podrían tratarse como uno solo (son equivalentes).

Ya que tienen iguales salidas; y para iguales entradas, se pasa a igual estado próximo (más

adelante, en el Capítulo 12, se verán algoritmos para determinar estados equivalentes).

Si se funden los estados B y C se llega al siguiente diagrama, que representa el cerebro de la

hormiga:

Figura P9.4 Reducción de estados equivalentes.

I’ D

I + D

Perdido

(A)

E/G

(DI)

A

(DI, A)

B/C

(DD,

A)

D’

I’ D’

D L’ D’

I I + D

I’ D’



Problema 9.2. Contador sincrónico con control de modo M.

Si M = 0 el contador es binario ascendente; si M = 1 el contador avanza según código Gray. A

continuación se indican las secuencias:

binario: 000, 001, 010, 011, 100, 101, 110, 111

Gray: 000, 001, 011, 010, 110, 111, 101, 100

El diagrama de estados se construye para la secuencia binaria, con transiciones con entrada de

control igual a cero. Luego, se marcan las transiciones para contar en Gray:

Figura P9.5 Contador binario ascendente.

Figura P9.6 Contador Gray.

Problema 9.3. Reconocedor de un patrón finito.

Sean: entrada x y salida z. La salida se activa cada vez que se presenta la secuencia 010, y

mientras que la secuencia 100 no se haya presentado, en cuyo caso la salida se desactiva

permanentemente.

Ejemplos de secuencias, y columna vertebral del diagrama de estados:

X: 0 0 1 0 1 0 1 0 0 1 0 …

Z: 0 0 0 1 0 1 0 1 0 0 0 …

X: 1 1 0 1 1 0 1 0 0 1 0 …

Z: 0 0 0 0 0 0 0 1 0 0 0 …

S0

[000]

S1

[001] S2

[010]

S3

[011] S4

[100]

S5

[101]

S6

[110]

S7

[111] reset

0

0 0 0 0 0 0 0

S0

[000]

S1

[001]

S2

[010]

S3

[011]

S4

[100]

S5

[101]

S6

[110]

S7

[111]

reset

0

0 0 0 0 0 0 0

1

1

1

1

1 1

1 1



Figura P9.7 Diagrama de estados inicial.

Luego deben completarse las transiciones que faltan.

Si en E5 llega un cero, debe ir al estado permanente E6, ya que habría reconocido la secuencia

100. Si estando en E3 (los últimos 3 bits de la secuencia son 010) llega un 1, los últimos dos

serán ahora 01, esto implica pasar al estado E2.

En E1 debe permanecer si llegan secuencias de ceros. En E4 debe permanecer si llegan

secuencias de unos.

Si estando en E2 llega un uno, se tendrán dos unos seguidos, entonces debe pasarse al estado

E4.

Si estando en E5 llega un uno, se tendrá hasta ese momento, que los dos últimos de la secuencia

son 01, entonces debe pasarse al estado E2.

El diagrama final se muestra a continuación:

E1

[0]

E2

[0]

0

1

E3

[1]

0

E4

[0]

1

0,1

E5

[0]

0

0

E6

[0]

E0

[0]

reset



Figura P9.8 Diagrama de estados final.

Si denominamos X a la entrada, el diagrama puede describirse, según el pseudo código:

While (1)

{if (reset) estado = E0;

else switch (estado) { case E0: if (X) estado = E4 else estado = E1;

case E1: if (X) estado = E2 else estado = E1;





case E6: estado = E6;

}

}

Problema 9.4. Diseñar el control de una máquina de lavar ropa. Uso de temporizadores.

El funcionamiento de la lavadora es el siguiente:

Cuando se oprime el botón “Partida”, después de colocar las prendas, la máquina determina

el tamaño de la carga (Mediano / Grande) y de acuerdo al tamaño dispensa la cantidad de

agua y detergente.

Luego de esto, la máquina lava la ropa por 10 minutos.

1

...01

...010 ...100

E4

[0]

E1

[0]

E0

[0]

E2

[0]

1 0

1

reset

0, 1 E3

[1]

0

E5

[0]

0

0

E6

[0]

...1 ...0

1 0

1

1 ...10



Después del ciclo anterior, la máquina enjuaga las ropas por 10 minutos. Detecta si el

líquido de salida está sucio, al final del enjuague; en caso de estarlo, repite el ciclo (lavado +

enjuague), pero no más de 3 repeticiones.

Luego centrifuga las ropas hasta que no detecta descarga de agua, pero por no más de 20

minutos.

Las duraciones de los ciclos se logran con temporizadores. Los cuales pueden modelarse con

una entrada que inicia la cuenta del tiempo, y una salida que indica que ya transcurrió el tiempo

programado.

Entradas Salidas

Descripción Variable Descripción Variable

Botón de Partida SP Dispensador mediano AM

Sensor carga mediana SM Dispensador Grande AG

Sensor carga grande SG Actuador lavado AL

Sensor salida sucia SS Actuador enjuague AE

Sensor descarga salida SD Actuador centrífuga AC

Timeout 60 min O60 Inicio timer 60 min I60

Timeout 10 min O10 Inicio timer 10 min I10

Figura P9.9 Especificaciones de variables.

Figura P9.10 Diagrama de estados control lavadora.

Inicio

Lavado

Enjuage Centrífuga

1

Centrífuga

2

reset

SP’

(SP&SM) / AM, AL, I10, I60

#

(SP&SG) / AG, AL, I10, I60

O10’ / AL

O10 / I10

O10’ / AE

O10&SS&O60’&SM / AM, AL, I10

#

O10&SS&O60’&SG / AG, AL, I10

O10&SS’ # O60 / I10

O10’&SD / AC

O10&SD / I10 O10’&SD / AC

SD’

SD’ # O10



Problema 9.5. Detector secuencia 0101.

Determinar el diagrama de estados de una máquina secuencial (Modelo de Mealy) que produce

una salida alta cada vez que se detecta la secuencia 0101 en la entrada; y salida cero en el resto

de los casos. Determinar la secuencia de salida y de estados para la siguiente secuencia de

entrada: 010110011…

Solución.

Figura P9.11 Diagrama de estados detector secuencia 0101.

La siguiente secuencia de entrada produce las siguientes secuencias de salida y de transiciones

de estados.

Entrada 0 1 0 1 1 0 0 1 1 ....

Salida 0 0 0 1 0 0 0 0 0 ....

Pxo. Estado B C D C A B B C A ….

Figura P9.12 Secuencias de entrada, salida y de estados.

Problema 9.6. Máquina con dos salidas.

Un sistema secuencial tiene una entrada x, y dos salidas: z1 y z2.

Con x = 1, las salidas recorren las siguientes secuencias periódicas:

z1 0 1 1 0 1 0

z2 1 1 1 1 0 1

Con x = 0, las salidas recorren las siguientes secuencias periódicas:

z1 0 1 1 0 0 1

z2 1 1 0 1 1 1

a) Determinar la tabla o matriz de transiciones, de un modelo de Moore. Los estados se

identifican con letras mayúsculas y A es el estado inicial.

b) Dibujar el diagrama de estados.

c) Determinar las salidas para la siguiente secuencia de entrada: 000110010

1/0

1/0

0/0 1/0

1/1

0/0 A B C D

0/0

B B

0/0



Solución:

a) Una posible solución es elegir la secuencia de x = 1 para asignar los nombres a los estados y

a partir de esta asignación completar la matriz de transición de tal manera que se cumpla con la

secuencia para x = 0.

En ambas secuencias las salidas pasan por seis estados, teniendo estados con iguales salidas las

soluciones pueden ser combinaciones de elecciones de estos estados, pero deben tenerse los seis

estados

Son posibles otras soluciones de acuerdo a la asignación de los nombres de los estados.

Figura P9.13 Matrices de transiciones y de salida.

b) Diagrama de estados de acuerdo a la matriz de transición en a)

Figura P9.14 Diagrama de estados Problema 9.6.

x

Estado

0 1

A C B

B A C

C E D

D B E

E F F

F D A

Salida

Estado

z2z1

A 10

B 11

C 11

D 10

E 01

F 10

A

10

B

11

C

11

D

10

E

01

F

10

1

1

1 1

1

1

0

0

0

0

0

0



c) Determinar las salidas para la siguiente secuencia de entrada: 000110010

Entrada Reset 0 0 0 1 1 0 0 1 0 -

Estado Actual - A C E F A B A C D B

Próximo Estado A C E F A B A C D B -

Salida (z2z1) 10 10 11 01 10 10 11 10 11 10 11

Problema 9.7. Máquina con dos entradas.

Para una máquina secuencial con dos entradas c1 y c0. A es el estado inicial.

Se tienen:

Con c1 = 0 y c0 = 0 el sistema recorre la siguiente secuencia periódica de estados: ABCD.

Con c1 = 1 y c0 = 1 el sistema recorre la siguiente secuencia periódica de estados: ADCB.

Con c1 = 1 y c0 = 0 el sistema recorre la siguiente secuencia periódica de estados: ADBC.

Con c1 = 0 y c0 = 1 el sistema recorre la siguiente secuencia periódica de estados: ABD. Y

si está en estado C, permanece en él.

a) Determinar la tabla o matriz de excitaciones.

b) Determinar la secuencia de estados para la siguiente secuencia de entradas:

c1 0 0 1 0 0 1

c0 0 0 0 1 1 1

Solución:

Se asume que al cambiar las entradas, mientras se genera una secuencia, se continúa con el

próximo estado de acuerdo a las entradas. Es decir no se retorna a un estado inicial.

Figura P9.15 Diagrama de estados Problema 9.7.

A

B D

C

0

0 00

C1C0 0

11

11 11

1

10

10

01 01

reset



a)

Figura P9.16 Matriz de transiciones Problema 9.7.

b)

Figura P9.17. Secuencias de estados Problema 9.7.

Estado inicial A. (se está en A y las entradas son 00)

Los cambios de estado ocurren en un canto del reloj.

Se inspeccionan las entradas antes de cada canto del reloj.

La secuencia de estados es: ABCABDC....

Problema 9.8. Máquina de estados finitos. Tres salidas.

Se tiene una máquina secuencial de Moore, con una entrada x, y tres salidas: z1, z2 y z3.

Cada vez que se presenta la secuencia 01 en la entrada, las salidas toman valores:

z1=1, z2=0 y z3=0.

Cada vez que se presenta la secuencia 10 en la entrada, las salidas toman valores:

z1=0, z2=1 y z3=0.

Cuando se presenta la secuencia 00 en la entrada, vuelve al estado inicial, con salidas: z1=0,

z2=0 y z3=0; y desde allí reanuda el análisis de las secuencias; es decir, vuelve a comenzar.

Cuando se presenta la secuencia 11 en la entrada, permanece en el estado al cual llegó, con

salidas: z1=0, z2=0 y z3=1.

En el resto de los casos las salidas toman valores: z1=0, z2=0 y z3=0.

Determinar:

a) El diagrama de estados.

b) La tabla de transiciones entre estados.

c) Diseño de ecuaciones para las salidas, mediante un mapa de Karnaugh. Indicar el nombre

elegido para las variables de estado y los nombres binarios elegidos para los estados lógicos.

Solución.

Entradas c1c0

Estado 00 01 11 10

A B B D D

B C D A C

C D C B A

D A A C B

Próximo estado

c1 0 0 1 0 0 1 ..

c0 0 0 0 1 1 1 ..

Estado Actual A B C A B D C

Próximo estado B C A B D C



a) Si los estados se denominan por xx, con significado: “los dos últimos de la secuencia son

xx”, esta interpretación vale para los nombres: 01, 10 y 11. Se usa el símbolo _ _ para indicar el

estado inicial, en el cual aún no han llegado entradas, o al que se llega después de recibir una

secuencia 00.

El nombre _0 se usa para el estado al que pasa la máquina cuando ha llegado un cero, estando

en el inicial. Y _1 se usa para el estado al que pasa la máquina cuando ha llegado un uno,

estando en el inicial.

b) A partir del diagrama de estados se obtienen las matrices de transición y de salida.

Figura P9.18. Diagrama de estados y tabla transiciones Problema 9.8.

c) Si el estado es Q2Q1Q0, y se escoge la siguiente asignación:

Figura P9.19. Asignación de estados Problema 9.8.

Resultan:

Estado

lógico

Estado

Físico

Q2Q1Q0

z1 z2 z3

_ _ 000 0 0 0

11 001 0 0 1

011

10 010 0 1 0

_ 0 110 0 0 0

_ 1 111 0 0 0

101

01 100 1 0 0

_ _

_1 _0

01 10

11

reset

0 1

0

1 0

000

000 000

100 010

001

1

1

1

0

0

x

Estado 0 1

_ _ _0 _1

_0 _ _ _ 1

_1 10 11

01 10 11

10 _ _ 01

11 11 11

Próximo Est.

Estado

lógico

z1 z2 z3

_ _ 0 0 0

_0 0 0 0

_1 0 0 0

01 1 0 0

10 0 1 0

11 0 0 1



z1 = Q2Q1’

z2 = Q2’Q1

z3 = Q2’Q0 y también Q1’Q0

Observaciones.

Estando en el estado inicial, cuando llega un uno o un cero, no pueden activarse las salidas z1,

z2 y z3. Ya que éstas reconocen las secuencias 01, 10 y 11 respectivamente; y no la presencia de

un cero o de un uno.

La frase: “Cuando se presenta...” es imperativa. Y tiene precedencia sobre las frases: “Cada vez

que se presente...”.

Por ejemplo, si llega la secuencia 001..., después de los dos ceros debe ir al estado inicial, y

volver a analizar. El estado inicial representa la situación en que aún no han llegado entradas, o

después de que llegó la secuencia 00.

Otro ejemplo, si llega la secuencia 1101...., va inmediatamente al estado 11, y no reconoce la

secuencia 01 que la sigue; tampoco debe reconocer la secuencia 10 que está también presente en

1101....

Con las especificaciones dadas, y la designación de los nombres dados antes, el diagrama queda

como sigue.

Figura P9.20. Diagrama de estados Problema 9.8.

Para completar el diagrama hay que agregar estados adicionales, entre el inicial y los estados

denominados 01 y 10. Aparecen los estados _0 y _1.

Si desde el estado inicial, con entrada cero, fuera al estado 10, detectaría la secuencia 10 cuando

sólo ha llegado un cero.

_ _

01 10

11

reset

0 1

1 0

000

100 010

001 1

1

0

0

Llegó 01

Llegó 10

Llegó 11

Llegó 00

No ha llegado nada

? ?



Si desde el estado inicial, con entrada uno, fuera al estado 01, detectaría la secuencia 01 cuando

sólo ha llegado un uno.

Ir al estado inicial implica comenzar de nuevo. Al estado inicial se llega después de aplicar

energía, o después de una activación de la señal reset.

El mismo diseño empleando un modelo de Mealy:

Figura P9.21. Modelo de Mealy Problema 9.8.

z1 = Q1Q0’x

z2= Q1’Q0 x’

z3= Q1Q0 + Q0 x

Problema 9.9.

Si x es una entrada, se tienen las ecuaciones que programan tres flip-flops Ds.

D2 = Q2’Q1Q0’x, D1= Q2’Q0 + Q1Q0 + Q2’Q1x, D0 = Q2’x + Q1Q0x

Y las siguientes ecuaciones para las salidas: z1 = Q2’Q1Q0, z0 = Q2Q1Q0

En funcionamiento normal, un pulso en la entrada reset, deja al sistema en el estado binario 000.

Determinar:

a) Si la máquina es de Mealy o de Moore. En qué basa su respuesta.

b) Matriz de transiciones.

c) Diagrama de estados. Indicar los estados que no participan en el trabajo normal del sistema

secuencial.

d) Acciones que realiza la máquina de estados, considerando que el estado binario 000 es el

estado inicial.

e) Indicar secuencias de estado y de salida para la secuencia de entrada:

A

B C

D

reset

0/000

1/000

0/000

1/001

/001 0/010

1/100

Estado

Lógico

presente

Estado

Físico

Q1Q0

x=0 x=1

A 00 B/000 C/000

B 10 A/000 C/100

C 01 B/010 D/001

D 11 D/001 D/001

Próximo estado/z1z2z3



Solución:

a) Las salidas sólo dependen del estado. Puede aplicarse el modelo de Moore.

b) Matriz de transiciones.

Figura P9.22. Matriz de transiciones Problema 9.9.

c) Diagrama de estados.

En funcionamiento normal no se pasa por los estados 110, 101 y 100.

No se puede llegar a ellos si la máquina parte en el estado inicial. Sin embargo están definidos

sus estados próximos como el estado inicial.


d) Acciones.

Reconoce la secuencia 101 cada vez que se presente, con salida z1=1 y z0 = 0.

Q2Q1Q0 x = 0 x = 1 Salidas

000 000 001 00

001 010 011 00

011 010 011 01

010 000 111 00

110 000 000 00

111 010 011 10

101 000 000 00

100 000 000 00

Q2+Q1+Q0+ z0z1

reset

0 000

_ _ 00

001

_ _ 00

010

_ _ 00

111 10

1 0 1

011 01

1

1

1

0

0 0

110 00

101 00

100 00

Q2Q1Q0

Z0Z1

Número

secuencia

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

x 1 0 1 1 1 0 1 0 1 1 1 1 0 0 1 1 .

Estado actual 000

Z1

Z0



Reconoce las secuencias de dos a más unos seguidos cada vez que se presenten, con salida z1=1

y z0 = 0.

Cuando llega la secuencia 100 vuelve al estado inicial con salida z1 = 0 y z0 = 0.

e) Secuencias de estados y de salida.

Figura P9.24. Secuencias Problema 9.9.

Problema 9.10. Sensores

Se tienen dos sensores i y d (izquierda y derecha) ubicados a cierta distancia sobre el suelo de

un pasillo y cuyo objetivo es detectar la dirección del paso de personas por el pasillo.

Estando la persona ubicada en la zona izquierda, con ambos sensores en cero, si la persona

avanza hacia la derecha y llega a la zona donde nuevamente ambos sensores son cero, debe

indicarse con la señal z1 =1.

Estando la persona ubicada en la zona derecha, con ambos sensores en cero, si la persona

avanza hacia la izquierda y llega a la zona donde nuevamente ambos sensores son cero, debe

indicarse con la señal z0 =1.

En el resto de los casos, las salidas deben ser ceros.

Las personas pueden quedarse detenidas o retroceder, pero sólo deben generarse las salidas

cuando se cumplen las condiciones anteriores.

Se ilustran los valores de los sensores cuando un objeto ocupa total o parcialmente las zonas

indicadas. Hacia la extrema izquierda y derecha los sensores marcan cero.

Figura P9.25. Diagrama sensores Problema 9.10.

Número

secuencia

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

x 1 0 1 1 1 0 1 0 1 1 1 1 0 0 1 1 .

Est. actual 000 001 010 111 011 011 010 111 010 111 011 011 011 010 000 001 011

Z0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0

Z1 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1

i d

i d

00 00

10 01

11



Determinar el diagrama de estados (modelo de Mealy) que modela el sistema. Indicar el estado

inicial, y la señal de reset.

Solución.

Todas las salidas son cero, excepto las de los estados F y G, con entradas 00.

De cada estado deben especificarse las transiciones que físicamente son permitidas. Por ejemplo

estando en el estado A, no puede presentarse el evento de que ambas entradas estén un uno. Si

por ejemplo la persona está ubicada en la zona con los dos sensores activos, es decir en los

estados D y E, las transiciones que deben especificarse son las correspondientes a las

combinaciones 11, 01 y 10 de las entradas; no puede presentarse, en esta situación, el evento de

que ambas entradas estén en cero.

En F con entradas 00 se activa la salida z1.

En G con entradas 00 se activa la salida z0.


Problema 9.11. Formas de ondas.

Se tiene un un sistema secuencial con entrada x y salidas y, z.

La señal reset deja al sistema en su estado inicial, con ambas salidas iguales a cero.

Se activa z cada vez que llega la secuencia 010 en la entrada y mientras no llegue la secuencia

100. Cuando llega esta última se activa la salida y, y la máquina permanece en ese estado.

Se tienen las siguientes formas de ondas:

reset

A 00

B C

D E

F G

10

11

01 10

11

01

11 10 01

11

11 01 10

11

00 00

01 10

00/10 00/01



Figura P9.27. Formas de ondas Problema 9.11.

1. Observando las formas de ondas:

a). Indicar si el evento sincronizante es el canto de subida o el de bajada.

b). Determinar si la secuencia temporal de entrada es sincrónica con el reloj.

c). Determinar si la secuencia de entrada garantiza un funcionamiento seguro de los flip-flops.

d). Determinar si la máquina puede ser representada por un diagrama de Mealy o de Moore,

indicando si las salidas dependen de la entrada.

e). Determinar si lo que lleva al estado inicial es el canto de subida o de bajada de reset.

f). Determinar las secuencias sincrónicas de valores que toman: x, y, z.

2. Determinar el diagrama de estados.

Solución.

Figura P9.28. Análisis de formas de ondas Problema 9.11.

a) Observando las salidas y, z se advierte que el evento sincronizante es el canto de subida, ya

que los cambios de éstas ocurren con el canto de subida del reloj.

b) La entrada x no tiene sus cambios asociados a los cantos del reloj, por lo tanto no es señal

sincrónica con el reloj.

c) Los cambios de las entradas ocurren un tiempo antes del canto del reloj y permanecen

estables después de un tiempo del canto de bajada. En la gráfica se requiere que t1 > ts y que

t2>th.

clk

reset

x

z

y

t1 > ts t2 > th



d) Se advierte que las salidas no son función de la entrada, por lo tanto puede usarse el modelo

de Moore.

e) El canto de subida de reset lleva al estado inicial.

f) Secuencias de valores de la entrada y las salidas. Debe inspeccionarse los niveles en el canto

de subida del reloj de las señales x, z, y. Existe un valor por cada canto de subida del reloj. Se

logran:

entrada x 0010101001011011010010100

salida z 0001010100000000001000000

salida y 0000000011100000000111111

2. Diagrama de estados. Se activa z cada vez que llega la secuencia 010 en la entrada y mientras

no llegue la secuencia 100. Cuando llega esta última se activa la salida y, y la máquina

permanece en ese estado.

Se forman los reconocedores de 010 y 100. Y se establecen las salidas asociadas al estado 3 y 6,

con z=1 e y=1 respectivamente.

Luego se completan las transiciones para cumplir generar salida z=1 para cada vez que se

presente la secuencia 010.

Luego se completan las transiciones para recocer la secuencia 100, apenas se presente.

Finalmente se completa las transiciones para permanecer en el estado 6 con salida y = 1.


El diagrama de Moore se interpreta: En la etapa k, el estado es Si; es decir, estando en Si, en la

etapa k, se analiza la entrada x(k) y se pasa al próximo estado en k+1.

S0/00

S1/0

0

0 0

S2/00

S4/00

S5/00

S3/01

1

S6/10

1

1

1

0

0

1

0

0

1

reset

Si/

x =

/yz



Otras soluciones:

Diagrama de Mealy:

Figura P9.30. Diagrama de estados de Mealy Problema 9.11.

S3 y S5 son equivalentes, ya que las transiciones que salen de S5, para iguales valores de las

entradas van con las mismas salidas a iguales estados próximos. Eliminando S5 se logra:

Figura P9.31. Diagrama de estados equivalente Problema 9.11.

S0

S1

0/00 0/00

S2

S4

S5

S3

1/00

S6 /10

1/00

1/00

1/0

00

0/01

0/0

0

1/00

0/10

0/10

1/00

reset

Si

x /yz

S0

S1

0/00 0/00

S2

S4

S3

1/00

S6 /10

1/00

1/00

1/0

00

0/01

0/0

0

0/10

1/00

reset

Si

x /yz



Referencias.

G. H. Mealy. A method for synthesizing sequential circuits, Bell System Technical Journal 34

(1955), 1045-1079.

E. F. Moore. Gedanken-Experiments on sequential machines, in Automata studies (editors C. E.

Shannon, J. McCarthy), Princeton University Press, 1956, 129-153.

Índice general.

CAPÍTULO 9 .............................................................................................................................................. 1

SISTEMAS SECUENCIALES .................................................................................................................. 1

9.1. DEFINICIONES .................................................................................................................................... 1 Evento .................................................................................................................................................. 1 Máquina abstracta. .............................................................................................................................. 1 Estado. ................................................................................................................................................. 1 Máquinas de estados. ........................................................................................................................... 2 Transición. ........................................................................................................................................... 2 Diagrama de estados. .......................................................................................................................... 2 Autómata de estados finitos determinista............................................................................................. 2 Tipos de máquinas. .............................................................................................................................. 2 Reloj. .................................................................................................................................................... 3 Máquinas secuenciales. ....................................................................................................................... 3 Máquinas secuenciales sincrónicas. .................................................................................................... 4 Síntesis lógica. ..................................................................................................................................... 4

9.2. SECUENCIAS. ...................................................................................................................................... 5 Ejemplos de secuencias. ....................................................................................................................... 5

a) Sincrónica de nivel. ...................................................................................................................................... 5 b) Sincrónica de pulsos .................................................................................................................................... 6 c) Asincrónica de nivel .................................................................................................................................... 6 d) Asincrónica de pulsos. ................................................................................................................................. 6

9.3. MODELO SECUENCIAL ........................................................................................................................ 6 9.4. REPRESENTACIÓN DE MÁQUINAS SECUENCIALES ............................................................................... 9

9.4.1. Modelo de Mealy ........................................................................................................................ 9 i) Diagrama de estados ..................................................................................................................................... 9 ii) Tabla de transición de estados ................................................................................................................... 10

9.4.2. Modelo de Moore ..................................................................................................................... 10 i) Diagrama de estados ............................................................................................................................. 11 ii) Tabla de transiciones ................................................................................................................................. 11

Ejemplo 9.1 ........................................................................................................................................ 12 Ejemplo 9.2. ....................................................................................................................................... 13 Ejemplo 9.3. ....................................................................................................................................... 14

Algunas observaciones sobre las representaciones: ....................................................................................... 15 Ejemplo 9.4. ....................................................................................................................................... 16 Ejemplo 9.5. Modelado de diagrama de estados. Lavadora. ............................................................. 17 9.4.3. Transformación de Mealy a Moore. ........................................................................................ 19



Ejemplo 9.6.Transformación para el reconocedor de dos unos seguidos. ...................................................... 21 Ejemplo 9.7. ................................................................................................................................................... 22

9.5. TIPOS DE MÁQUINAS SECUENCIALES ................................................................................................ 23 9.6 SÍNTESIS DE DIAGRAMAS DE ESTADO. MODELADO ......................................................................... 23

9.6.1 Reconocedor de secuencias de largo fijo. Verificador BCD ................................................... 24 9.6.2. Reconocedor continuo. ............................................................................................................ 25 9.6.3. Reconocedor continuo con reintento en caso de falla ............................................................. 26 9.6.4. Reconocedor continuo de códigos BCD válidos. .................................................................... 27 9.6.5. Del diagrama a la especificación. ........................................................................................... 28 9.6.6. Determinar conducta de la máquina secuencial ..................................................................... 29

PROBLEMAS RESUELTOS. ........................................................................................................................ 30 Problema 9.1. Cerebro de Hormiga. (Ant Brain. Propuesto en el MIT). ......................................... 30 Problema 9.2. Contador sincrónico con control de modo M. ........................................................... 33 Problema 9.3. Reconocedor de un patrón finito. .............................................................................. 33 Problema 9.4. Diseñar el control de una máquina de lavar ropa. Uso de temporizadores. ............. 35 Problema 9.5. Detector secuencia 0101. ........................................................................................... 37 Problema 9.6. Máquina con dos salidas. .......................................................................................... 37 Problema 9.7. Máquina con dos entradas. ........................................................................................ 39 Problema 9.8. Máquina de estados finitos. Tres salidas. .................................................................. 40 Problema 9.9. .................................................................................................................................... 43 Problema 9.10. Sensores ................................................................................................................... 45 Problema 9.11. Formas de ondas...................................................................................................... 46

REFERENCIAS. ........................................................................................................................................ 50 ÍNDICE GENERAL. ................................................................................................................................... 50 ÍNDICE DE FIGURAS ................................................................................................................................. 52



Índice de figuras

Figura 9.1 Máquina abstracta. ....................................................................................................... 1 Figura 9.2 Modelo de Moore. ........................................................................................................ 3 Figura 9.3 Modelo de Moore sincrónico. ...................................................................................... 4 Figura 9.4 Circuito digital C(G, W). .............................................................................................. 4 Figura 9.5. Secuencia sincrónica de niveles. ................................................................................. 5 Figura 9.6. Secuencia sincrónica de pulsos. .................................................................................. 6 Figura 9.7. Secuencia asincrónica de niveles. ............................................................................... 6 Figura 9.8. Secuencia asincrónica de pulsos. ................................................................................ 6 Figura 9.8. a. Modelo de memoria. ................................................................................................ 7 Figura 9.9. Modelo de Mealy. ....................................................................................................... 9 Figura 9.10. Diagrama de estados de Mealy. ................................................................................ 9 Figura 9.11. Tabla de transición de estados de Mealy. FPE. ....................................................... 10 Figura 9.12. Matriz de transiciones y matriz de salida. ............................................................... 10 Figura 9.13. Modelo de Moore .................................................................................................... 11 Figura 9.14. Diagrama de estados de Moore. .............................................................................. 11 Figura 9.15. Tabla de transiciones modelo de Moore. ................................................................ 11 Figura 9.16. Matriz de transiciones ejemplo 9.1. ........................................................................ 12 Figura 9.17. Secuencia de salida y de estados. ............................................................................ 12 Figura 9.18. Esquema generador de secuencias. ......................................................................... 12 Figura 9.19. Diagrama de Estados ejemplo 9.1. .......................................................................... 13 Figura 9.20. Diagrama de estados de Ejemplo 9.2. ..................................................................... 13 Figura 9.21. Secuencia de salida Ejemplo 9.2. ............................................................................ 13 Figura 9.22. Tabla de transiciones Ejemplo 9.2 .......................................................................... 14 Figura 9.23. Diagrama de Moore Ejemplo 9.3. ........................................................................... 14 Figura 9.23a. Secuencia de salida modelo de Moore Ejemplo 9.3. ............................................. 14 Figura 9.24 Diagrama de Mealy Ejemplo 9.3. ............................................................................ 15 Figura 9.24a. Secuencia de salida modelo de Mealy Ejemplo 9.3. ............................................. 15 Figura 9.24b. Salidas registradas en modelo de Mealy. .............................................................. 16 Figura 9.24c. Modelo de Moore. Salida registrada. .................................................................... 16 Figura 9.25. Diagramas de Mealy y Moore ejemplo 9.4. ............................................................ 17 Figura 9.26. Lavadora. ................................................................................................................. 17 Figura 9.27. Diagrama de estados de la Lavadora. ...................................................................... 18 Figura 9.28. Diagrama de estados ampliado de la Lavadora. ...................................................... 19 Figura 9.29. Separación de estados. ............................................................................................ 19 Figura 9.30. Conversión a Moore. ............................................................................................... 20 Figura 9.31. Estado inicial con salida cero. ................................................................................. 20 Figura 9.32. Estado inicial con salida uno. .................................................................................. 20 Figura 9.33. Agregar estado inicial. ............................................................................................ 20 Figura 9.34. Separación de estado S1. ......................................................................................... 21 Figura 9.35. No es necesario corregir S0. .................................................................................... 21 Figura 9.36. Diagrama de Moore ejemplo 9.6. ............................................................................ 22 Figura 9.37. Representación de Moore Ejemplo 9.7. .................................................................. 22 Figura 9.38. Representación de Mealy Ejemplo 9.7. ................................................................... 23



Figura 9.39 Diagrama en bloque verificador BCD. .................................................................... 24 Figura 9.40 Diagrama de estados verificador BCD. .................................................................... 24 Figura 9.41 Diagrama de estados reducido del verificador BCD. ............................................... 25 Figura 9.42 Reconocedor de secuencia 0101. ............................................................................. 25 Figura 9.43 Diagrama de estados completo del reconocedor continuo. ...................................... 26 Figura 9.44 Diagrama de estados inicial. .................................................................................... 27 Figura 9.45 Diagrama de estados completo. ............................................................................... 27 Figura 9.46 Estados siguientes al estado 001. ............................................................................. 27 Figura 9.47 Diagrama de estados completo, sin salida. .............................................................. 28 Figura 9.48 Tabla de verdad de la función de salida. .................................................................. 28 Figura 9.49 Diagrama de estados Ejemplo 9.6.5. ........................................................................ 29 Figura 9.50 Diagrama de estados ejemplo 9.6.6. ........................................................................ 29 Figura P9.1 Laberinto. ................................................................................................................. 30 Figura P9.2 Esquema de situaciones. Definición de estados. ...................................................... 31 Figura P9.3 Diagrama de estados para el cerebro de la hormiga. ............................................... 32 Figura P9.4 Reducción de estados equivalentes. ......................................................................... 32 Figura P9.5 Contador binario ascendente. ................................................................................... 33 Figura P9.6 Contador Gray. ........................................................................................................ 33 Figura P9.7 Diagrama de estados inicial. .................................................................................... 34 Figura P9.8 Diagrama de estados final. ....................................................................................... 35 Figura P9.9 Especificaciones de variables. ................................................................................. 36 Figura P9.10 Diagrama de estados control lavadora. .................................................................. 36 Figura P9.11 Diagrama de estados detector secuencia 0101. ...................................................... 37 Figura P9.12 Secuencias de entrada, salida y de estados. ........................................................... 37 Figura P9.13 Matrices de transiciones y de salida. ..................................................................... 38 Figura P9.14 Diagrama de estados Problema 9.6. ....................................................................... 38 Figura P9.15 Diagrama de estados Problema 9.7. ....................................................................... 39 Figura P9.16 Matriz de transiciones Problema 9.7. ..................................................................... 40 Figura P9.17. Secuencias de estados Problema 9.7. .................................................................... 40 Figura P9.18. Diagrama de estados y tabla transiciones Problema 9.8. ...................................... 41 Figura P9.19. Asignación de estados Problema 9.8. ................................................................... 41 Figura P9.20. Diagrama de estados Problema 9.8. ...................................................................... 42 Figura P9.21. Modelo de Mealy Problema 9.8. ........................................................................... 43 Figura P9.22. Matriz de transiciones Problema 9.9. .................................................................... 44 Figura P9.23. Diagrama de estados Problema 9.9. ...................................................................... 44 Figura P9.24. Secuencias Problema 9.9. ..................................................................................... 45 Figura P9.25. Diagrama sensores Problema 9.10. ....................................................................... 45 Figura P9.26. Diagrama de estados Problema 9.10. .................................................................... 46 Figura P9.27. Formas de ondas Problema 9.11. .......................................................................... 47 Figura P9.28. Análisis de formas de ondas Problema 9.11. ........................................................ 47 Figura P9.29. Diagrama de estados Problema 9.11. .................................................................... 48 Figura P9.30. Diagrama de estados de Mealy Problema 9.11. .................................................... 49 Figura P9.31. Diagrama de estados equivalente Problema 9.11. ................................................ 49

Documents

cap9