49
EL-4002 Sistemas Digitales Circuitos Secuenciales Parte 1: Elementos de Memoria y Análisis de Circuitos Secuenciales

EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

  • Upload
    others

  • View
    3

  • Download
    0

Embed Size (px)

Citation preview

Page 1: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

EL-4002

Sistemas Digitales

Circuitos Secuenciales

Parte 1: Elementos de Memoria y Análisis de

Circuitos Secuenciales

Page 2: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Introducción a los Circuitos Secuenciales

Un circuito Secuencial contiene: Elementos de memoria:

“Latches” o “Flip-Flops”

Lógica Combinacional: Implementa una función

de “switching” de salidas múltiples

Entradas son señales del exterior

Salidas son señales al exterior

Otras entradas, Estado Actual o Estado Presente, son señales de los elementos de memoria

Las salidas restantes, Estado Siguiente, son entradas a los elementos de memoria

Lógica

Combinacional

Elementos

de

Memoria

Entradas Salidas

Estado

Actual

Estado

Siguiente

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 3: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Lógica Combinacional

Función Estado Siguiente

Estado Siguiente =

f(Entradas, Estado Actual)

Función de Salida (Mealy)

Salidas = g(Entradas,

Estado Actual)

Función de Salida (Moore)

Salidas = h(Estado Actual)

El tipo de función de salida

depende de las

especificaciones y afecta

significativamente el diseño

Introducción a los Circuitos Secuenciales

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 4: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Tipos de Circuitos Secuenciales

Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y

los elementos de memoria cambian su estado

Síncronos Comportamiento definido por el conocimiento de sus señales en

instantes discretos en el tiempo

Los elementos de memoria observan las entradas y pueden cambiar de estado solamente en relación a una señal de tiempo (pulsos de reloj)

Asíncronos Comportamiento definido por el conocimiento de las entradas en

cualquier instante de tiempo y del orden en un tiempo continuo en el cual las entradas cambian

Si el reloj se considerara como otra entrada, todos los circuitos serían asíncronos!

Sin embargo, la abstracción de lo síncrono hace manejable diseños complejos!

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 5: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Simulación de Eventos Discretos

Con el fin de entender el comportamiento en el

tiempo de un circuito secuencial, se utiliza la

simulación de eventos discretos

Reglas: Las compuertas son modeladas por una función ideal

(instantánea) y un retardo de compuerta fijo

Cualquier cambio en los valores de entrada es evaluado

para ver si produce un cambio en los valores de salida

Los cambios en los valores de salida son programados por

el retardo de compuerta fijo después del cambio en la

entrada

Al momento del cambio de una salida programada, el valor

de salida es modificado junto con todas las entradas que

ella manejen

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 6: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Simulación Compuerta NAND

Ejemplo: Una compuerta NAND de 2 entradas con un

retardo de 0,5 ns:

Se supone que A y B han sido 1 por un largo tiempo

Al tiempo t=0, A cambia a 0; a t= 0,8 ns, vuelve a 1

F A

B DELAY 0.5 ns.

F(Instantánea)

t (ns) A B F(I) F Comentarios

– 1 1 0 0 A=B=1 por un largo tiempo

0 1 0 1 1 0 0 F(I) cambia a 1

0,5 0 1 1 1 0 F cambia a 1 después de 0,5 ns

0,8 1 0 1 1 0 1 F(Instantáneamente) cambia a 0

0,13 1 1 0 1 0 F cambia a 0 después de 0,5 ns

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 7: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Modelos de Retardos de Compuertas

Supongamos compuertas con retardos de n ns,

se representan por: n = 0.2 ns, n = 0.4 ns,

n = 0.5 ns, respectivamente:

0.2 0.5 0.4

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 8: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Considere un simple

multiplexor de 2

entradas:

Con función: Y = A para S = 0

Y = B para S = 1

“Glitch” debido al retardo del inversor

A

0.4

0.5

0.4

S

B

Y 0.2

Modelo de Retardo de un Circuito

A

S B

Y

S

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 9: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Estado Almacenado

¿Qué pasa si A se conecta a Y?

El circuito sería:

Con función: Y = B para S = 1, y

Y(t) dependiente de Y(t – 0.9) para S = 0

El simple circuito combinacional se ha convertido en un

circuito secuencial porque su salida es una función de una secuencia en el tiempo de señales de entrada!

B

S

Y

S

S

B

Y 0.5

0.4

0.2

0.4

Y es un valor guardado en área celeste Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 10: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Estado Almacenado (cont.)

La simulación muestra como las señales de entrada cambian con el tiempo. Si los cambios ocurren cada 100 ns, las decenas de ns de los retardos son insignificantes

Y representa el estado del circuito, no sólo una salida

B S Y Comentario 1 0 0 Y “recuerda” 0 1 1 1 Y = B cuando S = 1

1 0 1 Ahora Y “recuerda” B = 1 para S = 0 0 0 1 No hay cambios en Y cuando B cambia

0

1

0

Y = B cuando S = 1

0 0 0 Y “recuerda” B = 0 para S = 0 1 0 0 No hay cambios en Y cuando B cambia

Tiempo

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 11: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Estado Almacenado (cont.)

Supongamos que

se conecta un

inversor en el

“feedback path.”

Resulta el siguiente

comportamiento:

El circuito se hace

inestable.

Para S = 0, el circuito

se convierte en un

oscilador. Puede

utilizarse como un

reloj en bruto

B S Y Comentarios 0 1 0 Y = B cuando S = 1 1 1 1 1 0 1 Ahora Y “recuerda” A 1 0 0 Y, 1.1 ns más tarde 1 0 1 Y, 1.1 ns más tarde

1 0 0 Y, 1.1 ns más tarde

S

B

Y

0.2

0.5

0.4

0.4

0.2

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 12: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

“Latch” S–R (NAND) Básico

“Cross-Coupling”

de dos compuertas

NAND se obtiene

un “Latch” S-R:

Tiene el

comportamiento de

secuencia en el

tiempo:

S = 0, R = 0 es

prohibido como

patrón de entrada

Q S (set)

R (reset) Q

R S Q Q Comentario 1 1 ? ? Estado desconocido 1 0 1 0 “Set” Q a 1 1 1 1 0 Ahora Q “recuerda” 1 0 1 0 1 “Reset” Q a 0 1 1 0 1 Ahora Q “recuerda” 0 0 0 1 1 Ambos se van a 1 1 1 ? ? Inestable!

Tiempo

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 13: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

“Latch” S–R (NOR) Básico

“Cross-Coupling”

de dos compuertas

NAND se obtiene

un “Latch” S-R:

Tiene el

comportamiento de

secuencia en el

tiempo:

S (set)

R (reset) Q

Q

R S Q Q Comentario 0 0 ? ? Estado desconocido

0 1 1 0 “Set” Q a 1 0 0 1 0 Ahora Q “recuerda” 1 1 0 0 1 “Reset” Q a 0 0 0 0 1 Ahora Q “recuerda” 0 1 1 0 0 Ambos se van a 0 0 0 ? ? Inestable!

Tiempo

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 14: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

“Latch” S–R con Reloj

Agregando dos

compuertas NAND al

Latch S - R básico,

se obtiene el Latch

S – R con Reloj:

Tiene un comportamiento de secuencia en el tiempo

similar al Latch S-R básico, excepto que las entradas

S-R son solamente observadas cuando la línea C es

“high”

C significa “control” o “reloj”.

S

R

Q

C

Q

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 15: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

“Latch” S–R con Reloj (cont.)

El Latch S-R con Reloj puede ser descrito por

una tabla:

La tabla describe qué

sucede después del

reloj (en el tiempo (t+1))

en base a: entradas actuales (S,R), y

estado actual Q(t).

Q(t) S R Q(t+1) Comentario

0 0 0 0 No hay cambios

0 0 1 0 Clear Q

0 1 0 1 Set Q

0 1 1 ??? Indeterminado

1 0 0 1 No hay cambios

1 0 1 0 Clear Q

1 1 0 1 Set Q

1 1 1 ??? Indeterminado

S

R

Q

Q

C

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 16: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Latch D

Agregando un inversor

al Latch S-R, se

obtiene el Latch D:

Ya no hay estados

“indeterminados”!

Q D Q(t+1) Comentario

0 0 0 No hay cambios

0 1 1 Set Q

1 0 0 Clear Q

1 1 1 No hay cambios

El símbolo gráfico para el Latch D es:

C

D Q

Q

D Q

C

Q

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 17: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

“Flip-Flops”

El problema de tiempo del Latch

Flip-Flop “Master-Slave”

Flip-Flop activado por flanco (“Edge-triggered

Flip-Flop”)

Símbolos estándares para elementos de memoria

Entradas directas (asíncronas) a los Flip-Flops

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 18: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

El Problema de Tiempo del Latch

En un circuito secuencial, pueden existir

caminos a través de la lógica combinacional:

Desde un elemento de memoria a otro

Desde un elemento de memoria hacia el mismo

elemento de memoria

La lógica combinacional entre una salida de un

Latch y una entrada de un Latch, puede ser tan

simple como una interconexión

Para un Latch-D con reloj, la salida Q depende

de la entrada D siempre que la entrada de reloj

C tenga el valor 1

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 19: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

El Problema de Tiempo del Latch (cont.)

Considere el siguiente circuito:

Supongamos que inicialmente Y = 0

Mientras C = 1, el valor de Y sigue cambiando!

Los cambios están basados en el retardo presente en el

loop a través de la conexión de realimentación de Y a Y

Este comportamiento es claramente inaceptable

Comportamiento deseado: Y cambia sólo una vez por

pulso de reloj

Reloj

Y

C

D Q

Q

Y

Reloj

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 20: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

El Problema de Tiempo del Latch (cont.)

Una solución al problema de tiempo del Latch es

romper el camino cerrado de Y a Y dentro del

elemento de memoria

La solución comúnmente utilizada para romper el

camino cerrado, es reemplazar el Latch D con un:

Flip-Flop “Master-Slave”

Flip-Flop Activado por Flancos (“edge-triggered”)

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 21: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Consiste de dos Latches

S-R con Reloj en serie

con el reloj invertido en el

segundo Latch

La entrada es observada

por el primer Latch con C = 1

La salida es cambiada por el segundo Latch con C = 0

El camino de la entrada a la salida se rompe por la

diferencia en los valores del reloj (C = 1 y C = 0)

El comportamiento demostrado por el ejemplo dado

con D manejado por Y es evitado ya que el reloj debe

cambiar de 1 a 0 antes que pueda ocurrir un cambio en

Y basado en D

C

S

R

Q

Q

C

R

Q

Q

C

S

R

Q S

Q

Flip-Flop S-R Master-Slave

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 22: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Problema del Flip-Flop

El cambio en la salida del Flip-Flop es retardado

por el ancho del pulso lo cual hace al circuito

más lento, o

S y/o R pueden cambiar mientras C = 1

Supongamos que Q = 0 y S cambia a 1 y luego a 0

con R permaneciendo en 0

El Latch Master se pone en 1

Un 1 es transferido al Slave

Supongamos que Q = 0 y S cambia a 1 y luego a 0 y

R cambia a 1 y luego a 0

El Master hace un “set” y luego un “reset”

Un 0 es transferido al Slave

Este comportamiento se llama “1s catching” Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 23: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Solución para el Flip-Flop

Utilizar “edge-triggering” en vez de “master-slave”

Un Flip-Flop activado por flanco o “edge-triggered”,

ignora el pulso mientras está en un nivel constante

y actúa solamente durante una transición de la

señal de reloj

Los Flip-Flops activados por flanco pueden ser

construidos directamente a nivel de un circuito

electrónico, o

Se puede utilizar un Flip-Flop D Master-Slave el

cual presenta también un comportamiento “edge-

triggered”

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 24: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Flip-Flop D Edge-Triggered

El Flip-Flop D “edge-triggered”

es lo mismo que un Flip-Flop D

Master-Slave

Se puede formar por: El reemplazo del primer Latch S-R

con Reloj por un Latch D con Reloj, o

El agregar una entrada D y un inversor al Flip-Flop S-R Master-Slave

El retardo del Flip-Flop S-R Master-Slave se puede evitar ya

que el comportamiento “1s-catching” no se presenta cuando

se reemplazan las entradas S y R con la entrada D

El cambio de la salida del Flip-Flop D está asociado con el

flanco negativo al final del pulso

Esto se llama un Flip-Flop activado por flanco negativo

(“negative-edge triggered Flip-Flop”)

C

S

R

Q

Q C

Q

Q C

D Q D

Q

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 25: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Flip-Flop D Activado Con Flanco Positivo

Formado al agregar

inversores a las

entradas del reloj

Q cambia al valor en D al aplicar el flanco

positivo del reloj dentro de las restricciones

de tiempo a ser especificadas

Nuestra elección como el Flip-Flop Estándar

para la mayoría de los circuitos secuenciales

C

S

R

Q

Q C

Q

Q C

D Q D

Q

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 26: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Master-Slave:

indicador de salida

diferida

Edge-Triggered:

indicador

dinámico

D con 0 Control

“Triggered” D

Latches

S

R

SR SR

S

R

D

C

D con 1 Control

D

C

Flip-Flops “Master-Slave”

D

C

“Triggered” D “Triggered” SR

S

R

C

D

C

“Triggered” SR

S

R

C

Flip Flop “Edge-Triggered”

Triggered D

D

C

Triggered D

D

C

Símbolos Estándares para Elementos de

Memoria

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 27: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Entradas Asíncronas

Al encender o al “resetear”, todo o parte

de un circuito secuencial, normalmente

es inicializado a un estado conocido

antes de comenzar su operación

Esta inicialización es a menudo hecha

fuera del comportamiento síncrono

del circuito, es decir, asincrónicamente

Las entradas directas R y/o S, que controlan el

estado de los Latches dentro de los Flip-Flops, son

utilizadas para esta inicialización

Para el Flip-Flop de ejemplo mostrado:

0 aplicado a R “resetea” el Flip-Flop al estado 0

0 aplicado a S “setea” el Flip-Flop al estado 1

D

C

S

R

Q

Q

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 28: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Análisis de Circuitos Secuenciales

Modelo General El Estado Actual en el tiempo

(t) es guardado en un arreglo de Flip-Flops

El Estado Siguiente en el tiempo (t+1) es una función Booleana del Estado y de las Entradas

Las Salidas en el tiempo (t) son una función Booleana del Estado (t) y (a veces) de las Entradas (t).

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 29: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Análisis Sistema Secuencial: Ejemplo 1

Entrada: x(t)

Salida: y(t)

Estados: (A(t), B(t))

¿Cuál es la Función de

Salida?

¿Cuál es la Función del

Estado Siguiente?

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 30: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Análisis Sistema Secuencial: Ejemplo 1

(cont.)

Ecuaciones Booleanas

para las funciones:

𝐴 𝑡 + 1 = 𝐴 𝑡 𝑋 𝑡 +𝐵 𝑡 𝑋(𝑡)

𝐵 𝑡 + 1 = 𝐴(𝑡) 𝑋(𝑡)

𝑌 𝑡 = 𝑋 𝑡 (𝐵 𝑡 + 𝐴 𝑡 )

A(t+1) y B(t+1) son las

llamadas Funciones del

Estado Siguiente o

Funciones de Excitación

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 31: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Análisis Sistema Secuencial: Ejemplo 1

(cont.)

Comportamiento de las entradas, salidas y

estados del sistema

0

0

0

0

1

1

1

0

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 32: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Características de la Tabla de Estados

Tabla de Estados – una tabla de múltiples

variables con las siguientes cuatro secciones:

Estado Actual – los valores de las variables de estado

para cada estado permitido

Entradas – las combinaciones de entrada permitidas

Estado Siguiente – el valor del estado en el tiempo

(t+1) en base al estado actual y a las entradas

Salidas – el valor de las salidas como una función del

estado actual y (a veces) de las entradas

Del punto de vista de una tabla de verdad: las entradas son: Entradas, Estado Actual, y

las salidas son: Salidas y Estado Siguiente

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 33: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Ejemplo 1: Tabla de Estado

La Tabla de Estado se puede llenar utilizando las

ecuaciones de Estado Siguiente y de las Salidas

𝐴 𝑡 + 1 = 𝐴 𝑡 𝑋 𝑡 + 𝐵 𝑡 𝑋(𝑡)

𝐵 𝑡 + 1 = 𝐴(𝑡) 𝑋(𝑡)

𝑌 𝑡 = 𝑋 𝑡 (𝐵 𝑡 + 𝐴 𝑡 )

Estado Actual Entradas Estado Siguiente Salidas A(t) B(t) x(t) A(t+1) B(t+1) y(t)

0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 34: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Ejemplo 1: Tabla de Estado Alternativa

Tabla de 2 dimensiones que calza bien con un Mapa de

Karnaugh. Las filas del Estado Actual y las columnas de

las entradas en orden de acuerdo al código Gray

A(t+1) = A(t)x(t) + B(t)x(t)

B(t+1) =A (t)x(t)

y(t) =x (t)(B(t) + A(t))

Estado Actual

Estado Siguiente x(t)=0 x(t)=1

Salidas

x(t)=0 x(t)=1 A(t) B(t) A(t+1)B(t+1) A(t+1)B(t+1) y(t) y(t)

0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 0 1 0

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 35: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Diagrama de Estados

La función del circuito secuencial puede ser

representado en forma gráfica como un diagrama

de estados con las siguientes componentes:

Un círculo con el nombre del estado en él para cada

estado

Un arco directo desde el Estado Actual al Estado

Siguiente para cada transición de estado

Un rótulo en cada arco directo con los valores de las

Entradas que producen la transición de estado, y

Un rótulo: En cada círculo con el valor de la salida producida, o

En cada arco directo con el valor de la salida producida

Semestre Primavera 2013 EL-4002 Sistemas Digitales

SAGO
Resaltado
SAGO
Resaltado
Page 36: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Diagrama de Estados

Tipos de Rótulos:

Un círculo con salidas incluidas:

estado/salida

Máquina de Moore; salidas dependen sólo

del estado

Un arco directo con salidas incluidas:

entrada/salida

Máquina de Mealy; salidas dependen del

estado y de las entradas

Semestre Primavera 2013 EL-4002 Sistemas Digitales

SAGO
Resaltado
SAGO
Resaltado
Page 37: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Ejemplo 1: Diagrama de Estados

¿Qué tipo?

El diagrama se hace

confuso para

grandes circuitos

Para circuitos

pequeños,

normalmente es más

fácil de entender que

la Tabla de Estados

A B 0 0

0 1 1 1

1 0

x=0/y=1 x=1/y=0

x=1/y=0

x=1/y=0

x=0/y=1

x=0/y=1

x=1/y=0

x=0/y=0

Semestre Primavera 2013 EL-4002 Sistemas Digitales

SAGO
Nota adhesiva
Maquina de MealyPues tiene arcos que especifican entrada y salida.
SAGO
Texto escrito a máquina
Se hace una asignación para cada estado, es una codificación, entonces si hay 4 estados requiero 2 bits (AB), si hay 5 requiero 3 bits (sobran, pero no es necesario asignarlos todos)
SAGO
Texto escrito a máquina
Hay una sola variable de entrada, x=1 o x=0
SAGO
Nota adhesiva
x=0, se mantiene en el estadox=1 pasa al estado 01
SAGO
Nota adhesiva
x=1 permanece en el estado x=0 cambia al estado 00
SAGO
Cuadro de texto
En cada estado deben salir tantos arcos como bits de entradas/salidas hay, en este caso sólo 2.
Page 38: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Estados Equivalentes

Dos estados son equivalentes si sus respuestas

para cada secuencia de entrada posible son

secuencias de salida idénticas

Alternativamente, dos estados son equivalentes

si sus salidas producidas por cada símbolo de

entrada son idénticas y sus estados siguientes,

para cada símbolo de entrada, son los mismos o

equivalentes

Semestre Primavera 2013 EL-4002 Sistemas Digitales

SAGO
Resaltado
SAGO
Resaltado
Page 39: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Ejemplo Estados Equivalentes

Diagrama de Estados:

Para los estados S3 y S2, La salida para entrada

0 es 1 y entrada 1 es 0, y

El estado siguiente para entrada 0 es S0 y para entrada 1 es S2.

Por la definicición alternativa, los estados S3 y S2 son equivalentes

S2 S3

1/0 0/1

1/0

0

S0/0 S1

1/0

0/1

1

0/1

Semestre Primavera 2013 EL-4002 Sistemas Digitales

SAGO
Texto escrito a máquina
/0
SAGO
Texto escrito a máquina
/0
SAGO
Texto escrito a máquina
xx
Page 40: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Ejemplo Estados Equivalentes

Reemplazando S3 y S2 por un sólo estado, se obtiene el siguiente diagrama:

Examinando el nuevo diagrama, los estados S1 y S2 son equivalentes ya que: sus salidas para la entrada 0 es 1 y

para la entrada 1 es 0, y

su estados siguientes para la entrada 0 es S0 y para le entrada 1 es S2,

Reemplazando S1 y S2 por un sólo estado, se obtiene el siguiente diagrama:

S2

1/0

0/0

S0 S1

1/0

0/1

1/0

0/1

0/0

S0 S1

1/0

0/1

1/0

Semestre Primavera 2013 EL-4002 Sistemas Digitales

SAGO
Texto escrito a máquina
Esta última máquina es equivalente, pero físicamente es mas rápida.
Page 41: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Modelos de Moore y Mealy

Los Circuitos Secuenciales o Máquinas

Secuenciales son llamadas también Máquinas de

Estado Finito (“Finite State Machines” (FSMs))

Existen dos modelos formales:

Modelo de Moore

Debido a E.F. Moore

Las salidas son una

función SÓLO de los

estados

Normalmente

especificado en los

estados

Modelo de Mealy

Debido a G. Mealy

Las salidas son una

función de las entradas

Y de los estados

Normalmente

especificadas en los

arcos de transición de

estados Semestre Primavera 2013 EL-4002 Sistemas Digitales

SAGO
Texto escrito a máquina
es la mas usada.
Page 42: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Ejemplo Diagramas de Moore y de Mealy

Diagrama de Estado Modelo de Mealy, relaciona

entradas y estados a salidas

Diagrama de Estado Modelo de Moore, relaciona

estados a salidas

0 1

x=1/y=1

x=1/y=0

x=0/y=0

x=0/y=0

1/0 2/1

x=1 x=1

x=0

x=0

x=1

x=0

0/0

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 43: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Ejemplo Tablas de Moore y de Mealy

Tabla de Estado Modelo de Moore, relaciona estados

a salidas

Tabla de Estado Modelo de Mealy, relaciona

entradas y estados a salidas

Estado Actual

Estado

Siguiente x=0 x=1

Salida

0 0 1 0 1 0 2 0 2 0 2 1

Estado

Actual

Estado

Siguiente

x=0 x=1

Salida x=0 x=1

0 0 1 0 0 1 0 1 0 1

Semestre Primavera 2013 EL-4002 Sistemas Digitales

SAGO
Nota adhesiva
salida depende solo del estado
SAGO
Nota adhesiva
salida depende del estado y de la entrada X
Page 44: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Salidas Mezcladas Moore y Mealy

En diseños reales, algunas salidas pueden ser

del tipo Moore y otras salidas pueden ser del

tipo Mealy

Ejemplo: Estado 00: Moore

Estados 01, 10,

y 11: Mealy

Simplifica la especificación

de las salidas

10 11

1/0 0/1

1/0

0

00/0 01

1/0

0/1

1

0/1

Semestre Primavera 2013 EL-4002 Sistemas Digitales

Page 45: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Ejemplo 2: Análisis de un Circuito

Secuencial

Diagrama Lógico:

Reloj Reset

D

Q C

Q

R

D

Q C

Q

R

D

Q C

Q

R

A

B

C

Z

Semestre Primavera 2013 EL-4002 Sistemas Digitales

SAGO
Texto escrito a máquina
Hay 3 flip-flops, entonces hay a lo más 2^3 (=8) asignaciones de estados.
SAGO
Texto escrito a máquina
Funciones de excitación (entradas D a los flip-flops)
SAGO
Lápiz
SAGO
Lápiz
SAGO
Lápiz
Page 46: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Ejemplo 2: Ecuación de Entrada de los

Flip-Flops

Variables

Entradas: No hay

Salidas: Z

Variables de Estados: A, B, C

Inicialización: Resetear a (0,0,0)

Ecuaciones

A(t+1) = Z =

B(t+1) =

C(t+1) =

Semestre Primavera 2013 EL-4002 Sistemas Digitales

SAGO
Texto escrito a máquina
(cada flip-flop corresponde a una variable de estado)
SAGO
Texto escrito a máquina
(de las funciones de excitación)
SAGO
Texto escrito a máquina
B(t) * C(t) = BC
SAGO
Texto escrito a máquina
B(t)*C'(t) + B'(t)*C(t) = B xor C
SAGO
Texto escrito a máquina
A'(t)* C'(t) =A'C'
SAGO
Texto escrito a máquina
(t+1)
SAGO
Texto escrito a máquina
A(t) = A
SAGO
Texto escrito a máquina
asociada al estado (no hay entrada xD)
Page 47: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Ejemplo 2: Tabla de Transición de Estado

A B C A(t+1) B(t+1) C(T+1) Z

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Semestre Primavera 2013 EL-4002 Sistemas Digitales

SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
1
SAGO
Texto escrito a máquina
1
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
1
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
1
SAGO
Texto escrito a máquina
1
SAGO
Texto escrito a máquina
1
SAGO
Texto escrito a máquina
1
SAGO
Texto escrito a máquina
1
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
1
SAGO
Texto escrito a máquina
1
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
1
SAGO
Texto escrito a máquina
1
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
SAGO
Texto escrito a máquina
0
Page 48: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

¿Cuáles estados son utilizados?

¿Cuál es la función del circuito?

000

011 010

001 100

101

110

111

Reset ABC

Ejemplo 2: Diagrama de Estado

Semestre Primavera 2013 EL-4002 Sistemas Digitales

SAGO
Resaltado
SAGO
Resaltado
SAGO
Resaltado
SAGO
Cuadro de texto
Son estados inalcanzables, ya que la máquina parte de 000 siempre.
SAGO
Rectángulo
Page 49: EL-4002 Sistemas Digitales€¦ · Tipos de Circuitos Secuenciales Depende de los tiempos en los cuales: los elementos de memoria observan sus entradas, y los elementos de memoria

Se utilizan solamente los estados alcanzables

desde el estado “reset” 000: 000, 001, 010, 011

y 100

El circuito produce un 1 en Z después de 4

ciclos de reloj y luego cada 5 pulsos del reloj:

000 → 001 → 010 → 011→100 → 000 →

001 → 010 → 011 → 100 …

Ejemplo 2: Resultados

Semestre Primavera 2013 EL-4002 Sistemas Digitales