Un ejemplo de mapa de Karnaugh. Esta imagen en realidad muestra dos mapas de Karnaugh: para la función ƒ , usando minterms (rectángulos de colores) y para su complemento, usando maxterms (rectángulos grises). En la imagen, E () significa una suma de minitérminos, indicados en el artículo como .
El mapa de Karnaugh ( KM o K-map ) es un método para simplificar expresiones de álgebra booleana . Maurice Karnaugh lo introdujo en 1953 [1] [2] como un refinamiento del gráfico Veitch de 1952 de Edward W. Veitch , [3] [4] que fue un redescubrimiento del diagrama lógico de Allan Marquand de 1881 [5] [6] también conocido como diagrama de Marquand [4] pero ahora centrándose en su utilidad para cambiar circuitos. [4] Los gráficos de Veitch también se conocen como diagramas de Marquand-Veitch [4] o, raramente, como gráficos de Svoboda , [7] y los mapas de Karnaugh como mapas de Karnaugh-Veitch ( mapas KV ).
El mapa de Karnaugh reduce la necesidad de realizar cálculos extensos al aprovechar la capacidad de reconocimiento de patrones de los humanos. [1] También permite la rápida identificación y eliminación de posibles condiciones de carrera . [ se necesita aclaración ]
Los resultados booleanos requeridos se transfieren de una tabla de verdad a una cuadrícula bidimensional donde, en los mapas de Karnaugh, las celdas están ordenadas en código Gray , [8] [4] y cada posición de celda representa una combinación de condiciones de entrada. Las celdas también se conocen como mintérminos, mientras que el valor de cada celda representa el valor de salida correspondiente de la función booleana. Se identifican grupos óptimos de 1 o 0, que representan los términos de una forma canónica de la lógica en la tabla de verdad original. [9] Estos términos se pueden utilizar para escribir una expresión booleana mínima que represente la lógica requerida.
Los mapas de Karnaugh se utilizan para simplificar los requisitos lógicos del mundo real de modo que puedan implementarse utilizando la cantidad mínima de puertas lógicas. Una expresión de suma de productos (SOP) siempre se puede implementar utilizando puertas AND que alimentan una puerta OR , y una expresión de producto de sumas (POS) conduce a puertas OR que alimentan una puerta AND. La expresión POS da un complemento de la función (si F es la función entonces su complemento será F'). [10] Los mapas de Karnaugh también se pueden utilizar para simplificar expresiones lógicas en el diseño de software. Las condiciones booleanas, como se usan, por ejemplo, en declaraciones condicionales , pueden volverse muy complicadas, lo que dificulta la lectura y el mantenimiento del código. Una vez minimizadas, las expresiones canónicas de suma de productos y producto de sumas se pueden implementar directamente utilizando operadores lógicos Y y O. [11]
Ejemplo
Los mapas de Karnaugh se utilizan para facilitar la simplificación de funciones de álgebra booleana . Por ejemplo, considere la función booleana descrita en la siguiente tabla de verdad .
A continuación se muestran dos notaciones diferentes que describen la misma función en álgebra booleana no simplificada, utilizando las variables booleanas A , B , C , D y sus inversas.
¿Dónde están los minitérminos a mapear (es decir, filas que tienen salida 1 en la tabla de verdad)?
¿Dónde están los términos máximos para asignar (es decir, filas que tienen salida 0 en la tabla de verdad)?
K-map dibujado sobre un toroide y en un plano. Las celdas marcadas con puntos son adyacentes.Construcción de mapas K. En lugar de los valores de salida (los valores más a la derecha en la tabla de verdad), este diagrama muestra una representación decimal de la entrada ABCD (los valores más a la izquierda en la tabla de verdad), por lo tanto, no es un mapa de Karnaugh.En tres dimensiones, se puede doblar un rectángulo hasta formar un toroide.
Construcción
En el ejemplo anterior, las cuatro variables de entrada se pueden combinar de 16 maneras diferentes, por lo que la tabla de verdad tiene 16 filas y el mapa de Karnaugh tiene 16 posiciones. Por tanto, el mapa de Karnaugh está dispuesto en una cuadrícula de 4 × 4.
Los índices de filas y columnas (que se muestran en la parte superior e inferior del lado izquierdo del mapa de Karnaugh) están ordenados en código Gray en lugar de orden numérico binario. El código Gray garantiza que solo cambie una variable entre cada par de celdas adyacentes. Cada celda del mapa de Karnaugh completo contiene un dígito binario que representa la salida de la función para esa combinación de entradas.
Agrupamiento
Una vez construido el mapa de Karnaugh, se utiliza para encontrar una de las formas más simples posibles (una forma canónica ) para la información de la tabla de verdad. Los 1 adyacentes en el mapa de Karnaugh representan oportunidades para simplificar la expresión. Los minterms ('términos mínimos') para la expresión final se encuentran rodeando grupos de unos en el mapa. Los grupos de minterm deben ser rectangulares y deben tener un área que sea una potencia de dos (es decir, 1, 2, 4, 8...). Los rectángulos de Minterm deben ser lo más grandes posible sin contener ceros. Los grupos pueden superponerse para hacer cada uno más grande. Las agrupaciones óptimas en el ejemplo siguiente están marcadas por las líneas verde, roja y azul, y los grupos rojo y verde se superponen. El grupo rojo es un cuadrado de 2 × 2, el grupo verde es un rectángulo de 4 × 1 y el área de superposición se indica en marrón.
Las celdas a menudo se indican mediante una abreviatura que describe el valor lógico de las entradas que cubre la celda. Por ejemplo, AD significaría una celda que cubre el área de 2x2 donde A y D son verdaderos, es decir, las celdas numeradas 13, 9, 15, 11 en el diagrama anterior. Por otro lado, A D significaría las celdas donde A es verdadera y D es falsa (es decir, D es verdadera).
La rejilla está conectada toroidalmente , lo que significa que los grupos rectangulares pueden rodear los bordes (ver imagen). Las celdas del extremo derecho son en realidad "adyacentes" a las del extremo izquierdo, en el sentido de que los valores de entrada correspondientes sólo difieren en un bit; de manera similar, también lo son los que están en la parte superior y los que están en la parte inferior. Por lo tanto, A D puede ser un término válido (incluye las celdas 12 y 8 en la parte superior y se ajusta hacia abajo para incluir las celdas 10 y 14), al igual que B D , que incluye las cuatro esquinas.
Solución
Diagrama que muestra dos K-maps. El mapa K para la función f(A, B, C, D) se muestra como rectángulos coloreados que corresponden a mintérminos. La región marrón es una superposición del cuadrado rojo de 2×2 y el rectángulo verde de 4×1. El mapa K para la inversa de f se muestra como rectángulos grises, que corresponden a maxterms.
Una vez que se ha construido el mapa de Karnaugh y los unos adyacentes están unidos mediante cuadros rectangulares y cuadrados, los minitérminos algebraicos se pueden encontrar examinando qué variables permanecen iguales dentro de cada cuadro.
Para el grupo rojo:
A es igual y es igual a 1 en todo el cuadro, por lo tanto debe incluirse en la representación algebraica del mintérmino rojo.
B no mantiene el mismo estado (pasa de 1 a 0) y, por lo tanto, debe excluirse.
C no cambia. Siempre es 0, por lo que se debe incluir su complemento, NOT-C. Por tanto, debería incluirse C.
D cambia, por lo que está excluido.
Por tanto, el primer término mínimo en la expresión booleana de suma de productos es A C .
Para el grupo verde, A y B mantienen el mismo estado, mientras que C y D cambian. B es 0 y debe negarse antes de poder incluirse. Por tanto, el segundo término es A B . Tenga en cuenta que es aceptable que el grupo verde se superponga con el rojo.
De la misma forma, la agrupación azul da el término BC D.
Las soluciones de cada agrupación se combinan: la forma normal del circuito es .
Así, el mapa de Karnaugh ha guiado una simplificación de
También habría sido posible derivar esta simplificación aplicando cuidadosamente los axiomas del álgebra booleana , pero el tiempo que lleva hacerlo crece exponencialmente con el número de términos.
Inverso
La inversa de una función se resuelve de la misma manera agrupando los ceros. [nota 1]
Los tres términos que cubren el inverso se muestran con cuadros grises con bordes de diferentes colores:
El valor de para ABCD = 1111 se reemplaza por un "no me importa". Esto elimina completamente el término verde y permite que el término rojo sea más grande. También permite que el término inverso azul cambie y se haga más grande.
Los mapas de Karnaugh también permiten minimizaciones más sencillas de funciones cuyas tablas de verdad incluyen condiciones de " no importa ". Una condición de "no importa" es una combinación de entradas para las cuales al diseñador no le importa cuál sea la salida. Por lo tanto, las condiciones "no importa" pueden incluirse o excluirse de cualquier grupo rectangular, lo que lo haga más grande. Suelen estar indicados en el mapa con un guión o una X.
El ejemplo de la derecha es el mismo que el ejemplo anterior pero con el valor de f (1,1,1,1) reemplazado por "no me importa". Esto permite que el término rojo se expanda completamente hacia abajo y, por lo tanto, elimina el término verde por completo.
Esto produce la nueva ecuación mínima:
Tenga en cuenta que el primer término es solo A , no A C . En este caso, no me importa ha eliminado un término (el rectángulo verde); otro simplificado (el rojo); y eliminó el peligro de carrera (eliminando el término amarillo como se muestra en la siguiente sección sobre peligros de carrera).
El caso inverso se simplifica de la siguiente manera:
Los mapas de Karnaugh son útiles para detectar y eliminar condiciones de carrera . Los peligros de carrera son muy fáciles de detectar usando un mapa de Karnaugh, porque puede existir una condición de carrera cuando se mueve entre cualquier par de regiones adyacentes, pero separadas, circunscritas en el mapa. Sin embargo, debido a la naturaleza de la codificación Gray, adyacente tiene una definición especial explicada anteriormente: de hecho, nos estamos moviendo sobre un toro, en lugar de un rectángulo, envolviendo la parte superior, inferior y los lados.
En el ejemplo anterior, existe una posible condición de carrera cuando C es 1 y D es 0, A es 1 y B cambia de 1 a 0 (pasando del estado azul al estado verde). Para este caso, se define que la salida permanece sin cambios en 1, pero debido a que esta transición no está cubierta por un término específico en la ecuación, existe la posibilidad de que se produzca una falla (una transición momentánea de la salida a 0).
Hay un segundo error potencial en el mismo ejemplo que es más difícil de detectar: cuando D es 0 y A y B son ambos 1, con C cambiando de 1 a 0 (pasando del estado azul al estado rojo). En este caso, el error se extiende desde la parte superior del mapa hasta la parte inferior.
Los peligros de carrera están presentes en este diagrama.Diagrama superior con términos de consenso agregados para evitar riesgos raciales.
Que realmente se produzcan fallos depende de la naturaleza física de la implementación, y si debemos preocuparnos por ellos depende de la aplicación. En la lógica cronometrada, basta con que la lógica se establezca en el valor deseado en el tiempo para cumplir con el plazo. En nuestro ejemplo, no estamos considerando la lógica sincronizada.
En nuestro caso, un término adicional eliminaría el riesgo potencial de carrera, creando un puente entre los estados de salida verde y azul o los estados de salida azul y rojo: esto se muestra como la región amarilla (que se extiende desde la parte inferior hasta la parte superior de la derecha). mitad) en el diagrama adyacente.
El término es redundante en términos de la lógica estática del sistema, pero tales términos redundantes o de consenso a menudo son necesarios para asegurar un desempeño dinámico sin carreras.
De manera similar, se debe agregar un término adicional de al inverso para eliminar otro posible peligro de carrera. La aplicación de las leyes de De Morgan crea otra expresión de producto de sumas para f , pero con un nuevo factor de .
Ejemplos de mapas de 2 variables
Los siguientes son todos los posibles mapas de Karnaugh 2 × 2 de 2 variables. Junto a cada uno se enumeran los términos mínimos en función de la ecuación mínima libre de riesgos de carrera ( consulte la sección anterior ). Un minterm se define como una expresión que proporciona la forma más mínima de expresión de las variables asignadas. Se pueden formar todos los bloques interconectados horizontales y verticales posibles. Estos bloques deben ser del tamaño de las potencias de 2 (1, 2, 4, 8, 16, 32,...). Estas expresiones crean una asignación lógica mínima de las expresiones de variables lógicas mínimas para las expresiones binarias que se asignarán. Aquí están todos los bloques con un campo.
Un bloque puede continuar en la parte inferior, superior, izquierda o derecha del gráfico. Esto puede incluso extenderse más allá del borde del gráfico para minimizar las variables. Esto se debe a que cada variable lógica corresponde a cada columna vertical y fila horizontal. Una visualización del k-map puede considerarse cilíndrica. Los campos en los bordes de la izquierda y la derecha son adyacentes, y los campos superior e inferior son adyacentes. Los K-Maps para cuatro variables deben representarse como una forma de donut o toroide. Las cuatro esquinas del cuadrado dibujado por el k-map son adyacentes. Se necesitan mapas aún más complejos para 5 variables y más.
Σ m (0); k = 0
Σ m (1); K = A ′ B ′
Σ m (2); K = AB ′
Σ m (3); K = A ′ B
Σ m (4); K = AB
Σ m (1,2); K = B ′
Σ m (1,3); K = A ′
Σ m (1,4); K = A ′ B ′ + AB
Σ m (2,3); K = AB ′ + A ′ B
Σ m (2,4); k = un
Σ m (3,4); K = B
Σ m (1,2,3); K = A' + B '
Σ m (1,2,4); K = A + B ′
Σ m (1,3,4); K = A ′ + B
Σ m (2,3,4); K = A + B
Σ m (1,2,3,4); k = 1
Métodos gráficos relacionados
Los métodos de minimización gráfica relacionados incluyen:
Diagrama de Marquand (1881) de Allan Marquand (1853-1924) [5] [6] [4]
Gráfico de Veitch (1952) de Edward W. Veitch (1924-2013) [3] [4]
Gráfico de Svoboda (1956) de Antonín Svoboda (1907-1980) [7]
Mapa de Mahoney ( M-map , números de designación , 1963) de Matthew V. Mahoney (una extensión simétrica de reflexión de los mapas de Karnaugh para un mayor número de entradas)
Técnicas reducidas del mapa de Karnaugh (RKM) (de 1969) como variables poco frecuentes , variables ingresadas en el mapa (MEV), mapa ingresado por variables (VEM) o mapa de Karnaugh ingresado por variables (VEKM) por GW Schultz, Thomas E. Osborne, Christopher R Clare, J. Robert Burgoon, Larry L. Dornhoff, William I. Fletcher, Ali M. Rushdi y otros (varias extensiones sucesivas del mapa de Karnaugh basadas en entradas variables para un mayor número de entradas)
Mapa de anillos Minterm (MRM, 1990) de Thomas R. McCalla (una extensión tridimensional de los mapas de Karnaugh para un mayor número de entradas)
^ Curtis, Herbert Allen (1962). Un nuevo enfoque para el diseño de circuitos de conmutación . Serie de Laboratorios Bell (1 ed.). Princeton, Nueva Jersey, EE. UU.: D. van Nostrand Company, Inc. ISBN0-44201794-4. OCLC 1036797958. S2CID 57068910. ISBN 978-0-44201794-1 . arca:/13960/t56d6st0q. (viii+635 páginas) (NB. Este libro fue reimpreso por Chin Jih en 1969.)
^ ab Veitch, Edward Westbrook (3 de mayo de 1952) [2 de mayo de 1952]. "Un método gráfico para simplificar funciones de verdad". Transacciones de la reunión anual de la ACM de 1952 . Conferencia anual/Reunión anual de la ACM: Actas de la reunión anual de la ACM de 1952 (Pittsburgh, Pensilvania, EE. UU.). Nueva York, EE.UU.: Asociación de Maquinaria de Computación (ACM): 127–133. doi :10.1145/609784.609801.
^ abcdefg Brown, Frank Markham (2012) [2003, 1990]. Razonamiento booleano: la lógica de las ecuaciones booleanas (reedición de la 2ª ed.). Mineola, Nueva York: Dover Publications, Inc. ISBN978-0-486-42785-0.[1]
^ ab Marquand, Allan (1881). "XXXIII: Sobre diagramas lógicos para n términos". Revista filosófica y revista científica de Londres, Edimburgo y Dublín . 5. 12 (75): 266–270. doi : 10.1080/14786448108627104 . Consultado el 15 de mayo de 2017 .(NB. Muchas fuentes secundarias citan erróneamente este trabajo como "Un diagrama lógico para n términos" o "Sobre un diagrama lógico para n términos".)
^ ab Gardner, Martín (1958). "6. La máquina de Marquand y otros". Máquinas lógicas y diagramas (1 ed.). Nueva York, Estados Unidos: McGraw-Hill Book Company, Inc. págs. 104-116. ISBN1-11784984-8. LCCN 58-6683. arca:/13960/t5cc1sj6b.(x+157 páginas)
^ ab Klir, George Jiří (mayo de 1972). "Notaciones de referencia al Capítulo 2". Introducción a la Metodología de Circuitos de Conmutación (1 ed.). Binghamton, Nueva York, EE.UU.: Litton Educational Publishing, Inc. / D. van Nostrand Company . pag. 84.ISBN0-442-24463-0. LCCN 72-181095. C4463-000-3.(xvi+573+1 páginas)
^ Wakerly, John F. (1994). Diseño digital: principios y prácticas . Nueva Jersey, Estados Unidos: Prentice Hall . págs. 48–49, 222. ISBN0-13-211459-3.(NB. Las dos secciones de la página tomadas en conjunto dicen que los K-maps están etiquetados con un código Gray . La primera sección dice que están etiquetados con un código que cambia solo un bit entre entradas y la segunda sección dice que dicho código se llama Gray. código.)
^ Belton, David (abril de 1998). "Mapas de Karnaugh: reglas de simplificación". Archivado desde el original el 18 de abril de 2017 . Consultado el 30 de mayo de 2009 .
^ Cocinero, Aarón. "Uso de mapas de Karnaugh para simplificar el código". Rareza cuántica. Archivado desde el original el 18 de abril de 2017 . Consultado el 7 de octubre de 2012 .
Vingron, Shimon Peter (2004) [05 de noviembre de 2003]. "Mapas de Karnaugh". Teoría del cambio: conocimiento a través de la lógica de predicados . Berlín, Heidelberg, Nueva York: Springer-Verlag . págs. 57–76. ISBN 3-540-40343-4.
Wickes, William E. (1968). "3.5. Diagramas de Veitch". Diseño Lógico con Circuitos Integrados . Nueva York, Estados Unidos: John Wiley & Sons . págs. 36–49. LCCN 68-21185. pag. 36: […] un refinamiento del diagrama de Venn en el sentido de que los círculos se reemplazan por cuadrados y se organizan en forma de matriz. El diagrama de Veitch etiqueta los cuadrados con los minitérminos . Karnaugh asignó unos y ceros a los cuadrados y sus etiquetas y dedujo el esquema de numeración de uso común.
Maxfield, Clive "Max" (29 de noviembre de 2006). "Lógica de Reed-Muller". Lógica 101 . Tiempos EE.UU. Parte 3. Archivado desde el original el 19 de abril de 2017 . Consultado el 19 de abril de 2017 .
Lind, Larry Federico; Nelson, John Christopher Cunliffe (1977). "Sección 2.3". Análisis y Diseño de Sistemas Digitales Secuenciales. Prensa Macmillan . ISBN 0-33319266-4.(146 páginas)
Holder, Michel Elizabeth (marzo de 2005) [14 de febrero de 2005]. "Una técnica de mapa de Karnaugh modificada". Transacciones IEEE sobre educación . 48 (1). IEEE : 206–207. doi :10.1109/TE.2004.832879. eISSN 1557-9638. ISSN 0018-9359. S2CID 25576523.[2]
Cavanagh, José (2008). Fundamentos de aritmética informática y Verilog HDL (1 ed.). Prensa CRC .
Grund, Jürgen (2011). KV-Diagramme in der Schaltalgebra - Verknüpfungen, Beweise, Normalformen, schaltalgebraische Umformungen, Anschauungsmodelle, Paradebeispiele [ Diagramas KV en álgebra booleana - relaciones, demostraciones, formas normales, transformaciones algebraicas, modelos ilustrativos, ejemplos típicos ] (ejecutable de Windows/Mac o Adobe Flash -Navegador compatible en CD-ROM) (libro electrónico) (en alemán) (1 ed.). Berlín, Alemania: viademica Verlag. ISBN 978-3-939290-08-7. Archivado (PDF) desde el original el 12 de noviembre de 2022 . Consultado el 26 de noviembre de 2022 .[3] (282 páginas con 14 animaciones)