1
Profesor Leopoldo Silva Bijit 19-01-2010
Apéndice 6
Uso de sis
Sequential Interactive System
A6.1. Introducción
En las primeras etapas de un diseño digital se requiere obtener la estructura del sistema en
términos de componentes de hardware. Se denomina síntesis lógica al proceso de generar un
circuito en términos de compuertas y flip-flops; en esta etapa suele efectuarse una minimización
del número de transistores que se emplearán (optimización espacial). Luego es necesario
efectuar minimizaciones de los retardos (optimización temporal), para esto se requiere efectuar
transformaciones de la red booleana de tal modo que la implementación final satisfaga los
requerimientos.
A medida que aumenta el tamaño del sistema estas técnicas no pueden aplicarse
manualmente y resultan indispensables herramientas computacionales.
Sis es un programa interactivo para la síntesis y optimización de circuitos combinacionales,
secuenciales sincrónicos y asincrónicos.
Pueden describirse funciones booleanas mediante: ecuaciones (.eqn), tablas de verdad o
matrices de cobertura (.pla), redes lógicas booleanas (.blif).
Los circuitos secuenciales pueden almacenarse como máquinas de estados finitos
describiendo el diagrama de estados (.kiss) o mediante una red booleana formada por
compuertas lógicas y elementos de memoria (.kiss2 blif sincrónicos).
Las funciones pueden ser manipuladas escribiendo comandos en forma interactiva o
empleando archivos de comandos (scripts). Se dispone de herramientas para: minimizar y
asignar estados; optimizar el área requerida para implementar las ecuaciones lógicas y
minimizar los retardos; mapear tecnológicamente a componentes mediante bibliotecas de partes.
El comando help despliega las órdenes disponibles.
A6.2. Formato blif.
Berkeley Logic Interchange Format especifica mediante un archivo de texto una red lógica
booleana. Cada nodo queda descrito por una función booleana en dos niveles.
2 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
Puede encontrarse una especificación detallada de este formato en el apéndice del manual de
SIS.
Estudiaremos el formato a través de ejemplos. El siguiente código describe una simple
compuerta and de dos entradas. Se emplean comentarios de fin de línea para explicar los
comandos.
.model CompuertaAnd # nombre de la red. Suele ser el nombre del archivo
.inputs a b #entradas del módulo
.outputs c #salida del módulo
.names a b c # Descripción pla de la función nand del nodo.
11 1
.end
La siguiente descripción muestra un sumador completo, texto que asumimos almacenado en
el archivo sumadorcompleto.blif.
.model SumadorCompleto
.inputs a b cin
.outputs sum cout
.names a b cin sum
001 1
010 1
100 1
111 1
.names a b cin cout
110 1
101 1
011 1
111 1
.end
El formato blif permite descripciones jerárquicas de redes complejas. Por ejemplo un
sumador completo de 4 bits puede describirse empleando el comando subcircuito, mediante el
cual se instancian cuatro módulos con las variables actuales, según:
.module fulladder4
.inputs a3 a2 a1 a0 b3 b2 b1 b0
.outputs s3 s2 s1 s0 cout
.subckt sumadorcompleto a=a0 b=b0 cin=zero sum=s0 cout=cout0
.subckt sumadorcompleto a=a1 b=b1 cin=cout0 sum=s1 cout=cout1
.subckt sumadorcompleto a=a2 b=b2 cin=cout1 sum=s2 cout=cout2
.subckt sumadorcompleto a=a3 b=b3 cin=cout2 sum=s3 cout=cout
.names zero #define la señal zero con valor 0
.end
Apéndice 6. Uso de sis 3
Profesor Leopoldo Silva Bijit 19-01-2010
.search sumadorcompleto.blif #lee el modelo desde archivo
En el ejemplo la reserva de entrada se ha fijado en cero, mediante la señal zero. La definición
de compuerta: .names zero fija o fuerza un cero lógico en la señal zero.
Una señal puede fijarse en uno, mediante la declaración:
.names uno
1 # setea en 1 la señal uno.
Mediante el comando .search se lee el contenido del archivo, con las declaraciones del módulo
del sumador completo.
A6.3. Lectura y escritura de archivos.
En el apéndice 3 sobre uso de espresso se describieron los formatos pla y eqn.
Se puede traducir de un formato a otro mediante la lectura de un formato y la escritura en
otro.
Los comandos que leen especificaciones de sistemas digitales combinacionales son:
read_eqn, read_pla y read_blif, seguidos del nombre del archivo.
Los comandos que escriben en diferentes formatos son: write_blif, write_pla, write_eqn. Si
se les agrega a continuación del comando un nombre de archivo, éste se almacena en disco; si
no se especifica nombre de archivo se despliega el formato en la pantalla.
En versiones unix, los finales de línea deben terminar en LF solamente.
Ejemplo A6.1. eqn.
Si un archivo denominando “eq.eqn” contiene la siguiente línea, en formato eqn:
O = a*b + !c*((d+e+f)*!(g+h));
Puede ser ingresado en sis, con el comando:
sis> read_eqn eq.eqn
Puede verificarse la ecuación ingresada, mediante el comando print, que muestra la ecuación
del nodo:
sis> print
{O} = a b + c' d g' h' + c' e g' h' + c' f g' h'
Ejemplo A6.2. blif.
Puede ingresarse una red boolena en formato blif, en la cual se especifican funciones
combinacionales mediante tablas de verdad en formato pla.
4 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
El ejemplo siguiente crea el modelo de una compuerta NOR de 3 entradas usando tres nodos
descritos por sus tablas de verdad, se especifican dos formas de definir compuertas OR de dos
entradas y un inversor. El archivo tiene nombre “nor3.blif”.
# Las líneas de comentario comienzan con #
# Debe colocarse un nombre para cada modelo
.model NOR3
# Se definen las entradas y salidas del modelo
.inputs a b c
.outputs out
#OR de dos entradas a y b, con condiciones superfluas.
# Se define un nodo interno (wire) de nombre int1
.names a b int1
1- 1
-1 1
# Tabla de verdad del conjunto on de un OR de dos entradas
.names int1 c int2
10 1
01 1
11 1
# Inversor
.names int2 out
1 0
# Fin del modelo.
.end
La estructura de la red, se muestra en la Figura A6.1
int1 a b
c
int2 out
Figura A6.1
La red puede leerse y describirse mediante las ecuaciones de los nodos, con los comandos:
sis> read_blif nor3.blif
sis> print
{out} = int2'
int1 = a + b
int2 = c int1 + c int1' + c' int1
Puede comprobarse que: out = a’b’c’ = (a + b +c)’= nor3(a, b, c)
Apéndice 6. Uso de sis 5
Profesor Leopoldo Silva Bijit 19-01-2010
Ejemplo A6.3. Máquina de estados finitos.
Se puede especificar una máquina de estados empleando formato kiss, dentro de un archivo
con extensión blif. El diagrama de estados de la Figura A6.2 representa a un verificador
(chequeador) de paridad. La entrada es serial. La salida es cero si, hasta el momento, han
llegado un número par de unos; y es uno si el número de unos es impar.
La máquina se mantiene en el estado PAR si han llegado un número par de unos; y se
mantiene en el estado IMPAR, si el número de unos que han llegado, hasta ese momento es
impar.
PAR IMPAR
0/1
1/0
1/1
0/0
Figura A6.2
La descripción en formato kiss, se ilustra en el ejemplo siguiente. En el formato kiss no
pueden colocarse nombres a las señales. Sin embargo al incluirlo dentro de un blif, podrían
colocarse identificadores para las señales.
# El archivo se almacena con el nombre paridad.blif
# Se emplea formato kiss para especificar máquinas de estado
.start_kiss
# una entrada (i), una salida (o), y 2 estados (s)
.i 1
.o 1
.s 2
# <entrada> <EstadoActual> <ProximoEstado> <salida>
0 PAR PAR 0
1 PAR IMPAR 1
0 IMPAR IMPAR 1
1 IMPAR PAR 0
.end_kiss
Puede minimizarse el número de estados con el comando: state_minimize y luego efectuarse
la asignación de estados con el comando state_assign. La salida puede escribirse en formato blif
con el comando write_blif, esto genera un archivo con el diseño en base a compuertas y flip-
flops.
La siguiente secuencia realiza el diseño de la red booleana.
sis> read_blif parity.blif
sis> state_minimize
6 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
sis> state_assign
sis> write_blif
La cual genera, en forma automática nombres para las señales de entrada y salida, además
coloca automáticamente los nombres a las entradas y salidas de los latch:
.inputs IN_0
.outputs OUT_0
.latch v2.0 LatchOut_v1 0 //asigna nombres a la entrada y salida de un latch
.start_kiss
.i 1
.o 1
.p 4
.s 2
.r PAR
0 PAR PAR 0
1 PAR IMPAR 1
0 IMPAR IMPAR 1
1 IMPAR PAR 0
.end_kiss
.latch_order LatchOut_v1
.code PAR 0
.code IMPAR 1
.names IN_0 LatchOut_v1 OUT_0
01 1
10 1
.names IN_0 LatchOut_v1 v2.0
01 1
10 1
.end
Notar que después de la descripción kiss, se especifica la asignación de estados y luego se
agregan los nodos combinacionales del próximo estado y de la salida, en términos de las señales
definidas al inicio. Si las ecuaciones se interpretan como compuertas or exclusivo, la Figura
A6.3, muestra la red booleana, resultante del diseño:
IN_0 D Q
clk
Out_0
LatchOut_v1 v2_0
Figura A6.3
Apéndice 6. Uso de sis 7
Profesor Leopoldo Silva Bijit 19-01-2010
El comando print, muestra las ecuaciones de los nodos:
sis> print
{OUT_0} = IN_0 LatchOut_v1' + IN_0' LatchOut_v1
v2.0 = IN_0 LatchOut_v1' + IN_0' LatchOut_v1
El comando write_eqn escribe las ecuaciones de las redes combinacionales solamente.
sis> write_eqn
Se genera la siguiente descripción:
INORDER = IN_0 LatchOut_v1;
OUTORDER = v2.0 OUT_0;
OUT_0 = IN_0*!LatchOut_v1 + !IN_0*LatchOut_v1;
v2.0 = IN_0*!LatchOut_v1 + !IN_0*LatchOut_v1;
También se puede generar la descripción combinacional en formato pla, lo cual podría ser
utilizado para minimizar con espresso. El siguiente comando:
sis> write_pla
Genera la siguiente descripción de las redes combinacionales, notar que se ha definido
automáticamente con el nombre LatchIn_[14] la entrada D del latch:
.i 2
.o 2
.ilb IN_0 LatchOut_v1
.ob LatchIn_[14] OUT_0
.p 4
01 10
10 10
01 01
10 01
.e
La Figura A6.4 muestra un esquema de la red combinacional; se ha agregado el latch que
completa el diseño.
IN_0
Out_0 LatchOut_v1
LatchIn_[14]
D Q
clk
Figura A6.4
8 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
Latch genérico.
La sintaxis de un latch genérico es:
.latch <input> <output> [<tipo> <control>] [<valor inicial>]
Tipo es uno de los siguientes: ffe, re, ah, al, asg, que corresponden a acrónimos de “falling
edge,” “rising edge,” “active high,” “active low,” o “asynchronous.”
Control es la señal de reloj para el latch. Puede ser la señal definida con: .clock en el modelo,
la salida de cualquier función del modelo o “NIL” si no hay reloj
Valor-inicial es el valor del estado inicial del latch. Puede ser: f0, 1, 2, 3g. “2” si es “don’t
care” y “3” si es “unknown.” Un valor no especificado se asume “3.”
Un modelo que tenga realimentaciones debe usar latchs, no se aceptan lazos puramente
combinacionales.
Ejemplo.
.model ffd # flip-flop D sincronizado con cantos de subida (“re”) del reloj c.
.inputs d
.output q
.clock c
.latch d q re c 0
.end
A6.4. Comandos para minimización de redes multinivel.
Una vez ingresado el circuito en alguno de los formatos: eqn, pla o blif, pueden aplicarse los
comandos para minimización multinivel.
A6.4.1. Descomposición.
decomp descompone un nodo interno en más de un nodo.
Normalmente esto conduce a la reducción de literales; y al mismo tiempo lleva a incrementar el
retardo de la red.
Si tenemos en el archivo ejdecomp.eqn la siguiente ecuación:
f=a*d+a*e+b*d+b*e+c*d+c*e;
sis>read_eqn ejdecomp.eqn
sis>print_stats
ejdecomop.eqn pi=5 po=1 node=1 lits(sop)=12
El comando: print_stats muestra que el sistema tiene: 5 variables de entrada, 1 de salida, 1
nodo interno, y 12 literales.
Si se ejecuta el comando decomp, y luego se muestran las ecuaciones se tiene:
sis>decomp
sis>write_eqn
f=[2]*[1];
Apéndice 6. Uso de sis 9
Profesor Leopoldo Silva Bijit 19-01-2010
[1]=d +e;
[2]=a + b +c;
Lo cual muestra que se han creado dos nodos internos, a los cuales se les ha colocado, en forma
automática, los nombres [1] y [2]. La estadística muestra que se tienen ahora 3 nodos internos y
se han reducido los literales a 7.
A6.4.2. Eliminación.
eliminate k remueve todos los vértices internos de la red cuyos valores sean menores o
iguales a k. El valor del nodo es el número de literales que se ahorran en la cuenta de literales de
la red dejando el nodo. La variable correspondiente al nodo se reemplaza en todas sus
ocurrencias; esto aumenta la cuenta de los literales. Este comando efectúa lo contrario de
decomp; y ayuda a disminuir el retardo de la red.
eliminate -1 remueve nodos que son empleados sólo una vez.
La siguiente red tiene 12 literales y 4 nodos.
f = a*b*c;
g = f + d;
h = f + b*c;
i = f + b*c*d; Si se elimina el nodo f, resulta un costo de 15 literales; es decir se produce un incremento de
3 literales.
Entonces el comando eliminate 1, o eliminate 2 no producen cambios, pero eliminate 3 logra
la eliminación del nodo f; ya que es 3 el costo de eliminar f. La red reducida queda:
g = a*b*c + d;
h = a*b*c + b*c; #h puede reducirse a b*c solamente.
i = a*b*c + b*c*d;
En el caso de que un nodo sólo aparezca una vez, su eliminación se logra con el comando:
eliminate -1.
La red:
f = a*b;
g = f+c;
Se simplifica a:
g = a*b+c;
A6.4.3. Simplificación.
Los comandos simplify y full_simplify ejecutan un programa de minimización en dos
niveles en cada uno de los nodos de la red; la simplificación completa emplea algoritmos más
complejos que tienden a obtener mejores resultados, pero con un mayor costo temporal de
ejecución. Puede emplearse los comandos con opciones –m nocomp, que utiliza las heurísticas
de minimización de espresso.
Para la siguiente red con 10 literales
f = a*!b*c + !a*!c + a*b;
10 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
g = !a*!b + a;
Luego de simplify, se reduce a 8 literales
f = b*g + !a*!c + a*c;
g = !b + a;
A6.4.4. Resubstitución.
Resub intenta substituir la expresión correspondiente a un nodo en las expresiones
correspondientes a los otros nodos. El propósito es reutilizar la expresión de un nodo como
subexpresión en alguno de los otros nodos, disminuyendo el número de literales.
Para cada par de nodos verifica si uno es factor del otro y viceversa; si se agrega opción –a,
se emplea método de división algebraica para determinar si un nodo es factor de otro. Se intenta
con la expresión para el nodo y la expresión complementada, iterando entre los nodos de la red
hasta que la reducción del costo no siga disminuyendo.
La siguiente red, tiene costo de 11 literales.
f = a*b;
g = a*b + c;
h = a*b + e;
i = a' + b' +k;
Luego de resub, queda con 8 literales.
f = a*b;
g = f + c;
h = f + e;
i = f’ +k;
A6.4.5. Factorización.
Extrae subexpresiones comunes entre los nodos y reescribe las ecuaciones de los nodos en
términos de las subexpresiones comunes.
Si se tiene la siguiente red, con 4 nodos y 26 literales:
w = a*!e + !c*d + b*d + !a*d;
x = d*e + c*e + !b + !a;
y = b*d + a*d + b*c + a*c + e;
z = c + b + a;
Luego de ejecutado el comando fx, se crean, en forma automática dos nuevos nodos, y
disminuyendo la cuenta de literales a 21.
w = d*b + !c*d + !a*d + a*!e;
x = e*[16] + !b + !a;
y = [16]*[17] + e;
z = [17] + c;
[16] = d + c;
[17] = b + a;
Apéndice 6. Uso de sis 11
Profesor Leopoldo Silva Bijit 19-01-2010
Suele usarse la secuencia fx, seguida de resub, ya que el primer comando encuentra los
factores comunes, y el segundo intenta emplear esos factores para mejorar la red.
A6.4.6. Limpieza.
Sweep es un comando que elimina los vértices que tienen solo una entrada y los de valor
constante.
La red siguiente tiene el nodo i, con valor constante, y el nodo f, con una sola entrada:
f = a;
g = f + c*i;
h = f + d;
i = 1;
Luego de sweep, resulta:
g = a + c;
h = a + d;
A6.4.7 Archivos de optimización multinivel.
Si se desea ejecutar una secuencia de comandos de optimización se suele usar un script. El
cual es un archivo de texto que contiene la secuencia de comandos que se desean ejecutar. Por
ejemplo si se desea ejecutar: fx, resub y luego sweep, basta escribir un archivo de texto con el
nombre comandos.script, con las siguientes líneas:
fx
resub; sweep
Pueden colocarse varios comandos, en la misma línea, separados por puntos y comas.
Se ejecuta la secuencia anterior con el comando:
source comandos.script
No es sencillo determinar una secuencia de comandos que produzcan el nivel de
minimización multinivel deseado. Los creadores del sistema sis han propuesto una secuencia
que ha dado buenos resultados para una gran variedad de circuitos. El archivo de comandos se
denomina script.rugged, y contiene cuatro etapas de minimización.
#primera etapa de limpieza
sweep
eliminate -1
simplify -m nocomp
eliminate -1
#simplificación con disminución acotada del fan in
sweep
eliminate 5
simplify -m nocomp
resub -a
12 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
#factorización
fx
resub -a
sweep
#simplificación del nodo
eliminate -1
sweep
full_simplify -m nocomp
Ejemplo A6.4.
Sea la red de la Figura A6.5
Figura A6.5
Las ecuaciones de la red, con 7 nodos y 33 literales es la siguiente:
z = a*c + a*d + b*c + b*d + e;
q = c*e + d*e;
r = q + a';
w = r + b';
y = a'*d + b*d + c'*d + a*e';
p = a + b;
x = p'*c + p*c' + p*c;
Luego de ejecutado script.rugged con los datos de la red anterior, se logra la siguiente red:
con 6 nodos y 21 literales. Aparecen dos nuevos nodos y se eliminan p, q y r.
z = [28]*[29] + e;
w = e*[28] + !b + !a;
y = a*!e + d*b + !c*d + !a*d;
x = [29] + c;
[28] = d + c;
[29] = b + a;
a
b
c
d
e
y =a’d +bd +c’d+ ae’
z = ac +ad +bc +bd +e
p = a + b
r =q + a’ w =r+b’
x = p’c + pc’+ pc
w
z
x
y
q = ce +de
Apéndice 6. Uso de sis 13
Profesor Leopoldo Silva Bijit 19-01-2010
A6.4.8. Otros comandos multinivel.
print_level imprime el nivel de todos los nodos. Los de nivel cero son las entradas a la red.
print_io imprime las entradas y salidas de la red.
invert <nodo> obtiene el complemento del nodo. Entregando el complemento del
producto de sumas.
reduce_depth –d k este comando controla el retardo de la red en una optimización
multinivel, dejándola en k niveles.
A6.5. Mapeo tecnológico.
Se denomina mapeo tecnológico al proceso de convertir una red lógica formada por
componentes arbitrarias a una red formada por componentes especificadas en una biblioteca
tecnológica.
Primero se forman diagramas patrones representando cada una de las compuertas de la
biblioteca por el conjunto básico de compuertas, por ejemplo nand de dos entradas e inversores.
Luego la lógica del sistema se transforma a una red formada por el conjunto básico de
compuertas, por ejemplo nand de dos entradas e inversores; luego esta red, que es independiente
de la tecnología, se minimiza.
Finalmente la red, es cubierta por un conjunto de los diagramas patrones, que son elecciones
posibles desde la biblioteca. Existen diferentes coberturas posibles; durante la cobertura, el área
o el retardo se emplean como criterios de optimización.
Ejemplo A6.5.
Se tiene la función: f=a +b’ +c’, y una biblioteca de partes constituida por compuertas:
inversor, nand, and, y or.
El conjunto de compuertas básicas está formado por nand e inversor.
La Figura A6.6 muestra la red estructurada con compuertas básicas. Es el mapeo
independiente de la tecnología.
c
f
a
b
Figura A6.6
La Figura A6.7 muestra los patrones de biblioteca, en base a las compuertas básicas.
Se indica el costo asociado al área, para cada elemento de la biblioteca, representado por
patrones. El tiempo de propagación a través de un inversor es 1, y a través del nand es 1.5.
14 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
and
inv
nand
or
2
3
4
5
Figura A6.7 Patrones biblioteca.
Se van haciendo calzar los patrones de la biblioteca con partes de la red que se desea mapear.
Se reconocen los patrones hasta tener cobertura completa y se calcula el costo espacial y
temporal. Encontrar todos las calces es un problema complejo; seleccionar los calces que son
coberturas también es un problema complejo.
En general pueden obtenerse varias soluciones, debe seleccionarse la más conveniente de
acuerdo al costo espacial y temporal.
Costo espacial: 2+3+2+3=10. Costo temporal: 1.5+1+1.5=4.
c
f
a
b
Figura A6.8 Cobertura 1.
Costo espacial: 2+4 +3 =9. Costo temporal: 1.5+1+1.5=4.
c
f
a
b
Figura A6.9 Cobertura 2.
Costo: 5+3=8. Costo temporal: 1.5+1+1.5=4.
Apéndice 6. Uso de sis 15
Profesor Leopoldo Silva Bijit 19-01-2010
c
f
a
b
Figura A6.10 Cobertura 3.
La heurística de calce estructural no es adecuada para las componentes programables
actuales. Esto debido a que para celdas básicas formadas por tablas de búsqueda de cuatro
variables, la biblioteca tendría demasiadas componentes, ya que habría que generar una celda de
biblioteca para cada una de las funciones que pueden generarse en una LUT. Una LUT de 4
variables permite formar 216
funciones, sin embargo no todas son diferentes; pero el número es
demasiado elevado. Este problema requiere herramientas computacionales de ayuda al diseño.
tech_decomp [-a and-limit] [-o or-limit]
Descompone todos los nodos de la red en compuertas and o compuertas or, dependiendo del
tipo de flag que se especifique: -a, -o.
Los fan-in quedan limitados por los números and-limit u or-limit. Si no se especifican por
defecto se asumen límites en 2.
read_library [-ainr] filename
Se lee una biblioteca de compuertas disponibles para efectuar el mapeo tecnológico.
La opción -a agrega la biblioteca a la corriente; si no se especifica a, se descarta la biblioteca
previa. La opción i suprime agregar inversores extra a los primitivos. El flag n indica usar nand
en lugar de nor. El flag –r indica que la biblioteca está en formato blif, en lugar de genlib.
map [-b #][-f #][-i][-m #][-n #][-r][-s][-p][-v #] [-A][-B #][-F][-G][-W]
El comando map, realiza el mapeo tecnológico, previo a su ejecución debe haberse cargado
la biblioteca de compuertas.
Con opción –m 0 produce un circuito de mínima área, sin considerar límites de carga.
Con opción –m 0 –AF produce un circuito de mínima área, considerando límites de carga.
Con opción –n 1 –AFG produce un circuito de mínimo retardo, considerando límites de
carga. Pueden especificarse los requerimientos de tiempo con el comando set_delays, de este
modo el comando puede intercambiar área por tiempo.
Con flag –s se imprime estadística del mapeo.
Print_gate imprime los nombres de las compuertas empleadas en cada nodo.
Print_delay imprime los retardos de cada nodo.
16 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
El retardo de la red se calcula por la estructura de la red multinivel y por la elección de las
compuertas que implementan las funciones.
Existen dos algoritmos que reestructuran la lógica para disminuir el retardo.
El comando speed up descompone la red en términos de compuertas simples, nands de dos
entradas e inversores, e intenta reducir los niveles colapsando secciones a través de trayectorias
largas. Se sugiere correr el comando con el script:
decomp -g; eliminate -1; speed up;
map -m 1 -A.
El commando reduce depth reduce en forma uniforme la profundidad de la red, formando
racimos de nodos que luego transforma en un nodo simple. Para evitar crecimiento del área se
determinan tamaños máximos de los racimos y se emplean comando de simplificación y
factorización. Los creadores de sis sugieren el siguiente script.delay para emplear este
comando.
#script.delay
sweep
decomp -q
tech_decomp -o 2
resub -a -d
sweep
reduce_depth -b -r
red_removal
eliminate -l 100 -1
simplify -l
full_simplify -l
sweep
decomp -q
fx -l
tech_decomp -o 2
read_library lib2.genlib
read_library -a lib2_latch.genlib
map -s -n 1 -AFG -p
Formato de bibliotecas genlib.
Las celdas combinacionales tienen el siguiente formato:
GATE <cell-name> <cell-area> <cell-logic-function>
<pin-info>
..
<pin-info>
<cell-name> es el nombre de la celda en la biblioteca. El net-list queda en terminus de estos
nombres.
<cell-area> define un costo relativo del área de la celda, en punto flotante.
Apéndice 6. Uso de sis 17
Profesor Leopoldo Silva Bijit 19-01-2010
<cell-logic-function> es la ecuación de la celda, en formato eqn, la cual se termina en punto
y coma. La ecuación define las entradas y salida de la celda. Si existen formas factorizadas que
pueden escribirse de diferente manera se especifican separadamente.
Ejemplo de minimal.genlib
GATE zero 0 O=CONST0;
GATE one 0 O=CONST1;
GATE inv1 1 O=!a; PIN * INV 1 999 0.9 0.3 0.9 0.3
GATE nand2 2 O=!(a*b); PIN * INV 1 999 1.0 0.2 1.0 0.2
GATE nor2 2 O=!(a+b); PIN * INV 1 999 1.0 0.2 1.0 0.2
Cada <pin-info> tiene el formato:
PIN <pin-name> <phase> <input-load> <max-load>
<rise-block-delay> <rise-fanout-delay> <fall-block-delay> <fall-fanout-delay>
<pin-name> es el nombre del pin en la <cell-logic-function>, puede ser un * para
especificar que todos los pines tienen idéntica información.
<phase> es INV, NONINV, o UNKNOWN
<input-load> define la carga de entrada del pin.
<max-load> especifica el fanout del pin.
<rise-block-delay> y <rise-fanout-delay> son los tiempos de levantamiento, típicamente en
nanoseconds, y nanoseconds/unidad de carga.
<fall-block-delay> y <fall-fanout-delay> son los tiempos de bajada.
Ejemplo A6.6.
Para la siguiente red, almacenada en ejmap.eqn: f=a*b*c*!d;
Empleando minimal.genlib, con los siguientes comandos:
sis>read_eqn ejmap.eqn
sis>read_library minimal.genlib
sis>map
sis>print
[4]= a’ + b’
[3]= d’
[5]=[3]’ + c’
{f}=[4]’ + [5]’
sis>print_gate
[4] nand2 2.00
[3] inv1 1.00
[5] nand2 2.00
{f} nand2 2.00
Nótese que la suma de los pesos asociados a las áreas da 7.00.
Las ecuaciones del mapeo se representan en la red de la Figura A6.11:
18 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
b
c
f
a
d
4
5 3
Figura A6.11
Si el comando map se ejecuta con el flag –s, se obtienen los valores:
Total gate area: 7.00
Maximun arrival time <3.90, 3.90>
Se asume que un cambio de una entrada se realiza con un retardo de 0.3. Luego la
propagación de la señal d, a través del inversor, tiene un costo temporal de: 0.9+0.3*1, que es la
suma del tiempo de levantamiento, más el debido al fan-out, que es uno en este caso. La
propagación a través de la compuerta [5] que es un nand2, tiene costo temporal: 1.0+0.2*1=1.2,
igual retardo produce el nand en la salida. En total: (0.3 + 1.2 + 1.2 + 1.2) = 3.9, que es el
tiempo de retardo de la ruta crítica, que es entregado como el máximo tiempo de arribo.
Si se ejecutan los mismos comandos, pero cambiando la biblioteca para el mapeo, por la que
se muestra a continuación, se obtiene la red de la Figura A6.12.
GATE zero 0 O=CONST0;
GATE one 0 O=CONST1;
GATE inv1 1 O=!a; PIN * INV 1 999 0.9 0.3 0.9 0.3
GATE nand2 2 O=!(a*b); PIN * INV 1 999 1.0 0.2 1.0 0.2
GATE nand3 3 O=!(a*b*c); PIN * INV 1 999 1.1 0.3 1.1 0.3
GATE nand4 4 O=!(a*b*c*d); PIN * INV 1 999 1.4 0.4 1.4 0.4
Nótese que en este caso se utiliza un nand de 4 entradas que ahora está disponible.
sis>print_gate
[3] inv1 1.00
[4] nand4 4.00
[f] inv1 1.00
sis>print
[3] = d’
[4] = [3]’ + a’ + b’ + c’
{f}= [4]’
Total gate area: 6.00
Maximum arrival time: <4.50, 4.50>
Apéndice 6. Uso de sis 19
Profesor Leopoldo Silva Bijit 19-01-2010
b c f a
d 4 3
Figura A6.12
Cálculo del retardo: Cada inversor: 1.2, el nand aporta: 1.4+0.4*1=1.8. La señal de entrada
se asume con un cambio de 0.3. Resulta: 0.3+1.2+1.8+1.2=4.5.
A6.6. Mapeo tecnológico a FPGA.
Las arquitecturas de las fpga más representativas están formadas por arreglos repetidos de
bloques lógicos idénticos. Los bloques típicos son: tablas de búsqueda y arreglos de
multiplexores.
Arquitecturas basadas en multiplexores.
El comando act_map realiza el mapeo sobre una fpga con arquitectura Actel. Con el flag –r
<filename> se escribe el mapeo en el archivo de nombre filename. No es necesario cargar una
biblioteca.
En la Figura A6.13 se ilustra el bloque básico, que implementa la siguiente ecuación:
0 1 0 1 0 1 0 1( )( ) ( )( )A A B Bout s s s A s A s s s B s B
0
1
B0 0 1
out 0 1
B1
A0
A1
sA
sB
s1 s0
Figura A6.13
La siguiente ecuación: f=a*b*c*d'; una vez cargada, mediante el comando:
act_map –r <nombre_archivo>, genera el siguiente mapeo:
MODEL "ejmapfpga.eqn";
TECHNOLOGY scmos;
VIEWTYPE SYMBOLIC;
20 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
EDITSTYLE SYMBOLIC;
INPUT "a" : "a";
INPUT "b" : "b";
INPUT "c" : "c";
INPUT "d" : "d";
OUTPUT "f" : "[2]";
INSTANCE "BASIC_BLOCK":physical NAME = INST0;
"A0" : "GND";
"A1" : "c";
"SA" : "b";
"B0" : "GND";
"B1" : "GND";
"SB" : "Vdd";
"S0" : "d";
"S1" : "GND";
"out" : "[3]";
INSTANCE "BASIC_BLOCK":physical NAME = INST1;
"A0" : "GND";
"A1" : "GND";
"SA" : "Vdd";
"B0" : "GND";
"B1" : "[3]";
"SB" : "Vdd";
"S0" : "a";
"S1" : "GND";
"out" : "[2]";
ENDMODEL;
Se tiene, para la instancia 0, la ecuación del bloque, en la cual se reemplazaron las entradas:
[3] ( 0)( 0 ) ( 0)(1 0 1 0)d b b c d bcd
Reemplazando en la instancia 1, de la ecuación del bloque, se obtiene:
[2] ( 0)(1 0 1 0) ( 0)(1 0 1 [3]) 3a a a abcd
Que comprueba el mapeo realizado, usando dos bloques.
Mapeo a xilinx
Write_xnf –pXC40 <nombre_archivo>
Genera archivo con extensión xnf, que es compatible con las herramientas xilinx.
Apéndice 6. Uso de sis 21
Profesor Leopoldo Silva Bijit 19-01-2010
Write_xnf –p X4 out.xnf
A6.7. Minimización y asignación de estados.
Los métodos descritos en el Capítulo 12, quedan restringidos a matrices de transiciones con
un número limitado de renglones y columnas.
Ejemplo A6.7. Formato kiss en Sis.
Se tiene la siguiente matriz de transiciones, ver capítulo 12, ejemplo 12.3:
Estado/Entrada 0 1
A E/0 D/1
B F/0 D/0
C E/0 B/1
D F/0 B/0
E C/0 F/1
F B/0 C/0
Figura A6.14. Matriz de transiciones Ejemplo A6.7.
#La descripción se almacena el ej12_3.blif .start_kiss
# una entrada (i), una salida (o) y 6 estados (s)
.i 1
.o 1
.s 6 # número de estados
.r A # reset lleva a estado A.
# <entrada> <EstadoActual> <ProximoEstado> <salida>
0 A E 0
1 A D 1
0 B F 0
1 B D 0
0 C E 0
1 C B 1
0 D F 0
1 D B 0
0 E C 0
1 E F 1
0 F B 0
1 F C 0
.end_kiss
.end
Después de leer el archivo, puede efectuarse la minimización:
sis> read_blif ej12_3.blif
sis> state_minimize
sis> write_blif
22 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
Se reducen dos estados, y se cambian automáticamente los identificadores de los estados,
resulta: .start_kiss
.i 1
.o 1
.p 8
.s 4
.r S1
0 S0 S3 0
1 S0 S0 0
0 S3 S0 0
1 S3 S1 0
0 S1 S2 0
1 S1 S0 1
0 S2 S1 0
1 S2 S3 1
.end_kiss
La asignación de estados se logra con el comando state_assign, el cual además genera el
diseño de la red booleana. Se han agregado comentarios a los identificadores elegidos por el
programa:
.model ej12_3.blif
.inputs IN_0
.outputs OUT_0
.latch v3.0 LatchOut_v1 0 # flip-flop con entrada v3.0 y salida v1.
.latch v3.1 LatchOut_v2 1 # flip-flop con entrada v3.1 y salida v2.
.start_kiss #la aplicación repite el código con las transiciones entre estados.
.i 1
.o 1
.p 8
.s 4
.r S1
0 S0 S3 0
1 S0 S0 0
0 S3 S0 0
1 S3 S1 0
0 S1 S2 0
1 S1 S0 1
0 S2 S1 0
1 S2 S3 1
.end_kiss
.latch_order LatchOut_v1 LatchOut_v2 #códigos asignados
.code S0 00
.code S3 11
.code S1 01
.code S2 10
.names IN_0 LatchOut_v1 LatchOut_v2 OUT_0 #ecuación de salida
101 1
Apéndice 6. Uso de sis 23
Profesor Leopoldo Silva Bijit 19-01-2010
110 1
.names IN_0 LatchOut_v1 LatchOut_v2 v3.0 #entrada flip-flop v2
00- 1
110 1
.names IN_0 LatchOut_v1 LatchOut_v2 v3.1 #entrada flip-flop v1
11- 1
0-0 1
.end
Las ecuaciones que describen las redes combinacionales de salida y próximo estado, se
obtienen con el comando write_eqn.
INORDER = IN_0 LatchOut_v1 LatchOut_v2;
OUTORDER = v3.0 v3.1 OUT_0;
OUT_0 = IN_0*LatchOut_v1*!LatchOut_v2 + IN_0*!LatchOut_v1*LatchOut_v2;
v3.0 = IN_0*LatchOut_v1*!LatchOut_v2 + !IN_0*!LatchOut_v1;
v3.1 = !IN_0*!LatchOut_v2 + IN_0*LatchOut_v1;
IN_0
Out_0
LatchOut_v1
v3.1
clk
LatchOut_v2 v3.0
Figura A6.15. Red booleana.
De blif a Verilog.
Considerando que con una señal de reset, la máquina debe ir al estado inicial S1=01, el cual
equivale a LatchOut_v1=0 y LatchOut_v2=1, puede traducirse las ecuaciones a un módulo
Verilog, considerando el esquema de procesos, tipo Mealy, de la Figura A6.15 a.
D Q
clk
Y
Reset’
y
x z P1 P2
Figura A6.15a. Esquema procesos verilog.
24 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
module ej12_3 (input clk, Resetn, IN_0, output OUT_0);
reg LatchOut_v1, LatchOut_v2;
wire OUT_0, v3_0,v3_1;
// Redes combinacionales de próximo estado y de salida. P1 assign OUT_0 = (IN_0&LatchOut_v1&~LatchOut_v2) | (IN_0&~LatchOut_v1&LatchOut_v2);
assign v3_0 = (IN_0&LatchOut_v1&~LatchOut_v2) | ( ~IN_0&~LatchOut_v1);
assign v3_1 =( ~IN_0&~LatchOut_v2) | (IN_0&LatchOut_v1);
// Proceso registro. P2
always @(negedge Resetn or posedge clk)
if (Resetn == 0) begin LatchOut_v1<=0; LatchOut_v2 <= 1; end //Inicial=01
else begin LatchOut_v1<=v3_0; LatchOut_v2 <= v3_1; end
endmodule
Se han colocado los operadores booleanos de verilog, y el nombre de las señales blif v3.0 y
v3.1, por identificadores válidos verilog.
Ejemplo A6.7a.
El diagrama de estados del ejemplo 12.4, en formato kiss2: #ej12_4.kiss2
.i 1
.o 1
.p 30
.s 15
.r a
0 a b 0
1 a c 0
0 b d 0
1 b e 0
0 c f 0
1 c g 0
0 d h 0
1 d i 0
0 e j 0
1 e k 0
0 f l 0
1 f m 0
0 g n 0
1 g o 0
0 h a 0
1 h a 0
0 i a 0
1 i a 0
0 j a 0
1 j a 0
0 k a 0
1 k a 0
0 l a 0
Apéndice 6. Uso de sis 25
Profesor Leopoldo Silva Bijit 19-01-2010
1 l a 0
0 m a 1
1 m a 1
0 n a 1
1 n a 1
0 o a 1
1 o a 1
.e
Luego de ejecutar: read_kiss ej12_4.kiss2 y state_minimize, con write_kiss se obtiene: .i 1
.o 1
.p 16
.s 8
.r S3
0 S0 S3 1
1 S0 S3 1
0 S3 S4 0
1 S3 S5 0
0 S1 S3 0
1 S1 S3 0
0 S2 S1 0
1 S2 S1 0
0 S4 S2 0
1 S4 S2 0
0 S5 S6 0
1 S5 S7 0
0 S6 S1 0
1 S6 S0 0
0 S7 S0 0
1 S7 S0 0
Logrando una reducción a 8 estados. Ahora el inicial es S3.
Ejemplo A6.8. Nova
Reconocedor de secuencias de largo 4. Salida uno cuando llegan: 0110 y 1010; salida cero
en el resto de los casos. El comando externo reset, debe llevar al estado inicial E0.
Entrada
Estado 0 1
E0 E1/0 E2/0
E1 E3/0 E4/0
E2 E4/0 E3/0
E3 E5/0 E5/0
E4 E5/0 E6/0
E5 E0/0 E0/0
E6 E0/1 E0/0
Figura A6.16 Matriz de transiciones Ejemplo A6.8
26 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
En el Capítulo 12 se obtienen mediante reglas heurísticas:
Primera regla: E3 adyacente con E4; E5 con E6
Segunda regla: E1 adyacente con E2; E3 con E4; E5 con E6.
Tercera regla: Para entrada 0, estados E0, E1, E2, E3, E4, E5 adyacentes entre sí. E0, E1, E2,
E3, E4, E5, E6 adyacentes entre sí para entrada 1. Dando preferencia a las dos primeras reglas,
se obtuvo la asignación que se muestra en la Figura A6.17:
Figura A6.17. Asignación por reglas.
La descripción de la máquina secuencial:
.start_kiss
.i 1
.o 1
.s 7
.r E0
# <entrada> <EstadoActual> <ProximoEstado> <salida>
0 E0 E1 0
1 E0 E2 0
0 E1 E3 0
1 E1 E4 0
0 E2 E4 0
1 E2 E3 0
0 E3 E5 0
1 E3 E5 0
0 E4 E5 0
1 E4 E6 0
0 E5 E0 0
1 E5 E0 0
0 E6 E0 1
1 E6 E0 0
.end_kiss
.end
Luego de minimizar y asignar estados, con el comando state_assig, se obtiene la siguiente
asignación:
.latch_order LatchOut_v1 LatchOut_v2 LatchOut_v3
V3
V1V2
00 01
0
1
E0 E3
E1 E4
1
0 2
3
11 10
E6
E5 E2
7
6 4
5
Apéndice 6. Uso de sis 27
Profesor Leopoldo Silva Bijit 19-01-2010
.code E0 000
.code E1 001
.code E2 100
.code E3 011
.code E4 101
.code E5 111
.code E6 110
La cual se muestra en la Figura A6.18.
Figura A6.18. Asignación por defecto de nova.
El programa nova, tiene diferentes algoritmos de asignación de estados.
El comando: state_assign nova –h, produce un listado de opciones.
Por defecto aplica la opción –e ig, que aplica sólo las restricciones debidas a la entrada.
Ejecutando el comando: state_assign nova –e ioh, se aplican restricciones debidas a la
entrada y salida, y da mejores resultados. Se obtiene la asignación:
.code E0 110
.code E1 011
.code E2 001
.code E3 000
.code E4 010
.code E5 100
.code E6 101
En este caso se cumplen las dos primeras reglas.
Figura A6.19. Asignación –e ioh.
V3
V1V2
00 01
0
1
E0
E1 E3
1
0 2
3
11 10
E6 E2
E5 E4 7
6 4
5
V3
V1V2
00 01
0
1
E3 E4
E2 E1
1
0 2
3
11 10
E0 E5
E6 7
6 4
5
28 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
Ejemplo A6.9. Jedi.
Como alternativa para efectuar la asignación de estados se dispone de la aplicación Jedi. Que
permite generar la codificación binaria de entradas y/o salidas descritas en forma simbólica. A
la vez, si se describe la matriz de transiciones entre estados en forma simbólica (formato kiss),
puede efectuar la asignación de estados.
Como puede verificarse la elección de los códigos binarios puede significar un ahorro
considerable en el costo de la implementación.
El comando: jedi ej12_8.blif, genera en la salida estándar, en formato blif, la asignación de
estados.
Si se redirige la salida a un archivo se obtiene otro que luego puede ser procesado, dentro de
sis. Por ejemplo: jedi ej12_8.blif > ej128as.blif.
Si se comunica la salida de jedi con espresso, mediante una cañería o “pipe”, puede
obtenerse el diseño minimizado de las redes combinacionales. En este caso debe agregarse la
opción –p, para generar el formato pla, que es compatible con espresso.
Por ejemplo: jedi –p ej12_8.blif | espresso > ej12.pla, genera el siguiente archivo:
# JEDI, official release 1.2
#
# States.E0 100
# States.E1 111
# States.E2 110
# States.E3 001
# States.E4 101
# States.E5 000
# States.E6 010
#
.i 4
.o 4
.ilb v.0 v.1.0 v.1.1 v.1.2
.ob v.2.0 v.2.1 v.2.2 v.3
.p 7
001- 0001
1-11 1000
110- 0100
-100 1100
01-0 1010
-0-0 1000
-11- 0010
.e
Apéndice 6. Uso de sis 29
Profesor Leopoldo Silva Bijit 19-01-2010
v_0
v.2.0 v.1.0
v.2.2
clk
v.1.1 v.2.1
v.1.2 v.3
Figura A6.20. Asignación jedi.
El comando: jedi –h, muestra las opciones de codificación que pueden emplearse. Por
ejemplo, el comando: jedi –e c ej12_8.blif, emplea una combinación de codificación de las
entradas y salidas.
En el manual de la aplicación, puede encontrarse la descripción del formato para
codificación con entradas y salidas simbólicas.
Ejemplo A6.10. Modelo Mealy.
El siguiente diagrama representa a una máquina secuencial de estados finitos que tiene salida
uno cada vez que las últimas tres entradas son la secuencia 101; cero en el resto de las
secuencias de entrada.
1 / 0
0 / 0
0 / 0
1 / 0
st0
st1
st2
1 / 0
0 / 0
reset
st3
0 / 0
1 / 1
Figura A6.21. Detector secuencia 101.
Puede describirse el diagrama por su matriz de transiciones.
.model 101 # salida 1 cada vez que las últimas tres entradas sean 1, 0, 1
.start_kiss
.i 1
.o 1
0 st0 st0 0
1 st0 st1 0
0 st1 st2 0
30 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
1 st1 st1 0
0 st2 st0 0
1 st2 st3 1
0 st3 st2 0
1 st3 st1 0
.end_kiss
.end
Los comandos:
sis> read_blif model101.blif
sis> state_minimize
sis> state_assign
sis> write_blif
Generan el siguiente archivo, con el diseño:
.model model101
.inputs v0
.outputs v3.2
.latch [6] v1 0
.latch [7] v2 0
.start_kiss
.i 1
.o 1
.p 8
.s 4
.r st0
0 st0 st0 0
1 st0 st1 0
0 st1 st2 0
1 st1 st1 0
0 st2 st0 0
1 st2 st3 1
0 st3 st2 0
1 st3 st1 0
.end_kiss
.latch_order v1 v2
.code st0 00
.code st1 11
.code st2 01
.code st3 10
.names v0 [6]
1 1
.names v0 v1 v2 [7]
-1- 1
1-0 1
Apéndice 6. Uso de sis 31
Profesor Leopoldo Silva Bijit 19-01-2010
.names v0 v1 v2 v3.2
101 1
.end
Que describe la red, formada por dos flip-flops.
Si se eliminan las líneas que describen la matriz de transiciones y la asignación de estados,
resulta:
.model model101
.inputs v0
.outputs v3.2
.latch [6] v1 0
.latch [7] v2 0
.names v0 [6]
1 1
.names v0 v1 v2 [7]
-1- 1
1-0 1
.names v0 v1 v2 v3.2
101 1
.end
v0
v3.2 v1
[7]
clk
v2 [6]
Figura A6.22. Modelo blif, detector secuencia 101.
Empleando: x para la entrada, z para la salida, y con flip-flops Ds, puede escribirse:
.model model101
.inputs x
.outputs z
.latch D1 Q1 0
.latch D2 Q2 0
.names x D1
1 1
.names x Q1 Q2 D2
-1- 1
1-0 1
.names x Q1 Q2 z
101 1
.end
32 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
Del formato blif, pueden escribirse las ecuaciones para los flip-flops y la salida:
Z= xQ1’Q2; D1= x; D2=xQ2’+Q1
Las ecuaciones pueden obtenerse dentro de sis, mediante el comando print.
De blif a Verilog.
Ecuaciones de las cuales puede describirse la estructura de la red en Verilog:
// output 1 whenever last 3 inputs were 1, 0, 1
module model101 (input clk, Resetn, x, output z);
reg Q1, Q2;
wire z, D1, D2;
// Redes combinacionales de próximo estado y de salida. P1
assign z = (x&~Q1&Q2);
assign D1 = x;
assign D2 = (x&~Q2) | (Q1);
// Proceso registro. P2
always @(negedge Resetn or posedge clk)
if (Resetn == 0) begin Q1<=0; Q2 <= 0; end //Inicial=00
else begin Q1<=D1; Q2 <=D2; end
endmodule
Si se agregan los módulos siguientes puede efectuarse una simulación, con una secuencia de
entrada: 10100100.
module test(z,x,clk,Resetn);
input z;
output x,clk,Resetn;
reg x,clk,Resetn;
initial
begin
$dumpfile("model101.vcd");
$dumpvars(0, x, Resetn,clk,z);
end
initial begin: DetenerSimulacion
// Detiene la simulación después de 100 unidades de tiempo de simulación.
#1000 $stop;
end
initial
begin
$monitor("x=%b z=%b Resetn=%b clk=%b ", x,z, Resetn, clk, $time);
Resetn=1;clk=0;x=0;
Apéndice 6. Uso de sis 33
Profesor Leopoldo Silva Bijit 19-01-2010
#5 Resetn=0;
#5 Resetn=1;
#5 x=1;
#5 clk=~clk;
#5 clk=~clk;
#5 x=0;
#5 clk=~clk;
#5 clk=~clk;
#5 x=1;
#5 clk=~clk;
if(z!=1) $display("error salida debe ser 1.");
#5 clk=~clk;
#5 x=0;
#5 clk=~clk;
#5 clk=~clk;
#5 x=1;
#5 clk=~clk;
if(z!=1) $display("error salida debe ser 1.");
#5 clk=~clk;
#5 x=0;
#5 clk=~clk;
#5 clk=~clk;
#5 x=0;
#5 clk=~clk;
#5 clk=~clk;
#5 $finish;
end
endmodule
module BancoDePrueba;
wire clk,Resetn,x,z;
model101 m1 (clk, Resetn,x,z);
test t1 (z,x,clk,Resetn);
endmodule
Pueden visualizarse las formas de ondas que se generan en el archivo model101.vcd:
Figura A6.23. Formas de ondas. Secuencia de entrada 1010100.
34 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
La salida z es asincrónica, debido al Modelo de Mealy. No se especificó escala de tiempo en
la simulación.
Ejemplo A6.11. Modelo de Moore.
El siguiente diagrama de Moore representa a una máquina secuencial de estados finitos, que
tiene salida uno cada vez que las últimas tres entradas son la secuencia 101; cero en el resto de
las secuencias de entrada.
1
0
0
1
st0
st1
st2
1
0
reset
st3
0
1
0 0 0 1
Figura A6.24. Detector secuencia 101.
La descripción de los estados:
.model m101Moore
.inputs x
.outputs z
.start_kiss
.i 1
.o 1
.p 8
.s 4
.r st0
0 st0 st0 0
1 st0 st1 0
0 st1 st2 0
1 st1 st1 0
0 st2 st0 0
1 st2 st3 0
0 st3 st2 1
1 st3 st1 1
.end_kiss
Luego de diseñar en sis, se obtiene:
.model m101Moore
Apéndice 6. Uso de sis 35
Profesor Leopoldo Silva Bijit 19-01-2010
.inputs x
.outputs z
.latch x LatchOut_v1 0
.latch v3.1 LatchOut_v2 0
.names LatchOut_v1 LatchOut_v2 z
10 1
.names x LatchOut_v1 LatchOut_v2 v3.1
-1- 1
1-0 1
.end
De blif a Verilog.
El cual se puede escribir como un módulo Verilog. Nótese que sólo cambia el proceso
combinacional.
module model101Moore (input clk, Resetn, x, output z);
reg Q1, Q2;
wire z, D1, D2;
// Redes combinacionales de próximo estado y de salida. P1
assign z = (Q1&~Q2);
assign D1 = x;
assign D2 = (x&~Q2) | (Q1);
// Proceso registro. P2
always @(negedge Resetn or posedge clk)
if (Resetn == 0) begin Q1<=0; Q2 <= 0; end //Inicial=00
else begin Q1<=D1; Q2 <=D2; end
endmodule
El siguiente módulo de prueba ilustra la generación de la secuencia dentro de un lazo for.
module test(z,x,clk,Resetn);
input z;
output x,clk,Resetn;
reg x,clk,Resetn;
reg [1:10] sec; //variable para almacenar secuencia de entrada
integer j;
initial
begin
$dumpfile("model101.vcd");
$dumpvars(0, x, Resetn, clk, z);
end
initial
begin
sec={1'b1,1'b0,1'b1,1'b0,1'b1,1'b0,1'b0,1'b1,1'b0,1'b1}; //inicio secuencia
//for (j=1;j<11;j=j+1) $display(" %d %b", j, sec[j]);
36 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
$monitor("x=%b z=%b Resetn=%b clk=%b ", x,z, Resetn, clk, $time);
Resetn=1;clk=0;x=0;
#5 Resetn=0;
#5 Resetn=1;
for (j=1;j<11;j=j+1)
begin
#5 x=sec[j];
#5 clk=~clk; //subida
#5 clk=~clk;
if(j>2)
if( (x==1)&&(sec[j-1]==0)&&(sec[j-2]==1)&&(z==1)) $display ("ok");
end
#5 $finish;
end
endmodule
Figura A6.25. Formas de ondas. Modelo de Moore.
En la Figura A6.25, se muestra el momento en el que debe imprimirse “ok”, para
indicar que detectó la secuencia 101 en la entrada.
A6.8. Conversión de blif a VHDL.
En la distribución de sis se dispone de dos aplicaciones que permiten convertir archivos en
formato blif a vhdl y viceversa. El formato blif debe especificar las compuertas y flip-flops
como compuertas de biblioteca; es decir debe estar mapeado tecnológicamente.
Requieren de una biblioteca genlib, como primer argumento. La entrada y salida pueden ser
redirigidas desde y hacia archivos.
Para pasar de blif a vhdl:
blif2vst ejlib.genlib < intro.blif > intro.vhd
Para convertir de vhdl a blif:
vst2blif ejlib.genlib < intro.vhd > intro.blif
ok
Apéndice 6. Uso de sis 37
Profesor Leopoldo Silva Bijit 19-01-2010
Ejemplo A6.12.
Una compuerta de biblioteca crea una instancia de una compuerta o flip-flop dependiente de
la tecnología. Los parámetros de esas compuertas están definidos en una biblioteca con formato
genlib. Con la siguiente biblioteca, almacenada en un archivo con nombre: ejlib.genlib:
#
# library gates + flip-flop + buffer
# Mnemonic gate names
#
# --- COMBINATIONAL GATES
GATE "inv_comb" 16 O=!1A; PIN * INV 1 999 1 .2 1 .2
GATE "buffer_comb" 16 O=1A; PIN * NONINV 1 999 1 .2 1 .2
GATE "and2_comb" 32 O2=1A*1B; PIN * NONINV 1 999 1 .2 1 .2
GATE "or2_comb" 32 O1=1A+1B; PIN * NONINV 1 999 1 .2 1 .2
GATE "const1_comb" 8 O=CONST1;
GATE "const0_comb" 8 O=CONST0;
# --- EDGE_TRIGGERED FLIP FLOPS
# D-FF
LATCH "dff_re" 88 Q=D;
PIN D NONINV 1 999 1 .2 1 .2
SEQ Q ANY RISING_EDGE
CONTROL CLK 1 999 1 .2 1 .2
CONSTRAINT * .2 .2
Para el siguiente esquemático, la descripción blif con mapeo tecnológico, es la siguiente:
E1
E0
S1
S0
E1n
E0n
E2
E3
E4
Figura A6.26. Esquemático intro.blif.
#intro.blif
.model intro
.inputs E1, E0
.outputs S1, S0
.gate inv_comb 1A=E1 O=E1n
.gate inv_comb 1A=E0 O=E0n
.gate and2_comb 1A=E1n 1B=E0 O2=E2
.gate and2_comb 1A=E1 1B=E0n O2=E3
.gate or2_comb 1A=E2 1B=E3 O1=E4
.gate buffer_comb 1A=E0n O=S0
38 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
.gate buffer_comb 1A=E4 O=S1
.end
El cual puede ser traducido a vhdl:
--intro.vhd
--[]-----------------------------------------[]--
-- | File created by Blif2Sls v1.0 | --
-- | | --
-- | by Roberto Rambaldi | --
-- | D.E.I.S. Universita' di Bologna | --
--[]-----------------------------------------[]--
ENTITY intro IS
PORT(E1, E0: in BIT ; S1, S0: out BIT );
END intro;
ARCHITECTURE structural_from_SIS OF intro IS
COMPONENT "inv_comb"
PORT (O : out BIT ; 1A : in BIT );
END COMPONENT;
COMPONENT "buffer_comb"
PORT (O : out BIT ; 1A : in BIT );
END COMPONENT;
COMPONENT "and2_comb"
PORT (O2 : out BIT ; 1A : in BIT ; 1B : in BIT );
END COMPONENT;
COMPONENT "or2_comb"
PORT (O1 : out BIT ; 1A : in BIT ; 1B : in BIT );
END COMPONENT;
SIGNAL E1 : BIT;
SIGNAL E1n : BIT;
SIGNAL E0 : BIT;
SIGNAL E0n : BIT;
SIGNAL E2 : BIT;
SIGNAL E3 : BIT;
SIGNAL E4 : BIT;
SIGNAL S0 : BIT;
SIGNAL S1 : BIT;
BEGIN
inst0 : "inv_comb"
PORT MAP (O => E1n, 1A => E1);
inst1 : "inv_comb"
PORT MAP (O => E0n, 1A => E0);
inst2 : "and2_comb"
PORT MAP (O2 => E2, 1A => E1n, 1B => E0);
inst3 : "and2_comb"
PORT MAP (O2 => E3, 1A => E1, 1B => E0n);
Apéndice 6. Uso de sis 39
Profesor Leopoldo Silva Bijit 19-01-2010
inst4 : "or2_comb"
PORT MAP (O1 => E4, 1A => E2, 1B => E3);
inst5 : "buffer_comb"
PORT MAP (O => S0, 1A => E0n);
inst6 : "buffer_comb"
PORT MAP (O => S1, 1A => E4);
END structural_from_SIS;
A6.9. Síntesis de circuitos asincrónicos.
Mediante ejemplos simples se describe el uso de SIS para el diseño o síntesis de dispositivos
asincrónicos.
Los circuitos asincrónicos pueden describirse por un grafo de transiciones de señales
(ASTG). Se denominan transiciones a los eventos que representan cambios de los valores de las
señales de entrada o salida. Los estados o lugares representan las pre y post condiciones de las
transiciones.
Ejemplo A6.13.
Se tienen dos circuitos asincrónicos que interactúan entre sí a través de las señales: x, y, z.
x
y
z
Figura A6.27. Comunicación entre máquinas asincrónicas.
Los siguientes eventos se ilustran en la Figura A6.28: Un canto de subida de x desencadena
cantos de subida en z y en y. Un canto de subida en z implica un canto de bajada en x. Un canto
de subida en y, y un canto de bajada en x, producen un canto de bajada en z; éste último
desencadena un canto de bajada en y; el que a su vez produce un canto de subida en x.
x
y
z
Figura A6.28. Eventos.
40 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
El circuito a la derecha de la Figura A6.27, con entrada y, y con salidas x, z, puede
describirse mediante el siguiente grafo:
.model example
.inputs y
.outputs x z
.graph
x+ z+
x+ y+
z+ x-
x- z-
y+ z-
z- y-
y- x+
.end
El circuito a la izquierda tiene el mismo grafo, pero tiene como entradas a: x, z; con salida y.
El grafo puede almacenarse en el archivo: ex2astg.g, que se empleará más adelante.
Las listas de las señales de entrada y salida son separadas por espacios, no por comas. Un
nombre de señal seguido del símbolo + representa un canto de subida; seguido por el símbolo –
representa un canto de bajada. Puede usarse ~ para indicar conmutación. Cada línea describe un
elemento del grafo orientado, el cual se ilustra en la Figura A6.29.
x+
x-
y+
y-
z+
z-
Figura A6.29. Grafo ASTG.
Si se dispara x+, esta transición marca los lugares implícitos entre x+ y z+ y entre x+ e y+.
Entonces el evento x+ habilita las transiciones z+ e y+. Las transiciones z+ e y+ no comparten
precondiciones, por lo cual pueden dispararse en cualquier orden, se dice que son concurrentes.
Cuando las transiciones y+ y x- se disparan se habilita z-, ya que ambas precondiciones están
marcadas.
La representación, que es más general que el ejemplo simple que se ilustra, permite hacer
circular tokens a través del grafo, con lo cual pueden representarse las interacciones del circuito
con su ambiente. El ejemplo ilustra un caso sencillo de comunicación entre dispositivos
asincrónicos.
Apéndice 6. Uso de sis 41
Profesor Leopoldo Silva Bijit 19-01-2010
Estando dentro de SIS, el comando: read_astg <nombre_archivo> ingresa el grafo.
sis> read_astg exastg.g
sis> astg_syn
El comando astg_syn sintetiza el grafo en una implementación en dos niveles. Con una
asignación de estados libre de carreras.
El comando print muestra la red boolena.
sis> print
x_next = x_ z_' + y' z_'
z_next = x_ + y' z_
{x} = x_
{z} = z_
Las variables de estado se muestran seguidas de un underscore. Las salidas de las redes
combinacionales se muestran seguidas de next, por próximo estado.
Las ecuaciones anteriores resumen el diseño asincrónico mediante compuertas.
El comando astg_print_sg muestra el grafo con la asignación de estados y las transiciones
habilitadas en cada lugar.
sis> astg_print_sg
STATE GRAPH
state 0 : (y=0 x=0 z=0 )
enabled transitions : [x+ ]
state 1 : (y=0 x=1 z=0 )
enabled transitions : [y+ z+ ]
state 2 : (y=0 x=0 z=1 )
enabled transitions : [y+ ]
state 3 : (y=0 x=1 z=1 )
enabled transitions : [y+ x- ]
state 4 : (y=1 x=0 z=0 )
enabled transitions : [y- ]
state 5 : (y=1 x=1 z=0 )
enabled transitions : [z+ ]
state 6 : (y=1 x=0 z=1 )
enabled transitions : [z- ]
state 7 : (y=1 x=1 z=1 )
enabled transitions : [x- ]
La descripción gráfica de las transiciones entre estados, del listado anterior, se muestra en la
Figura A6.30.
42 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
xyz
000 x+
100 y+ z+
z+ y+
101 110
111
x-
x-
001
011 y+
z-
010
y-
Figura A6.30. Diagrama de transiciones.
Si se realiza el diseño para la red asincrónica a la izquierda de la Figura A6.27, resulta
sis> read_astg ex2astg.g
sis> astg_syn
sis> print
{y_next} = x + z
Ahora se tiene la variable de estado y.
Resumiendo las ecuaciones obtenidas, en ambos diseños, se obtiene, para las variables de
estado, identificando los próximos estados con el nombre de la variable seguida del símbolo +:
( )x z x y
z x y z
y z x
Las cuales pueden representarse por el esquemático de la Figura A6.31:
x
z
y
Figura A6.31. Red asincrónica.
Apéndice 6. Uso de sis 43
Profesor Leopoldo Silva Bijit 19-01-2010
Modificando el circuito de la Figura A6.31, agregando la señal r, que permite establecer el
estado inicial como x=0, y=0 y z=0, se obtiene:
x
z
y
r
a
b
Figura A6.32. Red asincrónica con señal de reset r.
Módulo que puede simularse, mediante Verilog, según:
module ej(r, x, y, z);
input r;
output x, y, z;
wire a, b;
or #2 G1 (y, x, z);
not #1 G2 (xp, x);
not #1 G3 (yp, y);
not #1 G4 (rp, r);
and #2 G5 (a, xp, y);
and #2 G6 (b, yp, z, rp);
nor #2 G7 (x, r, a, z);
or #4 G8 (z, x, b); // z se genera más lentamente que y
endmodule
Con lo cual pueden obtenerse las formas de ondas:
Figura A6.33. Formas de ondas.
44 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
Ejemplo A6.14.
Latch transparente. Sean las siguientes formas de ondas que especifican un latch, con D y G
entradas y salida Q:
2 3 4
G
D
Q
1
Figura A6.34. Formas de ondas latch.
Se indican cuatro pulsos de G. En el intervalo 1, puede ocurrir primero el canto de bajada de
D o bien el canto de subida de G; en la Figura A6.34 ocurre primero el canto de subida de G.
Para representar esta situación, puede definirse un lugar LQ1, de éste pueden gatillarse, en
cualquier orden, las transiciones G+ o D-.
El grafo de la Figura A6.35, muestra los lugares con círculos dobles, las transiciones con
círculos simples; un token como un punto negro, en el lugar LQ1. Esta marca indica que las
precondiciones se han cumplido; en el caso del ejemplo, significa que ya se produjo el canto de
bajada de G. Las diferentes instancias de G se enumeran de acuerdo a los números de la Figura
A6.34.
Cuando todas las pre-condiciones de una transición se han cumplido, ésta puede dispararse,
cambiando su valor y el token pasa a su post-condición. Los lugares con una pre-condición y
una post-condición se denominan lugares implícitos y no se dibujan. Un token sólo puede pasar
a un lugar, lo cual modela que los eventos deben producirse con una mínima separación
temporal entre ellos. Se acepta un no determinismo sólo en las entradas.
LQ1
G+/1 D-
G-/1 G+/2
Q-
G+/3
G-/2
LQ0
G-/3
D+
G+/4
Q+
G-/4
Figura A6.35. ASTG del latch.
Apéndice 6. Uso de sis 45
Profesor Leopoldo Silva Bijit 19-01-2010
En caso de estar en LQ1 se puede producir G+ o D- pero no ambas. Estando en LQ0 sólo se
puede producir una de las dos posibles: D+ o G+.
La descripción del grafo puede anotarse:
.name dlatch
.inputs D G
.outputs Q
.graph
LQ1 G+/1 D-
G+/1 G-/1
G-/1 LQ1
D- G+/2
G+/2 Q-
Q- G-/2
G-/2 LQ0
LQ0 G+/3 D+
G+/3 G-/3
G-/3 LQ0
D+ G+/4
G+/4 Q+
Q+ G-/4
G-/4 LQ1
.end
La síntesis puede realizarse según:
sis> read_astg dlatch.g
sis> astg_syn
sis> print
Q_next = G D + G' Q_ + D Q_
{Q} = Q_
sis> astg_print_sg
STATE GRAPH
state 7 : (D=1 CLK=1 Q=1 )
enabled transitions : [CLK- ]
state 6 : (D=1 CLK=1 Q=0 )
enabled transitions : [Q+ ]
state 5 : (D=0 CLK=1 Q=1 )
enabled transitions : [Q- ]
state 4 : (D=0 CLK=1 Q=0 )
enabled transitions : [CLK- ]
state 3 : (D=1 CLK=0 Q=1 )
enabled transitions : [D- CLK+ ]
state 2 : (D=1 CLK=0 Q=0 )
enabled transitions : [CLK+ ]
state 1 : (D=0 CLK=0 Q=1 )
46 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
enabled transitions : [CLK+ ]
state 0 : (D=0 CLK=0 Q=0 )
enabled transitions : [D+ CLK+ ]
Del listado anterior puede confeccionarse el diagrama de transiciones:
DGQ
111
G-
101
G+
D- Q+
G+
001 110
100
G+
D+
011
010
Q-
G-
000
G+
Figura A6.36. Diagrama de transiciones del latch.
De las ecuaciones de la red booleana, se obtiene el esquemático en base a compuertas. El
diseño está libre de perturbaciones y sin carreras críticas.
G
Q D
Figura A6.37. Circuito latch.
Ejemplo A6.15.
Sintetizar mediante compuertas un sistema digital con dos entradas m y s, y una salida q.
Apéndice 6. Uso de sis 47
Profesor Leopoldo Silva Bijit 19-01-2010
q
m
s
Figura A6.38. Entradas y salida de latch.
La Figura A6.39 muestra las relaciones causa-efecto entre las entradas y la salida. El canto
de subida de s, coloca alta la salida q; la señal m, puede ocurrir antes o después del canto de
subida de s, y su canto de bajada (en caso de estar presente) coloca baja la salida q. Si m no está
presente, la bajada de s también pone la salida q baja. El circuito que genera las señales s y m,
además debe cumplir que el canto de bajada de s ocurre antes que el canto de bajada de la señal
m.
2
1 2
s
m
q
1
1 2
Figura A6.39. Formas de ondas latch.
m+/1
LQ1
q+ /1
s+/1
s+/2
q+/2
s-/1
LQ2
m+/2
s-/2 m-
LQ4 LQ3
q-
Figura A6.40. ASTG del latch.
48 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
La descripción del grafo resulta:
#sm1.g
.inputs s m
.outputs q
.graph
LQ1 s+/1 m+/1
s+/1 q+/1
q+/1 LQ2
m+/1 s+/2
s+/2 q+/2
q+/2 LQ3
LQ2 s-/1 m+/2
s-/1 p4
m+/2 LQ3
LQ3 s-/2
s-/2 m-
m- LQ4
LQ4 q-
q- LQ1
.end
Notar que se han definido lugares donde existen más de una transición de salida o donde
llega más de una transición de entrada. Los tres recorridos posibles del token, a través del grafo,
representan las tres situaciones ilustradas en las formas de ondas. Se han numerado los cantos,
que especifican instancias de los eventos, en la Figura A6.39.
La síntesis mediante sis, se efectúa con los comandos:
sis> read_astg sm1.g
sis> astg_syn
sis> print
q_next = m q_ + s
{q} = q_
sis> astg_print_sg
STATE GRAPH
state 5 : (s=0 m=1 q=1 )
enabled transitions : [m- ]
state 4 : (s=0 m=1 q=0 )
enabled transitions : [s+ ]
state 7 : (s=1 m=1 q=1 )
enabled transitions : [s- ]
state 6 : (s=1 m=1 q=0 )
enabled transitions : [q+ ]
state 1 : (s=0 m=0 q=1 )
Apéndice 6. Uso de sis 49
Profesor Leopoldo Silva Bijit 19-01-2010
enabled transitions : [q- ]
state 0 : (s=0 m=0 q=0 )
enabled transitions : [s+ m+ ]
state 3 : (s=1 m=0 q=1 )
enabled transitions : [s- m+ ]
state 2 : (s=1 m=0 q=0 )
enabled transitions : [q+ ]
Las ecuaciones obtenidas permiten dibujar el esquemático del latch.
s
q m
Figura A6.41. Síntesis del latch.
El diagrama con asignación de estados libre de carreras, puede dibujarse a partir de la
descripción que entrega sis. Se ha mantenido de igual forma que el ASTG de la Figura A6.40,
para reforzar las similitudes y diferencias.
m+/1
q+ /1
s+/1
110
s-/1 m+/2
s-/2
m-
q-
000
100
smq
101
001
111
010
s+/2
q+/2
011
2 4
6
0
3
7
1
5
Figura A6.42. Diagrama de estados.
50 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
Ejemplo A6.16.
Diseñar un contador binario asincrónico ascendente, módulo 4, en base a compuertas, sin
emplear flip-flops, el diseño debe estar libre de perturbaciones y carreras. Con z1 la cifra más
significativa. Se cuentan los cantos de subida de la señal de entrada x. Expresar el diseño
mediante ecuaciones.
x z1
z0
Figura A6.43. Contador asincrónico módulo cuatro.
Se requieren ocho estados, los que se muestran en la Figura A6.44.
1
0 A
B
C
G 0
1
1
0 0
D
1
F
0 E
1
0
0
1
1
H 1 0
Figura A6.44. Diagrama de estados contador asincrónico módulo cuatro.
Asumiendo q2, q1 y q0 como variables de estado, en la Figura A6.45 se muestran las
relaciones causa-efecto entre la entrada y el estado.
Se han numerado algunos eventos, debido a que, en un período, existen cuatro cantos de
subida y bajada de x, y dos de q0. La descripción del grafo de las transiciones de las señales, se
basa en la Figura A6.45.
Apéndice 6. Uso de sis 51
Profesor Leopoldo Silva Bijit 19-01-2010
2 x
q2
q1
1 3 4
1 2 q0
z1
z0
Figura A6.45. Eventos en contador módulo 4.
La representación del grafo resulta:
.model cntmod4
.inputs x
.outputs q2 q1 q0
.graph
x+/1 q0+/1
q0+/1 x-/1
x-/1 q1+
q1+ x+/2
x+/2 q0-/1
q0-/1 x-/2
x-/2 q2+
q2+ x+/3
x+/3 q0+/2
q0+/2 x-/3
x-/3 q1-
q1- x+/4
x+/4 q0-/2
q0-/2 x-/4
x-/4 q2-
q2- x+/1
.end
Luego de lo cual puede obtenerse información de las ecuaciones y del diagrama de estados.
sis> read_astg contador.g
sis> astg_syn
sis> print
q2_next = q0_ q2_ + q0_' q1_ x' + q1_ q2_ + q2_ x
q1_next = q0_ q2_' x' + q0_' q1_ + q1_ q2_' + q1_ x
q0_next = q0_ q1_ q2_ + q0_ q1_' q2_' + q0_ x' + q1_ q2_ x + q1_' q2_' x
{q2} = q2_
{q1} = q1_
{q0} = q0_
52 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
Para el diagrama de estados, se obtiene:
sis> astg_print_sg
STATE GRAPH
state 11 : (x=1 q2=1 q1=1 q0=0 )
enabled transitions : [q0+ ]
state 0 : (x=0 q2=0 q1=0 q0=0 )
enabled transitions : [x+ ]
state 1 : (x=0 q2=1 q1=0 q0=0 )
enabled transitions : [q2- ]
state 12 : (x=1 q2=0 q1=0 q0=1 )
enabled transitions : [x- ]
state 13 : (x=1 q2=1 q1=0 q0=1 )
enabled transitions : [q0- ]
state 2 : (x=0 q2=0 q1=1 q0=0 )
enabled transitions : [q2+ ]
state 3 : (x=0 q2=1 q1=1 q0=0 )
enabled transitions : [x+ ]
state 14 : (x=1 q2=0 q1=1 q0=1 )
enabled transitions : [q0- ]
state 15 : (x=1 q2=1 q1=1 q0=1 )
enabled transitions : [x- ]
state 4 : (x=0 q2=0 q1=0 q0=1 )
enabled transitions : [q1+ ]
state 5 : (x=0 q2=1 q1=0 q0=1 )
enabled transitions : [x+ ]
state 6 : (x=0 q2=0 q1=1 q0=1 )
enabled transitions : [x+ ]
state 7 : (x=0 q2=1 q1=1 q0=1 )
enabled transitions : [q1- ]
state 8 : (x=1 q2=0 q1=0 q0=0 )
enabled transitions : [q0+ ]
state 9 : (x=1 q2=1 q1=0 q0=0 )
enabled transitions : [x- ]
state 10 : (x=1 q2=0 q1=1 q0=0 )
enabled transitions : [x- ]
Ejemplo A6.17. Contador asincrónico módulo tres.
Primero realizaremos un diseño clásico de la red asincrónica; luego describiremos las
relaciones causa-efecto que determinan el ASTG, y se empleará sis.
La Figura A6.46 muestra un diagrama de estados para el contador asincrónico módulo 3.
Apéndice 6. Uso de sis 53
Profesor Leopoldo Silva Bijit 19-01-2010
1
H
A
B
F 0
1
1
0 0
C
1
E
0 D
1
0
0
1
1
G 1
00
00
01 01
10
10
00 00
Figura A6.46. Diagrama de estados contador módulo 3.
La asignación de estados se efectúa empleando código Gray, de tal modo que los estados
adyacentes en la Figura A6.46 estén a distancia 1. Se elige arbitrariamente que el estado A esté
asociado al código 000.
G y H son estados inestables, empleados para transitar sin carreras desde estado F hasta el
estado A. Se dejan dos estados próximos sin especificar: estando en G con entrada 0, y estando
en H con entrada 0.
x
q2q1q0 0 1
A 000 001 000 00
B 001 001 011 00
C 011 010 011 01
D 010 010 110 01
E 110 111 110 10
F 111 111 101 10
G 101 - 100 00
H 100 - 000 00
q2+q1+q0+ z1z0
Figura A6.47. Tabla de transiciones contador módulo 3.
La Figura A6.48 muestra un mapa del próximo estado, construido a partir de la tabla de la
Figura A6.47. Minimizando las funciones de próximo estado, libres de perturbaciones, se
obtienen:
q2+ = xq1q0’ + q2q1 + q2q0
q1+ = xq2’q0 + q1q0’+ x’q1 + q2’q1
q0+ = q2q1q0+ q2'q1'q0 + xq2'q0 + x'q1' + x'q2 + xq1q0
54 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
q1q0
xq2
00 01
00
01
001 ---
001 ---
11 10
000 000
100 011
11
10
010 111
010 111
101 011
110 110
q2+q1+q0+
Figura A6.48. Mapa de próximos estados de contador módulo 3.
Las funciones de salida, se representan en el mapa de la Figura A6.49, a partir de la tabla de
la Figura A6.47.
q0
q2q1
00 01
0
1
00 01
00 01
11 10
10 00
10 00
z1z0
Figura A6.49. Mapa de funciones de salida de contador módulo 3.
Se obtienen:
z1 = q2q1; z0 = q2’1
La Figura A6.50 muestra las formas de ondas de los cambios de estado relativas a los pulsos
asincrónicos de la entrada x. Se han enumerado los diferentes cambios de las señales, x y q0, en
un período.
Apéndice 6. Uso de sis 55
Profesor Leopoldo Silva Bijit 19-01-2010
2 x
q2
q1
1 3
1 2 q0
z1
z0
C D E F G B H A
Figura A6.50. Relaciones causa-efecto contador módulo 3.
La representación del grafo resulta:
.model cntmod3
.inputs x
.outputs q2 q1 q0
.graph
x+/1 q1+
q1+ x-/1
x-/1 q0-/2
q0-/2 x+/2
x+/2 q2+
q2+ x-/2
x-/2 q0+/1
q0+/1 x+/3
x+/3 q1-
q1- q0-/1
q0-/1 q2-
q2- x-/3
x-/3 q0+/2
q0+/2 x+/1
.end
La síntesis, libre de perturbaciones se obtiene mediante:
sis> read_astg cntmod3.g
sis> astg_syn
sis> print
q2_next = q0_ q2_ + q0_' q1_ x + q1_ q2_
q1_next = q0_ q2_' x + q0_' q1_ + q1_ q2_' + q1_ x'
q0_next = q0_ q1_ q2_ + q0_ q1_' q2_' + q0_ q2_' x + q1_' x' + q2_ x'
{q2} = q2_
{q1} = q1_
{q0} = q0_
56 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
En el diseño clásico se obtiene un término adicional, xq1q0, para eliminar perturbaciones en la
función q0+. La posible perturbación se produce con x=1, q1=1, q0=1; ya que con estos valores
la función, sin el término de consenso, queda: q0+= q2 + q2’. Si q2’ se genera a partir de q2, se
producirá la perturbación, de tipo falso cero, en el canto de bajada de q2. Observando las
formas de ondas de la Figura A6.50, se aprecia que el canto de bajada de q2 se produce con
q1=0 y q0=0; de este modo no es necesario emplear el término xq1q0. Debe notarse que la
síntesis de sis no lo genera.
La información del diagrama de estados, se logra con:
sis> astg_print_sg
STATE GRAPH
state 15 : (x=1 q2=1 q1=1 q0=1 )
enabled transitions : [q1- ]
state 4 : (x=0 q2=0 q1=0 q0=1 )
enabled transitions : [x+ ]
state 8 : (x=1 q2=0 q1=0 q0=0 )
enabled transitions : [x- ]
state 9 : (x=1 q2=1 q1=0 q0=0 )
enabled transitions : [q2- ]
state 6 : (x=0 q2=0 q1=1 q0=1 )
enabled transitions : [q0- ]
state 7 : (x=0 q2=1 q1=1 q0=1 )
enabled transitions : [x+ ]
state 10 : (x=1 q2=0 q1=1 q0=0 )
enabled transitions : [q2+ ]
state 0 : (x=0 q2=0 q1=0 q0=0 )
enabled transitions : [q0+ ]
state 11 : (x=1 q2=1 q1=1 q0=0 )
enabled transitions : [x- ]
state 2 : (x=0 q2=0 q1=1 q0=0 )
enabled transitions : [x+ ]
state 3 : (x=0 q2=1 q1=1 q0=0 )
enabled transitions : [q0+ ]
state 12 : (x=1 q2=0 q1=0 q0=1 )
enabled transitions : [q1+ ]
state 13 : (x=1 q2=1 q1=0 q0=1 )
enabled transitions : [q0- ]
state 14 : (x=1 q2=0 q1=1 q0=1 )
enabled transitions : [x- ]
Con la información anterior puede confeccionarse un grafo de transiciones con el estado total;
en éste se identifica el estado como la suma de las entradas y los estados internos, y se muestran
las transiciones únicas entre estados como eventos asincrónicos.
Apéndice 6. Uso de sis 57
Profesor Leopoldo Silva Bijit 19-01-2010
xq2q1q0
z1z2 q1+
B=St4 0001
x+ 00
01
01
1001 St12
1011 St14
St6 0011
q0- 01
01
10
0010 St2
1010 St10
x-
x+
q1-
St9 1100
q0- 00
00
00
1
1101 St13
1111 St15
St7 0111
q0+
10
10
10
0110 St3
1110 St11
x+
x-
q2+
St8 1000 00
q2-
A = St0 0000 00
x-
q0+
-
Figura A6.51. Grafo de transiciones entre estados totales.
Ejemplo A6.18. Elemento C.
Los cuatro posibles recorridos del ASTG se ilustran con las formas de ondas.
Se acepta concurrencia entre las entradas. Estando x baja, puede producirse primero el canto
de a o b; similarmente estando x alta, los cantos de bajada de a y b pueden llegar en cualquier
orden. El canto de subida de x tiene dos precondiciones: que hayan llegado primero los cantos
de subida de a y b.
.model elementoC
.inputs a b
.outputs x
.graph
x- a+ b+
a+ x+
b+ x+
x+ a- b-
a- x-
b- x-
.end
58 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
a+
x-
b+
b- a-
x+
Figura A6.53. ASTG de elemento C.
2 a
b
x
1 3 4
2 1 3 4
Figura A6.54. Formas de ondas en elemento C.
La síntesis se realize mediante:
sis> read_astg elementoC.g
sis> astg_syn
sis> print
x_next = a b + a x_ + b x_
{x} = x_
a
x
b
Figura A6.55. Síntesis de elemento C.
sis> astg_print_sg
STATE GRAPH
state 1 : (a=0 b=0 x=1 )
Apéndice 6. Uso de sis 59
Profesor Leopoldo Silva Bijit 19-01-2010
enabled transitions : [x- ]
state 0 : (a=0 b=0 x=0 )
enabled transitions : [a+ b+ ]
state 3 : (a=1 b=0 x=1 )
enabled transitions : [a- ]
state 2 : (a=1 b=0 x=0 )
enabled transitions : [b+ ]
state 5 : (a=0 b=1 x=1 )
enabled transitions : [b- ]
state 4 : (a=0 b=1 x=0 )
enabled transitions : [a+ ]
state 7 : (a=1 b=1 x=1 )
enabled transitions : [a- b- ]
state 6 : (a=1 b=1 x=0 )
enabled transitions : [x+ ]
Ejemplo A6.19. Compuerta and.
2 a
b
x
1 3 4
2 1 3 4
1 2 3 4
5
5
Figura A6.56. Formas de ondas en compuerta and.
Descripción del grafo asociado a compuerta and.
.model and
.inputs a b
.outputs x
.graph
a+/1 b+/1
b+/1 x+/1
x+/1 a-/1
a-/1 x-/1
x-/1 b-/1
b-/1 a+/2
a+/2 b+/2
b+/2 x+/2
x+/2 b-/2
b-/2 x-/2
x-/2 a-/2
a-/2 b+/3
60 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
b+/3 a+/3
a+/3 x+/3
x+/3 a-/3
a-/3 x-/3
x-/3 b-/3
b-/3 b+/4
b+/4 a+/4
a+/4 x+/4
x+/4 b-/4
b-/4 x-/4
x-/4 a-/4
a-/4 a+/5
a+/5 a-/5
a-/5 b+/5
b+/5 b-/5
b-/5 a+/1
.end
Grafo del estado total.
sis> astg_print_sg
STATE GRAPH
state 0 : (a=0 b=0 x=0 )
enabled transitions : [a+ b+ ]
state 2 : (a=1 b=0 x=0 )
enabled transitions : [a- b+ ]
state 3 : (a=1 b=0 x=1 )
enabled transitions : [x- ]
state 4 : (a=0 b=1 x=0 )
enabled transitions : [a+ b- ]
state 5 : (a=0 b=1 x=1 )
enabled transitions : [x- ]
state 6 : (a=1 b=1 x=0 )
enabled transitions : [x+ ]
state 7 : (a=1 b=1 x=1 )
enabled transitions : [a- b- ]
Finalmente, la síntesis:
sis> print
{x_next} = a b
Apéndice 6. Uso de sis 61
Profesor Leopoldo Silva Bijit 19-01-2010
Referencias
http://www-cad.eecs.berkeley.edu
SIS: A System for Sequential Circuit Synthesis. Ellen M. Sentovich, Kanwar Jit Singh, Luciano
Lavagno, Cho Moon, Rajeev Murgai, Alexander Saldanha, Hamid Savoj, Paul R. Stephan,
Robert K. Brayton, Alberto Sangiovanni-Vincentelli. Electronics Research Laboratory
Memorandum No. UCB/ERL M92/41, Mayo 1992.
62 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
Índice general.
APÉNDICE 6 ......................................................................................................................................... 1
USO DE SIS ........................................................................................................................................... 1
SEQUENTIAL INTERACTIVE SYSTEM ........................................................................................ 1
A6.1. INTRODUCCIÓN .......................................................................................................................... 1 A6.2. FORMATO BLIF. .......................................................................................................................... 1 A6.3. LECTURA Y ESCRITURA DE ARCHIVOS. ....................................................................................... 3
Ejemplo A6.1. eqn. ........................................................................................................................ 3 Ejemplo A6.2. blif. ......................................................................................................................... 3 Ejemplo A6.3. Máquina de estados finitos. ................................................................................... 5 Latch genérico. ............................................................................................................................... 8
Ejemplo. ................................................................................................................................................ 8 A6.4. COMANDOS PARA MINIMIZACIÓN DE REDES MULTINIVEL. ......................................................... 8
A6.4.1. Descomposición. ................................................................................................................ 8 A6.4.2. Eliminación. ....................................................................................................................... 9 A6.4.3. Simplificación. ................................................................................................................... 9 A6.4.4. Resubstitución. ................................................................................................................. 10 A6.4.5. Factorización. .................................................................................................................. 10 A6.4.6. Limpieza. .......................................................................................................................... 11 A6.4.7 Archivos de optimización multinivel. ................................................................................ 11
Ejemplo A6.4. .......................................................................................................................................... 12 A6.4.8. Otros comandos multinivel. ............................................................................................ 13
A6.5. MAPEO TECNOLÓGICO. ............................................................................................................ 13 Ejemplo A6.5. ............................................................................................................................... 13 tech_decomp ................................................................................................................................. 15 read_library ................................................................................................................................. 15 map ............................................................................................................................................... 15 Print_gate ..................................................................................................................................... 15 Print_delay ................................................................................................................................... 15 Formato de bibliotecas genlib. ..................................................................................................... 16 Ejemplo A6.6. ............................................................................................................................... 17
A6.6. MAPEO TECNOLÓGICO A FPGA. .............................................................................................. 19 Arquitecturas basadas en multiplexores....................................................................................... 19 Mapeo a xilinx ............................................................................................................................. 20
A6.7. MINIMIZACIÓN Y ASIGNACIÓN DE ESTADOS. ............................................................................ 21 Ejemplo A6.7. Formato kiss en Sis. .............................................................................................. 21
De blif a Verilog. ..................................................................................................................................... 23 Ejemplo A6.7a. ................................................................................................................................... 24
Ejemplo A6.8. Nova ...................................................................................................................... 25 Ejemplo A6.9. Jedi. ...................................................................................................................... 28 Ejemplo A6.10. Modelo Mealy. .................................................................................................... 29
De blif a Verilog. ..................................................................................................................................... 32 Ejemplo A6.11. Modelo de Moore. ............................................................................................... 34
De blif a Verilog. ..................................................................................................................................... 35
Apéndice 6. Uso de sis 63
Profesor Leopoldo Silva Bijit 19-01-2010
A6.8. CONVERSIÓN DE BLIF A VHDL. .............................................................................................. 36 Ejemplo A6.12. ............................................................................................................................ 37
A6.9. SÍNTESIS DE CIRCUITOS ASINCRÓNICOS. .................................................................................. 39 Ejemplo A6.13. ............................................................................................................................ 39 Ejemplo A6.14. ............................................................................................................................ 44 Ejemplo A6.15. ............................................................................................................................ 46 Ejemplo A6.16. ............................................................................................................................ 50 Ejemplo A6.17. Contador asincrónico módulo tres. .................................................................... 52 Ejemplo A6.18. Elemento C. ........................................................................................................ 57 Ejemplo A6.19. Compuerta and. .................................................................................................. 59
REFERENCIAS.................................................................................................................................... 61 ÍNDICE GENERAL. .............................................................................................................................. 62 ÍNDICE DE FIGURAS. .......................................................................................................................... 64
64 Sistemas Digitales
Profesor Leopoldo Silva Bijit 19-01-2010
Índice de figuras.
Figura A6.1 .................................................................................................................................... 4 Figura A6.2 .................................................................................................................................... 5 Figura A6.3 .................................................................................................................................... 6 Figura A6.4 .................................................................................................................................... 7 Figura A6.5 .................................................................................................................................. 12 Figura A6.6 .................................................................................................................................. 13 Figura A6.7 Patrones biblioteca. ................................................................................................. 14 Figura A6.8 Cobertura 1. ............................................................................................................. 14 Figura A6.9 Cobertura 2. ............................................................................................................. 14 Figura A6.10 Cobertura 3. ........................................................................................................... 15 Figura A6.11 ................................................................................................................................ 18 Figura A6.12 ................................................................................................................................ 19 Figura A6.13 ................................................................................................................................ 19 Figura A6.14. Matriz de transiciones Ejemplo A6.7. .................................................................. 21 Figura A6.15. Red booleana. ....................................................................................................... 23 Figura A6.15a. Esquema procesos verilog. ................................................................................. 23 Figura A6.16 Matriz de transiciones Ejemplo A6.8 .................................................................... 25 Figura A6.17. Asignación por reglas. .......................................................................................... 26 Figura A6.18. Asignación por defecto de nova. .......................................................................... 27 Figura A6.19. Asignación –e ioh. ................................................................................................ 27 Figura A6.20. Asignación jedi. .................................................................................................... 29 Figura A6.21. Detector secuencia 101. ........................................................................................ 29 Figura A6.22. Modelo blif, detector secuencia 101..................................................................... 31 Figura A6.23. Formas de ondas. Secuencia de entrada 1010100. ............................................... 33 Figura A6.24. Detector secuencia 101. ........................................................................................ 34 Figura A6.25. Formas de ondas. Modelo de Moore. ................................................................... 36 Figura A6.26. Esquemático intro.blif. ......................................................................................... 37 Figura A6.27. Comunicación entre máquinas asincrónicas. ........................................................ 39 Figura A6.28. Eventos. ................................................................................................................ 39 Figura A6.29. Grafo ASTG. ........................................................................................................ 40 Figura A6.30. Diagrama de transiciones. .................................................................................... 42 Figura A6.31. Red asincrónica. ................................................................................................... 42 Figura A6.32. Red asincrónica con señal de reset r. .................................................................... 43 Figura A6.33. Formas de ondas. .................................................................................................. 43 Figura A6.34. Formas de ondas latch. ......................................................................................... 44 Figura A6.35. ASTG del latch. .................................................................................................... 44 Figura A6.36. Diagrama de transiciones del latch. ...................................................................... 46 Figura A6.37. Circuito latch. ....................................................................................................... 46 Figura A6.38. Entradas y salida de latch. .................................................................................... 47 Figura A6.39. Formas de ondas latch. ......................................................................................... 47 Figura A6.40. ASTG del latch. .................................................................................................... 47 Figura A6.41. Síntesis del latch. .................................................................................................. 49 Figura A6.42. Diagrama de estados............................................................................................. 49
Apéndice 6. Uso de sis 65
Profesor Leopoldo Silva Bijit 19-01-2010
Figura A6.43. Contador asincrónico módulo cuatro. .................................................................. 50 Figura A6.44. Diagrama de estados contador asincrónico módulo cuatro. ................................. 50 Figura A6.45. Eventos en contador módulo 4. ............................................................................ 51 Figura A6.46. Diagrama de estados contador módulo 3. ............................................................ 53 Figura A6.47. Tabla de transiciones contador módulo 3. ............................................................ 53 Figura A6.48. Mapa de próximos estados de contador módulo 3. .............................................. 54 Figura A6.49. Mapa de funciones de salida de contador módulo 3. ........................................... 54 Figura A6.50. Relaciones causa-efecto contador módulo 3. ....................................................... 55 Figura A6.51. Grafo de transiciones entre estados totales. ......................................................... 57 Figura A6.53. ASTG de elemento C. .......................................................................................... 58 Figura A6.54. Formas de ondas en elemento C. .......................................................................... 58 Figura A6.55. Síntesis de elemento C. ........................................................................................ 58 Figura A6.56. Formas de ondas en compuerta and. .................................................................... 59