Diseño Combinatorio - Apuntes FAC - 2023-S2 PDF

Diseño Combinatorio Chavarrı́aZamora, Luis Alberto Introducción Diseño Combinatorio Personajes Retrieval Lección 3 Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Luis Alberto Chavarrı́a Zamora Especificación de un Circuito Ecuaciones Booleanas Notación Product...

Diseño Combinatorio Chavarrı́aZamora, Luis Alberto Introducción Diseño Combinatorio Personajes Retrieval Lección 3 Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Luis Alberto Chavarrı́a Zamora Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas CE1107 Fundamentos de Arquitectura de Computadores Área de Ingenierı́a en Computadores Tecnológico de Costa Rica Producto de Sumas Chavarrı́a-Zamora, Luis Alberto II Semestre, 2023 3 de agosto de 2023 Diseño Combinatorio 1/ 26 Diseño Combinatorio Contenido Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico 1 Introducción Personajes Retrieval Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas 2 Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Producto de Sumas 3 Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 2/ 26 Diseño Combinatorio Retrieval Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas Quote: ”The Analytical Engine act upon other things besides number, were objects found whose mutual fundamental relations could be expressed by those of the abstract science of operations, and which should be also susceptible of adaptations to the action of the operating notation and mechanism of the engine. . . Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition were susceptible of such expression and adaptations, the engine might compose elaborate and scientific pieces of music of any degree of complexity or extent. Ada Lovelace Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 3/ 26 Diseño Combinatorio Personajes Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas Figura 1: 3.1 Ada Byron Dagerrotipo Chavarrı́a-Zamora, Luis Alberto Figura 2: 3.2 Ada Byron Pintura Diseño Combinatorio 4/ 26 Diseño Combinatorio Personajes Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas Figura 3: 3.3 Bardeen,Shockley,Brattain Chavarrı́a-Zamora, Luis Alberto Figura 4: 3.4 Réplica Bell Lab Primer Transistor Diseño Combinatorio 5/ 26 Diseño Combinatorio Personajes Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas Figura 5: 3.5 William Shockley Chavarrı́a-Zamora, Luis Alberto Figura 6: 3.6 Robert Noyce Diseño Combinatorio 6/ 26 Diseño Combinatorio Retrieval Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas Conceptos relacionados con: XOR NAND NOR Fuentes de Tensión Niveles Lógico Márgenes de Ruido Disciplina Estática Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 7/ 26 Diseño Combinatorio Diseño Lógico Combinatorio Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas En electrónica digital, un circuito es una red que procesa variables de valores discretos con una especificación funcional y con una especificación de tiempos o sincronización. Notación Producto de Sumas Producto de Sumas Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 8/ 26 Diseño Combinatorio Circuitos Combinatorios y Secuenciales Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas Los circuitos digitales se clasifican como Combinatorios (algunas traducciones como Combinacionales) y el otro tipo Secuenciales. Circuito Combinatorio: En un circuito combinatorio, las salidas dependen únicamente de los valores corrientes de las entradas. Este es un circuito sin memoria. Puede ocurrir que dos circuitos diferentes respondan a la misma función lógica. Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 9/ 26 Diseño Combinatorio Circuito Lógico Combinatorio Chavarrı́aZamora, Luis Alberto Introducción Personajes Ejemplo Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas Figura 7: 3.7 Dos implementaciones para el circuito lógico combinatorio Y=A+B Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 10/ 26 Diseño Combinatorio Circuitos Combinatorios y Secuenciales (cont.) Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas Circuitos Secuenciales: En un Circuito Secuencial, la salida depende tanto de los valores de las entradas corrientes, como de los valores de las entradas previas, es decir, depende de la secuencia de entradas, esto implica memoria. Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 11/ 26 Diseño Combinatorio Especificación de un Circuito Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas Esta especificación se realiza en dos términos: la Funcional y la de Sincronización. La especificación funcional de un circuito combinatorio, expresa los valores de salida en términos de valores corrientes de las entradas. La especificación de sincronización o especificación de tiempos de un circuito combinatorio, consiste en los lı́mites inferiores y superiores considerando los tiempos de respuesta. Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 12/ 26 Diseño Combinatorio Especificación de un Circuito (cont.) Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Un circuito es combinatorio, si este consiste en circuitos de elementos interconectados de forma tal que: 1 Cada elemento en el circuito es un circuito combinatorio. 2 Cada nodo en el circuito, es una entrada del circuito o se conecta a exactamente a una salida de un elemento del circuito. 3 El circuito no contiene rutas cı́clicas: cada camino visita un nodo a lo más una vez. Notación Producto de Sumas Producto de Sumas Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 13/ 26 Diseño Combinatorio Especificación de un Circuito (cont.) Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas Las anteriores reglas son suficientes, pero no estrictamente necesarias! Ciertos circuitos que la desobedecen aún son circuitos combinatorios. Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 14/ 26 Diseño Combinatorio Notación Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas El complemento de la variable A es Ā. La variable A se llama forma verdadera. Esto no significa que la variable A tenga un valor de TRUE. Ā se le conoce como la forma complementaria. La operación AND de una o más literales se denomina producto. La operación OR de una o más literales se denomina suma. Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 15/ 26 Diseño Combinatorio mintémintérminos y Maxitérminos Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial 1 mintérmino: es el producto que involucra todas las variables de entrada de la función. 2 Maxitérmino: es una suma que involucra todas las variables de entrada Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 16/ 26 Diseño Combinatorio Forma Suma de Productos Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas En la Forma Suma de Productos, la especificación de una función Booleana se realiza mediante una Tabla de Verdad, esto consiste en considerar la especificación en todos y cada uno de los valores de cada variable de entrada de la función, aprovechando que es discreta binaria. Una Tabla de Verdad de n entradas contiene 2n filas (posibles combinaciones). Es por esto que un circuito construido para representar la función Booleana se puede llamar combinatorio. Como se ha mencionado anteriormente,en algunos textos, le denominan combinacional. Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 17/ 26 Diseño Combinatorio Forma Suma de Productos Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Ejemplo de relación de una Tabla de Verdad con los mintérminos Ejemplo Circuito Lógico Secuencial A 0 0 1 1 Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas B 0 1 0 1 Y 0 1 0 0 mintérmino ĀB̄ ĀB AB̄ AB Nombre min m0 m1 m2 m3 Cuadro 1: 3.1 Tabla de Verdad y mintérminos Cada fila de una Tabla de Verdad está asociada a un mintérmino. Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 18/ 26 Diseño Combinatorio Suma de Productos (cont.) Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Para construir la ecuación Booleana a partir de la Tabla de Verdad, se suman todos los mintérminos, que den como salida TRUE (uno). En el caso de la función de la Tabla anterior habrı́a un único mintérmino. Producto de Sumas Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 19/ 26 Diseño Combinatorio Forma Suma de Productos Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Otro ejemplo de derivación de la expresión a partir de la TT Ejemplo Circuito Lógico Combinatorio A 0 0 1 1 Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas B 0 1 0 1 Y 0 1 0 1 mintérmino ĀB̄ ĀB AB̄ AB Nombre min m0 m1 m2 m3 Cuadro 2: 3.2 Tomando los mintérminos que tienes salida TRUE. Se obtiene la expresión: Y=A B + AB Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 20/ 26 Diseño Combinatorio Forma Canónica y Notación Sigma Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas La forma de la expresión del ejemplo anterior, se le llama Canónica de suma de productos, dado que es la suma (OR) de los mintérminos (formados por AND de todas las variables de las entradas). También se puede escribir en la notación Sigma P F(A,B) = (m1 , m3 ) P F(A,B) = (1, 3) Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 21/ 26 Diseño Combinatorio Forma Producto de Sumas Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas: otra forma para expresar una función Booleana es la forma Canónı́ca de Producto de Sumas. Cada fila de Tabla de Verdad, corresponde a un Maxitémino. El siguiente ejemplo, toma de base la misma función booleana anterior. Producto de Sumas Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 22/ 26 Diseño Combinatorio Producto de Sumas Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Ejemplo de derivación de la expresión a partir de la TT Ejemplo Circuito Lógico Combinatorio A 0 0 1 1 Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas B 0 1 0 1 Y 0 1 0 1 Maxitérmino A+B A+B̄ Ā+B Ā+B̄ Nombre Max M0 M1 M2 M3 Cuadro 3: 3.3 Tomando los Maxitérminos que tienen salida FALSE. Se obtiene la expresión: Y = (A + B)(Ā + B) Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 23/ 26 Diseño Combinatorio Forma Canónica y Notación Pi Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas Producto de Sumas La forma Canónica, de la expresión del ejemplo anterior, en términos de produco de sumas: Se toman los Maxitérminos estos incluyen todas las variables, operandolas con la suma (u OR) y se aplica con AND a todos y cada uno. También se puede escribir en la notación Pi Q F(A,B) = (M0 , M2 ) Q F(A,B) = (0, 2) Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 24/ 26 Diseño Combinatorio Referencia Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas • Harris, David Money, and Sarah L. Harris. Digital Design and Computer Architecture. Morgan Kaufmann, 2012. Notación Producto de Sumas Producto de Sumas Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 25/ 26 Diseño Combinatorio Chavarrı́aZamora, Luis Alberto Introducción Personajes Retrieval Este documento ha sido elaborado con software libre incluyendo LATEX, Beamer, GNU-Make y Git en GNU/Linux Diseño Lógico Circuito Lógico Combinatorio Circuito Lógico Secuencial Especificación de un Circuito Ecuaciones Booleanas Notación Producto de Sumas © 2023 Luis Alberto Chavarrı́a-Zamora Área de Ingenierı́a en Computadores Instituto Tecnológico de Costa Rica Producto de Sumas Chavarrı́a-Zamora, Luis Alberto Diseño Combinatorio 26/ 26