Upload
victor-miranda-toro
View
223
Download
0
Embed Size (px)
Citation preview
Organización del Organización del Computador 1Computador 1
Lógica Digital 1Lógica Digital 1
Algebra de Boole y compuertasAlgebra de Boole y compuertas
Representación de la InformaciónRepresentación de la Información
La computadoras necesitan almacenar La computadoras necesitan almacenar datos e instrucciones en memoriadatos e instrucciones en memoria
Sistema binario (sólo dos estados Sistema binario (sólo dos estados posibles)posibles)
Por qué?Por qué? Es mucho más sencillo identificar entre sólo Es mucho más sencillo identificar entre sólo
dos estados dos estados Es menos propenso a erroresEs menos propenso a errores
Lógica digitalLógica digital
Los circuitos operan con valores [0, 1], que Los circuitos operan con valores [0, 1], que pueden ser interpretados lógicamente pueden ser interpretados lógicamente como [Falso, Verdadero].como [Falso, Verdadero].
Idea:Idea: implementar las operaciones lógicas implementar las operaciones lógicas y matemáticas combinando circuitosy 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 Boole1815-1864
Algebra de BooleAlgebra 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) )
Operadores básicosOperadores básicos
Un operador booleano puede ser Un operador booleano puede ser completamente descripto usando completamente descripto usando tablas de verdadtablas de verdad..
El operador El operador ANDAND es conocido como es conocido como producto booleano (.) y el producto booleano (.) y el OROR como como co-producto booleano (+)co-producto booleano (+)
El operador El operador NOTNOT (¬ ó una barra (¬ ó una barra encima de la expresión) conocido encima de la expresión) conocido como complemento.como complemento.
Funciones booleanasFunciones booleanas
Tabla de verdad de Tabla de verdad de esta función:esta función:
El NOT tiene más El NOT tiene más precedencia que el resto precedencia que el resto de los operadoresde los operadores
Y el AND más que el ORY el AND más que el OR
Identidades del Algebra de BooleIdentidades del Algebra de Boole
IdentidadIdentidad 1.A=A1.A=A 0+A=A0+A=A
NulaNula 0.A=00.A=0 1+A=11+A=1
IdempotenciaIdempotencia A.A=AA.A=A A+A=AA+A=A
InversaInversa A.˜A=0A.˜A=0 A+˜A=1A+˜A=1
ConmutativaConmutativa A.B=B.AA.B=B.A A+B=B+AA+B=B+A
AsociativaAsociativa (A.B)C=A.(B.C)(A.B)C=A.(B.C) (A+B)+C=A+(B+C)(A+B)+C=A+(B+C)
DistributivaDistributiva A+B.C=(A+B).(A+C)A+B.C=(A+B).(A+C) A.(B+C)=A.B+A.CA.(B+C)=A.B+A.C
AbsorciónAbsorción A.(A+B)=AA.(A+B)=A A+A.B=AA+A.B=A
De MorganDe Morgan ˜(A.B) = ˜A+˜B˜(A.B) = ˜A+˜B ˜(A+B) = ˜A.˜B˜(A+B) = ˜A.˜B
EjemploEjemplo
Usando identidades booleanas podemos reducir esta Usando identidades booleanas podemos reducir esta
función:función:
(X+Y)(X+(X+Y)(X+Y)(Y)(X+Z)X+Z) DeMorganDeMorgan
(XX + X(XX + XY+YX+YY+YX+YY)(Y)(X+Z)X+Z) DistributivaDistributiva
(X + X(X + XY+YX + 0) (Y+YX + 0) (X+Z)X+Z) Indempotencia e InversaIndempotencia e Inversa
(X + X((X + X(Y+Y)) (Y+Y)) (X+Z)X+Z) Nula y DistributivaNula y Distributiva
(X) ((X) (X+Z)X+Z) Inversa, Identidad y NulaInversa, Identidad y Nula
XXX+XZX+XZ DistributivaDistributiva
XZXZ Inversa e IdentidadInversa e Identidad
Fórmulas equivalentesFórmulas equivalentes
Varias fórmulas pueden tener la Varias fórmulas pueden tener la misma tabla de verdadmisma tabla de verdad Son lógicamente equivalentesSon lógicamente equivalentes
En general se suelen elegir las formas En general se suelen elegir las formas “canónicas”“canónicas” Suma de productos: Suma de productos:
• F(x,y,z) = xy + xz +yzF(x,y,z) = xy + xz +yz Producto de sumas: Producto de sumas:
• F(x,y,z) = (x+y) . (x+z) .(y+z)F(x,y,z) = (x+y) . (x+z) .(y+z)
Suma de ProductosSuma de Productos
Es fácil convertir una Es fácil convertir una función a una función a una suma de suma de productosproductos usando la tabla usando la tabla de verdad.de verdad.
Elegimos los valores que Elegimos los valores que dan 1 y hacemos un dan 1 y hacemos un producto (AND) de la fila producto (AND) de la fila (negando si aparece un 0)(negando si aparece un 0)
Luego sumamos todo (OR)Luego sumamos todo (OR)
F(x,y,z) = (¬F(x,y,z) = (¬xxy¬z)+(¬xyz)+(x¬y¬z)+(xy¬z)+(xyz)y¬z)+(¬xyz)+(x¬y¬z)+(xy¬z)+(xyz)
Circuitos booleanosCircuitos booleanos
Las computadores digitales contienen Las computadores digitales contienen circuitos que implementan funciones circuitos que implementan funciones booleanasbooleanas
Cuando más simple la función más chico Cuando más simple la función más chico el circuitoel circuito Son más baratos, consumen menos, y en Son más baratos, consumen menos, y en
ocasiones son mas rápidos!ocasiones son mas rápidos! Podemos usar las identidades del algebra Podemos usar las identidades del algebra
de Boole para reducir estas funciones.de Boole para reducir estas funciones.
Compuertas lógicasCompuertas lógicas
Una compuerta es un dispositivo electrónico Una compuerta es un dispositivo electrónico que produce un resultado en base a un que produce un resultado en base a un conjunto de valores de valores de entradaconjunto de valores de valores de entrada
En realidad, están formadas por uno o En realidad, están formadas por uno o varios transitores, pero lo podemos ver varios transitores, pero lo podemos ver como una unidad.como una unidad.
Los circuitos integrados contienen Los circuitos integrados contienen colecciones de compuertas conectadas con colecciones de compuertas conectadas con algún propósitoalgún propósito
Compuertas LógicasCompuertas Lógicas
Las más simples: AND, OR, y NOT.Las más simples: AND, OR, y NOT.
Se corresponden exactamente con las funciones Se corresponden exactamente con las funciones booleanas que vimosbooleanas que vimos
Compuertas lógicasCompuertas lógicas
Una compuerta muy útil: el OR exclusivo (XOR)Una compuerta muy útil: el OR exclusivo (XOR) La salida es 1 cuando los valores de entrada La salida es 1 cuando los valores de entrada
difieren.difieren.
Usamos el simbolo para el XOR.
Componentes digitalesComponentes digitales
Combinando compuertas se pueden Combinando compuertas se pueden implementar funciones booleanasimplementar funciones booleanas
Este circuito implementa la siguiente Este circuito implementa la siguiente función:función:
Simplificando las funciones se crean circuitos más chicos!
Ejemplo: La función MayoríaEjemplo: La función Mayoría
AA BB CC MM
00 00 00 00
00 00 11 00
00 11 00 00
00 11 11 11
11 00 00 00
11 00 11 11
11 11 00 11
11 11 11 11
ABCCABCBABCAC)B,M(A,
NANDNAND y y NORNOR son dos son dos compuertas muy compuertas muy importantes. importantes.
Con la identidad de De Con la identidad de De Morgan se pueden Morgan se pueden implementar con implementar con ANDAND u u OROR..
Son más baratas y ambas Son más baratas y ambas por sí solas son un por sí solas son un conjunto adecuado para conjunto adecuado para la lógica proposicional. Es la lógica proposicional. Es decir que cualquier decir que cualquier operador se puede operador se puede escribir usando cualquiera escribir usando cualquiera de ellas.de ellas.
Compuertas lógicasCompuertas lógicas
NAND y NORNAND y NOR
EjercicioEjercicio
Ejemplo: NOT usando NANDEjemplo: NOT usando NAND
Utilizando solo NAND o NOR Utilizando solo NAND o NOR realizar circuitos con la realizar circuitos con la misma funcionalidad que el misma funcionalidad que el AND y ORAND y OR
Circuitos combinatoriosCircuitos combinatorios
Producen una salida específica (casi) Producen una salida específica (casi) al instante que se le aplican valores de al instante que se le aplican valores de entradaentrada
Implementan funciones booleanasImplementan funciones booleanas La aritmética y la lógica de la CPU se La aritmética y la lógica de la CPU se
implementan con estos circuitosimplementan con estos circuitos
SumadoresSumadores
Como podemos Como podemos construir un circuito construir un circuito que sume dos bits X que sume dos bits X e Y?e Y?
F(X,Y) = X + Y (suma F(X,Y) = X + Y (suma aritmética)aritmética)
Que pasa si X=1 e Que pasa si X=1 e Y=1?Y=1?
Podemos usar un XOR para Podemos usar un XOR para la suma y un AND para el la suma y un AND para el acarreoacarreo
A este circuito se lo llama A este circuito se lo llama Half-AdderHalf-Adder
Half-AdderHalf-Adder
X
Y
C
Half Adder
¿Cómo se suman números de dos bits?
Ej:
1 1 + 1 1
___________________
Full AddersFull Adders
Full AddersFull 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 AddersFull Adders
Full AddersFull Adders
¿Cómo se suman números de dos bits?
Ej: 1 1
1 1 + 1 1
___________________
1 1 0
Full AdderX
Y
Ci
Co
Full AddersFull 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.
¿Podemos adaptar ¿Podemos adaptar nuestro half-adder para nuestro half-adder para convertirlo en un full convertirlo en un full adder?adder?
Full AddersFull Adders
Half Adder
X
Y
Ci
Co
Full Adder
Half Adder
C
C
X
Y
Full AddersFull Adders
He aquí el full adderHe aquí el full adder
Full AddersFull Adders
Ejercicio: diseñar un sumador de cuatro bits usando half y/o full adders.
Ae
B
As
Full AdderA
A
B
As
Half Adder
A4 A3 A2 A1B4 B3 B2 B1
+
C5 C4 C3 C2 C1
AddersAdders
A4 A3 A2 A1
B4 B3 B2 B1+
C5 C4 C3 C2 C1
A1
B1
AsHA
AsFA
AsFA
Ae
AsFA
Ae
AeA2
B2
A3
B3
A4
B4
C1
C2
C3
C4
C5
Sumador de cuatro bits:
AddersAdders
DecodificadoresDecodificadores
Decodificadores de n entradas pueden Decodificadores de n entradas pueden seleccionar una de 2seleccionar una de 2nn salidas salidas
Son muy importantes, por ejemplo:Son muy importantes, por ejemplo: Seleccionar una locación en una memoria a partir Seleccionar una locación en una memoria a partir
de una dirección colocada en el bus memoriade una dirección colocada en el bus memoria
Decodificadores - EjemploDecodificadores - Ejemplo
Decodificador 2-a-4Decodificador 2-a-4
Si x = 0 e y = 1, que línea de salida queda habilitada?
Selecciona una salida a de Selecciona una salida a de varias entradas varias entradas
La entrada que es La entrada que es seleccionada como salida es seleccionada como salida es determinada por las líneas determinada por las líneas de controlde control
Para seleccionar entre Para seleccionar entre nn entradas, se necesitan entradas, se necesitan loglog22nn líneas de control.líneas de control.
MultiplexoresMultiplexores
DemultiplexorDemultiplexor Exactamente lo contrarioExactamente lo contrario Dada una entrada la Dada una entrada la direcciona entre direcciona entre nn salidas, salidas, usando usando loglog22nn líneas de control. líneas de control.
Así luce un multiplexor 4-a-1Así luce un multiplexor 4-a-1
Si S0 = 1 y S1 = 0, que entrada es transferida a la salida?
Multiplexor - EjemploMultiplexor - Ejemplo
Función MayoríaFunción Mayoría
Ejercicio: Implementar la función Ejercicio: Implementar la función Mayoría con un MultiplexorMayoría con un Multiplexor
Ejercicio: Implementar la función Ejercicio: Implementar la función Mayoría con un MultiplexorMayoría con un Multiplexor
EjercicioEjercicio
Construir una ALU de 1 bitConstruir una ALU de 1 bit 3 entradas:3 entradas:
A, B, CarryA, B, Carry Cuatro operaciones: Cuatro operaciones:
A.B, A+B, NOT B, Suma(A,B,Carry)A.B, A+B, NOT B, Suma(A,B,Carry) SalidasSalidas
Resultado, CarryResultado, CarryOutOut
Alu de 1bitAlu de 1bit
Decoder
Full Adder
Alu de 1bitAlu de 1bit
Un ALU de 8 bitsUn ALU de 8 bits
Memoria ROMMemoria ROM
ROM usando un decoderROM usando un decoder
LinksLinks
Libro TanenbaumLibro Tanenbaum Demo compuertas: Demo compuertas:
http://www.play-hookey.com/digital/derived_gates.html
Para ver Compuertas logicas en detalle: Para ver Compuertas logicas en detalle: http://www.csc.sdstate.edu/%7egamradtk/csc317/csc317notes.html