Fundamentos de lógica digital: El mapa de Karnaught
Continuamos con los fundamentos de la lógico digital ahora vamos con el mapa de Karnought que este será un método para simplificar el álgebra…
En el capítulo anterior vimos que el álgebra Boleana es un arma poderosa para el estudio de los circuitos lógicos.
Sin embargo, el álgebra Boleana tiene sus limitaciones.
Considérese la siguiente expresión:
Aparentemente, esta expresión ya no se puede simplificar. Sin embargo, podemos comprobar (construyendo las Tablas de Verdad) que esta expresión cuya simplificación no es tan obvia pese a todo es equivalente a la siguiente expresión:
la cual es mucho más sencilla. Se hace evidente que hay casos en los cuales el álgebra Boleana no es suficiente. Tenemos pues que recurrir a otras técnicas que la complementen.
Los diagramas de subconjuntos nos proporcionan una manera sencilla de poder visualizar las relaciones que puede haber entre varias variables. Quizá los diagramas más sencillos de todos son los que representan al “1” lógico, el cual podemos representar como un cuadro completamente lleno, y al “0” lógico, el cual podemos representar como un cuadro completamente vacío:
En este tipo de diagramas, no sólo podemos representar el “uno” y el “cero”. También podemos representar variables. El diagrama más sencillo de todos es el que utilizamos para representar una sola variable, el cual está dividido en dos partes: una parte “llena” que es la parte en la cual la variable A toma el valor de “1” (a la izquierda, de color ciano), y la parte “vacía” que es la parte en la cual la variable A toma el valor de “0” (a la derecha, sin color):
Pero con estos diagramas no sólo podemos representar a la variable. También podemos representar el inverso lógico de la variable, el cual será como se muestra a continuación:
Del mismo modo, podemos representar una segunda variable B y el complemento de la misma de la siguiente manera:
Superimponiendo ambas variables en un mismo diagrama, podemos contestar algunas preguntas interesantes como la siguiente: ¿en qué parte del diagrama mixto se encontrará la región en la cual ambas variables A y B se traslapan? La respuesta se dá a continuación:
A continuación tenemos la región en donde la variable A se traslapa con el complemento de la variable B, así como la región en la cual los complementos de ambas variables se traslapan:
Hagámonos ahora otra pregunta: ¿cuál sería la región en la cual las variables A y B se unen (en lugar de intersectarse), la porción del diagrama en donde podemos estar ya sea en A ó en B, o sea la región que representaría la suma Boleana A+B de dichas variables? La respuesta se dá a continuación:
Y el área que representa la suma Boleana de los complementos de ambas variables es la siguiente:
Por su parte, la expresión Boleana AB+AB que representa la salida de un bloque OR-EXCLUSIVO es la siguiente:
Si queremos superimponer en el mismo mapa una tercera variable C, lo podemos hacer de la siguiente manera:
Y si queremos superimponer en el mismo mapa una cuarta variable D, lo podemos hacer de la siguiente manera:
El mismo procedimiento constructivo se puede extender hacia una quinta variable e inclusive hacia una sexta variable, aunque la ventaja de visualización se va perdiendo rápidamente encima de las cuatro variables.
Para representar en el mapa una expresión elaborada como (A+B)(C+D):
primero localizamos en el mapa la región que representa la suma de las regiones A y B, o lo que es lo mismo, la suma Boleana de las variables A y B:
tras lo cual localizamos en el mapa la región que representa la suma de las regiones C y D, o lo que es lo mismo, la suma Boleana de las variables C y D:
tras lo cual obtenemos un mapa que represente las regiones que ambos mapas de A+B y C+D tengan en común, o sea la región común en la que ambos se intersectan, lo cual equivale a llevar a cabo la operación lógica AND de A+B y de C+D.
Los diagramas de subconjuntos permiten verificar de manera casi inmediata todos los teoremas Boleanos que fueron demostrados en el capítulo anterior. Por ejemplo, el teorema que dice:
es verificado de la siguiente manera:
Es importante señalar que para los matemáticos puros, esto no constituye una demostración formal, sino una simple verificación de un teorema. Sin embargo, entanto que nosotros mismos nos podamos convencer visualmente de la veracidad de algún enunciado Boleano mediante este recurso, podemos hacer a un lado el rigorismo formalista y continuar adelante con la mentalidad típica del ingeniero que busca procedimientos que den resultados comprobados en la práctica.
Con cambios mínimos, los diagramas de subconjuntos nos sirven de base para introducirnos a una de las herramientas de simplificación de circuitos lógicos más populares que hay. Estudiaremos a continuación el siguiente mapa para dos variables boleanas A y B conocido como el mapa de Karnaugh, inventado en 1952 por Edward W. Veitch y refinado posteriormente por Maurice Karnaugh, un ingeniero de telecomunicaciones trabajando para Bell Labs:
Para la construcción de nuestro primer mapa de Karnaugh, utilizaremos un concepto introducido en la sección de problemas resueltos del capítulo anterior, el concepto del minterm. Supóngase que desamos localizar el minterm AB en el mapa de Karnaugh. Estudiando el mapa detenidamente, vemos que podemos representar dicho minterm en el mapa como se muestra a continuación:
De la misma manera, si deseamos representar los minterms AB y A·B en el mapa de Karnaugh, podemos hacerlo de la siguiente manera:
Ahora bien, también podemos representar variables sencillas en el mapa de Karnaugh. Supóngase que deseamos representar B en el mapa de Karnaugh. Esto lo logramos de la siguiente manera:
Estudiamos ahora un hecho de importancia trascendental. Este último mapa de Karnaugh nos indica que B es igual a la suma de los minterms AB y A·B, lo cual podemos comprobar mediante el álgebra Boleana como sigue:
Tenemos aquí nuestra primera indicación sobre cómo podemos usar el mapa de Karnaugh para simplificar circuitos lógicos.
Supóngase que la salida de un circuito está dada por la siguiente expresión:
Podemos describir la salida del circuito en un mapa de Karnaugh de la manera siguiente:
Vemos de inmediato en el mapa cómo los minterms AB y A·B forman dos grupos adyacentes que están cubiertos completamente en el mapa por la variable A. Concluímos, pues, que la salida simplificada del circuito está dada por la siguiente expresión:
La regla general para simplificar un circuito usando el mapa de Karnaugh es examinar el mapa que le corresponde y determinar los agrupamientos más grandes de grupos adyacentes que se pueden describir con el menor número de variables boleanas.
Usando el mapa de Karnaugh, tratemos ahora de simplificar la expresión que encontramos al comienzo de este capítulo:
Su mapa de Karnaugh con una simplificación posible tendrá el siguiente aspecto (el “minterm” correspondiente a la variable B está enmarcado dentro de una línea verde cubriendo todo el renglón representativo de B, mientras que el “minterm” AB es puesto antes de los agrupamientos simplificadores en la esquina inferior izquierda) :
Como se puede ver, es posible hacer dos agrupamientos de grupos adyacentes, los cuales están descritos por la expresión:
que es la expresión simplificada que buscábamos.
Asimismo, el mapa de Karnaugh nos indica cuáles son las expresiones que no se pueden simplificar. Por ejemplo, la siguiente expresión:
está descrita por el siguiente mapa:
Esta expresión, como se puede ver en su mapa de Karnaugh, ya no se puede simplificar.
Existen también mapas de Karnaugh para expresiones con tres o más variables, algunos de los cuales se muestran al final de esta introducción.
Supóngase que deseamos simplificar un circuito con tres variables de entrada A, B y C cuya salida es la siguiente:
En este caso, tenemos que utilizar el mapa de Karnaugh para tres variables:
El mapa de Karnaugh para la expresión lógica dada se muestra a continuación:
La primera simplificación es evidente. Los minterms ABC y ABC pueden ser agrupados para ser representados por la relación BC (esta agrupación es la que corresponde a los unos que están encerrados dentro del rectángulo rojo). La siguiente simplificación no es tan obvia.
Obsérvese que si conectamos los vértices del mapa alrededor de un cilindro (esto es, si enrollamos el mapa y unimos el lado izquierdo con el lado derecho), se puede llevar a cabo otra simplificación. En efecto, los minterms A·B·C y A·B·C se pueden agrupar dentro de la relación BC (correspondiente a los unos que están encerrados dentro del rectángulo verde).
La salida simplificada será por lo tanto:
Consideremos un circuito cuya Tabla de Verdad es la siguiente:
Podemos representar esta expresión de salida en función no de sus minterms sino de sus maxterms, los cuales fueron introducidos en la sección de problemas resueltos del capítulo anterior, basados en el producto-de-sumas en lugar de la suma-de-productos, como se muestra en el siguiente mapa de Karnaugh:
Como se muestra en el mapa, los maxtems A+B y A+B se pueden agrupar dentro del “maxterm” B.
Asimismo, los maxterms A+B y A+B se pueden agrupar para formar el “maxterm” A.
Puesto que la salida del circuito sigue siendo el producto de sus maxterms, la salida en este caso será:
Este es el resultado que buscábamos.
El mapa de Karnaugh se puede extender para manejar cuatro variables, como se muestra a continuación:
Para intentar simplificar un circuito lógico con cinco variables, podemos recurrir a un mapa de Karnaugh como el siguiente:
Existe otro tipo de representación para el mapa de Karnaugh, la cual es completamente equivalente a la que ya hemos visto. Bajo esta representación, a continuación tenemos un mapa de Karnaugh para dos variables A y B:
Aquí la entrada correspondiente a la combinación AB=01 estará situada en el segundo renglón y en la primera columna. Esta representación es completamente a la representación que vimos al principio. A continuación se muestran los dos tipos de representación, lado a lado, para dos variables A y B:
Para tres variables de entrada A, B y C, bajo la representación alterna un mapa de Karnaugh tendrá el siguiente aspecto:
Aquí el casillero correspondiente a la entrada ABC= 011 estará situado en el segundo renglón y en la segunda columna. Y el casillero correspondiente a la entrada ABC=101 estará situado en el primer renglón y en la cuarta columna.
Y para cuatro variables A, B, C y D, el mapa de Karnaugh para este tipo de representación será el siguiente:
El acomodo de variables en el mapa se puede llevar a cabo de acuerdo con las preferencias personales de cada persona, lo principal es que en el mapa aparezcan de modo apropiado todas las variables con todos sus diversos valores posibles de “unos” y “ceros”.
A continuación se llevará a cabo la simplificación de un circuito lógico de tres variables a, b y c, mediante un mapa de Karnaugh de este tipo trazado de la siguiente manera:
Dentro de este mapa de Karnaugh, se destacarán las combinaciones de valores tanto de las entradas como de la salida:
El propósito del mapa de Karnaugh es aprovechar al máximo la capacidad humana de poder “agrupar” visualmente patrones similares para poder descubrir así los agrupamientos de “unos” (o alternamente, de “ceros”) que pueden resultar en una simplificación. En este caso, podemos llevar a cabo los siguientes agrupamientos:
Fuente | Lógica digital
Continuación: Parte 2
