Organización del Computador
Práctico 2: Circuitos Combinacionales¹

B. Gonzalez Kriegel - N. Wolovick

1. Para la siguiente fórmula booleana
   
   $$f(a_{4}a_{3}a_{2}a_{1}a_{0})=a_{0}(a_{1}a_{2}+\overline{a_{1}}\,\overline{a_{2}})+a_{1}(a_{2}a_{3}+a_{4})$$
   
   
   1. Diseñe el circuito que implementa la función usando compuertas $\ensuremath{\mathit{AND}}$, $\ensuremath{\mathit{OR}}$ y $\ensuremath{\mathit{NOT}}$, respetando la estructura de la expresión.
   2. ¿Es posible obtener una implementación de la $f$ que no siga esta estructura? Explique.

2. Para cada uno de los siguientes circuitos:
   
   1. Dar la expresión lógica que sigue la estructura del circuito.
   2. Dar la tabla de verdad².
   3. Computar $\ensuremath{\mathit{Depth}}$ y $\ensuremath{\mathit{GCount}}$.
   4. Dibujar el circuito que computa la misma función pero que sólo contiene compuertas $\ensuremath{\mathit{OR}}$ y $\ensuremath{\mathit{NOT}}$.

3. ¿Son equivalentes las siguientes funciones? Demuestre o de un contraejemplo.
   
   $$f(A,B,C) = ABC+\overline{A}B\overline{C} \ \ \ \ \ \ \ g(A,B,C)=(A\oplus C)B$$
   
   

   
   

4. Escriba la $f_{1}$ del ejercicio 2 en la forma normal reducida $\ensuremath{\mathit{SOP}}$ (suma de productos) de minitérminos.

5. Un comparador de $n$ bits $\ensuremath{\mathit{CMP}}_{n}:\mathcal{B}^{2n}\rightarrow\mathcal{B}$ es un componente que tiene como entrada 2 palabras de $n$ bits y como salida un único bit, que será 0 si las palabras son idénticas (bit a bit) y 1 en caso contrario. Diseñe un comparador de $n$ bits utilizando compuertas lógicas discretas³.

6. Diseñe un circuito que implemente la funcionalidad de un $\ensuremath{\mathit{MUX}}$8-a-1, utilizando solamente $\ensuremath{\mathit{MUX}}$es2-a-1. Muestre su respuesta en la forma de un diagrama lógico.

7. Diseñe un $\ensuremath{\mathit{MUX}}$2-a-1 utilizando sólo tri-state buffers con control directo o invertido.

8. ! Diseñe un $8\times\ensuremath{\mathit{MUX}}$4-a-1 que multiplexa 4 palabras de 8 bits en una salida de 8 bits, utilizando tri-state buffers y $\ensuremath{\mathit{DECODERS}}$2-a-4. Pensar el mismo diseño utilizando compuertas tradicionales de 2 estados. Comparar.

9. Diseñe un $\ensuremath{\mathit{DECODER}}$ decimal de 2 bits con entrada de habilitación que puede desconectar las salidas del dispositivo de manera tal que pueda ser usado en un bus de señales.

10. El $\ensuremath{\mathit{DEMUX}}$1-a-2 es una base completa.
    1. Construya una compuerta $\ensuremath{\mathit{NAND}}_{2}$ utilizando solamente $\ensuremath{\mathit{DEMUX}}$es1-a-2.
    2. A partir de las expresiones booleanas que especifican el $\ensuremath{\mathit{DEMUX}}$ y la compuerta $\ensuremath{\mathit{NAND}}$ demuestre que el circuito del punto anterior es equivalente a una $\ensuremath{\mathit{NAND}}_{2}$.

11. Un display de 7 segmentos es un conjunto de LEDs (diodos emisores de luz) dispuestos como se muestra abajo, donde los segmentos están etiquetados con letras de la $a$ a $g$.
    
    1. Obtenga la tabla de verdad que especifica el funcionamiento del segmento $b$.
    2. Implemente la función $b(a_{3}a_{2}a_{1}a_{0})$ de dos maneras distintas, utilizando un $\ensuremath{\mathit{MUX}}$16-a-1 y empleando un $\ensuremath{\mathit{MUX}}$8-a-1.

12. ¿Cuántas funciones booleanas $f_{n}:\mathcal{B}^{n}\rightarrow \mathcal{B}$ hay? Obtenga las tablas de todas las $f_{2}$ y nombre las conocidas⁴.

13. ! Demuestre asociatividad y teorema de la absorción del producto $(AB)C=A(BC),\ A(A+B)=A$ mediante análisis exhaustivo de casos (tablas de verdad) y por manipulación simbólica usando los axiomas del álgebra de Boole.

14. * Demostrar en estilo de cálculo el teorema de De Morgan $\overline{AB}=\overline{A}+\overline{B}$ partiendo de los axiomas del Algebra de Boole.

15. De las funciones $f_{2}:\mathcal{B}^{2}\rightarrow \mathcal{B}$ obtenidas en el ejercicio 12, obtenga 2 bases completas, una de ellas con 2 funciones y la otra con una sola. Reescriba la función de paridad de 3 bits $\ensuremath{\mathit{PAR}}_{3}$ en función de estas 2 bases.

16. * Bases completas.
    1. ¿Hay alguna función $f_{2}:\mathcal{B}^{2}\rightarrow \mathcal{B}$ que no pueda ser hecha con $\ensuremath{\mathit{AND}}$ y $\ensuremath{\mathit{OR}}$? Demuéstrelo con un argumento riguroso.
    2. Demuestre que una función $f_{2}$ no puede ser una base completa cuando su salida es independiente de una o ambas entradas.
    3. Obtenga todas las funciones $f_{2}$ completas.
    4. Idem a 16c pero sin utilizar las constantes 0 y 1.
    5. Si tuviera que diseñar una $\ensuremath{\mathit{CPU}}$ partiendo de una sóla compuerta $\ensuremath{\mathit{AND}}$ o $\ensuremath{\mathit{NAND}}$. ¿Cuál elegiría y por qué?

17. $\ensuremath{\mathit{AND}}_{n}$ a partir de $\ensuremath{\mathit{AND}}_{2}$⁵
    1. Obtenga una compuerta $\ensuremath{\mathit{AND}}_{n}$ a partir de compuertas $\ensuremath{\mathit{AND}}_{2}$ mediante 2 partrones de conexión distintos; uno que produzca un diseño ``profundo'' y el otro uno ``chato''. Obtenga las funciones $\ensuremath{\mathit{Depth}}(\ensuremath{\mathit{AND}}_{n})$ y $\ensuremath{\mathit{GCount}}(\ensuremath{\mathit{AND}}_{n})$ para ambos diseños.
    2. ! Funcionaría el mismo planteo para la compuerta $\ensuremath{\mathit{OR}}$. ¿Qué debe cumplir en general la función $f_{2}$ para que estos patrones de conexión sean válidos?

18. ** La función $\ensuremath{\mathit{PAR}}_{n}:\mathcal{B}^{n}\rightarrow \mathcal{B}$ da un 1 si el número de entradas en 1 es impar y 0 en caso contrario. El $\ensuremath{\mathit{KMAP}}$ de ésta función es un tablero de ajedrez (¡`comprobarlo!) por lo que no es posible combinar implicantes primos para reducirlos.

    Existen dos implementaciones distintas para esta función. En una la expresamos como $\ensuremath{\mathit{SOP}}$ y en la otra utilizamos una compuerta $\ensuremath{\mathit{XOR}}$ de $n$ entradas. Obtenga las expresiones $\ensuremath{\mathit{Depth(\ensuremath{\mathit{PAR}}_{n})}}$ y $\ensuremath{\mathit{GCount}}(\ensuremath{\mathit{PAR}}_{n})$ para ambos diseños donde sólo se pueden utilizar compuertas $\ensuremath{\mathit{NOT}}$, $\ensuremath{\mathit{AND}}_{2}$ y $\ensuremath{\mathit{OR}}_{2}$. Deduzca el trade-off existente entre profundidad y cantidad de compuertas. ¿Cambiarían mucho estas expresiones si elegimos otra base?

19. Para cada uno de los circuitos del ejercicio 2 obtenga el $\ensuremath{\mathit{KMAP}}$ y a partir de éste las expresiones $\ensuremath{\mathit{SOP}}$ mínimas.

20. Usando un $\ensuremath{\mathit{KMAP}}$, simplifique la siguiente función booleana que incluye condiciones no-importa.
    
    $$f(A,B,C,D)=\sum (2,8,10,11) + \sum (0,9)_{d}$$
    
    

    
    

21. Los circuitos integrados 4511 y 7448 (de tecnología $\ensuremath{\mathit{CMOS}}$ y $\ensuremath{\mathit{TTL}}$ respectivamente) implementan un decodificador $\ensuremath{\mathit{BCD}}$ a 7 segmentos que opera de la misma forma que el presentado en el ejercicio 11, salvo que supone $0\leq (a_{3}a_{2}a_{1}a_{0})_{2}\leq 9$. Reimplemente la función $b(a_{3}a_{2}a_{1}a_{0})$ con la menor cantidad de compuertas discretas utilizando un $\ensuremath{\mathit{KMAP}}$ que aproveche la combinaciones de bits no utilizadas para reducir aún más la expresión.

22. El siguiente $\ensuremath{\mathit{KMAP}}$ está formado incorrectamente. Muestre la expresión reducida que produce este mapa, para luego generar un $\ensuremath{\mathit{KMAP}}$ correcto y derivar la expresión correcta a partir de él. Notar que ambos mapas producen expresiones correctas, es decir equivalentes a la dada, pero sólo el $\ensuremath{\mathit{KMAP}}$ bien formado produce una expresión mínima.

    ABC
    		000	001	011	010	110	111	101	100
    D	0	1			1	1			1
    	1	1			1	1			1

23. Obtenga el fan-in y el fan-out para cada uno de los circuitos del ejercicio 2. Muestre dos formas de reducir el fan-out del tercer circuito.

24. ! Circuitos como grafos
    1. Relacione circuito y fórmula booleana con grafo acíclico dirigido ( $\ensuremath{\mathit{DAG}}$) y árbol dirigido.
    2. Relacione fan-in, fan-out con la valencia de entrada y salida de los nodos. Defina cuando un nodo es entrada, salida o compuerta a partir de los valores de su valencia de entrada y salida.
    3. Transforme el segundo circuito del ejercicio 2 en un $\ensuremath{\mathit{DAG}}$ etiquetado.
    4. * Demuestre como cualquier circuito puede ser transformado a un circuito equivalente con fanout=1 sin aumentar la profundidad (es decir que esta limitación no quita expresividad a los circuitos booleanos). Muestre un ejemplo donde la transformación propuesta genera una explosión exponencial en el tamaño del circuito ( $\ensuremath{\mathit{GCount}}$).

25. * Implemente la función del sumador completo $\ensuremath{\mathit{FA}}:\mathcal{B}^{3}\rightarrow \mathcal{B}^{2}$ con la mínima cantidad de compuertas $\ensuremath{\mathit{NOT}}$, $\ensuremath{\mathit{AND}}_{2}$, $\ensuremath{\mathit{OR}}_{2}$, $\ensuremath{\mathit{NAND}}_{2}$ y $\ensuremath{\mathit{NOR}}_{2}$. Demuestre que el circuito obtenido es efectivamente un sumador completo.