Representación de la Información La computadoras necesitan almacenar datos e instrucciones en memoria Sistema binario (sólo dos estados posibles) Por qué? Es mucho más sencillo identificar entre sólo dos estados Es menos propenso a errores
Lógica digital Los circuitos operan con valores [0, 1], que pueden ser interpretados lógicamente como [Falso, Verdadero].
Idea: implementar las operaciones lógicas y matemáticas combinando circuitos
George Boole, desarrolló un sistema algebraico para formalizar la lógica proposicional. El libro se llama “Análisis matemático de la lógica”. George Boole 1815-1864 Algebra de Boole El sistema consiste en un cálculo para resolver problemas de lógica proposicional (dos valores posibles [0, 1] y tres operaciones: AND (y) OR (o) NOT (no) )
Las variables Booleanas sólo toman los valores binarios: 1 ó 0.
Una variable Booleana representa un el balor que puede tomar un bit, que como vimos quiere decir:
Binary digIT Algebra de Boole
Operadores básicos Un operador booleano puede ser completamente descripto usando tablas de verdad. El operador AND es conocido como producto booleano (.) y el OR como co-producto booleano (+) El operador NOT (¬ ó una barra encima de la expresión) conocido como complemento.
Funciones booleanas Tabla de verdad de esta función:
El NOT tiene más precedencia que el resto de los operadores
Y el AND más que el OR
Identidades del Algebra de Boole
Ejemplo Usando identidades booleanas podemos reducir esta función:
Fórmulas equivalentes Varias fórmulas pueden tener la misma tabla de verdad Son lógicamente equivalentes En general se suelen elegir formas normales Suma de productos: F(x,y,z) = xy + xz +yz Producto de sumas: F(x,y,z) = (x+y) . (x+z) .(y+z)
Suma de Productos Es fácil convertir una función a una suma de productos usando la tabla de verdad. Elegimos los valores que dan 1 y hacemos un producto (AND) de la fila (negando si aparece un 0) Luego sumamos todo (OR) F(x,y,z) = (¬xy¬z)+(¬xyz)+(x¬y¬z)+(xy¬z)+(xyz)
Circuitos booleanos Las computadores digitales contienen circuitos que implementan funciones booleanas Cuando más simple la función más chico el circuito Son más baratos, consumen menos, y en ocasiones son mas rápidos! Podemos usar las identidades del algebra de Boole para reducir estas funciones.
Compuertas lógicas Una compuerta es un dispositivo electrónico que produce un resultado en base a un conjunto de valores de valores de entrada
En realidad, están formadas por uno o varios transitores, pero lo podemos ver como una unidad. Los circuitos integrados contienen colecciones de compuertas conectadas con algún propósito
Compuertas Lógicas Las más simples: AND, OR, y NOT.
Se corresponden exactamente con las funciones booleanas que vimos
Compuertas lógicas Una compuerta muy útil: el OR exclusivo (XOR) La salida es 1 cuando los valores de entrada difieren. Usamos el simbolo ? para el XOR.
Componentes digitales Combinando compuertas se pueden implementar funciones booleanas Este circuito implementa la siguiente función: Simplificando las funciones se crean circuitos más chicos!
Ejemplo: La función Mayoría
NAND y NOR son dos compuertas muy importantes. Con la identidad de De Morgan se pueden implementar con AND u OR. Son más baratas y ambas por sí solas son un conjunto adecuado para la lógica proposicional. Es decir que cualquier operador se puede escribir usando cualquiera de ellas. Compuertas lógicas
NAND y NOR
Ejercicio Ejemplo: NOT usando NAND
Utilizando solo NAND o NOR realizar circuitos con la misma funcionalidad que el AND y OR
Circuitos combinatorios Producen una salida específica (casi) al instante que se le aplican valores de entrada Implementan funciones booleanas La aritmética y la lógica de la CPU se implementan con estos circuitos
Sumadores Como podemos construir un circuito que sume dos bits X e Y? F(X,Y) = X + Y (suma aritmética) Que pasa si X=1 e Y=1?
Podemos usar un XOR para la suma y un AND para el acarreo
A este circuito se lo llama Half-Adder Half-Adder (Gp:) X (Gp:) Y (Gp:) ? (Gp:) C (Gp:) Half Adder
¿Cómo se suman números de dos bits?
Ej:
1 1 + 1 1 ___________________
Full Adders
Full Adders ¿Cómo se suman números de dos bits?
Ej: 1 1 1 + 1 1 ___________________
0
¿Cómo se suman números de dos bits?
Ej: 1 1 1 1 + 1 1 ___________________
1 0 Full Adders
Full Adders ¿Cómo se suman números de dos bits?
Ej: 1 1 1 1 + 1 1 ___________________
1 1 0
(Gp:) Full Adder (Gp:) X (Gp:) Y (Gp:) Ci (Gp:) ? (Gp:) Co
Full Adders ¿Cómo se suman números de dos bits?
Ej: 1 1 1 1 + 1 1 ___________________
1 1 0 En el caso de los Full Adders se asume que poseen una entrada más, el acarreo.
Cómo es la tabla de verdad de un Full Adder? Podemos mejorar nuestro half-adder para considerar un “acarreo” en la entrada. Full-Adder
¿Podemos adaptar nuestro half-adder para convertirlo en un full adder? Full Adders
Half Adder X Y Ci ? Co Full Adder Half Adder ? C ? C X Y Full Adders
He aquí el full adder Full Adders
Ejercicio: diseñar un sumador de cuatro bits usando half y/o full adders.
(Gp:) Ae (Gp:) B (Gp:) ? (Gp:) As (Gp:) Full Adder (Gp:) A
(Gp:) A (Gp:) B (Gp:) ? (Gp:) As (Gp:) Half Adder
A4 A3 A2 A1 B4 B3 B2 B1 + C5 C4 C3 C2 C1 Adders
(Gp:) A4 A3 A2 A1 (Gp:) B4 B3 B2 B1 (Gp:) + (Gp:) C5 C4 C3 C2 C1
(Gp:) A1 (Gp:) B1 (Gp:) ? (Gp:) As (Gp:) HA (Gp:) ? (Gp:) As (Gp:) FA (Gp:) ? (Gp:) As (Gp:) FA (Gp:) Ae (Gp:) ? (Gp:) As (Gp:) FA (Gp:) Ae (Gp:) Ae (Gp:) A2 (Gp:) B2 (Gp:) A3 (Gp:) B3 (Gp:) A4 (Gp:) B4 (Gp:) C1 (Gp:) C2 (Gp:) C3 (Gp:) C4 (Gp:) C5
Sumador de cuatro bits: Adders
Decodificadores Decodificadores de n entradas pueden seleccionar una de 2n salidas Son muy importantes, por ejemplo: Seleccionar una locación en una memoria a partir de una dirección colocada en el bus memoria
Decodificadores – Ejemplo Decodificador 2-a-4 Si x = 0 e y = 1, que línea de salida queda habilitada?
Selecciona una salida de varias entradas La entrada que es seleccionada como salida es determinada por las líneas de control Para seleccionar entre n entradas, se necesitan log2n líneas de control. Multiplexores Demultiplexor Exactamente lo contrario Dada una entrada la direcciona entre n salidas, usando log2n líneas de control.
Así luce un multiplexor 4-a-1 Si S0 = 1 y S1 = 0, que entrada es transferida a la salida? Multiplexor – Ejemplo
Función Mayoría
Ejercicio: Implementar la función Mayoría con un Multiplexor
Ejercicio: Implementar la función Mayoría con un Multiplexor
Ejercicio Construir una ALU de 1 bit 3 entradas: A, B, Carry Cuatro operaciones: A.B, A+B, NOT B, Suma(A,B,Carry) Salidas Resultado, CarryOut
Alu de 1bit
Decoder
Full Adder
Alu de 1bit
Un ALU de 8 bits
ROM usando un decoder
Links Libro Tanenbaum Demo compuertas: http://www.play-hookey.com/digital/derived_gates.html Para ver Compuertas logicas en detalle: http://www.csc.sdstate.edu/%7egamradtk/csc317/csc317notes.html