ELO211: Sistemas Digitales Tomás Arredondo Vidal 1er Semestre – 2008 Este material está basado en: ❒ textos y material de apoyo:

Contemporary Logic Design 1st / 2nd edition. Gaetano

Borriello and Randy Katz. Prentice Hall, 1994, 2005 ❒ material del curso ELO211 del Prof. Leopoldo Silva ❒ material en el sitio http://es.wikipedia.org

8: Multinivel

1

8-Síntesis Multinivel 8.1 Lógica de dos niveles con NOR y NAND 8.2 Lógica multinivel 8.3 Compuertas AND, OR, INVERT (AOI) 8.4 Introducción a síntesis multinivel

8: Multinivel

2

Lógica de dos niveles con NOR ❒ AND con inputs invertidos es un NOR ❍

de Morgan’s:

A’ • B’ = (A + B)’

❒ Circuito de dos niveles NOR-NOR ❍ ❍

inputs invertidos no se cuentan en un circuito típico se invierte una vez y se distribuye la señal

8: Multinivel

3

Lógica de dos niveles con NAND ❒ OR con inputs invertidos es compuerta NAND ❍

de Morgan’s:

A’ + B’ = (A • B)’

❒ Circuito NAND-NAND de dos niveles ❍ ❍

inputs invertidos no se cuentan en un circuito típico se invierte una vez y se distribuye la señal

8: Multinivel

4

Lógica de dos niveles con NAND y NOR

❒ Circuitos NAND-NAND y NOR-NOR ❍ ❍

de Morgan’s law: (A + B)’ = A’ • B’ escrito de otra forma: A + B = (A’ • B’)’

(A • B)’ = A’ + B’ (A • B) = (A’ + B’)’

❒ En otras palabras ❍ ❍ ❍ ❍

NOR es lo mismo que AND con inputs invertidos OR es lo mismo que NAND con inputs invertidos AND es lo mismo que NOR con inputs invertidos NAND es lo mismo que OR con inputs invertidos

8: Multinivel

5

Conversión entre formas ❒ Convertir entre circuitos de ANDs y ORs a

circuitos de NANDs y NORs ❍ introducir inversiones apropiadas (“burbujas”) ❒ Cada burbuja tiene que tener un burbuja correspondiente ❍ conservación de inversiones ❍ no se altera la lógica de la función ❒ Ejemplo: AND/OR to NAND/NAND A

A B

B

NAND

Z

NAND

C

C

D

D

Z

NAND 8: Multinivel

6

Conversión entre formas (continuado) ❒ Ejemplo: verificar equivalencia A

A

B

B

NAND

Z C D

NAND

Z

C D

NAND

Z = [ (A • B)’ • (C • D)’ ]’ = [ (A’ + B’) • (C’ + D’) ]’ = [ (A’ + B’)’ + (C’ + D’)’ ] = (A • B) + (C • D) ➼ 8: Multinivel

7

8-Síntesis Multinivel 8.1 Lógica de dos niveles con NOR y NAND 8.2 Lógica multinivel 8.3 Compuertas AND, OR, INVERT (AOI) 8.4 Introducción a síntesis multinivel

8: Multinivel

8

Lógica Multinivel ❒ x=ADF + AEF + BDF + BEF + CDF + CEF + G ❍ ❍

❍

forma reducida de suma de productos (no es canónica) 6 x 3-input AND + 1 x 7-input OR (puede que ni siquiera exista!) 25 alambres (19 literales más 6 alambres internos)

❒ x = (A + B + C) (D + E) F + G ❍ ❍

❍

forma factorizada – no escrita como suma de productos 1 x 3-input OR gate, 2 x 2-input OR gates, 1 x 3-input AND gate 10 alambres (7 literales más 3 alambres internos) A B C

X

D E F G

8: Multinivel

9

Conversión de lógica multinivel a compuertas NAND ❒ F = A (B + C D) + B C’

Level 1

Level 2

Level 3

Level 4

C D original AND-OR network

F

B A B \C C D

introduction and conservation of bubbles

redrawn in terms of conventional NAND gates

F

B A B \C

C D

F

\B A B \C 8: Multinivel

10

Conversión de lógica multinivel a compuertas NOR ❒ F = A (B + C D) + B C’ original AND-OR network

Level 1 C D B A B \C

Level 2

Level 3

Level 4 F

C introduction and conservation of bubbles

D B A

F

B \C \C \D redrawn in terms of conventional NOR gates

F

B \A \B C 8: Multinivel

11

Conversión entre formas ❒ Ejemplo A

A

B C D

B C D

F X

F X

sumar burbujas dobles para invertir inputs a compuerta OR

circuito original A

A

X B C \D

F X

sumar burbujas dobles para invertir output de AND

B C \D

F \X

insertar inversor para eliminar doble burbuja en alambre

8: Multinivel

12

8-Síntesis Multinivel 8.1 Lógica de dos niveles con NOR y NAND 8.2 Lógica multinivel 8.3 Compuertas AND, OR, INVERT (AOI) 8.4 Introducción a síntesis multinivel

8: Multinivel

13

Compuertas AND-OR-invert (AOI) ❒ Función AOI: tres etapas de lógica, AND,

OR, Invertir ❍

múltiples compuertas empaquetadas como un bloque implementación posible

concepto lógico A B

Z

C D AND

OR

2x2 AOI gate simbolo

Z

C D NAND

Invert

& + &

A B

NAND

3x2 AOI gate simbolo

Invert

& + & 8: Multinivel

14

Conversión a formas AOI ❒ Procedimiento para poner en forma AOI ❍ calcular complemento de la función en forma suma de productos ❍ agrupar los 0s en el mapa de Karnaugh ❒ Ejemplo: Implementar XOR ❍ A xor B = A’ B + A B’ A’ ❍ AOI form: & •

F = (A’ B’ + A B)’

B’ A

+

F

&

B

8: Multinivel

15

Ejemplo del uso del compuertas AOI ❒ Ejemplo: ❍ ❍ ❍

❍ ❍ ❍

F = A B + A C’ + B C’ F = (A’ B’ + A’ C + B’ C)’ Implementado con compuerta AOI de 3x2-inputs F = (A + B) (A + C’) (B + C’) F = [(A’ + B’) (A’ + C) (B’ + C)]’ Implementado con compuerta AOI de 3x2-inputs

❒ Ejemplo: Función de igualdad de 4-bits ❍

Z = (A0 B0 + A0’ B0’)(A1 B1 + A1’ B1’)(A2 B2 + A2’ B2’)(A3 B3 + A3’ B3’) cada uno implementado con una compuerta 2x2 AOI 8: Multinivel

16

Ejemplo del uso del compuertas AOI ❒ Ejemplo: Función de igualdad de 4-bits A0 B0

high if A0 ≠ B0 low if A0 = B0

& + &

A1 B1

&

conservation of bubbles

+ & NOR

A2 B2

& + &

A3 B3

Z if all inputs are low then Ai = Bi, i=0,...,3 output Z is high

& + & 8: Multinivel

17

8-Síntesis Multinivel 8.1 Lógica de dos niveles con NOR y NAND 8.2 Lógica multinivel 8.3 Compuertas AND, OR, INVERT (AOI) 8.4 Introducción a síntesis multinivel

8: Multinivel

18

Introducción: Síntesis Multinivel ❒ La minimización como suma de productos o producto de sumas es

un proceso de síntesis lógica en dos niveles. ❒ Estos tienen un mínimo retardo para la propagación de los

cambios entre las entradas y salidas pero a un costo de tener compuertas con gran numero de entradas ❒ Estas requieren mayor superficie para ubicar los transistores

por lo cual típicamente los diseños de sistemas complejos suelen tener mas de dos niveles ❒ Los dispositivos FPGA basado en interconexión de pequeñas

celdas estándar se presta para implementación de lógica multinivel

8: Multinivel

19

Introducción: Síntesis Multinivel ❒ Un circuito optimo de dos niveles usa el menor numero ❒

❒

❒ ❒ ❒

de términos de productos y literales Se entiende por optimización multinivel al proceso de encontrar factores lógicos que sean comunes, lo cual reduce el fan-in pero aumenta el numero de niveles En muchas tecnologías fan-ins de mas de cuatro son raros o no existentes es por eso que hay mucho interés en optimización (o síntesis) multinivel No es tan fácil definir un circuito optimo para implementaciones de multinivel. Es el que tiene el mínimo numero de compuertas, retardo, fan-ins o literales? El objetivo es sintetizar una implementación razonable 8: Multinivel 20 ya que cuesta saber a ciertas si es optimo

Introducción: Síntesis Multinivel ❒ Se modelan las ecuaciones usando una red lógica

❒

❒ ❒ ❒

boolana en la cual los componentes conectados (nodos) tienen como outputs funciones booleanas Usando transformaciones locales se trata de reducir el área y el tiempo de propagación del nodo o bien a mapear la función del nodo a determinada interconexión de celdas básicas Se intentan cambios (operaciones) y se aceptan si es que logran disminuir el costo del circuito (red o grafo). En caso contrario se intenta otra modificación y esto se repite hasta lograr reducciones en el costo La operaciones usadas tienen analogías con la multiplicación y división de polinomios (ver texto). 8: Multinivel

21

Introducción: Síntesis Multinivel ❒ Se modelan las ecuaciones usando una red lógica

boolana en la cual los componentes conectados (nodos) tienen como outputs funciones booleanas w = f1(A, B) A x1

B x2

A B y = f2(A, B)

z(w, y) 8: Multinivel

22

Introducción: Síntesis Multinivel ❒ Hay cinco operaciones básicas para manipular redes

multinivel: factorizar, descomposición, extracción, substitución y colapsar ❒ Factorizar toma una expresión en dos niveles y la reexpresa como una función multinivel sin introducir subfunciones. Puede ser mucho mas compacta que la cobertura mínima dada por la suma de implicantes primos. ❒ Ejemplo: La función F usa 9 literales y 5 compuertas F = AC + AD + BC + BD + E Factorizando el numero de literales se reduce a 5 y las compuertas a 4: F = (A + B)(C + D) + E 8: Multinivel

23

Introducción: Síntesis Multinivel ❒ Descomposición toma una expresión booleana y la

remplaza por nuevas expresiones mas simples. Se aplica a funciones que ya han sido factorizadas. ❒ Ejemplo: La función F usa 12 literales y 9 compuertas F = ABC + ABD + A’C’D’ + B’C’D’ Factorizando: F = (AB)(C + D) + (A’ + B’)(C’D’) = (AB)(C+D) + (AB)’(C+D)’ Decomponiendo el grafo en tres funciones mas simples: F = XY + X’Y’ X = AB Y=C+D La función final tiene 8 literales y requiere 7 compuertas. Tiene tres nodos en su representación en el grafo. 8: Multinivel

24

Introducción: Síntesis Multinivel ❒ Extracción toma una colección de expresiones booleanas y

determina sub-expresiones comunes para ser reutilizados. ❒ Requiere que las funciones se expresen como factores y que los factores comunes se extraigan ❒ Ejemplo: Las funciones F, G y H (contienen 11 literales y 8 compuertas). F = (A+B)CD + E G = (A + B)E’ H = CDE Se extraen sub-funciones comunes (divisores primarios): X = (A + B) e Y = (CD) Las funciones se pueden expresar como: F = XY + E G=XE’ H=YE X=A+B Y=CD Esta función tiene 11 literales y solo 7 compuertas. Cuantos 8: Multinivel 25 nodos tiene?

Introducción: Síntesis Multinivel ❒ Substitución substituye una función G en otra función F y

re-expresa F en términos de G. ❒ Ejemplo: La función F (4 literales y 2 compuertas). F = A + BCD Si se tiene la función G = A + BC y se substituye en F: F = A + BCD = G(A + D) (simplificando) Esta función (F) tiene 3 literales y 2 compuertas. Esto es ventajoso solo si podemos usar G en otra función ya que tiene 3 literales y una compuerta. ❒ Una vez que se determinan sub-expresiones comunes se pueden usar para expresar las funciones originales como funciones factorizadas usando las sub-expresiones. 8: Multinivel

26

Introducción: Síntesis Multinivel ❒ Colapsar es la operación reversa de substitución. Puede

ser usada para reducir el numero de niveles para satisfacer un requerimiento temporal. ❒ Ejemplo: Colapsar G de vuelta en F F = A + BCD = G(A + D) F = (A + BC) (A + D) F = AA + AD + ABC + BCD F = A + BCD ❒ Esto es ventajoso si no podemos usar G en otra función. ❒ Muchas veces se tiene que limpiar el grafo usando operaciones ya que los resultados de otras operaciones lo requieren (e.g. si es que G ya no es usado en otra función) 8: Multinivel

27

Resumen de lógica multinivel ❒ Ventajas ❍ circuitos puede ser mas pequeños ❍ compuertas tienen menor fan-in ❍ circuitos pueden ser mas rápido ❒ Desventajas ❍ mas difícil diseñar ❍ herramientas para la optimización no son tan buenas como para dos niveles ❍ análisis es mas complejo

8: Multinivel

28