Appendix A - Digital Logic

A-1

Unidad 3: Circuitos digitales.

Diapositivas traducidas del libro Principles of Computer Architecture Miles Murdocca and Vincent Heuring Appendix A: Digital Logic

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-2

Objetivos generales • El objetivo de este tema es abordar los principios básicos de la lógica digital, que pueden aplicarse en el diseño de una computadora digital. • Lograr el entendimiento de los principios de la Lógica combinatoria y de la Lógica Secuencial, utilizadas en el diseño de circuitos lógicos digitales, a partir de los cuales es posible construir integramente una computadora. • Estos circuitos implementan las operaciones básicas de mas bajo nivel , de las cuales depende el funcionamiento de una computadora.

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-3

Indice general • Lógica Combinatoria:

• Definiciones • Algebra de Boole • Componentes digitales

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-5

Algunas definiciones • Unidad lógica Combinatoria: un circuito lógico digital en el cual las decisiones lógicas se toman exclusivamente en base a las combinaciones de las entradas. Ejemplo: un sumador. • Unidad lógica Secuencial: un circuito donde las decisiones se adoptan no sólo en virtud de las combinaciones de entrada sino también de la historia anterior de las mismas entradas. Ejemplo: una unidad de memoria. • Máquina de estado finito: Un circuito que posee un estado interno y cuya salida es función de las entradas corrientes y de la historia previa de sus entradas

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-6

Unidad lógica Combinatoria •

Transforma un conjunto de entradas en un conjunto de salidas de acuerdo con una o más funciones lógicas.

•

Las salidas de una CLU son estrictamente funciones de las entradas, y se actualizan inmediatamente luego de cualquier cambio en las entradas. La unidad recibe un conjunto de entradas i0 – in y produce un conjunto de salidas f0 – fm que dependeran de las funciones lógicas correspondientes.

•

Las entradas y salidas para una CLU normalmente tienen dos valores binarios distintos : alto y bajo, 1 y 0, 0 y 1, o 5 volt y 0 volt por ejemplo.

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-8

Circuito combinacional • En general, un circuito combinacional consiste de n entradas binarias y m salidas binarias. Un circuito combinacional puede definirse de tres formas: • Tabla de verdad: Para cada una de las posibles combinaciones de las n señales de entrada, se enumera el valor binario de cada una de las m señales de salida. • Símbolo gráfico: Describe la organización de las interconexiones entre puertas. • Ecuaciones booleanas: Cada señal de salida se expresa como una función booleana de las señales de entrada. • Los circuitos combinacionales implementan las funciones esenciales de una computadora digital. Pero no proporcionan memoria, que es un elemento también esencial para el funcionamiento. • Para estos fines, se utilizan circuitos lógicos digitales mas complejos denominados circuitos secuenciales.

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-9

Algebra de Boole: Tablas de verdad • Es el sistema matemático usado para la representación de la logica, en el diseño de circuitos lógicos, que nos permite identificar mediante símbolos el objeto de un circuito lógico de modo que su estado sea equivalente a un circuito real. • Desarrollada en 1854 por George Boole • Más tarde mejorada por Claude Shannon (Bell Labs)

• Las salidas son calculadas para todas las posibles combinaciones de entradas ( ¿Cuántas combinaciones de entrada hay aquí ?)

Considere un cuarto con dos llaves A y B que actuan sobre la lampara Z. Cómo trabajan ? Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

A-10

Appendix A - Digital Logic

Asignación Alternativa de salida en función del estado de las llaves • En una tabla de verdad, se enumeran todas las posibles combinaciones de entrada de las var. binarias y se asigna el correspondiente valor 0 o 1 a la salida para cada combinación.

Aquí se presenta una asignación logica alternativa

En general, dadas n variables de entrada se pueden obtener 2 n n) combinaciones de entradas, existen -> 2 (2 posibles asignaciones de salida. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-11

COMPUERTAS LOGICAS

Tablas de verdad con todas las posibles funciones de dos variables binarias

• Las funciones lógicas booleanas que más frecuentemente se usan: AND, XOR, OR, NOR, XNOR, y NAND. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-12

Puertas lógicas y sus símbolos Una compuerta lógica es un dispositivo físico que implementa una función básica del Algebra de Boole. Símbolos lógicos de las funciones booleanas AND (Y), OR (O) , buffer, y NOT

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

A-13

Appendix A - Digital Logic

Símbolos lógicos para las funciones booleanas NAND,NOR, XOR y XNOR

O excluyente (XOR): Produce 1 en su salida, cuando el nro. de 1 en su entrada es impar Principles of Computer Architecture by M. Murdocca and V. Heuring

NOR EXCLUYENTE (XNOR): Produce una salida complementaria a la de XOR. © 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-14

Variantes de los símbolos lógicos básicos

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

A-15

Appendix A - Digital Logic

Propiedades básicas del Álgebra de Boole

Principio de dualidad: El dual de una función booleana se obtiene intercambiando sumas lógicas ( O ) por productos ( Y ) y productos por sumas.

Postulados

Teoremas

A, B, etc. son Literales; 0 y 1 son constantes. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

A-16

Appendix A - Digital Logic

Teorema de DeMorgan ( dos variables)

Se utiliza el Teorema de DeMorgan para convertir una compuerta O en una compuerta NAND. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-17

Conjunto de puertas Un conjunto completo de puertas permite generar otras compuertas lógicas que no son parte de dicho conjunto. Existen 3 conjuntos de compuertas lógicas que permiten lograr una estructura completa. (Y, O y NO, las compuertas NAND y las compuertas NOR). En el ejemplo anterior vimos como una función O, se implementa únicamente a través de compuertas NAND. La equivalencia funcional entre compuertas lógicas es importante en lo que hace a la aplicación practica, dado que un tipo de compuerta lógica puede tener mejores características operativas que otro, dependiendo de la tecnología utilizada. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-18

Representación en suma de productos y diagramas lógicos. • Muchas veces surge la necesidad de representar funcionas mas complejas que una simple compuerta lógica, tal como la función mayoría. • La función mayoría es cierta cada vez que mas de la mitad de sus variables lógicas de entrada son ciertas. • Este tipo de operación es común para la recuperación de errores, en la que se comparan las salidas de circuitos idénticos que operan sobre los mismos datos, a partir de lo cual se determina la salida real por medio del mayor nro. de salidas similares ( como una votación). • Una forma de representar ecuaciones lógicas requiere el uso de la forma suma de productos. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-19

La forma suma de productos (SOP) Fig. A.15—Tabla de verdad correspondiente a la función mayoría

• Ninguna de las compuertas analizadas hasta ahora puede ejecutar en forma directa la función mayoría-> Transforma la función en una ecuación lógica de dos niveles Y (producto lógico) y O • Implementa la función con un un arreglo de compuertas lógicas, usando el conjunto {AND, OR, NOT} • M es verdadero cuando A=0, B=1, y C=1, o cuando A=1, B=0, y C=1, y así sucesivamente en los restantes casos. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-21

La forma suma de productos •

La siguiente suma de productos describe la función mayoría para tres entradas:

• M = ABC + ABC + ABC + ABC = m3 + m5 +m6 +m7 = (3, 5, 6, 7) •

Expresión de la función mayoría en su “ forma canónica suma de productos”.

•

Cuando un producto lógico contiene todas las variables de la función, expresadas una sola vez, ya sea en su forma real o complementada, se denomina Termino Mínimo

•

Cada uno de los 2n términos son llamados mínimos comenzando desde 0 to 2n - 1

•

Note las relaciones entre números minitérminos y valores booleanos

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

A-22

Appendix A - Digital Logic

Implementación circuital de la función mayoría utilizando dos niveles ANDOR

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

A-23

Appendix A - Digital Logic

Cuatro convenciones utilizadas para indicar intersecciones

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-24

LA FORMA PRODUCTO DE SUMA (POS) Como expresión dual de la forma suma de productos, una ecuación representada en su forma producto de suma contiene conjuntos de variables afectadas por operaciones de suma lógica cuyos resultados se convierten en un producto lógico. Se obtiene el complemento de la función suma de productos y aplicando los teoremas de DeMorgan. Seleccionando los términos de entrada que hacen 0 a la salida:

F  A * B*C  A * B* C  A * B *C  A * B*C Principles of Computer Architecture by M. Murdocca and V. Heuring

A.3

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-25

LA FORMA PRODUCTO DE SUMA (POS) (I) Se complementa ambos miembros de la igualdad, surge la ecuación

F  A * B*C  A * B* C  A * B *C  A * B*C La aplicación del teorema de DeMorgan; en la primera negación, en la forma siguiente:

W  X  Y  Z  W * X *Y * Z

Da origen a la ecuación:

F = ( A* B* C) * ( A* B* C ) * ( A* B* C ) * ( A* B* C )

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-26

LA FORMA PRODUCTO DE SUMA (POS) (II) Una nueva aplicación del Teorema de DeMorgan a los términos entre paréntesis, ahora en su forma:

W * X *Y * Z  W  X  Y  Z Da origen a la ecuación:

F  ( A  B  C) * ( A  B  C) * ( A  B  C) * ( A  B  C)

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-27

LA FORMA PRODUCTO DE SUMA (POS) (III) Esta ecuación esta expresada en la forma producto de sumas y contiene 4 términos máximos, en los que cada variable de la función aparece una sola vez en forma real o complementada. Un termino máximo ( A + B + C ) adopta un valor 0, para una única entrada de la tabla de verdad. Un argumento para el uso de la forma producto de sumas en reemplazo de la forma de la forma suma de productos, puede ser la obtención de una expresión booleana mas sencilla.

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-28

La función mayoría implementada con dos niveles AND – OR (POS) F  ( A  B  C) * ( A  B  C) * ( A  B  C) * ( A  B  C)

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-29

Formas SOP Y POS • Una expresión booleana mas sencilla puede significar un circuito mas simple. • Existen además consideraciones que no dependen del tamaño de la ecuación booleana, sino de la complejidad de la topología de cableado. • Parámetros de complejidad del circuito • Cantidad de compuertas

• Cantidad de entradas en las compuertas

• En función de lo anterior se pueden comparar ambas implementaciones de circuitos.

• Dado que una ecuación booleana mas pequeña se traduce en un circuito con menor cantidad de compuertas, -> la reducción es importante ( Mapas de Karnaugh).

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-30

Componentes digitales • En los diseños de circuitos digitales de alto nivel, además de las compuertas individuales, suelen utilizarse componentes ( conjuntos de compuertas lógicas ) o bloques funcionales. • Objetivo: Abstraer un cierto nivel de complejidad circuital • La función mayoría puede verse como una componente. • Niveles de integración (número de puertas) en un único circuito integrado:

• Integrados en pequeña escala (SSI): 10-100 elementos. • Integración en escala media (MSI): 100 a 1000 elementos. • Integración a gran escala (LSI): 1000-10.000 elementos.

• Integración en mayor escala (VLSI): 10.000 y más. • Estos son niveles aproximados, pero son útiles para comparar la complejidad relativa de los distintos circuitos. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-31

Componentes digitales MSI • Multiplexores • Demultiplexores • Decodificadores • • Codificadores de prioridad

• Matrices logicas programables • Sumador con arrastre serie Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-32

Multiplexores Entradas de datos

Cuando se diseñan circuitos utilizando multiplexores, se los considera como un Bloque funcional, que se representa como una “Caja negra”. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-33

Circuito AND – OR que implementa el multiplexor de cuatro entradas.

Comparando con el anterior: Se evitan detalles innecesarios en el diseño de circuitos complejos Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

A-34

Appendix A - Digital Logic

La función mayoría implementada con un Mux 8-1

La implementación de funciones booleanas puede ser realizada por medio de multiplexores. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

A-35

Appendix A - Digital Logic

Mayor eficiencia: Uso de un multiplexor 4-1 para implementar la función mayoría.( 3 variables y 4 entradas de datos.)

Principle: Uso de las entradas A y B inputs para seleccionar un par de miniterminos. Las entradas de datos al MUX se toman del conjunto {0, 1, C, C}. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-36

Demultiplexores (DEMUX)

D: Entrada de datos; A y B: Entradas de control Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-37

El demultiplexor con su entrada en 1 es un decodificador. Comparar con la Fig A.29

Aplicación: Envío de datos desde un origen único hacia un conjunto de destinos. Ej.: Circuito de llamada de ascensores que deriva la llamada al ascensor mas cercano. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-38

Decodificadores Decodificador: traduce una codificación lógica hacia una ubicación espacial. En cada momento solo una de las salidas del decodificador está en estado activo ( 1 lógico). Puede usarse para controlar otros circuitos. Para no habilitar circuitos erróneamente incorpora entonces una línea de habilitación. Aplicación: Traducción de direcciones de memoria a sus correspondientes ubicaciones físicas. En la implementación de funciones booleanas. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-39

Decodificadores. •Un decodificador traduce una codificación logica hacia una ubicación espacial. •A veces se introduce una línea de habilitación que fuerza todas las salidas a 0, cuando se le aplica un 0 en la entrada.

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-40

Decodificador 2-4. A.29. Circuito de compuertas Y para el decodificador 2 a 4

Demultiplexor de 4 Salidas con su entrada En 1

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

A-41

Appendix A - Digital Logic

La función mayoría implementada por un decodificador 3 a 8

En c/momento, solo una de las salidas del decodificador esta en el estado activo. Las salidas no utilizadas se dejan desconectadas Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-42

Codificadores de prioridad • Traduce un conjunto de entradas en un código binario • Puede pensarse como el circuito opuesto al de un decodificador • Un codificador de prioridad establece un ordenamiento de las entradas. • Ai tiene una mayor prioridad que Ai+1

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

A-43

Appendix A - Digital Logic

Matrices lógicas programables (PLAs) • Una PLA es una matriz configurable de compuertas AND seguida de otra matriz configurable de compuertas OR. • Se personalizan anulando fusibles para una funcion especifica.

Una PLA como una caja negra Diseño de la matriz puede dejarse en Manos de un programa automatizado. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-44

Implementación de la función mayoría mediante matriz lógica programable. PLA: Es un elemento que minimiza la cdad de conexiones del circuito. Existen programas que diseñan PLA a partir de descripciones funcionales.

Son componentes de gran aplicación en los sistemas digitales. Ventajas: Se tienen pocas entradas y salidas, aun cuando haya un importante numero de compuertas entre las entradas y las salidas.

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-45

Matriz lógica programable (PLA). Importante: Minimizar la cantidad de conexiones del circuito para: •Obtener un sistema modular formado por componentes discretos que se diseñan y se implementan por separado. •Haciendo uso del criterio modular es que se diseña una PLA como una caja negra.

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

A-46

Appendix A - Digital Logic

Uso de PLAs: Diseño de un circuito digital que suma dos numeros binarios

Tabla de verdad de un sumador completo. Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

Appendix A - Digital Logic

A-47

PLA Implementacion Circuito sumador con arrastre de un sumador en serie de 4 bits implementado completo con sumadores completos

conectados en cascada (Para el ejemplo anterior)

Desventaja: Los resultados de c/columna se determinan en secuencia empezando desde la derecha Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring

A-48

Appendix A - Digital Logic

Matrices lógicas programables (PLAs) •El uso de herramientas CAD favorecen su uso sobre el de la lógica discreta o de multiplexores Estas herramientas de diseño asistido reducen los tamaños de las PLAs, por lo que la gran cdad de compuertas aparentemente utilizadas no es tan elevada en la practica.

Principles of Computer Architecture by M. Murdocca and V. Heuring

© 1999 M. Murdocca and V. Heuring