5.5. Análisis y diseño de Análisis y diseño desistemas sistemas …serdis.dis.ulpgc.es/~gii-fc/material_clases_teoria/Tema5/... · 2013-03-06 · 06/03/2013 2 Estado de un sistema

06/03/2013

1

5.5. Análisis y diseño deAnálisis y diseño de sistemas sistemas i l (I)i l (I)secuenciales (I)secuenciales (I)

Fundamentos de los ComputadoresGrado en Ingeniería Informática

IntroducciónIntroducció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

06/03/2013

2

Estado de un sistema secuencialEstado de un sistema secuencial

En los sistemas secuenciales las salidas dependen de las entradas actuales y de toda la secuencia de entradas anteriores

{ } Xconjunto

de puertas lógicas

memoria

x0

x1

xm…

y0

y1

yn…

{x0, x1, … xm} ≡ Xt

{y0, y1, … yn} ≡ Yt

Yt = F(Xt, Xt-1, Xt-2 , …)


Estado de un sistema secuencialEstado 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 , …)

Descomponemos la ecuación general en dos ecuaciones: una de salida y otra de estado siguiente

Yt = F(Xt, Xt-1, Xt-2 , …) = F(Xt, Et)

Y F(X E )salida actual Yt = h(Xt, Et)


Yt = F(Xt, Et) estado siguiente Et+1 = f(Xt, Et)

06/03/2013

3

Caracterización de sistemas secuencialesCaracterizació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 mismomismo

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 – Finite-State Machine) que se define como una quíntupla <S, I, O, f, h> S conjunto de estados (states)

I conjunto de entradas (inputs)


j ( p )

O conjunto de salidas (outputs)

f función de estado siguiente

h función de salida

Modelo de máquinas de estados finitosModelo 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

La función de estado siguiente (f) define cuál será el estado en el

Yt = h(Xt, Et)


siguiente intervalo de tiempo de acuerdo con el estado y las entradas actuales

Et+1 = f(Xt, Et)

06/03/2013

4

Tipos de FSMTipos 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 En el modelo de Moore las salidas sólo dependen del estado del circuito

En el modelo de Mealy las salidas dependen del estado del circuito y de las entradas actuales

Yt = h(Et)Et+1 = f(Xt, Et)


Yt = h(Et, Xt)Et+1 = f(Xt, Et)

Implementación de FSMImplementació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


06/03/2013

5

Análisis de sistemas secuencialesAná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á:

Di d t d d l i it 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


sistema

Procedimiento de análisisProcedimiento de análisis


06/03/2013

6

Análisis de sistemas de tipo Moore (I)Análisis de sistemas de tipo Moore (I)


Análisis de sistemas tipo Análisis de sistemas tipo MealyMealy (I)(I)


06/03/2013

7

Análisis de sistemas Análisis de sistemas tipo tipo Moore (II)Moore (II)


Análisis de sistemas tipo Análisis de sistemas tipo MealyMealy (II(II))


06/03/2013

8


Análisis de sistemas de tipo Análisis de sistemas de tipo Moore (I)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 l l d i f ió d l d Clo que plantearemos dos ecuaciones en función de la entrada Cnt y de las salidas de los biestables


06/03/2013

9

Análisis de sistemas de tipo Análisis de sistemas de tipo Moore Moore (I)(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 i d d i i í i d d bi blecuaciones 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:



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 l lid d l bi bllas salidas de los biestables


06/03/2013

10


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

C d l d l t bl t l d l t d 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



Para facilitar la visualización del funcionamiento del circuito podemos representar el contenido de esta tabla usando un diagrama de estados

C d t d t í l ti l l d l 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


yserá 2m · 2k

06/03/2013

11


El diagrama de estados puede obtenerse fácilmente a partir de la tabla de estado siguiente y de salida



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


06/03/2013

12


Con toda esta información podemos generar un cronograma que permita ver el comportamiento del circuito bajo determinadas circunstancias



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


06/03/2013

13


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 d l jde reloj en t2



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 l d 11 l fl d bid den el estado 11 tras el flanco de subida de t5


06/03/2013

14


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

Estructura del temaEstructura 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

06/03/2013

15

Análisis de sistemas tipo Análisis de sistemas tipo MealyMealy (I)(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

di i i i l d i l Este diagrama muestra un circuito secuencial de tipo Mealy compuesto de dos biestables D


Análisis de sistemas de tipo Análisis de sistemas de tipo MealyMealy (I)(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 l l d i f ió d l d Clo que plantearemos dos ecuaciones en función de la entrada Cnt y de las salidas de los biestables


06/03/2013

16


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 d l lde la señal D, tenemos que:



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 d l idel mismo


06/03/2013

17


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 l l d lid bié d d d lMoore es que los valores de salida también dependen de los

valores de entrada



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


06/03/2013

18


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



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

C d C t 0 l i it l t d t l 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, …


06/03/2013

19


Con toda esta información podemos generar un cronograma que permita ver el comportamiento del circuito bajo determinadas circunstancias



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


06/03/2013

20


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 d l jde reloj en t2



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 l d 11 l fl d bid den el estado 11 tras el flanco de subida de t5


06/03/2013

21


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









06/03/2013

22

Análisis de sistemas tipo Moore (II)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

d d l i i d l destado del circuito y no de las entradas



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


06/03/2013

23


A partir del circuito podemos obtener las ecuaciones correspondientes a las entradas de los biestables



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


06/03/2013

24


A partir del circuito también podemos obtener las ecuaciones correspondientes a las señales de salida



Dadas las ecuaciones de salida, es sencillo obtener la tabla de salida


06/03/2013

25


Con las tablas anteriores podemos obtener el diagrama de estados que describe el funcionamiento del circuito



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


06/03/2013

26








Análisis de sistemas tipo Análisis de sistemas tipo MealyMealy (II)(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


06/03/2013

27


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



A partir del circuito podemos obtener las ecuaciones correspondientes a las entradas de los biestables


06/03/2013

28


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



Partiendo del circuito también podemos obtener la ecuación correspondiente a la señal de salida


06/03/2013

29


A partir de la ecuación de salida podemos generar la tabla de salida



Con las tablas anteriores podemos obtener el diagrama de estados del circuito que describe su funcionamiento


06/03/2013

30


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


Documents

5.5. Análisis y diseño de Análisis y diseño desistemas sistemas …serdis.dis.ulpgc.es/~gii-fc/material_clases_teoria/Tema5/... · 2013-03-06 · 06/03/2013 2 Estado de un sistema