Download Circuitos Lógicos Combinatorios

Simplificación de circuitos lógicos
Algebra de Conmutación
Unidad 2
1
Tabla de Contenido
 Introducción
 Algebra de conmutación
 Manipulación algebraica
 Operaciones lógicas
 Implementación de funciones lógicas
 Introducción a los Mapas de Karnaugh
 Propiedades de las compuertas NAND y NOR
2
Introducción
 En la unidad anterior llegamos hasta la transformación de un
problema digital en su equivalente tabla de verdad, en un formato
binario, esto sería suficiente para construcción de sistemas que usen
memorias de solo lectura (ROM), para realizar la implementación
de estos sistemas con otro tipo de componentes (compuertas
lógicas) es necesario tener una descripción algebraica de estos
sistemas.
 De lo dicho anterior, podemos concluir que necesitamos el álgebra
para:
 Interpretar o describir una red de compuertas que componen el
sistema digital.
 Permite simplificar y minimizar la cantidad de lógica usada en un
sistema.
 Es básica en el proceso de implementación de una red de
compuertas.
3
Definición del Algebra de Conmutación
 Es el conjunto axiomático que normaliza las
operaciones que podrán existir en un ambiente con
variables binarias, esto es, variables que puedan asumir
únicamente dos valores, incluso, variables que
físicamente no son binarias, pero pueden ser
representadas en términos binarios.
4
Operadores del Algebra de
Conmutación
 OR (suma lógica)
 Símbolos: + , V
 a + b (se lee: a or b), y es 1 sí y sólo sí a=1 ó b=1 ó ambos.
 AND (producto lógico)
 Símbolos: . , Λ, o simplemente dos variables seguidas
 a . b (se lee: a and b), y es 1 sí y sólo sí a=1 y b=1.
 NOT (negación, complemento, inversión)
 Símbolos: ’
 a’ (se lee: not a , a negado), y es 1 sí y sólo sí a=0.
5
Tablas de verdad para las operaciones
OR. AND y NOT
6
a
b
a+b
a
b
ab
0
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
0
1
1
1
1
1
1
a
a’
0
1
1
0
Propiedades del Algebra de
Conmutación
(Postulados y Teoremas)
7
Propiedad Conmutativa
 Las operaciones OR y AND son conmutativas
 P1a. a + b = b + a
 P1b. a . b = b . A
 Note que el valor para las combinaciones en la tabla de
verdad para las segundas y terceras líneas son iguales
8
Propiedad Asociativa (1)
 Las operaciones OR y AND son asociativas
 P2a. (a+b)+c = a+(b+c)
 P2b. (a.b).c = a.(b.c)
 Esta propiedad es mencionada como la Ley Asociativa,
declara que el orden de los factores no altera el
resultado.
 Esta propiedad nos ayuda a establecer algunas
particularidades de las operaciones OR y AND.
9
Propiedad Asociativa (2)
 OR
 a+b+c+d+…. Es 1 si cualquiera de las variables es 1 y es
0 sólo si todas las variables son 0.
 AND
 abcd …. Es 1 si todas las variable son 1 y es 0 si
cualquiera de las variables es 0.
10
Las compuertas (1)
 Es el elemento básico en los sistemas digitales.
 Es un elemento con una sola salida que implementa
una de las funciones básicas como AND y OR.
 Está disponibles en configuraciones de dos, tres, cuatro
y ocho entradas.
11
Las compuertas (2)
 Símbolos para OR y AND
12
Implementación para la propiedad 2b
13
Símbolo para la compuerta NOT
El circulo al final del triángulo es la representación de la negación
14
Identidad
 Existen 2 elementos neutros, el 0 y el 1,
cumpliéndose la propiedad en dos de los casos,
quedando como 1 y 0 lógicos en los otros dos (ver
teorema 2):
 P3a. a.1 = a
 P3b. a+0 = a
15
(identidad)
(identidad)
Nulo
 Casos en que no se cumple la propiedad de elemento
neutro, pero existen y se definen de esta forma.
 P4a. a.0 = 0
 P4b. a+1 = 1
16
Complemento
 Existe el elemento complementario para cada
variable binaria y el resultado para cada operación es
el que sigue.
 P5a. a + a’ = 1
 P5b. a . a’ = 0
17
Idempotencia
 La suma o producto de dos variables iguales equivale a
la misma variable
 P6a. a+a = a
 P6b. a.a = a
18
Involución
 Para todo elemento de un álgebra de boole se cumple
que:
 P7. (a’)’=a
19
Distributiva
 Ambas operaciones son distributivas
 P8a. a(b+c) = (ab)+(ac)
 P8b. a+bc = (a+b)(a+c)
 (Este postulado no existe para el álgebra común)
20
Adyacencia
 Se define de la siguiente forma:
 P9a. ab + ab’= a
 P9b. (a+b)(a+b’) = a
21
Simplificación
 Es una combinación de las propiedades distributivas y
asociativas, se usa comúnmente en la simplificación de
funciones.
 P10a. a + a’ b = (a’ + a) (a+b) = a+b
 P10b. a (a’ + b) = a’ a + a b = ab
22
Absorción
 Ley de Absorción.
 P11a. a + ab = a
 P11b. a(a + b) = a
23
Ley de Moorgan
 Ley De Moorgan.
 P12a. (a + b + c + ...) ' = a' . b' . c' . ...
 P12b. ( a . b . c. ... ) ' = a' + b' + c' + ...
24
Manipulación de Funciones
Algebraicas
25
Conceptos importantes
 Literal o variable
 Término de producto
 Término estándar de productos o minitérmino
 Sumatoria de productos
 Sumatoria canónica o sumatoria de términos de
productos estándares.
 Sumatoria de productos mínima o expresión
simplificada.
 Nota: cada uno de estos conceptos tiene un concepto
dual para la suma.
26
La simplificación
 El proceso de la simplificación consiste en aplicar los
postulados y teoremas del álgebra de conmutación para
llegar a la expresión más simple de la ecuación, está,
se presentará normalmente en su forma de sumatoria
de productos mínima.
27
Ejemplo de simplificación
 F = xy’(z+x+zy’)
 F=xy’z+xy’x+xy’zy’
 F=xy’z+xy’+xy’z
 F=xy’z+xy’
 F=xy’
 Simplificar:
 x’yz’ + x’yz + xy’z’ + xy’z + xyz
28
Sobre la simplificación
 No existe una metodología para realizar la
simplificación.
 Sólo la práctica es la manera de alcanzar la
simplificación más óptima.
 La aplicación del álgebra de conmutación no garantiza
el llegar a la simplificación óptima.
29
Implementación de Funciones con
Compuertas
30
Redes con AND, OR y NOT
 Una vez que se define la suma de productos mínima se
debe de definir el diagrama lógico, compuesto por una
red de compuertas que describan la función.
31
Ejemplo de un circuito de dos niveles
f  xyz  xyz  xyz  xyz
X’
Y
Z’
X’
Y
Z
X
Y’
Z’
X
Y’
Z
32
Niveles
 El número de niveles corresponde al máximo número
de compuertas que una señal debe pasar desde su
entrada hasta la salida.
 En el caso anterior tenemos dos niveles, esto
asumiendo que tenemos disponibles en la entradas los
complementos de la literales, cuando no se dispone de
los complementos es necesario complementar con
compuertas NOT.
33
Problema
f  xyz  xyz  xyz  xyz  xyz
a)
b)
34
Diagrama de la suma de productos
Diagrama de la suma de productos mínimo
Una red multinivel
h  z  wxy  v( xz  w)
Las redes multinivel son el resultado de implementar funciones que no estén
en la forma ni de suma de productos ni de productos de sumas.
35
De la Tabla de Verdad a la Expresión
Algebraica
 En la mayoría de los casos, un problema digital es
presentado en la forma de una declaración o como una
tabla de verdad, esto nos obliga a tener la habilidad de
llevar los datos de una tabla de verdad a una expresión
algebraica.
 En la tabla de verdad, cada combinación de las
variables de entrada corresponde a un termino de
producto estándar.
 Es posible extraer una sumatoria de productos
estándares sumando cada termino de producto cuyo
resultado en la tabla de verdad es igual a 1.
36
Miniterminos
•En la tabla se muestra la
equivalencia entre las
combinaciones de una tabla de
verdad y los minitérminos que
están asociados a cada uno de
los productos estándares de
una expresión algebraica.
•Los miniterminos pueden ser
referidos también por sus
números, que están mostrados
en la columna de la derecha.
37
a
b
c
Minitermino
Número
0
0
0
A’B’C’
0
0
0
1
A’B’C
1
0
1
0
A’BC’
2
0
1
1
A’BC
3
1
0
0
AB’C’
4
1
0
1
AB’C
5
1
1
0
ABC’
6
1
1
1
ABC
7
Ejemplo 1
38
A
B
C
f
f’
La expresión algebraica será:
0
0
0
0
1
f(A,B,C) = Σm(1,2,3,4,5)
= A’B’C+A’BC’+A’BC+AB’C’+AB’C
0
0
1
1
0
0
1
0
1
0
0
1
1
1
0
1
0
0
1
0
1
0
1
1
0
1
1
0
0
1
1
1
1
0
1
f’(A,B,C) = Σm(0,6,7)
= A’B’C’+ABC’+ABC
Para la mayoría de los casos la
suma de los minitérminos no
representa la sumatoria mínima de
productos.
Ejemplo 2, con condiciones
irrelevantes (don’t care)
39
a
b
c
f
0
0
0
x
La expresión algebraica será:
0
0
1
1
f(a,b,c) = Σm(1,2,5) + Σd(0,3)
0
1
0
1
0
1
1
x
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
0
Problema
 Desarrollar las expresiones algebraicas para EJE1,
EJE2 y EJE3.
40
Finalización del proyecto EJE1
 Z2= A’BCD+AB’CD+ABC’D+ABCD’+ABCD
 Z2 suma mínima = ACD+BCD+ABC+ABD
 Diagrama lógico
41
Introducción a los Mapas de
Karnaugh
42
Mapas de Karnaugh
 Es un método gráfico usado para la simplificación de
funciones de conmutación.
 Propuesto por Maurice Karnaugh en 1953.
 Los mapas de Karnaugh se compone de un cuadrado
por cada minitérmino posible de una función.
 2 variables, 4 cuadrados
 3 variables, 8 cuadrados
 4 variables, 16 cuadrados
43
Mapa de Karnaugh para dos variables
A
A
B
A’B’
AB’
A’B
AB
B
m0
m2
m1
m3
0
0
1
0
2
1
3
1
Aquí tenemos tres vistas de una mapa de dos variables, las casillas sombreadas,
por ejemplo, corresponden al minitérmino 2 donde A=1 y B=0
44
Representando funciones en un Mapa
de Karnaugh (1)
 Cuando se quiere llevar una función a un mapa, se
coloca un 1 en el casillero correspondiente al
minitérmino que resultó como 1 en la función.
 Los otros casilleros se dejan en blanco
 Si existen condiciones irrelevantes, es necesario poner
una X en los minitérminos correspondientes.
45
Representando funciones en un Mapa
de Karnaugh (2)
a
A
0
b
0
1
1
B
0
1
1
F(a,b) = Σm(0,3)
46
0
1
1
X
1
1
F(A,B) = Σm(0,3) + Σd(2)
Mapa de Karnaugh para 3 variables
AB
AB
11
10
A’BC’
ABC’
AB’C’
A’BC
ABC
AB’C
00
01
0
A’B’C’
1
A’B’C
C
11
10
2
6
4
3
7
5
00
01
0
0
1
1
C
La idea con la codificación es poder usar el P9a. ab+ab’=a
47
Mapa de Karnaugh para 4 variables
AB
CD
00
01
11
10
48
10
AB
00
01
11
A’B’C’D’
A’BC’D’
ABC’D’
AB’C’D’
00
A’B’C’D
A’BC’D
ABC’D
AB’C’D
01
A’B’CD
A’BCD
ABCD
AB’CD
A’B’CD’
A’BCD’
ABCD’
AB’CD’
00
01
11
10
0
4
12
8
1
5
13
9
11
3
7
15
11
10
2
6
14
10
CD
Ejemplo de adyacencia para un mapa
de 4 variables
 Los 1 en dos celdas adyacentes corresponden a un solo término de producto.
AB
CD
AB
00
01
11
10
00
00
01
1
1
00
01
1
01
11
11
10
10
AC’D
49
CD
1
A’B’D’
11
10
Extendiendo el concepto de
adyacencia para agrupar más celdas
AB
AB
00
C
01
11
10
0
1
00
01
1
1
11
10
1
1
0
1
1
A’C
50
C
1
1
AC
1
C
Otros ejemplos para grupos de 4
AB
CD
00
01
AB
00
11
10
CD
00
1
1
1
1
11
1
1
1
10
1
A’B’
51
01
01
11
1
01
11
10
AD
00
1
1
1
1
1
1
B’D’
10
1
BD
Grupos de 8
AB
AB
01
1
1
1
1
11
1
1
11
10
1
1
10
00
01
A’
52
11
10
00
CD
CD
00
00
01
11
10
1
1
1
1
1
1
1
1
01
D’
Ejemplo de simplificación usando
Mapas de Karnaugh
x’yz’ + x’yz + xy’z’ + xy’z + xyz
xy
xy
00
z
01
0
1
1
1
10
11
1
00
z
01
1
0
1
1
1
1
11
10
1
1
1
xy
00
z
53
01
0
1
1
1
11
10
1
1
1
x’y + xy’ + xz
Problema
 f = a’b’c’ + a’bc’ + a’bc + ab’c’
 Para la función f encontrar:
 La suma de productos mínima usando un mapa d karnaugh.
 Retomaremos el estudio de los Mapas de Karnaugh un
poco más adelante
54
Compuertas NAND, NOR y OR
EXCLUISIVAS
55
Compuerta NAND y NOR
Como la otras compuertas que estudiamos, también están disponibles
en el comercio con dos, tres, cuatro y ocho entradas.
Símbolos para NAND
Símbolos para NOR
56
Importancia de las NAND y NOR
 Todas las funciones Booleanas pueden ser substituibles
por una función equivalente que utilice únicamente
compuertas NAND y/o NOR, esto con los siguientes
objetivos:
 Disminución del número de componentes en una tarjeta de
circuito impreso.
 Dar facilidad de mantenimiento futuro y
 Disminuir el consumo de energía.
 La transformación de cualquier función se efectuará
mediante la correcta utilización del teorema de
Moorgan.
57
Algunas equivalencias
58
Metodología para transformar una
expresión a NAND
1.
2.
3.
59
Una vez obtenida la expresión correspondiente del problema
digital, se realiza a todo el conjunto una doble inversión o
negación.
Como nos encontramos en el caso de implementar con puertas
NAND, si la expresión resultante está en función de productos,
las dos negaciones deben dejarse tal cual. Si, por el contrario, es
una suma, se aplica el teorema de Moorgan sobre dicha suma.
Continuar 2, hasta la obtención de una función compuesta
exclusivamente como productos negados.
Metodología para transformar una
expresión a NOR
1.
2.
3.
60
Con la expresión correspondiente se realiza a todo el conjunto
una doble inversión o negación.
Si la expresión resultante está en función de sumas, las dos
negaciones deben dejarse tal cual. Si se trata de un producto,
tendremos que aplicar el teorema de Moorgan sobre el producto.
Continuar 2 (realizando el proceso anterior) hasta la obtención de
una función compuesta exclusivamente por sumas negadas.
Compuerta OR-Exclusiva y NOR-Exclusiva
61
a
b
a xor b
a
b
a xnor b
0
0
0
0
0
1
0
1
1
0
1
0
1
0
1
1
0
0
1
1
0
1
1
1