stringtranslate.com

mapa de karnaugh

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.

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:

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:

Esto produce lo inverso:

Mediante el uso de las leyes de De Morgan , se puede determinar el producto de sumas :

no me importa

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:

Mediante el uso de las leyes de De Morgan , se puede determinar el producto de sumas :

Peligros 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 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.

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étodos gráficos relacionados

Los métodos de minimización gráfica relacionados incluyen:

Ver también

Notas

  1. ^ Esto no debe confundirse con la negación del resultado de la función encontrada anteriormente.

Referencias

  1. ^ ab Karnaugh, Maurice (noviembre de 1953) [23 de abril de 1953, 17 de marzo de 1953]. "El método de mapas para la síntesis de circuitos lógicos combinacionales" (PDF) . Transacciones del Instituto Americano de Ingenieros Eléctricos, Parte I: Comunicaciones 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 ).
  2. ^ 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. 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.)
  3. ^ 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.
  4. ^ 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. ISBN  978-0-486-42785-0.[1]
  5. ^ 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".)
  6. ^ 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. ISBN 1-11784984-8. LCCN  58-6683. arca:/13960/t5cc1sj6b.(x+157 páginas)
  7. ^ 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.ISBN 0-442-24463-0. LCCN  72-181095. C4463-000-3.(xvi+573+1 páginas)
  8. ^ 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 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.)
  9. ^ 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 .
  10. ^ Esquivar, 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 .
  11. ^ 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 .

Otras lecturas

enlaces externos