ObjetivosIntroduccion
EjerciciosResumen
Logica Digital - Circuitos Combinatorios
Expositor: Esteban PontnauPrimer Cuatrimestre de 2012
Departamento de Computacion, FCEyN,Universidad de Buenos Aires.
3 de abril de 2012
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Objetivos de la clase de hoy
I Repasar los operadores y propiedades del algebra de boolevistas en la teorica y utilizarlas para implementar circuitoscombinatorios simples.
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
Repasemos. . .
I Operadores logicos: Pueden ser completamente descriptosusando su tabla de verdad.
I AND, OR, NOT −→ Operadores basicosI NAND, NOR −→ Operadores universales
I Expresiones booleanas:I Combinacion de operadores logicos y variables booleanas. Ej.
F (X ,Y ,Z ) = X + YZ .I Orden de precedencia en la evaluacion NOT > AND > OR.I Dos expresiones son iguales sii tienen la misma tabla de verdad.I Identidades booleanas: Reducciones utilizando propiedades o
leyes.
XYZ + XYZ + XZ == XY + XZ
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
Propiedades
Identidad 1.A = A 0 + A = ANulo 0.A = 0 1 + A = 1
Idempotencia A.A = A A + A = A
Inverso A.A = 0 A + A = 1Conmutatividad A.B = B.A A + B = B + A
Asociatividad (A.B).C = A.(B.C) (A + B) + C = A + (B + C)Distributividad A + B.C = (A + B).(A + C) A.(B + C) = A.B + A.C
Absorcion A.(A + B) = A A + A.B = A
De Morgan (A.B) = A + B (A + B) = A.B
I No existe una forma mecanica y facil para reducir unafuncion, hay que practicar.
I De esto se deduce que no hay una unica forma de escribir unafuncion logica, surge la necesidad de las formas canonicas.
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
Formas Canonicas
I La idea es, dada una tabla de verdad escribir una expresionbooleana que la represente.
I Las dos tecnicas que vamos a ver son Suma de Productos yProducto de Sumas.
I No necesariamente vamos a obtener la expresion ”Optima” (osea la que use menos operadores).
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
Suma de productos
I Por cada valor de la funcion que sea 1 escribimos un terminoutilizando todas las variables unidas por operadores AND, deforma tal que el termino tambien valga 1. Luego combinamostodo con operadores OR.
I Probemos con un ejemplo sencillo:
A B F(A,B)0 0 00 1 11 0 11 1 0
F (A,B) = AB + AB
(Es el operador OR-Excusivo o XOR)
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
Producto de sumas
I Por cada valor de la funcion que sea 0 escribimos un terminoutilizando todas las variables unidas por operadores OR, deforma tal que el termino tambien valga 0. Luego combinamostodo con operadores AND.
I Usando el ejemplo anterior:
A B F(A,B)0 0 00 1 11 0 11 1 0
F (A,B) = (A + B)(A + B)
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
Compuertas logicas
I Una compuerta es un dispositivo electronico que produce unresultado en base a un conjunto de valores de entrada.
I Se corresponden exactamente con los operadores que vimosantes.
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
Compuerta NOT
A NOT A
0 11 0
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
Compuerta AND
A B A AND B
0 0 00 1 01 0 01 1 1
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
Compuerta OR
A B A OR B
0 0 00 1 11 0 11 1 1
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
Compuerta XOR u OR-EXCLUSIVA
A B A XOR B
0 0 00 1 11 0 11 1 0
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
Compuerta NOR
A B A NOR B
0 0 10 1 01 0 01 1 0
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
Compuerta NAND
A B A NAND B
0 0 10 1 11 0 11 1 0
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
PropiedadesSuma de productosProducto de sumasCompuertas logicas
CEDAR Logic Simulator
http://cedarlogic.scienceontheweb.net/
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Ejercicio 1
Demostrar si la siguiente igualdad entre expresiones booleanas esverdadera o falsa:
(X + Y ) = (X .Y ).Z + X .Z + (Y + Z )
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Recordemos las propiedades
Identidad 1.A = A 0 + A = ANulo 0.A = 0 1 + A = 1
Idempotencia A.A = A A + A = A
Inverso A.A = 0 A + A = 1Conmutatividad A.B = B.A A + B = B + A
Asociatividad (A.B).C = A.(B.C) (A + B) + C = A + (B + C)Distributividad A + B.C = (A + B).(A + C) A.(B + C) = A.B + A.C
Absorcion A.(A + B) = A A + A.B = A
De Morgan (A.B) = A + B (A + B) = A.B
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Una solucion:
(X .Y ).Z + X .Z + (Y + Z ) ←− De Morgan
(X .Y ).Z + X .Z + Y .Z ←− Distributiva
(X .Y ).Z + (X + Y ).Z ←− De Morgan(X + Y ).Z + (X + Y ).Z ←− Distributiva(X + Y ).(Z + Z ) ←− Inverso(X + Y ).1 ←− IdentidadX + Y ←− Listo!, probamos que es igual
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Ejercicio 2Dada la siguiente tabla de verdad:
A B C F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
I Escribir una expresion booleana que la represente.
I Implementarla utilizando a lo sumo una compuerta AND, unacompuerta OR y una compuerta NOT.
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Recordemos las propiedades
Identidad 1.A = A 0 + A = ANulo 0.A = 0 1 + A = 1
Idempotencia A.A = A A + A = A
Inverso A.A = 0 A + A = 1Conmutatividad A.B = B.A A + B = B + A
Asociatividad (A.B).C = A.(B.C) (A + B) + C = A + (B + C)Distributividad A + B.C = (A + B).(A + C) A.(B + C) = A.B + A.C
Absorcion A.(A + B) = A A + A.B = A
De Morgan (A.B) = A + B (A + B) = A.B
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
I Expresamos como una suma de productos:
(A.B.C ) + (A.B.C ) + (A.B.C )
I Como nos restringen la cantidad de compuertas tenemos quesimplificar.(A.B.C ) + (A.B.C ) + (A.B.C ) −→ Distributiva((A.B) + (A.B) + (A.B)).C −→ Distributiva((A.B) + (A + A).B).C −→ Inverso((A.B) + 1.B).C −→ Identidad((A.B) + B).C −→ Distributiva((A + B).(B + B)).C −→ Inverso((A + B),1).C −→ Identidad(A + B).C −→ Bingo!
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
¿Para que nos sirvio esto?
Implementacion de la primer expresion.
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
¿Para que nos sirvio esto?
Implementacion de la segunda expresion.
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Ejercicio 3
Armar un inversor de 3 bits. Este circuito invierte o no tresentradas de acuerdo al valor de una cuarta que actua comocontrol. En otras palabras, un inversor de k-bits es un circuito dek+1 entradas (e1, ..., ek , ek+1) y k salidas (s1, ..., sk) que funcionadel siguiente modo:
I Si ek+1 = 1, entonces si = not(ei ) para todo i < k + 1
I Si ek+1 = 0, entonces si = ei para todo i < k + 1
Ejemplo:inversor(0110)=011inversor(1001)=011
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Solucion: Tabla de verdad
e1 e2 e3 e4 s1 s2 s3
0 0 0 0 0 0 0
0 0 1 0 0 0 1
0 1 0 0 0 1 0
0 1 1 0 0 1 1
1 0 0 0 1 0 0
1 0 1 0 1 0 1
1 1 0 0 1 1 0
1 1 1 0 1 1 1
(Continua)
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Solucion: Tabla de verdad (Continuacion)
e1 e2 e3 e4 s1 s2 s3
0 0 0 1 1 1 1
0 0 1 1 1 1 0
0 1 0 1 1 0 1
0 1 1 1 1 0 0
1 0 0 1 0 1 1
1 0 1 1 0 1 0
1 1 0 1 0 0 1
1 1 1 1 0 0 0
¿Como quedarıan las ecuaciones?
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Ecuaciones para S1, S2 y S3
s1 = (e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3e4) +(e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3.e4)
s2 = (e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3e4) +(e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3.e4)
s3 = (e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3e4) +(e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3.e4)
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Primero pensar como invertir un solo bit
ei e(k+1) si0 0 0
0 1 1
1 0 1
1 1 0
Hay que usar (P.Q) + (P.Q) que es una XOR (⊕)P ⊕ Q = (P.Q) + (P.Q)
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Comparemos con la ecuacion de S1
(e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3e4) +(e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3.e4) + (e1.e2.e3.e4)
e1((e2.e3.e4) + (e2.e3.e4) + (e2.e3.e4) + (e2.e3.e4)) +e1((e2.e3.e4) + (e2.e3.e4) + (e2.e3.e4) + (e2.e3.e4)
e1(((e2.e3) + (e2.e3) + (e2.e3) + (e2.e3))e4) +e1(((e2.e3) + (e2.e3) + (e2.e3) + (e2.e3))e4)
e1((e2(e3 + e3) + e2(e3 + e3))e4) +e1((e2(e3 + e3) + e2(e3 + e3))e4)
e1((e2 + e2)e4) +e1((e2 + e2)e4)
(e1.e4) + (e1.e4)
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Solucion:
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Ejercicio 4
Armar un circuito de 3 bits. Este debera mover a izquierda o aderecha los bits de entrada de acuerdo al valor de una de ellas queactua como control. En otras palabras, un shift izq-der de k-bits esun circuito de k+1 entradas (ek , ..., e0) y k salidas (sk−1, ..., s0)que funciona del siguiente modo:
I Si ek = 1, entonces si = ei−1 para todo 0 < i < k y s0 = 0
I Si ek = 0, entonces si = ei+1 para todo 0 ≤ i < k − 1 ysk−1 = 0
Ejemplo:shift lr(1,011)=110shift lr(0,011)=001shift lr(1,100)=000shift lr(1,101)=010
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Ejercicio 4Solucion:
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Ejercicio 5
Armar un sumador de un solo bit utilizando solo una compuertaAND y una compuerta XOR.
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Solucion:
X Y Cout Sum
0 0 0 00 1 0 11 0 0 11 1 1 0
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Solucion:
X Y Cout Sum
0 0 0 00 1 0 11 0 0 11 1 1 0
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Ejercicio 6
Teniendo dos sumadores simples y solo una compuerta a eleccion,arme un sumador completo de un bit.(Recordar que un sumador completo tambien tiene entrada decarry)
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
X Y Cin Sum Cout
0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Solucion:
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Ejercicio 7
Usando sumadores completos y un tipo de compuerta a eleccionarmar un circuito que convierta un entero en su inverso aditivo (elinverso aditivo de un numero n es el numero x tal que x + n = 0).Los enteros se representan con notacion complemento a 2 de 4bits. En esta reprepresentacion el -8 no tiene inverso aditivo, nohace falta contemplar el caso aparte.
Ejemplo:inversoAd(1001)=0111inversoAd(0110)=1010
(HINT: Para los que NO HICIERON el ejercicio 24 de la practica 1, elinverso aditivo de un numero en complemento a 2 se obtiene invirtiendobit a bit y sumando 1)
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Solucion:
(Pensar como serıa la solucion usando sumadores simples.)
Practica 2
ObjetivosIntroduccion
EjerciciosResumen
Cosas que tendrıamos que haber entendido y tips
I Operadores y expresiones booleanas, reducciones utilizandopropiedades.
I Dada una tabla de verdad escribir una expresion booleana quela represente.
I Implementar las expresiones utilizando compuertas logicas.
RECOMENDACIONES Sean cuidadosos cuando dibujan circuitos:
I Que quede claro cuando un cable esta conectado a otro ycuando lo saltea (pongan un circulito en la union o una curvacuando no quieren que lo toque).
Con todo esto pueden hacer la primera parte de la practica 2.
Practica 2