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 diagrama Veitch de 1952 de Edward W. Veitch , [3] [4] que fue un redescubrimiento del diagrama lógico de 1881 de Allan Marquand [5] también conocido como diagrama de Marquand [4] pero con un enfoque ahora puesto en su utilidad para circuitos de conmutación. [4] Por lo tanto, los gráficos de Veitch también se conocen como diagramas de Marquand-Veitch ,[4] y 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 .
Los resultados booleanos requeridos se transfieren de una tabla de verdad a una cuadrícula bidimensional donde, en los mapas de Karnaugh, las celdas se ordenan en código Gray , [6] [4] y cada posición de celda representa una combinación de condiciones de entrada. Las celdas también se conocen como minitérminos, mientras que cada valor de celda representa el valor de salida correspondiente de la función booleana. Se identifican grupos óptimos de unos o ceros, que representan los términos de una forma canónica de la lógica en la tabla de verdad original. [7] Estos términos se pueden usar 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 para que se puedan implementar utilizando un número mínimo de puertas lógicas. Una expresión de suma de productos (SOP) siempre se puede implementar usando compuertas AND que ingresan a una compuerta OR , y una expresión de producto de sumas (POS) conduce a compuertas OR que alimentan una compuerta AND. La expresión POS da un complemento de la función (si F es la función, entonces su complemento será F '). [8] 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 AND y OR. [9]
Ejemplo
Los mapas de Karnaugh se utilizan para facilitar la simplificación de las funciones de álgebra de Boole . Por ejemplo, considere la función booleana descrita en la siguiente tabla de verdad .
A | B | C | D | ||
---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 1 | 0 |
2 | 0 | 0 | 1 | 0 | 0 |
3 | 0 | 0 | 1 | 1 | 0 |
4 | 0 | 1 | 0 | 0 | 0 |
5 | 0 | 1 | 0 | 1 | 0 |
6 | 0 | 1 | 1 | 0 | 1 |
7 | 0 | 1 | 1 | 1 | 0 |
8 | 1 | 0 | 0 | 0 | 1 |
9 | 1 | 0 | 0 | 1 | 1 |
10 | 1 | 0 | 1 | 0 | 1 |
11 | 1 | 0 | 1 | 1 | 1 |
12 | 1 | 1 | 0 | 0 | 1 |
13 | 1 | 1 | 0 | 1 | 1 |
14 | 1 | 1 | 1 | 0 | 1 |
15 | 1 | 1 | 1 | 1 | 0 |
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 son los términos mínimos a mapear (es decir, filas que tienen la salida 1 en la tabla de verdad).
- dónde son los maxterms para mapear (es decir, filas que tienen salida 0 en la tabla de verdad).
Mapa de Karnaugh
En el ejemplo anterior, las cuatro variables de entrada se pueden combinar de 16 formas diferentes, por lo que la tabla de verdad tiene 16 filas y el mapa de Karnaugh tiene 16 posiciones. Por lo tanto, el mapa de Karnaugh está organizado 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 en orden numérico binario. El código gris asegura 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.
Una vez que se ha 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 en la tabla de verdad. Los 1 adyacentes en el mapa de Karnaugh representan oportunidades para simplificar la expresión. Los minitérminos ('términos mínimos') para la expresión final se encuentran rodeando grupos de 1 en el mapa. Los grupos de minitérminos deben ser rectangulares y deben tener un área que sea una potencia de dos (es decir, 1, 2, 4, 8 ...). Los rectángulos de término mínimo deben ser lo más grandes posible sin contener ceros. Los grupos pueden superponerse para agrandar cada uno. 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 verdaderas, 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 cuadrícula está conectada toroidalmente , lo que significa que los grupos rectangulares pueden envolver 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 solo 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 a la parte inferior para incluir las celdas 10 y 14, al igual que B D , que incluye las cuatro esquinas.
Solución
Una vez que se ha construido el mapa de Karnaugh y los 1 adyacentes vinculados por cajas rectangulares y cuadradas, los minitérminos algebraicos se pueden encontrar examinando qué variables permanecen iguales dentro de cada caja.
Para la agrupación roja:
- A es igual y es igual a 1 en todo el cuadro, por lo que debe incluirse en la representación algebraica del minité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 debe incluirse su complemento, NOT-C. Por tanto, debería incluirse C.
- D cambia, por lo que se excluye.
Así, la primera en términos producto en la expresión booleana de suma de productos es A C .
Para la agrupación verde, A y B mantienen el mismo estado, mientras que C y D cambian. B es 0 y debe negarse antes de que pueda incluirse. Por consiguiente, el segundo término es A B . Tenga en cuenta que es aceptable que la agrupación verde se superponga con la roja.
De la misma manera, 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 de Boole , pero el tiempo que lleva hacerlo aumenta exponencialmente con el número de términos.
Inverso
La inversa de una función se resuelve de la misma manera agrupando los ceros.
Los tres términos para cubrir el inverso se muestran todos con recuadros grises con bordes de diferentes colores:
- marrón : A B
- oro : A C
- azul : BCD
Esto produce lo inverso:
Mediante el uso de las leyes de De Morgan , se puede determinar el producto de las sumas :
No le importa
Los mapas de Karnaugh también permiten minimizaciones más fáciles 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 que al diseñador no le importa cuál es la salida. Por lo tanto, las condiciones "no importa" pueden incluirse o excluirse de cualquier grupo rectangular, lo que lo haga más grande. Por lo general, se indican en el mapa con un guión o una X.
El ejemplo de la derecha es el mismo que el anterior pero con el valor de f (1,1,1,1) reemplazado por un "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 sólo una , no un C . En este caso, no 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:
Mediante el uso de las leyes de De Morgan , se puede determinar el producto de las sumas :
Riesgos de carrera
Eliminación
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 disjuntas, 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 en un toro, en lugar de un rectángulo, envolviendo la parte superior, inferior y los lados.
- En el ejemplo anterior , existe una condición de carrera potencial 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, la salida se define para permanecer 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 una falla (una transición momentánea de la salida a 0).
- Hay una segunda falla 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, la falla se envuelve desde la parte superior del mapa hasta la parte inferior.
Si realmente se producirán fallos depende de la naturaleza física de la implementación, y si debemos preocuparnos por ello depende de la aplicación. En la lógica cronometrada, es suficiente que la lógica se asiente en el valor deseado a tiempo para cumplir con la fecha límite de tiempo. En nuestro ejemplo, no estamos considerando la lógica sincronizada.
En nuestro caso, un término adicional de eliminaría el peligro 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 envuelve desde la parte inferior hasta la parte superior de la mitad derecha) en el diagrama adyacente.
El término es redundante en términos de la lógica estática del sistema, pero estos términos redundantes o consensuados a menudo son necesarios para asegurar un rendimiento dinámico libre de carreras.
Del mismo modo, un término adicional de debe agregarse a la inversa para eliminar otro peligro potencial de carrera. La aplicación de las leyes de De Morgan crea otro producto de la expresión 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 de 2 variables y 2 × 2. Con cada uno se enumeran los términos mínimos en función dey la ecuación mínima de carrera libre de peligros ( ver sección anterior ). Un minitérmino 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 posibles bloques interconectados horizontales y verticales. Estos bloques deben ser del tamaño de las potencias de 2 (1, 2, 4, 8, 16, 32, ...). Estas expresiones crean un mapeo lógico mínimo de las expresiones de variable lógica mínima para las expresiones binarias que se mapeará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. Eso incluso puede pasar 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 la parte superior e inferior son adyacentes. Los K-Maps para cuatro variables deben representarse en forma de rosquilla o toro. 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 = A
Σ 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] [4]
- Gráfico de Veitch (1952) de Edward W. Veitch (1924-2013) [3] [4]
- Mapa de Mahoney ( mapa M , números de designación , 1963) por Matthew V. Mahoney (una extensión simétrica de reflexión de los mapas de Karnaugh para un mayor número de entradas)
- Reducción mapa de Karnaugh (RKM) técnicas (desde 1969) como las variables poco frecuentes , las variables mapa a entrar (MEV), mapa variable introducida (VEM) o mapa de Karnaugh variable introducida (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 de mapas de Karnaugh basadas en entradas variables para un mayor número de entradas)
- Mapa de anillo mínimo (MRM, 1990) de Thomas R. McCalla (una extensión tridimensional de los mapas de Karnaugh para un mayor número de entradas)
Ver también
- Forma normal algebraica (ANF)
- Diagrama de decisión binaria (BDD), una estructura de datos que es una representación comprimida de una función booleana
- Minimizador de lógica heurística de espresso
- Lista de temas de álgebra de Boole
- Optimización lógica
- Punnett Square (1905), un diagrama similar en biología
- Algoritmo de Quine-McCluskey
- Expansión Reed-Muller
- Diagrama de Venn (1880)
- Polinomio de Zhegalkin
Referencias
- ↑ a b Karnaugh, Maurice (noviembre de 1953) [23 de abril de 1953, 17 de marzo de 1953]. "El método de mapa para la síntesis de circuitos lógicos combinacionales" (PDF) . Transacciones del Instituto Americano de Ingenieros Eléctricos, Parte I: Comunicación y Electrónica . 72 (5): 593–599. doi : 10.1109 / TCE.1953.6371932 . Documento 53-217. Archivado desde el original (PDF) el 16 de abril de 2017 . Consultado el 16 de abril de 2017 .(NB. También contiene una breve reseña de Samuel H. Caldwell .)
- ^ Curtis, Herbert Allen (1962). Un nuevo enfoque para el diseño de circuitos de conmutación . The Bell Laboratories Series (1 ed.). Princeton, Nueva Jersey, EE. UU .: D. van Nostrand Company, Inc. ISBN 0-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.)
- ^ a b Veitch, Edward Westbrook (3 de mayo de 1952) [2 de mayo de 1952]. "Un método de gráfico para simplificar las funciones de la 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, Estados Unidos: Asociación de Maquinaria de Computación (ACM): 127-133. doi : 10.1145 / 609784.609801 .
- ^ a b c d e f g 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. ISBN 978-0-486-42785-0. [1]
- ^ a b Marquand, Allan (1881). "XXXIII: en diagramas lógicos para n términos" . The London, Edinburgh y Dublin Philosophical Magazine y Journal of Science . 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 "En un diagrama lógico para n términos".)
- ^ Wakerly, John F. (1994). Diseño digital: principios y prácticas . Nueva Jersey, Estados Unidos: Prentice Hall . págs. 48–49, 222. ISBN 0-13-211459-3.(NB. Las dos secciones de página tomadas juntas dicen que los mapas K están etiquetados con código Gray . La primera sección dice que están etiquetados con un código que cambia solo un bit entre las 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 .
- ^ Dodge, Nathan B. (septiembre de 2015). "Simplificación de circuitos lógicos con mapas de Karnaugh" (PDF) . Universidad de Texas en Dallas , Escuela de Ingeniería y Ciencias de la Computación Erik Jonsson . Archivado (PDF) desde el original el 18 de abril de 2017 . Consultado el 18 de abril de 2017 .
- ^ Cook, Aaron. "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 .
Otras lecturas
- Katz, Randy Howard (1998) [1994]. Diseño de lógica contemporánea . The Benjamin / Cummings Publishing Company . págs. 70–85 . doi : 10.1016 / 0026-2692 (95) 90052-7 . ISBN 0-8053-2703-7.
- Vingron, Shimon Peter (2004) [5 de noviembre de 2003]. "Mapas de Karnaugh". Teoría de conmutación: 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 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ó 1 y 0 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 Reed-Muller" . Lógica 101 . EE Times . Part 3. Archivado desde el original el 19 de abril de 2017 . Consultado el 19 de abril de 2017 .
- Lind, Larry Frederick; 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/02/2005]. "Una técnica de mapa de Karnaugh modificada" . Transacciones IEEE sobre educación . IEEE . 48 (1): 206–207. doi : 10.1109 / TE.2004.832879 . eISSN 1557-9638 . ISSN 0018-9359 . S2CID 25576523 . [2]
- Cavanagh, Joseph (2008). Computer Arithmetic y Verilog HDL Fundamentals (1 ed.). Prensa CRC .
- Kohavi, Zvi; Jha, Niraj K. (2009). Teoría de la conmutación y de los autómatas finitos (3 ed.). Prensa de la Universidad de Cambridge . ISBN 978-0-521-85748-2.
enlaces externos
- Detectar rectángulos superpuestos , por Herbert Glarner.
- Uso de mapas de Karnaugh en aplicaciones prácticas , proyecto de diseño de circuitos para controlar los semáforos.
- Tutorial de K-Map para 2, 3, 4 y 5 variables
- Ejemplo de mapa de Karnaugh
- SIMPLIFICACIÓN DE FUNCIONES BOOLEAN POCKET – PC, Ledion Bitincka - George E. Antoniou
- Solución de problemas de K-Map