cátedra de sistemas digitales i dpto. de sistemas e ... · síntesis cableada (con elementos de...

Cátedra de Sistemas Digitales I Dpto. de Sistemas e Informática

Escuela de Ingeniería Electrónica

Síntesis cableada de una red de Petri

1.- INTRODUCCIÓN

2.- DISPOSITIVOS ELEMENTALES DE MEMORIA

3.- SINTESIS POR TRANSFERENCIA IMPULSIONAL (T-I)

4.- SINTESIS POR LLAMADA – RESPUESTA (LL-R).

5.- COMENTARIOS RESUMIDOS

6.- CONVERSIÓN DE FLIP-FLOPs

7.- FLIP-FLOPS COMERCIALES

8.- PROBLEMAS

Síntesis cableada de ...., Sistemas Digitales I 2

SÍNTESIS CABLEADA DE UNA RED DE PETRI

1.- INTRODUCCIÓN

Uno de los objetivos del modelado es obtener la información necesaria para tomar decisiones correctas, por medio de las cuales el sistema real (planta) puede ser debidamente regulado o controlado hacia el objetivo deseado.

Uno de los modelos visto para representar sistemas lógicos digitales utilizaba una descripción de tipo algorítmica: las redes de Petri. Como lo muestra la Figura 1, la abstracción lograda en el modelo, deberá ser llevada a un dispositivo concreto, tal que sea éste, finalmente, el que controle el sistema real (y se comporte como el modelo describe).

Figura 1

Ante la necesidad de sintetizar en un dispositivo electrónico, lo descrito en el modelo, se presentan varias alternativas:

Síntesis cableada (con elementos de baja escala de integración -SSI: compuertas y flip-flop) Síntesis programada en Controladores Lógicos Programables - PLC. Síntesis con Memorias y/o Matrices Lógicas - PLD (elementos de gran escala de integración –LSI–) Síntesis con Arreglos Lógicos de Puertas Programables en Campo – FPGA (muy grande escala de

integración –VLSI–).

En este apunte trataremos la realización cableada de una descripción hecha con redes de Petri. Se utilizará un método que permite la obtención directa del circuito, obviando dos etapas clásicas de la síntesis convencional: a) la codificación y b) las ecuaciones lógicas.

2.- DISPOSITIVOS ELEMENTALES DE MEMORIA

Partimos de una red de Petri básica como la dibujada en la Figura 2

Figura 2


Pregunta: ¿ Cómo sintetizar un lugar?. ¿Qué dispositivo electrónico se “comporta” como un lugar? Debería ser un dispositivo elemental que cumpla con:

1. Debe tener dos estados estables

2. Se le debe poder ordenar

Es decir, un dispositivo elemental de memoria (DEM), que se le pueda indicar tres cosas distintas y

por lo tanto –si se le indica con líneas binarias– con dos entradas, una de activación A y otra de desactivación D. Además, una salida donde pueda leerse su estado. En la Figura 3 se ha dibujado una parte de una RdeP, en donde al lugar 1 –en el modelo– se le ha asociado un DEM –en el circuito–. El disparo de la transición de entrada, debería generar una señal de activación en el DEM (A=1) y el disparo de la transición de salida debería generar una señal de desactivación (D=1).

Figura 3

Entonces, si pensamos que disponemos de este dispositivo teórico básico (que luego veremos que efectivamente existe algo parecido), podemos intentar sintetizar la red de la Figura 2. Para esto, cada lugar es representado –en el circuito– por un DEM. Además, representamos las transiciones con compuertas and , ya que éstas dan un nivel alto, cuando se verifican todas sus entradas (esto es: cuando se verifica que todos los lugares de entrada están marcados y vale 1 la condición externa asociada a esa transición). Así resulta la Figura 4, en la que se expresa la correspondencia referida. En esta figura se ha desarrollado sólo el lugar 2 . Vemos que el DEM2 se activa cuando:

Por ejemplo:

A D

grabar ------- 1 0

desgrabar ---- 0 1

mantener ---- 0 0

marcado

no marcado

- grabar (marcar), - desgrabar o borrar (desmarcar) - mantener (la marca o la no-marca)


i) el DEM1 está activado y

ii) a=1

Se desactiva cuando:

i) el DEM2 está activado y

ii) b=1

Figura 4

La tabla de comportamiento que debería presentar un dispositivo que nos permita sintetizar en forma directa cada lugar es la siguiente:

A D QT+1

0 0

0 1

1 0

1 1

Qt

0

1

1 , 0, -

Tabla I

ADQDADADAQQ ttt ''''1 Ecuación característica

Para llevar a un circuito con compuertas nand y not , complementamos dos veces y aplicamos De

Morgan,

'''''''1 ADQADQQ ttt cuyo circuito se muestra en Figura 5.

¿Cómo podemos, con elementos ya vistos (compuertas), realizar un dispositivo que presente este comportamiento? Para obtenerlo, planteamos la ecuación característica del dispositivo buscado, a partir de la tabla, resultando la ecuación:

→ por lo que resulta A=1

→ por lo que resulta D=1.


Figura 5

El DEM representado en forma teórica en la Tabla I, tiene existencia real (comercial) y se lo conoce con el nombre de latch RS de activación o grabado prioritario 1. En este caso, se reemplaza A por S (set) y D por R (reset).

A partir de la tabla de comportamiento de un flip-flop (Tabla I), se puede hallar la ecuación característica en forma analítica (como lo hicimos anteriormente), pero también lo podemos hacer a partir de la tabla de excitación del flip flop. La tabla de excitación de un flip-flop, se construye a partir de la de comportamiento, preguntándonos qué valor deben tener las entradas del flip flop para que su salida transicione de una determinada forma . Esto lo analizamos para cada una de las posibles transiciones Qt → Qt+1 (esto es: 00, 01, 10, 11), como se realiza en la siguiente tabla:

Por ejemplo, para llenar la fila (∆) nos preguntamos, ¿qué debemos colocar en RS para que Q pase

de 0 a 1?. La respuesta es: cualquier cosa en R y un 1 en S. A partir de la tabla de excitación, se determina el MdeK para escribir la ecuación característica (Qt=1)

3.- SINTESIS POR TRANSFERENCIA IMPULSIONAL (T-I)

En la Figura 6 se muestra el diagrama de un lugar, con varias transiciones de entrada y varias transiciones de salida. Cada disparo de una transición de entrada, configura una condición de activación del

1 También lo podemos encontrar que lo llaman flip-flop RS. Sin embargo, otros autores dejan esta

denominación, para cuando el dispositivo es sincrónico.

Q Qt+1 R S

0 0 - 0

0 1 - 1

1 0 1 0

1 1 0 1 0

0 1 1

0 1 1 0

1 1 1 0

En el desarrollo de la ecuación característica, y se refleja en el circuito, hemos tomado Qt+1=1 para AD=11. Esto es, hemos considerado

un dispositivo con activación prioritaria

Estos son los valores de RS para lograr cada una de las transiciones de Q, según las

columnas #. #

TABLA DE EXCITACIÓN DEL R-S

RS

00 01 11 10 Q 0

1 Resulta: Qt+1 =S + Q R’

(∆)

Tabla II


lugar; así como cada disparo de una transición de salida lo es de desactivación. Si cada lugar “p”, es materializado con un flip-flop, cuya salida es simbolizada con la letra Q, ¿cómo se interconectan?. Lo haremos a través de las condiciones de activación y de desactivación. Un disparo de una transición de entrada deberá hacer que el elemento que la representa en el circuito, entregue un nivel alto que deberá ser aplicado a la entrada “S” del flip-flop. De forma similar sucederá con una transición de salida y la entrada “R” del flip-flop.

Figura 6

Generalizando decimos que hay ‘n’ condiciones de activación ( una por cada transición de entrada) y ‘m’ condiciones de desactivación (una por cada transición de salida). Esto lo indicamos en las expresiones siguientes:

m

k

kD

n

i

iA CRCS11

;

Vamos a analizar cuales son las condiciones de activación y de desactivación en un lugar genérico pj, para esto nos vamos a valer de la Figura 7 .

Figura 7 Condiciones de activación del lugar pj:

Para que se active el lugar pj, se debe disparar alguna de las transiciones Aij, entonces la condición de activación es:

a

i

n

i

ij

n

i

jAi

jA QACC

111 (3.1)

Condiciones de desactivación del lugar pj:

Para que se desactive el lugar pj, se debe disparar alguna de las transiciones Ajk, entonces la condición de desactivación es:


r

jjk

m

k

m

k

j

Ak

jD QACC

111 (3.2)

Cada término de CJ

A ó de CJD representa el disparo de una transición. Tener presente que cada

disparo, activa y desactiva –al mismo tiempo– lugares. Por ejemplo el término

r

jjk QA1

desactiva los lugares “pjρ” pero también activa los lugares “pkβ”. En la Figura 8, se muestra la implementación del lugar “pj” según las ecuaciones (3.1) y (3.2).

Figura 8

3.1.- Aleatorios de transferencia impulsional

Vamos analizar ahora, algunos inconvenientes (comportamiento aleatorio) que puede presentar este método. Estos problemas no se presentan en el análisis teórico, sino cuando tenemos en cuenta aspectos prácticos, como lo constituyen los tiempos de respuesta de los dispositivos reales utilizados (compuertas y flip-flop). Analicemos la Figura 7, particularmente pongamos nuestra atención en la transición Ajk. El disparo de esta transición debe garantizar:

1) La activación de todos sus lugares de salida 2) La desactivación de todos sus lugares de entrada

Sin embargo, la condición 1), puede, en ocasiones, no cumplirse. En efecto, el término

r

jjk QA1

de la ecuación (3.2) debe desactivar los lugares de entrada (pjρ , con ρ = 1, ..., r) y activar los

lugares de salida (pkβ, con β=1, ..., b)); pero si alguno de los dispositivos Qjρ es demasiado rápido en su desactivación, puede suceder que la señal de valor alto –debido a la productoria, materializada con una and– no dure el tiempo suficiente para activar a todos los Qkβ, que materializan los lugares de salida. Es decir, no cumplió la condición 1. Este inconveniente puede salvarse si se utiliza el método que estudiamos a continuación −aunque podemos estar introduciendo otros problemas−.


4.- SINTESIS POR LLAMADA – RESPUESTA (LL-R). Para solucionar el problema mencionado en § 3.1.-, modificamos la condición de desactivación

expresada en la ecuación (3. 2), exigiendo ahora que, además de verificar el disparo de la transición, se verifique que todos los lugares de salida estén marcados. Recién, después de esto, se da la orden de desactivar los lugares de entrada. Resulta entonces,

2

1

1

111

b

k

r

jjk

m

k

m

k

j

Ak

jD QQACC

(4.1)

Donde se ha agregado el término (2) que exige que todos los “Qkβ” estén en nivel alto, para enviar la señal de desactivación. La (4.1) es la ecuación de desactivación por Llamda-Respuesta generalizada (LL-R-G). Resumiendo, el lugar “pj” se desactiva debido al disparo de Ajk si:

i) Todos los DEM asociados a los lugares de salida de la transición Ajk están activados (término 2 de la 4.1)

ii) La transición Ajk es la disparada (término 1 de la 4.1)

Sin embargo, si bien solucionamos el aleatorio planteado en § 3.1.-, el término 1de la ecuación (4.1), todavía puede ocasionar problemas. En efecto, la señal Cj D, que debe desactivar todos los lugares pjρ, puede que no dure el tiempo suficiente para lograrlo. Esto puede suceder si alguno de los dispositivos Qjρ es más rápido que sus compañeros en desactivarse, en este caso –lamentablemente- el término 1 se hace cero antes de tiempo y no logra desactivar todos los Qjρ.

Para solucionar este último problema, analizamos la ecuación (4.1). La segunda condición (término 1) parece redundante, en tal caso, si lo eliminamos, resulta la siguiente ecuación.

b

k

m

k

jD QC

1

(4.2)

La (4.2) es la ecuación de desactivación denominada Llamada- Respuesta simplificada (LL-R-S). Para garantizar la desactivación de todos los lugares de entrada (pjρ en la Figura 7), el marcado de los lugares de salida (pKβ) debe permanecer el tiempo suficiente para lograrlo. Con la expresión (4.2) hemos solucionado el inconveniente ocasionado por el término 1 de la ecuación (4.1)

Como suele suceder en un diseño –la aplicación de un método soluciona un tipo de problemas pero introduce otro– la síntesis por el método de LL-R-S, también puede presentar comportamientos aleatorios por falta de información (al eliminar el término 1). Veamos esto en la Figura 9.

Figura 9 Vamos a suponer que aplicamos el método de LL-R-S. En el esquema, la transición `b` está

sensibilizada, por lo que de verificarse la condición externa asociada (b=1), la transición se dispara. Si esto sucede, se marca el lugar 4. De acuerdo al método aplicado (LL-R-S), al estar el lugar 4 marcado, se debe desmarcar el lugar 3, y esto es correcto. Pero también se deben desmarcar los lugares 1 y 2, y esto es incorrecto, porque la transición `a´ no se ha disparado. Este error del método LL-R-S se debe a que falta


información en la ecuación (4.2), precisamente falta el término 1 de la ecuación (4.1), que indica que la transición ´a´ no se ha disparado. Como vemos, este método tampoco se puede aplicar a toda red binaria y viva, se debe analizar cada red en particular para decidir el método más conveniente.

5.- COMENTARIOS RESUMIDOS

En la Tabla 3 se consignan un conjunto de comentarios que caracterizan, muy simplificadamente, estos métodos.

METODO VENTAJA PRECAUCION/DESVENTAJA

T-I -Tiempos de respuesta bajos -Adecuado para sist. sincrónicos

- No garantiza el activado de los flip-flops (lugares) de salida de la transición que se ha disparado

LL-R-G

-Garantiza el activado de los flip-flops (lugares) de salida de la transición que se ha disparado

No se puede usar en sistemas sincrónicos - No garantiza el desactivado de los flip-flops (lugares) de entrada de la transición que se dispara

LL-R-S

-Garantiza el activado de los flip-flops (lugares) de salida de la transición que se dispara. -Garantiza el desactivado de los flip-flops (lugares) de entrada de la transición que se dispara

-No se puede usar en sistemas sincrónicos -Tiene tiempos de respuesta mayores a los de T-I -En algunos casos, no tiene información suficiente para discernir entre transiciones que verdaderamente se han disparado y las que no.

RdeP Sincrónicas Usar T.I. RdP Asincrónica Usar LL-R-S (o LL-R-G, si el microanálisis lo indica) con FF de GP

Tabla III Én la Figura 10 se muestra una parte de una RdeP y seguidamente se plantean las ecuaciones de activación y desactivación, par el lugar ´4´ para los tres métodos vistos.

69874

6498744

444

3214

QQQQr

QdQQQQcQr

dQcQr

bQaQQs

Figura 11 6.- CONVERSIÓN DE FLIP-FLOPs

Para convertir un flip-flop en otro, existen varias maneras de hacerlo. Una de ellas es por

comparación de las respectivas tablas de excitación. En Figura 11 se muestra, en forma esquemática, el problema mencionado. ¿Qué debemos colocar en el “circuito-?”, para que el FF-x se comporte como un FF-z?

activ.

des. T-I

des. LL-R-G

des. LL-R-S


Figura 11

Se muestra el método con un ejemplo concreto: convertir un flip-flop JK en un RS. Para esto ponemos las respectivas tablas de excitación apareadas, como se muestra seguidamente. En ella vemos qué debemos colocar en J y en K (en función de Qt, R y S) para lograr las transiciones Qt → Qt+1 deseadas. Es decir, debemos buscar las funciones booleanas de J y de K. Lo hacemos con el MdeK respectivo.

Resulta entonces el circuito de la Figura 12

Figura 12

Q 00 01 10 11

0 0 1 1 0

1 - - - -

Q Qt+1 R S J K

0 0 - 0 0 -

0 1 - 1 1 -

1 0 1 0 - 1

1

1

0 1 0

0 1 1

-

0 Q 00 01 10 11

0 - - - -

1 0 0 0 1

RS

RS

J = S

K = R S´


7.- FLIP-FLOPs COMERCIALES Comercialmente se fabrican los siguientes tipos de FF: Asincrónicos: SR Sincrónicos: D, JK, y T

8. - PROBLEMAS

Problemas de Implementación Cableada Por simplicidad en el dibujo, los lugares que estén marcados en el momento inicial aparecerán con un trazo GRUESO. Por otra parte, en todos los casos se cuenta con una señal de inicio (I) para inicializar al sistema, según se muestra a continuación: En todos los casos, se piden:

a) Las Ecuaciones de Marcado (Sn) y Desmarcado (Rn) de cada FFn b) Las Ecuaciones de las Salidas c) El Circuito incluyendo la inicialización

Además se debe indicar el tipo de FF (BP o GP utilizado) NOTA 1: Del tipo de FF utilizado En caso de que sea indistinto para la implementación por no contar la RdP con bucles cerrados, conviene usar FF de BP porque no hace falta agregarle los inversores a las entradas (como lo requieren los FF de GP). En caso que hubiese bucles cerrados hay 2 alternativas: implementar con FF de GP (agregándoles los inversores) o implementar con FF de BP agregando la información necesaria a la ecuación de R para discriminar el sentido de evolución de la marca para que ésta no se pierda por ser S=R=1 (microanálisis). NOTA 2: De la inicialización Si la RdP es ASINCRÓNICA, la señal de inicio I aparecerá en las ecuaciones de Sn y Rn como otra variable (se usan FF SR asincrónicos). Si la RdP es SINCRÓNICA, Los FF serán SR sincrónicos (en realidad armados con JK o D), por lo que contarán con entrada de sincronismo (CLK) y la inicialización debe ser asincrónica. De manera que la señal de inicio I se conectará a alguna de las entradas asincrónicas de Preset o Clear. Se conectará a los PR de los FF que deben grabarse en el inicio y al CLR de los FF que deben desactivarse en el inicio. Supongamos que al inicio se marca el lugar 1 y se desmarcan todos los demás: RdP Asincrónica:

RdP Sincrónica: EJEMPLO:

V

t

I

t

Las ecuaciones de las Salidas son IGUALES tanto si la RdP es Asincrónica como si es Sincrónica [Casos (a) y (b)]: Las ecuaciones de Marcado (Activación) se escriben de una manera única y se diferencian sólo en la señal de inicio (I). En las RdP Sincrónicas no aparece porque se conecta directamente al PR o al CLR del respectivo FF. En cambio en las RdP Asincrónicas aparece sumada o multiplicada por su inversa, ya que forma parte de las ecuaciones de las entradas S o R..

A = y2 D = y1 + y3.C

Dada la Rdp que se muestra, sacar las ecuaciones de Marcado y Desmarcado de los FF y las ecuaciones de las Salidas.

Caso a: suponer RdP Asincrónica Caso b: Suponer RdP Sincrónica.

I

S1 Q1

R 1 Q´1

S2 Q2

R 2 Q´2

S1 = f1 + I S2 = f2 . I´

R1 = g1 . I´ R2 = g2 + I

S2 Q2

R 2 Q´2 >

PR

CLR

S2 Q2

R 2 Q´2 >

PR

CLR I

CLK

La señal de inicio I no aparece en las ecuaciones de Sn y Rn, sino que se conecta directamente a las entrada de PR o CLR de los FF SR sincrónicos (implementados con FF JK o D y compuertas). La señal de reloj CLK se conecta a la entrada de sincronismo de cada FF.

D

A D/C

SB´

SB´

B´S´ B´S´

BS´

BS´

1

2 3

Desmarcado o Desactivación: Caso a: En las RdP ASINC. se puede desmarcar de la siguiente manera: 1) Si no hay bucles cerrados: utilizando LL-R-S con FF BP (para evitar los inversores que debiera agregar a los FF GP) 2) Si hay bucles cerrados: utilizando con LL-R-S con FF GP o LL-R-S+ID con FF BP (microanálisis). En este problema hay bucles cerrados, por lo que las alternativas son las indicadas en (2). Caso b: En las RdP SINC. se desmarca utilizando Transferencia Impulsional (T.I.). Las ecuaciones se escriben de una única manera:

ENUNCIADOS DE PROBLEMAS En todos los casos se pide que se seleccione el tipo de FF que se utilizará fundamentando el criterio para dicha elección:

a) Las Ecuaciones de Marcado (Sn) y Desmarcado (Rn) de cada FFn b) Las Ecuaciones de las Salidas c) El Circuito incluyendo la inicialización

Resolver considerando que la RdP fuese: 1) Asincrónica 2) Sincrónica

Caso a: RdP ASINC. S1 = (y2 B´S´+ y3 B´S´) + I

S2 = (y1 SB´+ y3 SB´) . I´ S3 = (y1 BS´+ y2 BS´) . I´

El FF1 se marca en el inicio y los FF1y2 se desmarcan en el inicio. En la ec. de R1 aparecerá multiplicado por I´ y en la ec. de R2 y R3 aparecerá sumado I.

Caso b: RdP SINC. S1 = (y2 B´S´+ y3 B´S´) S2 = (y1 SB´+ y3 SB´) S3 = (y1 BS´+ y2 BS´)

El FF1 se marca en el inicio conectando I a la entrada asinc. de PR y los FF 1y2 se desmarcan en el inicio conectando I a la entrada de CLR. La señal I no forma parte de las ecuaciones de S y de R.

Con FF GP: R1 = (y2+y3) .I´ R2 = (y1+y3) +I

R3 = (y2+y1) +I

No importa un posible seteo y reseteo simultáneos, ya que al utilizarse FF GP se grabará a pesar de ello. En este caso solo debe usarse la SALIDA NORMAL (Q) del FF, ya que al producirse S=R=1 sería Q´=Q.

Con FF BP: R1 = (y2.S+y3.B) .I´ R2 = (y1.S´+y3.S´) +I

R3 = (y2.B´+y1.B´) +I

Al multiplicar por una condición que se verifica al evolucionsr DESDE el lugar (ORIGEN) y no se verifica HACIA él (DESTINO) se vita el seteo y reseteo simultáneo (microanálisis).

R1=y1.S B´+y1.B S´ R2=y2.B´S´+y2.B S´ = y2.S´ R3=y3.B´S´+y3.S B´ = y3.B´

OBS: En las RdP Sinc. no existe el problema del seteo y reseteo simultáneos, ya que cuando se marca el destino se desmarca el origen (con el mismo pulso de reloj)

Y

1 2

3

4

X,W Y

Y/B

A+B´C

X

B

Problema 1: Problema 2:

7

6 5 4

2 3

1

X

X, W/C

C+E

A

Y

A´.D´

Y, X/B D´

B

A.D

B

2

Problema 3:

1

4 5

6 7 8

3

A´.B

W, Z/B Y

X

Y

X/C

W

A

B´+D A

A´.D

D´

Resolución Problema 1

Implementación Circuital (bosquejo incompleto para graficar la inicialización en cada caso) RdP Asincrónica:

RdP Sincrónica:

1.1 RdP ASINC. 1.2 RdP SINC:

Marcado S1=(y4.D)+I

S2=(y3.B)+I S3=y1.y2.(A+BĆ).I´ S4=(y3.B).I´

Desmarcado: FF GP R1=(y3).I´ R2=(y3).I´ R3=(y4.y2.)+I R4=(y1)+I

Desmarcado: FF BP R1=(y3).I´ R2=[y3.(A+B´)].I´ R3=(y4.y2.B)+I R4=(y1)+I

Salidas X=y2+y3 Y=y1+y4.B W=y2

Marcado S1=y4.D

S2=y3.B S3=y1.y2.(A+BĆ) S4=y3.B

La única diferencia es que en RdP SINC. la señal de inicio se conecta directamente a la entrada de PR y CLR de los FF sincrónicos (no forman parte de las ecuaciones de S y R)

Desmarcado R1= y1.y2.(A+BĆ) R2= y1.y2.(A+BĆ) R3=y3.B R4=y4 D

Salidas X=y2+y3 Y=y1+y4.B W=y2

RdP ASINC: método LL-R-S (con ID para FF BP si hay bucles cerrados). La señal inicio se incluye en ecuación. RdP SINC: método TI. Los bucles no afectan. La señal de inicio no forma parte de las ecuaciones.

Son IGUALES

S1 = f1 + I S3 = f3 . I´

R1 = g1 . I´ R3 = g3 + I

La señal de inicio I no aparece en las ecuaciones de Sn y Rn, sino que se conecta directamente a las entrada de PR o CLR de los FF SR sincrónicos (implementados con FF JK o D y compuertas). La señal de reloj CLK se conecta a la entrada de sincronismo de cada FF.

I

S1 Q1

R 1 Q´1

S3 Q3

R 3 Q´3

CLK

S2 Q2

R 2 Q´2 >

PR

CLR

S3 Q3

R 3 Q´3 >

PR

CLR I

La señal de inicio forma parte de las ecuaciones

cátedra de sistemas digitales i dpto. de sistemas e ... · síntesis cableada (con elementos de...

Documents