🔥 Mapas de Karnaugh || BY - WILDOANTRAXXX 🔥

¿Que son los Mapas de Karnaugh?

La minimización de las funciones lógicas es una de las tareas típicas en el proceso de aprendizaje de los circuitos. Por lo tanto, creo que ese artículo tiene un lugar para estar, espero que lo disfruten.

¿Por qué se necesita esto?

La complejidad de una función lógica, y por lo tanto la complejidad y el costo del circuito (circuito) que la implementa, es proporcional al número de operaciones lógicas y al número de ocurrencias de variables o sus negaciones. En principio, cualquier función lógica puede simplificarse directamente usando axiomas y teoremas de lógica, pero, como regla, tales transformaciones requieren cálculos engorrosos.

Además, el proceso de simplificación de expresiones booleanas no es algorítmico. Por lo tanto, es más aconsejable utilizar métodos especiales de minimización algorítmica que permitan simplificar la función de manera más simple, rápida y precisa. Dichos métodos incluyen, por ejemplo, el método Quine, el método de la tarjeta Carnot, el método de prueba implicante, el método de la matriz implicante, el método Quine-McCluskey, etc. Estos métodos son los más adecuados para la práctica ordinaria, especialmente minimizando la función lógica usando tarjetas Carnot. El método del mapa de Carnot conserva la claridad cuando el número de variables no es más de seis. En los casos en que el número de argumentos es más de seis, generalmente se usa el método Quine-McCluskey.

En el proceso de minimizar una u otra función lógica, generalmente se tiene en cuenta en qué base será más eficiente realizar su forma mínima utilizando circuitos electrónicos.

Minimizando funciones lógicas con tarjetas Carnot

El mapa de Carnot es una forma gráfica de minimizar las funciones de conmutación (booleanas), proporcionando una simplicidad relativa de trabajar con expresiones grandes y eliminando posibles razas. Representa las operaciones de unión incompleta por pares y absorción elemental. Los mapas de Carnot se consideran como una tabla de verdad de una función adecuadamente reorganizada. Las tarjetas de Carnot se pueden considerar como un cierto escaneo plano de un cubo booleano n-dimensional.

Los mapas de Carnot fueron inventados en 1952 por Edward W. Veitch y mejorados en 1953 por Maurice Carnot, físico de Bell Labs, y fueron diseñados para ayudar a simplificar los circuitos electrónicos digitales.

En el mapa de Carnot, las variables booleanas se transfieren de la tabla de verdad y se ordenan usando el código Gray, en el que cada número siguiente difiere del anterior en solo un dígito.

El método principal para minimizar las funciones lógicas presentadas en forma de SDNF o SKNF es la operación de unión incompleta por pares y absorción elemental. La operación de pegado por pares se lleva a cabo entre dos términos (miembros) que contienen las mismas variables, cuyas ocurrencias (directa e inversa) coinciden para todas las variables excepto una. En este caso, todas las variables, excepto una, se pueden quitar de los corchetes, y las ocurrencias directas e inversas de una variable que queda en los corchetes se pueden unir. Por ejemplo:

La posibilidad de absorción se deriva de las igualdades obvias.

Por lo tanto, la tarea principal para minimizar SDNF y SKNF es la búsqueda de términos adecuados para pegar con posterior absorción, lo que para formas grandes puede ser una tarea bastante difícil. Las tarjetas Carnot proporcionan una forma visual de encontrar dichos términos.

Como se sabe, las funciones booleanas de N variables representadas en forma de SDNF o SKNF pueden incluir 2N términos diferentes. Todos estos términos forman una estructura que es topológicamente equivalente al cubo N-dimensional, y cualesquiera dos términos conectados por un borde son adecuados para pegar y absorber.

La figura muestra una tabla de verdad simple para una función de dos variables, un cubo (cuadrado) bidimensional correspondiente a esta tabla, así como un cubo bidimensional con la designación de los miembros SDNF y una tabla equivalente para agrupar términos:

En el caso de una función de tres variables, debe tratar con un cubo tridimensional. Es más complicado y menos obvio, pero técnicamente posible. Como ejemplo, la figura muestra la tabla de verdad para la función booleana de tres variables y el cubo correspondiente.

Como se puede ver en la figura, para el caso tridimensional son posibles configuraciones de términos más complejas. Por ejemplo, cuatro términos que pertenecen a una cara de un cubo se combinan en un término con la absorción de dos variables:

En el caso general, se puede decir que los términos 2K que pertenecen a una cara K-dimensional de un hipercubo se pegan en un término, y las variables K se absorben.

Para simplificar el trabajo con funciones booleanas de un gran número de variables, se propuso la siguiente técnica conveniente. El cubo, que es una estructura de términos, se despliega en un plano como se muestra en la figura. Por lo tanto, es posible representar funciones booleanas con más de dos variables en una tabla plana. Debe recordarse que el orden de los códigos de término en la tabla (00 01 11 10) no corresponde al orden de los números binarios, y las celdas ubicadas en las columnas extremas de la tabla son adyacentes entre sí.

Del mismo modo, puede trabajar con las funciones de cuatro, cinco o más variables. En la figura se muestran ejemplos de tablas para N = 4 y N = 5. Para estas tablas, debe recordarse que las celdas vecinas son aquellas ubicadas en las celdas correspondientes de las columnas extremas y las celdas correspondientes de las filas superior e inferior. Para las tablas de 5 o más variables, también es necesario tener en cuenta que los cuadrados 4x4 están virtualmente uno encima del otro en la tercera dimensión, por lo tanto, las celdas correspondientes de dos cuadrados 4x4 adyacentes son adyacentes y los términos correspondientes se pueden pegar.

Se puede compilar un mapa de Carnot para cualquier número de variables, sin embargo, es conveniente trabajar con el número de variables no más de cinco. De hecho, el Mapa de Carnot es una tabla de verdad compilada en una forma bidimensional. Debido al uso del código Gray, la fila superior es adyacente a la inferior y la columna derecha es adyacente a la izquierda, es decir. toda la Tarjeta Carnot se desploma en una figura de toro (bagel). En la intersección de la fila y la columna, se fija el valor correspondiente de la tabla de verdad. Una vez que la tarjeta está llena, puede comenzar a minimizar.

Si es necesario obtener el DNF mínimo, entonces en el Mapa consideramos solo aquellas celdas que contienen unidades, si se necesita CNF, entonces consideramos aquellas celdas que contienen ceros. La minimización en sí se lleva a cabo de acuerdo con las siguientes reglas (por ejemplo, DNF):

Combina celdas adyacentes que contienen unidades en una región para que una región contenga 2 n ( n entero = 0 ...infinito ) celdas (recuerde que las filas y columnas extremas son adyacentes entre sí), en el área no debe haber celdas que contengan ceros;

El área debe ubicarse simétricamente a los ejes (los ejes se ubican cada cuatro celdas);

Las áreas no adyacentes ubicadas simétricamente a los ejes se pueden combinar en una sola;

El área debe ser lo más grande posible, y el número de áreas lo más pequeño posible;

Las áreas pueden cruzarse;

Varias opciones de cobertura son posibles.

Luego, tomamos la primera región y observamos qué variables no cambian dentro de esta región, escribimos la conjunción de estas variables, si la variable que no cambia es cero, coloca una inversión sobre ella. Tomamos la siguiente área, hacemos lo mismo que para la primera, etc. para todas las áreas. Las conjunciones de regiones están unidas por una disyunción.

Por ejemplo (para Mapas en 2 variables):

 

Para CNF, todo es igual, solo consideramos las celdas con ceros, combinamos variables que no cambian dentro de la misma región en disyunciones (coloca inversiones sobre variables individuales) y combinamos las disyunciones de regiones en una conjunción. Esta minimización se considera completa. Entonces, para el Mapa de Carnot en la Fig. 1, la expresión en el formato DNF se verá así: