Organización del
Computador 1
Lógica Digital 1
Algebra de Boole y compuertas
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
Algebra de Boole
George Boole, desarrolló un sistema
algebraico para formalizar la lógica
proposicional. El libro se llama “Análisis
matemático de la lógica”.
El sistema consiste en un cálculo para
resolver problemas de lógica
proposicional (dos valores posibles [0, 1]
George Boole y tres operaciones:
• AND (y)
1815-1864
• OR (o)
• NOT (no) )
Algebra de Boole
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
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
Identidad
1.A=A
0+A=A
Nula
0.A=0
1+A=1
Idempotencia
A.A=A
A+A=A
Inversa
A.˜A=0
A+˜A=1
Conmutativa
A.B=B.A
A+B=B+A
Asociativa
(A.B)C=A.(B.C)
(A+B)+C=A+(B+C)
Distributiva
A+B.C=(A+B).(A+C)
A.(B+C)=A.B+A.C
Absorción
A.(A+B)=A
A+A.B=A
De Morgan
˜(A.B) = ˜A+˜B
˜(A+B) = ˜A.˜B
Ejemplo

Usando identidades booleanas podemos reducir esta
función:
(X+Y)(X+Y)(X+Z)
DeMorgan
(XX + XY+YX+YY)(X+Z)
Distributiva
(X + XY+YX + 0) (X+Z)
Indempotencia e Inversa
(X + X(Y+Y)) (X+Z)
Nula y Distributiva
(X) (X+Z)
Inversa, Identidad y Nula
XX+XZ
Distributiva
XZ
Inversa e Identidad
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
A
B
C
M
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
M(A,B, C)  ABC  ABC  ABC  ABC
Compuertas lógicas

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.
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?
Half-Adder

Podemos usar un XOR para
la suma y un AND para el
acarreo

A este circuito se lo llama
Half-Adder

X
Half
Adder
Y
C
Full Adders
¿Cómo se suman números de dos bits?
Ej:
1
1
+
1
1
___________________
Full Adders
¿Cómo se suman números de dos bits?
Ej:
1
1
1
+
1
1
___________________
0
Full Adders
¿Cómo se suman números de dos bits?
Ej:
1
1
1
1
+
1
1
___________________
1
0
Full Adders
¿Cómo se suman números de dos bits?
Ej:
1
1
1
1
+
1
1
___________________
1
1
0
Full Adders
¿Cómo se suman números de dos bits?

Ci
Ej:
1
1
1
1
+
1
1
___________________
X
Full Adder
Co
Y
1
1
0
En el caso de los Full Adders se asume que poseen una entrada más, el acarreo.
Full-Adder
Cómo es la tabla de
verdad de un Full
Adder?
 Podemos mejorar
nuestro half-adder
para considerar un
“acarreo” en la
entrada.

Full Adders
Ci

X
Half
Y Adder
X
Y
Half
Adder

C

Co
C
Full Adder
Full Adders
 He
aquí el full adder
Adders
Ejercicio:
A4 A3 A2 A1
diseñar un sumador de cuatro bits + B4 B3 B2 B1
usando half y/o full adders.
C5 C4 C3 C2 C1

A
Half
Adder
B
A
As

Ae
B
Full
Adder
As
Adders

A1
B1
Sumador de cuatro bits:
A4 A3 A2 A1
+ B4 B3 B2 B1
C5 C4 C3 C2 C1
Ae
A2
B2
Ae
A3
B3
Ae
A4
B4
HA
As

FA
C3
As

FA
C2
As

FA
C1
As
C4
C5
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
Si x = 0 e y = 1, que
línea de salida
queda habilitada?
2-a-4
Multiplexores

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.
Demultiplexor
Exactamente lo contrario
 Dada una entrada la
direcciona entre n salidas,
usando log2n líneas de control.

Multiplexor - Ejemplo

Así luce un multiplexor 4-a-1
Si S0 = 1 y S1 = 0,
que entrada es
transferida a la
salida?
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
Full Adder
Decoder
Alu de 1bit
Un ALU de 8 bits
Memoria ROM
ROM usando un decoder
Links
 Libro
Tanenbaum
 Demo compuertas: http://www.playhookey.com/digital/derived_gates.html
 Para ver Compuertas logicas en detalle:
http://www.csc.sdstate.edu/%7egamradtk/
csc317/csc317notes.html
Descargar

Kein Folientitel