Download Análisis y diseño de sistemas secuenciales

5. Análisis y diseño de sistemas
secuenciales (I)
Fundamentos de los Computadores
Grado en Ingeniería Informática
Introducción

Objetivos:
 Comprender el funcionamiento de un circuito secuencial partiendo de su
implementación (= ANALISIS)
 Implementar un circuito secuencial a partir de una descripción funcional
(=SÍNTESIS ó DISEÑO)
Análisis y diseño de sistemas secuenciales
2
Estado de un sistema secuencial

En los sistemas secuenciales las salidas dependen de las entradas
actuales y de toda la secuencia de entradas anteriores
x0
x1
xm
conjunto
… de puertas
lógicas
{x0, x1, … xm} ≡ Xt
y0
y1
yn
memoria
Análisis y diseño de sistemas secuenciales
…
{y0, y1, … yn} ≡ Yt
Yt = F(Xt, Xt-1, Xt-2 , …)
3
Estado de un sistema secuencial

El estado de un sistema secuencial depende de la secuencia de entradas
anteriores al sistema
Et = F(Xt-1, Xt-2 , …)
Yt = F(Xt, Xt-1, Xt-2 , …) = F(Xt, Et)

Descomponemos la ecuación general en dos ecuaciones: una de salida y otra
de estado siguiente
Yt = F(Xt, Et)
salida actual
 Yt = h(Xt, Et)
estado siguiente
 Et+1 = f(Xt, Et)
Análisis y diseño de sistemas secuenciales
4
Caracterización de sistemas secuenciales

Es necesario plantear las tablas y ecuaciones que definen:
 El siguiente estado del sistema a partir de las entradas del circuito y el estado
actual del mismo
 Las salidas del sistema a partir de las entradas del circuito y el estado actual del
mismo

Esta información puede visualizarse usando un diagrama de estados que
muestre todos los estados posibles del sistema y las transiciones entre ellos

Nos basamos en un modelo de máquinas de estados finitos (FSM – FiniteState Machine) que se define como una quíntupla <S, I, O, f, h>





S  conjunto de estados (states)
I  conjunto de entradas (inputs)
O  conjunto de salidas (outputs)
f  función de estado siguiente
h  función de salida
Análisis y diseño de sistemas secuenciales
5
Modelo de máquinas de estados finitos

El modelo FSM supone que el tiempo se divide en intervalos
uniformes y que las transiciones de un estado a otro solo ocurren
al principio de cada intervalo

La función de salida (h) define los valores de salida durante el
intervalo de tiempo actual de acuerdo con el estado y las entradas
actuales
Yt = h(Xt, Et)

La función de estado siguiente (f) define cuál será el estado en el
siguiente intervalo de tiempo de acuerdo con el estado y las
entradas actuales
Et+1 = f(Xt, Et)
Análisis y diseño de sistemas secuenciales
6
Tipos de FSM

La función de salida puede definirse de dos maneras distintas, lo
que da lugar a dos modelos FSM distintos

En el modelo de Moore las salidas sólo dependen del estado del
circuito
Yt = h(Et)
Et+1 = f(Xt, Et)

En el modelo de Mealy las salidas dependen del estado del
circuito y de las entradas actuales
Yt = h(Et, Xt)
Et+1 = f(Xt, Et)
Análisis y diseño de sistemas secuenciales
7
Implementación de FSM

Cualquier sistema secuencial se puede modelar utilizando una
máquina de estados finitos y, a partir de ella, realizar su
implementación

El estado del sistema secuencial será almacenado en circuitos
biestables que actuarán como elementos de memorización

Las funciones de estado siguiente f y de salida h se
implementarán utilizando lógica combinacional
Análisis y diseño de sistemas secuenciales
8
Análisis de sistemas secuenciales

El análisis de un sistema secuencial consiste en la generación de
una descripción funcional a partir del esquema lógico del circuito
y contendrá:
 Diagrama de estados del circuito
 Ecuaciones y tablas que definan el estado siguiente
 Ecuaciones y tablas que definan la salida del circuito

Una vez obtenida la descripción funcional, es posible desarrollar
cronogramas que permitan estudiar el comportamiento del
sistema
Análisis y diseño de sistemas secuenciales
9
Procedimiento de análisis
Análisis y diseño de sistemas secuenciales
10
Análisis de sistemas de tipo Moore (I)
Análisis y diseño de sistemas secuenciales
11
Análisis de sistemas tipo Mealy (I)
Análisis y diseño de sistemas secuenciales
12
Análisis de sistemas tipo Moore (II)
Análisis y diseño de sistemas secuenciales
13
Análisis de sistemas tipo Mealy (II)
Análisis y diseño de sistemas secuenciales
14
Análisis y diseño de sistemas secuenciales
15
Análisis de sistemas de tipo Moore (I)


El primer paso en el análisis es obtener las ecuaciones de entrada
a cada biestable del circuito
En este caso hay dos biestables cuyas entradas son D0 y D1, por
lo que plantearemos dos ecuaciones en función de la entrada Cnt
y de las salidas de los biestables
Análisis y diseño de sistemas secuenciales
16
Análisis de sistemas de tipo Moore (I)



Estas ecuaciones se denominan ecuaciones de excitación, ya que
determinan el valor de las entradas de los biestables del circuito
A continuación hay que transformar estas ecuaciones en las
ecuaciones de estado siguiente características de cada biestable
Dado que el estado siguiente de un biestable D es igual al valor
de la señal D, tenemos que:
Análisis y diseño de sistemas secuenciales
17
Análisis de sistemas de tipo Moore (I)


A continuación debemos calcular la ecuación de salida
Dado que estamos hablando de un circuito de tipo Moore, la
salida dependerá sólo del estado actual del sistema, es decir, de
las salidas de los biestables
Análisis y diseño de sistemas secuenciales
18
Análisis de sistemas de tipo Moore (I)

A partir de las ecuaciones de estado siguiente y de salida
generamos una tabla que refleje esta información
 Cada fila de la tabla se corresponde con un estado del circuito
 Cada columna de la tabla representa un valor de las entradas

Dado que el circuito tiene dos biestables, el número total de
estados posibles es cuatro
Análisis y diseño de sistemas secuenciales
19
Análisis de sistemas de tipo Moore (I)

Para facilitar la visualización del funcionamiento del circuito
podemos representar el contenido de esta tabla usando un
diagrama de estados
 Cada estado se representa con un círculo que contiene el valor de los
biestables que representa y el valor de las salidas
 Las transiciones entre estados se representan como flechas entre los
círculos, etiquetadas con el valor de las entradas que causa la transición

En general, en un circuito con m biestables y k entradas, el
número total de estados será 2m y el número total de transiciones
será 2m · 2k
Análisis y diseño de sistemas secuenciales
20
Análisis de sistemas de tipo Moore (I)

El diagrama de estados puede obtenerse fácilmente a partir de la
tabla de estado siguiente y de salida
Análisis y diseño de sistemas secuenciales
21
Análisis de sistemas de tipo Moore (I)

Con este diagrama podemos comprobar que:
 Cuando Cnt = 0 el circuito permanece en el estado actual
 Mientras Cnt = 1 el circuito va recorriendo todos los estados siguiendo
esta secuencia: 0, 1, 2, 3, 0, 1, 2, 3, 0, …

Por lo tanto, este circuito es un contador módulo 4 con una
entrada de control que habilita la cuenta
Análisis y diseño de sistemas secuenciales
22
Análisis de sistemas de tipo Moore (I)

Con toda esta información podemos generar un cronograma que
permita ver el comportamiento del circuito bajo determinadas
circunstancias
Análisis y diseño de sistemas secuenciales
23
Análisis de sistemas de tipo Moore (I)


Este cronograma muestra cuatro ciclos de reloj con la señal Cnt
activa entre los instantes de tiempo t0 y t4
Suponemos que el estado inicial del contador es 00
Análisis y diseño de sistemas secuenciales
24
Análisis de sistemas de tipo Moore (I)


El contador pasa al estado 01 tras el flanco de subida de la señal
de reloj en t1
El contador pasa al estado 10 tras el flanco de subida de la señal
de reloj en t2
Análisis y diseño de sistemas secuenciales
25
Análisis de sistemas de tipo Moore (I)


El contador pasa al estado 11 tras el flanco de subida de la señal
de reloj en t3, activando la salida Y
Dado que la señal Cnt se desconecta en t3, el contador permanece
en el estado 11 tras el flanco de subida de t5
Análisis y diseño de sistemas secuenciales
26
Análisis de sistemas de tipo Moore (I)

Para comprobar el comportamiento del circuito sería necesario
construir cronogramas para todas las posibles secuencias de
valores de entrada

Finalmente, estos cronogramas deben ser verificados utilizando
una herramienta de simulación de circuitos
 Las herramientas de simulación a nivel físico permiten describir el
circuito lógico utilizando puertas y biestables
 Las herramientas de simulación a nivel funcional permiten describir el
circuito en base a tablas o diagramas de estado
 En cualquier caso, estas herramientas no permiten verificar los retardos
reales del circuito, ya que no tienen información sobre su implementación
Análisis y diseño de sistemas secuenciales
27
Estructura del tema



Introducción
Modelo de máquinas de estados finitos
Análisis de sistemas secuenciales
 Análisis de sistemas de tipo Moore
 Análisis de sistemas de tipo Mealy
 Ejemplos

Diseño de sistemas secuenciales







Generación del diagrama de estados
Minimización del diagrama de estados
Codificación de estados
Elección de los biestables
Implementación y verificación del sistema
Ejemplos
Resumen y bibliografía
Análisis y diseño de sistemas secuenciales
28
Análisis de sistemas tipo Mealy (I)


Los circuitos secuenciales de tipo Mealy son aquellos en los que
las salidas dependen del valor actual de las entradas y del estado
actual
Este diagrama muestra un circuito secuencial de tipo Mealy
compuesto de dos biestables D
Análisis y diseño de sistemas secuenciales
29
Análisis de sistemas de tipo Mealy (I)


El primer paso en el análisis es obtener las ecuaciones de
excitación que definen la entrada de cada biestable
En este caso hay dos biestables cuyas entradas son D0 y D1, por
lo que plantearemos dos ecuaciones en función de la entrada Cnt
y de las salidas de los biestables
Análisis y diseño de sistemas secuenciales
30
Análisis de sistemas de tipo Mealy (I)


A continuación hay que transformar estas ecuaciones en las
ecuaciones de estado siguiente características de cada biestable
Dado que el estado siguiente de un biestable D es igual al valor
de la señal D, tenemos que:
Análisis y diseño de sistemas secuenciales
31
Análisis de sistemas de tipo Mealy (I)


A continuación calculamos la ecuación de salida
En un circuito de tipo Mealy la salida depende tanto del estado
actual del sistema como de los valores actuales de las entradas
del mismo
Análisis y diseño de sistemas secuenciales
32
Análisis de sistemas de tipo Mealy (I)


A partir de estas ecuaciones generamos la tabla de estado
siguiente y de salida
La principal diferencia de esta tabla con la de un circuito de tipo
Moore es que los valores de salida también dependen de los
valores de entrada
Análisis y diseño de sistemas secuenciales
33
Análisis de sistemas de tipo Mealy (I)

El diagrama de estados puede obtenerse a partir de esta tabla,
pero teniendo en cuenta que las salidas no se asocian con los
estados sino con las transiciones
Análisis y diseño de sistemas secuenciales
34
Análisis de sistemas de tipo Mealy (I)

Un arco con la etiqueta X/Y se interpreta así:
 Mientras el circuito permanezca en el estado del que sale el arco y el valor
de las entradas sea igual a X, la salida del circuito será igual a Y
 Si el valor de las entradas en el flanco de reloj es igual a X, el circuito
cambiará en el siguiente ciclo al estado apuntado por el arco
Análisis y diseño de sistemas secuenciales
35
Análisis de sistemas de tipo Mealy (I)

A partir del diagrama de estados podemos comprobar que el
circuito es un contador módulo 4 con una entrada de control que
habilita la cuenta
 Cuando Cnt = 0 el circuito permanece en el estado actual
 Mientras Cnt = 1 el circuito va recorriendo todos los estados siguiendo
esta secuencia: 0, 1, 2, 3, 0, 1, 2, 3, 0, …
Análisis y diseño de sistemas secuenciales
36
Análisis de sistemas de tipo Mealy (I)

Con toda esta información podemos generar un cronograma que
permita ver el comportamiento del circuito bajo determinadas
circunstancias
Análisis y diseño de sistemas secuenciales
37
Análisis de sistemas de tipo Mealy (I)


Este cronograma muestra cuatro ciclos de reloj con la señal Cnt
activa entre los instantes de tiempo t0 y t4
Suponemos que el estado inicial del contador es 00
Análisis y diseño de sistemas secuenciales
38
Análisis de sistemas de tipo Mealy (I)


El contador pasa al estado 01 tras el flanco de subida de la señal
de reloj en t1
El contador pasa al estado 10 tras el flanco de subida de la señal
de reloj en t2
Análisis y diseño de sistemas secuenciales
39
Análisis de sistemas de tipo Mealy (I)


El contador pasa al estado 11 tras el flanco de subida de la señal
de reloj en t3, activando la salida Y
Dado que la señal Cnt se desconecta en t3, el contador permanece
en el estado 11 tras el flanco de subida de t5
Análisis y diseño de sistemas secuenciales
40
Análisis de sistemas de tipo Mealy (I)

La principal diferencia con respecto al contador equivalente de
tipo Moore es que la salida Y no permanece a 1 cuando se
desactiva Cnt, sino que también pasa a 0
Análisis y diseño de sistemas secuenciales
41
Estructura del tema



Introducción
Modelo de máquinas de estados finitos
Análisis de sistemas secuenciales
 Análisis de sistemas de tipo Moore
 Análisis de sistemas de tipo Mealy
 Ejemplos

Diseño de sistemas secuenciales







Generación del diagrama de estados
Minimización del diagrama de estados
Codificación de estados
Elección de los biestables
Implementación y verificación del sistema
Ejemplos
Resumen y bibliografía
Análisis y diseño de sistemas secuenciales
42
Análisis de sistemas tipo Moore (II)


Vamos a realizar el análisis de este circuito
En primer lugar podemos determinar que se trata de un circuito
de tipo Moore, ya que las salidas dependen únicamente del
estado del circuito y no de las entradas
Análisis y diseño de sistemas secuenciales
43
Análisis de sistemas tipo Moore (II)



El circuito tiene 3 biestables, es decir, 8 estados posibles
El circuito tiene una única señal de entrada X
El circuito tiene tres señales de salida Y0, Y1, e Y2
Análisis y diseño de sistemas secuenciales
44
Análisis de sistemas tipo Moore (II)

A partir del circuito podemos obtener las ecuaciones
correspondientes a las entradas de los biestables
Análisis y diseño de sistemas secuenciales
45
Análisis de sistemas tipo Moore (II)

Conociendo el funcionamiento de un biestable JK es posible,
partiendo de las ecuaciones de las entradas, generar la tabla de
excitación y de estado siguiente
Análisis y diseño de sistemas secuenciales
46
Análisis de sistemas tipo Moore (II)

A partir del circuito también podemos obtener las ecuaciones
correspondientes a las señales de salida
Análisis y diseño de sistemas secuenciales
47
Análisis de sistemas tipo Moore (II)

Dadas las ecuaciones de salida, es sencillo obtener la tabla de
salida
Análisis y diseño de sistemas secuenciales
48
Análisis de sistemas tipo Moore (II)

Con las tablas anteriores podemos obtener el diagrama de
estados que describe el funcionamiento del circuito
Análisis y diseño de sistemas secuenciales
49
Análisis de sistemas tipo Moore (II)

El circuito es un contador módulo 8
 Cuando X = 1 sigue la secuencia 0,1,2,3,4,5,6,7,0,1,2,3,…
 Cuando X = 0 el circuito cuenta en orden inverso
Análisis y diseño de sistemas secuenciales
50
Estructura del tema



Introducción
Modelo de máquinas de estados finitos
Análisis de sistemas secuenciales
 Análisis de sistemas de tipo Moore
 Análisis de sistemas de tipo Mealy
 Ejemplos

Diseño de sistemas secuenciales







Generación del diagrama de estados
Minimización del diagrama de estados
Codificación de estados
Elección de los biestables
Implementación y verificación del sistema
Ejemplos
Resumen y bibliografía
Análisis y diseño de sistemas secuenciales
51
Análisis de sistemas tipo Mealy (II)

A continuación analizaremos el siguiente circuito: es de tipo
Mealy porque las salidas dependen tanto del estado del circuito
como de las entradas del mismo
Análisis y diseño de sistemas secuenciales
52
Análisis de sistemas tipo Mealy (II)



El circuito tiene 2 biestables, es decir, 4 estados posibles
El circuito tiene una única señal de entrada X
El circuito tiene una única señal de salida Y
Análisis y diseño de sistemas secuenciales
53
Análisis de sistemas tipo Mealy (II)

A partir del circuito podemos obtener las ecuaciones
correspondientes a las entradas de los biestables
Análisis y diseño de sistemas secuenciales
54
Análisis de sistemas tipo Mealy (II)

Conociendo el funcionamiento de los biestables JK y D es
posible, partiendo de las ecuaciones de las entradas, generar la
tabla de excitación y de estado siguiente
Análisis y diseño de sistemas secuenciales
55
Análisis de sistemas tipo Mealy (II)

Partiendo del circuito también podemos obtener la ecuación
correspondiente a la señal de salida
Análisis y diseño de sistemas secuenciales
56
Análisis de sistemas tipo Mealy (II)

A partir de la ecuación de salida podemos generar la tabla de
salida
Análisis y diseño de sistemas secuenciales
57
Análisis de sistemas tipo Mealy (II)

Con las tablas anteriores podemos obtener el diagrama de
estados del circuito que describe su funcionamiento
Análisis y diseño de sistemas secuenciales
58
Análisis de sistemas tipo Mealy (II)

El circuito es un contador módulo 4
 La entrada X es una señal de reset síncrono
 La salida Y es una indicación de vuelta a cero
Análisis y diseño de sistemas secuenciales
59