1

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.

Acciones

Mensajes Máquina

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.

Profesor Leopoldo Silva Bijit

19-01-2010

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: Profesor Leopoldo Silva Bijit

19-01-2010

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). Reset x

FPE

M Y

FS y

z

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 Profesor Leopoldo Silva Bijit

19-01-2010

4

Sistemas Digitales

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. Reset’ x

FPE

M Y

D Q

FS y

z

Clk

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).

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

5

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:

xi (t ) = xi (t0 ), xi (t1 ), xi (t2 ), ..., xi (tk ),... xi (tn )... Con: tk

t0 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 tk describe los valores que toma una variable aleatoria; en este caso se dice que la secuencia es asincrónica. Las variables xi , 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.

xi (k )

xi (0), xi (1), xi (2), ..., xi ( k ),... xi ( n)...

Ejemplos de secuencias. a) Sincrónica de nivel. 0

1

2

3

4

5

6

7

8

9

(valores de k)

t0 ... xn = { 0

1

0

0

1

1

0

1

0

0

... }

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.

Profesor Leopoldo Silva Bijit

19-01-2010

6

Sistemas Digitales

b) Sincrónica de pulsos reloj

xp = { 0,

1,

0,

0,

1,

1,

0,

1,

0,

0, ... }

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

t0

t1

t2

t3

t4

t5

xa = { 0

1

0

1

0 1 ...}

Figura 9.7. Secuencia asincrónica de niveles. Los intervalos ti tienen una duración aleatoria. d) Asincrónica de pulsos.

t

t

0

1

t

2

t

3

t

4

t

5

t

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.

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

7

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:

 y (t

 t ) Y (t )

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:

y j (k 1) = Y j (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 y j (k 1) son estables, pero los valores Y j (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 Y j (k ) ; la salida de esa memoria, en el mismo intervalo, es y j (k ) . Y(k)

y(k+1) Y(k)

k

y(k)

k+1

Figura 9.8. a. Modelo de memoria.

Profesor Leopoldo Silva Bijit

19-01-2010

8

Sistemas Digitales

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:

zi

FSi ( x1 ,.., xn , y1 ,.. ym )

i (1.. p)

Yj

FPE j ( x1 ,.., xn , y1 ,.. ym )

j (1..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:

y j (k 1)

FPE j ( x1 (k ),...xn (k ), y1 (k ),... ym (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:

y (0)

y (1)

y (2)

y (3)

x (0)

x (1)

x (2)

x (3)

....... ..

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:

y (k 1) = 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:

y(k 1)

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.

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

9

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. Reset’ x

z

M

FS FPE

Y

DQ

y

Clk

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: y2 x/z y1 Figura 9.10. Diagrama de estados de Mealy. El diagrama anterior puede leerse: Estando en el estado y1 , cuando llega la entrada x se pasa al estado y2 , con salida z.

Profesor Leopoldo Silva Bijit

19-01-2010

10

Sistemas Digitales

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: x

Y/z

y

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. x x

y

Y Y(x,y) Matriz Transiciones

y

z

z(x,y) Matriz de salida

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.

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

11 Reset’

x(k)

FPE

M y(k+1)

D Q

FS y(k)

z(k)

Clk

Figura 9.13. Modelo de Moore i) Diagrama de estados y2/z2 x y1/z1 Figura 9.14. Diagrama de estados de Moore. El diagrama anterior, puede leerse: Estando en estado y1 , con salida z1 ; cuando ocurre la entrada x se pasa al estado y2 , con salida z2 . La salida no cambia en la transición; por esta razón, las salidas se asocian a los estados. x

ii) Tabla de transiciones

y

Y

y

z

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.

Profesor Leopoldo Silva Bijit

19-01-2010

12

Sistemas Digitales

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: X Estado A B C D

0

1

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 Entrada Estado actual Próximo estado Salida

0 0 A D 0

1 1 D B 1

2 1 B A 0

3 0 A D 0

4 1 D B 1

5 0 B B 1

6 1 B A 0

7 1 A C 1

8 0 C C 1

9 10 0 0 C C C C 1 1

Figura 9.17. Secuencia de salida y de estados. La máquina de Mealy anterior, se comporta como un generador de secuencias.

z

x

...

... 0123..

012...

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: Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

13 1/1 A

0/1

C 0/0 0/0

1/0

1/0

B

D

0/1

1/1

Figura 9.19. Diagrama de Estados ejemplo 9.1. Ejemplo 9.2. Determinar la secuencia de estados para la siguiente máquina de Moore: 1 0 A/1

C/0 0

1

1

0 B/0

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 Entrada Estado presente Estado próximo Salida

0 0 C B 0

1 0 B A 0

2 0 A A 1

3 1 A B 1

4 1 B C 0

5 1 C A 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:

Profesor Leopoldo Silva Bijit

19-01-2010

14

Sistemas Digitales Estado actual A B C

Entrada x 0 1 A B A C B A Próximo Estado

Estado Salida A 1 B 0 C 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: 1 1 0 0 Inicio

Estado0

0

0

Estado1

Estado2

1

0

1

0 1 reset

0 Figura 9.23. Diagrama de Moore Ejemplo 9.3. Moore Entrada Estado presente Estado próximo Salida

0 0

1 1

2 1 Inicio Inicio Est0 Inicio Est0 Est1 0 0 0

3 0 Est1 Est2 0

4 1 Est2 Est0 1

5 1 Est0 Est1 0

Figura 9.23a. Secuencia de salida modelo de Moore Ejemplo 9.3. El diagrama de Mealy requiere tres estados:

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

15 1/0

1/0 0/0

1/0 Inicio

Estado 0

Estado 1

0/0

0/1 reset Figura 9.24 Diagrama de Mealy Ejemplo 9.3. Mealy Entrada Estado presente Estado próximo Salida

0 0

1 1

2 3 4 5 1 0 1 1 Inicio Inicio Est0 Est1 Inicio Est0 Inicio Est0 Est1 Inicio Est0 Est1 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 flipflop. Esto se muestra en la Figura 9.24b, donde la salida zr , 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.

Profesor Leopoldo Silva Bijit

19-01-2010

16

Sistemas Digitales Reset’ x(k)

z(k+1)

M

FS FPE

y(k+1)

D Q

zr(k) y(k)

Clk

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. Reset’ x(k)

M

FS FPE

y(k+1)

DQ

zr(k) y(k)

Clk

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.

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

17

reset reset

0 S0/0

0/0

S0

1

0

1/0

0/0

0

S1/0

S1 1 1

1/1

S2/1

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.

encender

detener

lavar

L

puerta

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. Profesor Leopoldo Silva Bijit

19-01-2010

18

Sistemas Digitales

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. Encender/ L Lavar/ L

Apagada

Encendida

Puerta/ L’

Lavando

Detener/ L

Puerta/ L’

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. Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

19

Apagada

Encender/ L

Puerta/ L’

Puerta/ L’

Puerta/ L’ Encendida

Lavar/ L

Detener/ L Rotar Derecha 1/ G’

Izquierda/ G

Puerta/ L’

Rotar

Rotar

Puerta/ L’

Derecha/ G’

Izquierda 1/ G

Rotar

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: x/0 x/0

Sa0

Sa x/1

Sa1 x/1 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:

Profesor Leopoldo Silva Bijit

19-01-2010

20

Sistemas Digitales

Sa0/0

x

Sa1/1 x 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.

reset

S/0

Figura 9.31. Estado inicial con salida cero. b2) Estado inicial con salida diferente de cero.

S/1 reset 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:

S/1

Si/0 reset Figura 9.33. Agregar estado inicial.

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

21

Ejemplo 9.6.Transformación para el reconocedor de dos unos seguidos. Al modificarse el estado S1 del diagrama de Mealy, resulta: reset 0/0

reset 0/0

S0

S0

1/0

0/0 0/0

1/0

0/0

S10

S1 1/1 1/1 1/1

S11

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. reset 0/0 S0 0/0

1/0 0/0

S10 1/1 1/1 S11

Figura 9.35. No es necesario corregir S0. Finalmente puede plantearse:

Profesor Leopoldo Silva Bijit

19-01-2010

22

Sistemas Digitales reset 0 S0/0 1

0

0

S10/0 1 1 S11/1

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. 0 1

B/0 0

D/1

0

reset A/0

1

0

1

1 C/0 1

0

E/1

reset entrada estado próximo salida actual estado 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.37. Representación de Moore Ejemplo 9.7. En un diagrama de Mealy, se especifican las salidas asociadas a las transiciones.

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

23

0/0 B 0/0 reset A

1/1

0/1 1/0 C

reset entrada Estado próximo salida actual estado 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

1/0

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.

Profesor Leopoldo Silva Bijit

19-01-2010

24

Sistemas Digitales

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:

z

M.S.

x

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. Estado Inicial

a 1/0

0/0

c

b 0/0

0/0

1/0

d 0/0

e

h 0/0

0/0

1/0

1/0 0/0

1/0

0/0

g

f 0/0

1/0

j

i

1/0

l

k 1/0 0/0

1/0 0/0

0/0

1/0

n

m 1/0 0/1

1/0

1/1 0/1

o 1/1 0/1

1/1

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:

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

25

a

1/0

0/0 b

e

1/0

0/0

/0 c

f

/0 /0 /0

1/0

g /0

0/0 h

d /0

/1

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 flipflops 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: la salida debe ser:

0, 1, 0, 1, 0, 1, ... 0, 0, 0, 1, 0, 1, ...

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

A

B 0/0

C 1/0

D 0/0 1/1

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. Profesor Leopoldo Silva Bijit

19-01-2010

26

Sistemas Digitales

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: 1/0 0/0 1/0

0/0

B B

A

D

C

0/0

1/0 1/1 0/0

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

B

A

1/0

0/0 C

D

0/0 0/1

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

27

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:

0/0

1/0 E 1/0 A

1/0

0/0 B

0/0

0/0

C

1/0

D

0/1

1/0

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: 001 1

011

0

010

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.

Profesor Leopoldo Silva Bijit

19-01-2010

28

Sistemas Digitales 0 000 1

0 1

001

100

0 0

010 1

0

1

0

101

1

1

011

110

0 1

0 111 1

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. Estado 000 001 010 011 100 101 110 111

x 0 0 0 0 0 0 1 1 1 z

1 0 0 0 0 0 1 1 1

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.

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

29

Asumir estado 1 como estado inicial. 0/0 1/0 1

1/0

1/0

2

3

1/0

0/0

5

4

0/0 0/0 0/1, 1/1

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 A 0/0

1/0 1/0

0/0

B

1/1

C

1/0

/0

/0 0/0

D

E

1/0 F

/0 0/0 G

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.

Profesor Leopoldo Silva Bijit

19-01-2010

30

Sistemas Digitales

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).

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

31

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: 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. Figura P9.2 Esquema de situaciones. Definición de estados. Profesor Leopoldo Silva Bijit

19-01-2010

32

Sistemas Digitales

No se encuentran otras situaciones que no se hayan planteado, entonces se procede a conectar los diferentes estados, mediante el siguiente diagrama: I+D Perdido (A)

I+D

I’ D

E/G (DI) D

I’ D’

I’ D’

A (DI, A)

I

D

I’ D’ B

C

(DD, A)

(DD, A)

D’

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: I+D Perdido (A)

E/G (DI)

I+D

I’ D

D

L’ D’

I’ D’

A (DI, A)

I

I’ D’

D’

B/C (DD, A)

Figura P9.4 Reducción de estados equivalentes. Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

33

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: 0

reset

S0 [000]

0

S1 [001]

S2 [010]

0

S3 [011]

0

0

S4 [100]

0

S5 [101]

S6 [110]

0

0

S7 [111]

Figura P9.5 Contador binario ascendente. 0

reset

S0 [000]

0

S1 [001]

0

S2 [010]

0

S3 [011]

0

0

S4 [100]

S5 [101]

0

0

S6 [110]

S7 [111]

1 1

1

1

1 1

1

1

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 …

Profesor Leopoldo Silva Bijit

19-01-2010

34

Sistemas Digitales

E0

reset

[0] 0

1

E1

E4

[0]

[0]

1

0 E2

E5

[0]

[0]

0

0 E3

E6

[1]

[0]

0,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:

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

35

E0

reset

[0] 0 0

E1

E4

[0]

[0]

...0

1

1

0 1

E5

[0]

0

...010

...1 1

E2 ...01

1

[0] 1

...10

0

E3

E6

[1]

[0]

...100

0, 1

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 E2: if (X) estado = E4 else estado = E3; case E3: if (X) estado = E2 else estado = E6; case E4: if (X) estado = E4 else estado = E5; case E5: if (X) estado = E2 else estado = E6; 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.

Profesor Leopoldo Silva Bijit

19-01-2010

36

Sistemas Digitales

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 Descripción Botón de Partida Sensor carga mediana Sensor carga grande Sensor salida sucia Sensor descarga salida Timeout 60 min Timeout 10 min

Variable SP SM SG SS SD O60 O10

Salidas Descripción Dispensador mediano Dispensador Grande Actuador lavado Actuador enjuague Actuador centrífuga Inicio timer 60 min Inicio timer 10 min

Variable AM AG AL AE AC I60 I10

Figura P9.9 Especificaciones de variables.

reset SD’ # O10

SP’

Inicio SD’

(SP&SM) / AM, AL, I10, I60 # (SP&SG) / AG, AL, I10, I60

Centrífuga

2 O10’&SD / AC

Lavado

O10&SD / I10

O10’ / AL O10&SS&O60’&SM / AM, AL, I10 # O10&SS&O60’&SG / AG, AL, I10

O10 / I10

Centrífuga

Enjuage

O10’ / AE

1

O10&SS’ # O60 / I10 O10’&SD / AC

Figura P9.10 Diagrama de estados control lavadora.

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

37

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. 1/0 0/0 1/0

0/0

B B

A

C

0/0

D

1/0 1/1 0/0

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 Salida Pxo. Estado

0 0 B

1 0 C

0 0 D

1 1 C

1 0 A

0 0 B

0 0 B

1 0 C

1 0 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 Profesor Leopoldo Silva Bijit

19-01-2010

38

Sistemas Digitales

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. x 0 1 Estado A B C D E F

C A E B F D

Salida z2z1 Estado A 10 B 11 C 11 D 10 E 01 F 10

B C D E F A

Figura P9.13 Matrices de transiciones y de salida. b) Diagrama de estados de acuerdo a la matriz de transición en a)

0

A 10

1

1

F 10

B 11 0

1

1

0 0

E 01 0

1

D 10

C 11

0

1

Figura P9.14 Diagrama de estados Problema 9.6.

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

39

c) Determinar las salidas para la siguiente secuencia de entrada: 000110010 Entrada Estado Actual Próximo Estado Salida (z2z1)

Reset 0 0 0 1 1 0 0 1 0 A C E F A B A C D B A C E F A B A C D B 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. reset

A

0

0

C1C0 1

11 10

D

B

10 11

11 0

00 C 01

01 Figura P9.15 Diagrama de estados Problema 9.7.

Profesor Leopoldo Silva Bijit

19-01-2010

40

Sistemas Digitales

a) Estado A B C D

Entradas c1c0 01 11 B D D A C B A C Próximo estado

00 B C D A

10 D C A B

Figura P9.16 Matriz de transiciones Problema 9.7. b)

c1 c0

0 0 Estado Actual A Próximo estado B

0 0 B C

1 0 C A

0 1 A B

0 1 B D

1 .. 1 .. D C C

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.

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

41

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. reset

Estado __ _0 _1 01 10 11

__ 0

000

1

0 _0 000

1

_1

0

000

0

0

01

10

100

010

x 0 1 _0 _1 __ _1 10 11 10 11 __ 01 11 11 Próximo Est.

Estado lógico __ _0 _1 01 10 11

z1 z2 z3 0 0 0 1 0 0

0 0 0 0 1 0

0 0 0 0 0 1

1

1 11 001

1

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: Estado lógico __ 11 10 _0 _1 01

Estado Físico Q2Q1Q0 000 001 011 010 110 111 101 100

z1 z2 z3

0 0

0 0

0 1

0 0 0

1 0 0

0 0 0

1

0

0

Figura P9.19. Asignación de estados Problema 9.8. Resultan: Profesor Leopoldo Silva Bijit

19-01-2010

42

Sistemas Digitales 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. reset No ha llegado nada __ 0 000

1

?

? 0

Llegó 00 Llegó 01

1

0

0

01

10

100

010

Llegó 10

1 11 1

001

Llegó 11

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.

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

43

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: reset

Estado Estado x=0 x=1 Lógico Físico presente Q1Q0 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

A 1/000 0/000 0/000 1/100 B

C 1/001 /001

0/010 D

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:

Profesor Leopoldo Silva Bijit

19-01-2010

44

Sistemas Digitales

Número 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 secuencia x 1 0 1 1 1 0 1 0 1 1 1 1 0 0 1 1 . Estado actual 000 Z1 Z0 Solución: a) Las salidas sólo dependen del estado. Puede aplicarse el modelo de Moore. b) Matriz de transiciones. Q2Q1Q0 000 001 011 010 110 111 101 100

x = 0 x = 1 Salidas 000 001 00 010 011 00 010 011 01 000 111 00 000 000 00 010 011 10 000 000 00 000 000 00 Q2+Q1+Q0+ z0z1

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.

Q2Q1Q0

011

1

Z0Z1

01

1

reset

0

000 _00_

1

1

0

001 _00_

0

0 110

101

100

00

00

00

010 _00_

1

111 10

0

Figura P9.23. Diagrama de estados Problema 9.9. d) Acciones. Reconoce la secuencia 101 cada vez que se presente, con salida z1=1 y z0 = 0. Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

45

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. Número 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 secuencia 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

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.

i

d

11 10

00

01

id

00

Figura P9.25. Diagrama sensores Problema 9.10. Profesor Leopoldo Silva Bijit

19-01-2010

46

Sistemas Digitales

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. reset

00

A 01

10 00 10

00

B

C 10

11

01

00/10 11

00/01

D

11

E 01

11 01

01

F

10 G

11 11 10

Figura P9.26. Diagrama de estados Problema 9.10. 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:

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

47

clk reset x z y

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.

t1 > ts

t2 > th

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.

Profesor Leopoldo Silva Bijit

19-01-2010

48

Sistemas Digitales

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 salida z salida y

0010101001011011010010100 0001010100000000001000000 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. reset Si/ S0/00

x=

1 0

0

/yz

S1/0 0 1

S4/00 0

1 S2/00 1 1

0 S3/01

1

S5/00 0 S6/10

0

Figura P9.29. Diagrama de estados Problema 9.11. 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.

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

49

Otras soluciones: Diagrama de Mealy:

reset

Si S0 x /yz

1/0 00

0/00

0/00 S1

S4

1/00

0/0 0 S5

1/00 S2 1/00 0/01

1/00

1/00

0/10 /10

S3

S6 0/10

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: reset Si S0 x /yz

1/0 00

0/00

0/00 S1

S4

1/00

1/00 1/00 S2 1/00

0/0 0

0/01

/10 S3

S6 0/10

Figura P9.31. Diagrama de estados equivalente Problema 9.11. Profesor Leopoldo Silva Bijit

19-01-2010

50

Sistemas Digitales

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

Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

51

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

Profesor Leopoldo Silva Bijit

19-01-2010

52

Sistemas Digitales

Í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 Profesor Leopoldo Silva Bijit

19-01-2010

Capítulo 9. Sistemas secuenciales

53

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

Profesor Leopoldo Silva Bijit

19-01-2010