MAPA DE KARNAUGH
Técnicas Digitales y Arquitectura de Computadores.
Ing. Jorge Mercado
Análisis Booleano de circuitos lógicos
El álgebra de Boole proporciona una manera concisa de expresar el
funcionamiento de un circuito lógico formado por una combinación de puertas
lógicas.
Para obtener la expresión booleana de un determinado circuito lógico,
la manera de proceder consiste en comenzar con las entradas situadas más a la
izquierda e ir avanzando hasta las líneas de salida, escribiendo la expresión para
cada puerta.
Construcción de una tabla de verdad para un circuito lógico
Una vez que se ha determinado la expresión booleana de un circuito
dado, puede desarrollarse una tabla de verdad que represente la salida del
circuito lógico para todos los valores posibles de las variables de entrada.
El procedimiento requiere que se evalúe la expresión booleana para
todas las posibles combinaciones de valores de las variables de entrada.
Evaluación de la expresión: Para evaluar la expresión A.(B + CD), en
primer lugar hallamos los valores de las variables que hacen que la expresión sea
igual a 1, utilizando las reglas de la suma y la multiplicación booleanas. En este caso,
la expresión es igual a 1 sólo si A = 1 y (B+CD) = 1, ya que:
1° condición: A=1 de lo contrario la salida es cero
2° condición B+CD=1 de lo contrario la salida es cero
Si B=1 se cumple la condición
o
Si C=1 y D=1 se cumple la condición
Con estas condiciones se arma la tabla de verdad y se pone a uno la
salida que cumplen las condiciones indicadas
Construcción de una tabla de verdad para un circuito lógico
En la tabla se puede ver que la
salida es 1 cuando A=1 y B=1, las
variables C y D no influyen, en
consecuencia se podría simplificar
el circuito y en lugar de colocar
A.(B + CD) bastaría con una
compuerta AND que haga A.B
El álgebra de boole juntamente con los teoremas de DeMorgan son
herramientas muy útiles para la simplificación de circuitos. Sin embargo cuando la
función es compleja el cálculo puede llegar a ser muy dificultoso; existe un método
más sencillo que veremos más adelante y se denominan mapas de Karnaugh
Formas Estándar de las expresiones BOOLEANAS
Todas las expresiones booleanas, independientemente de su forma,
pueden convertirse en cualquiera de las dos formas estándar:
a) suma de productos o suma de minterms (SOP, Sum Of Products)
b) producto de sumas o producto de maxterms (POS, Product Of
Sums)
La estandarización posibilita que la evaluación, simplificación e
implementación de las expresiones booleanas sea mucho más sistemática y
sencilla.
Expresiones booleanas y tablas de verdad
Todas las expresiones booleanas pueden convertirse fácilmente en
tablas de verdad utilizando los valores binarios de cada término de la expresión.
Desarrollar una tabla de verdad para la expresión suma de productos
Se denominan minterms a la combinación de entradas que hacen que la función X
valga uno. Se los representa con una letra m minúscula y el de menor valor lleva
un subíndice 0 y van en forma creciente hasta completar la tabla de verdad.
Expresiones booleanas y tablas de verdad
Desarrollar una tabla de verdad para la expresión producto de sumas
estándar siguiente
Se denominan maxterms a la combinación de entradas que hacen que la función X
valga cero. Se los representa con una letra M mayúscula y el de menor valor lleva
un subíndice 0 y van en forma creciente hasta completar la tabla de verdad.
MAPAS DE KARNAUGH
Un mapa de Karnaugh proporciona un método sistemático de
simplificación de expresiones booleanas y, si se aplica adecuadamente, genera las
expresiones suma de productos y producto de sumas más simples posibles,
conocidas como expresiones mínimas.
El mapa de Karnaugh es básicamente una “receta” para la simplificación.
se pueden utilizar para expresiones de dos, tres, cuatro y cinco variables.
El número de celdas de un mapa de Karnaugh es igual al número total
de posibles combinaciones de las variables de entrada
Mapa de Karnaugh
para 3 variables
MAPAS DE KARNAUGH
Mapa de Karnaugh
para 4 variables
Las celdas de un mapa de
Karnaugh se disponen de manera
que sólo cambia una única
variable entre celdas adyacentes.
Minimización de suma de productos
Por cada término de la expresión suma de productos, se coloca un 1 en el
mapa de Kanaugh en la celda correspondiente al valor del producto.
Por ejemplo:
Minimización de suma de productos
Después de haber obtenido el mapa de Karnaugh de una suma de
productos, la expresión suma de productos mínima se obtiene agrupando los 1s y
determinando la expresión suma de productos mínima a partir del mapa.
Podemos agrupar los unos del mapa de Karnaugh de acuerdo con
las reglas siguientes, rodeando las celdas adyacentes que contengan unos.
1. Un grupo tiene que contener 1, 2, 4, 8 ó 16 celdas, valores que se
corresponden con las potencias de 2.
2. Cada celda de un grupo tiene que ser adyacente a una o más celdas
del mismo grupo.
3. Incluir siempre en cada grupo el mayor número posible de 1s de
acuerdo a la regla número 1.
4. Cada 1 del mapa tiene que estar incluido en al menos un grupo. Los
1s que ya pertenezcan a un grupo pueden estar incluidos en otro, siempre que los
grupos que se solapen contengan 1s no comunes.
Minimización de suma de productos
En la Figura se muestran los grupos. En algunos casos, puede existir más de una forma de
agrupar los 1s para formar grupos máximos.
Determinación de la expresión suma de productos
1) Agrupar las celdas que contienen 1s. Cada grupo de celdas que
contiene 1s da lugar a un término producto compuesto por todas las variables que
aparecen en el grupo en sólo una forma. (La variable que cambia de valor, se
elimina).
2) Cuando se han obtenido todos los términos producto mínimos , se
suman para obtener la expresión suma de productos mínima.
F=
Obtención directa del mapa de Karnaugh a partir de la tabla de verdad
Recuerde que una tabla de verdad proporciona la salida de una expresión
booleana para todas las posibles combinaciones de las variables de entrada.
En esta figura puede ver que tanto la expresión booleana, la tabla de
verdad como el mapa de Karnaugh son sólo distintas maneras de representar
una función lógica.
Condiciones indiferentes
Algunas veces se producen situaciones en las que algunas combinaciones de las
variables de entrada no están permitidas. (Por ejemplo el código BCD). Estos estados no
permitidos pueden considerarse como términos indiferentes con respecto a su efecto en la
salida. Esto significa que a estos términos se les puede asignar tanto un 1 como un 0 en la
salida; realmente no son importantes dado que nunca van a generarse.
Los términos “indiferentes” pueden utilizarse para aprovechar mejor el método del
mapa de Karnaugh. La Figura muestra que, para cada término indiferente, se escribe una
X en la celda. Cuando se agrupan los 1s, las X pueden ser consideradas también como 1s para
agrandar los grupos, o como 0s si no obtenemos ninguna ventaja. Cuanto mayor sea el grupo,
más sencillo será el término resultante.
Determinación de la expresión suma de productos
EJEMPLO 1: Utilizar un mapa de Karnaugh para minimizar la siguiente
expresión suma de productos estándar
La suma de productos estándar se pasa al mapa y las celdas se
agrupan como se muestra en la Figura
F=
Determinación de la expresión suma de productos
EJEMPLO 2: Utilizar un mapa de Karnaugh para minimizar la siguiente
expresión suma de productos estándar
El primer término tiene que desarrollarse en los términos
para obtener la suma de productos estándar
F=
