Circuitos digitales: método K-Map

En capítulos anteriores, hemos simplificado las funciones booleanas usando postulados y teoremas booleanos. Es un proceso que lleva mucho tiempo y tenemos que volver a escribir las expresiones simplificadas después de cada paso.

Para superar esta dificultad, Karnaughintrodujo un método para simplificar funciones booleanas de una manera fácil. Este método se conoce como método de mapa de Karnaugh o método de mapa K. Es un método gráfico, que consta de 2 n celdas para 'n' variables. Las celdas adyacentes se diferencian solo en la posición de un solo bit.

K-Maps para 2 a 5 variables

El método K-Map es más adecuado para minimizar funciones booleanas de 2 variables a 5 variables. Ahora, hablemos de los K-Maps para 2 a 5 variables una por una.

2 K-Map variable

El número de celdas en el mapa K de 2 variables es cuatro, ya que el número de variables es dos. La siguiente figura muestra2 variable K-Map.

  • Solo existe una posibilidad de agrupar 4 términos mínimos adyacentes.

  • Las posibles combinaciones de agrupar 2 términos mínimos adyacentes son {(m 0 , m 1 ), (m 2 , m 3 ), (m 0 , m 2 ) y (m 1 , m 3 )}.

3 K-Map variable

El número de celdas en el mapa K de 3 variables es ocho, ya que el número de variables es tres. La siguiente figura muestra3 variable K-Map.

  • Solo existe una posibilidad de agrupar 8 términos mínimos adyacentes.

  • Las posibles combinaciones de agrupar 4 términos mínimos adyacentes son {(m 0 , m 1 , m 3 , m 2 ), (m 4 , m 5 , m 7 , m 6 ), (m 0 , m 1 , m 4 , m 5 ), (m 1 , m 3 , m 5 , m 7 ), (m 3 , m 2 , m 7 , m 6 ) y (m 2 , m 0 , m 6 , m 4 )}.

  • Las combinaciones posibles de agrupar 2 términos mínimos adyacentes son {(m 0 , m 1 ), (m 1 , m 3 ), (m 3 , m 2 ), (m 2 , m 0 ), (m 4 , m 5 ) , (m 5 , m 7 ), (m 7 , m 6 ), (m 6 , m 4 ), (m 0 , m 4 ), (m 1 , m 5 ), (m 3 , m 7 ) y ( m 2 , m 6 )}.

  • Si x = 0, entonces el mapa K de 3 variables se convierte en mapa K de 2 variables.

4 K-Map variable

El número de celdas en el mapa K de 4 variables es dieciséis, ya que el número de variables es cuatro. La siguiente figura muestra4 variable K-Map.

  • Solo existe una posibilidad de agrupar 16 términos mínimos adyacentes.

  • Sea R 1 , R 2 , R 3 y R 4 los términos mínimos de la primera fila, segunda fila, tercera fila y cuarta fila respectivamente. De manera similar, C 1 , C 2 , C 3 y C 4 representan los términos mínimos de la primera columna, segunda columna, tercera columna y cuarta columna respectivamente. Las posibles combinaciones de agrupar 8 términos mínimos adyacentes son {(R 1 , R 2 ), (R 2 , R 3 ), (R 3 , R 4 ), (R 4 , R 1 ), (C 1 , C 2 ) , (C 2 , C 3 ), (C 3 , C 4 ), (C 4 , C 1 )}.

  • Si w = 0, el mapa K de 4 variables se convierte en el mapa K de 3 variables.

5 K-Map variable

El número de celdas en el mapa K de 5 variables es treinta y dos, ya que el número de variables es 5. La siguiente figura muestra 5 variable K-Map.

  • Solo existe una posibilidad de agrupar 32 términos mínimos adyacentes.

  • Hay dos posibilidades de agrupar 16 términos mínimos adyacentes. es decir, agrupación de términos mínimos de m 0 a m 15 y m 16 a m 31 .

  • Si v = 0, el mapa K de 5 variables se convierte en el mapa K de 4 variables.

En todos los mapas K anteriores, utilizamos exclusivamente la notación de términos mínimos. Del mismo modo, puede utilizar exclusivamente la notación de términos Max.

Minimización de funciones booleanas usando K-Maps

Si consideramos la combinación de entradas para las que la función booleana es '1', obtendremos la función booleana, que está en standard sum of products formulario después de simplificar el K-map.

De manera similar, si consideramos la combinación de entradas para las que la función booleana es '0', obtendremos la función booleana, que está en standard product of sums formulario después de simplificar el K-map.

Siga estos rules for simplifying K-maps para obtener la forma estándar de suma de productos.

  • Seleccione el mapa K respectivo según el número de variables presentes en la función booleana.

  • Si la función booleana se da como suma de términos mínimos, coloque los unos en las respectivas celdas de término mínimo en el mapa K. Si la función booleana se da como suma de productos, coloque los unos en todas las celdas posibles de K-map para las que los términos de producto dados son válidos.

  • Verifique las posibilidades de agrupar el número máximo de adyacentes. Deberían ser potencias de dos. Comience desde la potencia más alta de dos y hasta la potencia mínima de dos. La potencia más alta es igual al número de variables consideradas en el mapa K y la potencia mínima es cero.

  • Cada agrupación dará un término literal o de un producto. Es conocido comoprime implicant. Se dice que el principal implicante esessential prime implicant, si al menos un solo '1' no está cubierto por ninguna otra agrupación, sino solo por esa agrupación.

  • Anote todos los implicantes principales y los implicantes principales esenciales. La función booleana simplificada contiene todos los implicantes primos esenciales y solo los implicantes primos requeridos.

Note 1 - Si las salidas no se definen para alguna combinación de entradas, esos valores de salida se representarán con don’t care symbol ‘x’. Eso significa que podemos considerarlos como '0' o '1'.

Note 2- Si los términos de indiferencia también están presentes, coloque la 'x' de indiferencia en las respectivas celdas de K-map. Considere solo las 'x' de no importa que sean útiles para agrupar el número máximo de adyacentes. En esos casos, trate el valor de no importa como '1'.

Ejemplo

Nos deja simplify la siguiente función booleana, f(W, X, Y, Z)= WX’Y’ + WY + W’YZ’ utilizando K-map.

La función booleana dada está en forma de suma de productos. Tiene 4 variables W, X, Y y Z. Por lo tanto, requerimos4 variable K-map. los4 variable K-map con los correspondientes a los términos del producto dados se muestra en la siguiente figura.

Aquí, los 1 se colocan en las siguientes celdas de K-map.

  • Las celdas, que son comunes a la intersección de la Fila 4 y las columnas 1 y 2, corresponden al término del producto, WX’Y’.

  • Las celdas, que son comunes a la intersección de las Filas 3 y 4 y las columnas 3 y 4, corresponden al término del producto, WY.

  • Las celdas, que son comunes a la intersección de las filas 1 y 2 y la columna 4, corresponden al término del producto, W’YZ’.

No hay posibilidad de agrupar 16 adyacentes ni 8 adyacentes. Hay tres posibilidades de agrupar 4 adyacentes. Después de estas tres agrupaciones, no queda ninguna sin agrupar. Por lo tanto, no es necesario verificar la agrupación de 2 adyacentes. los4 variable K-map con estos tres groupings se muestra en la siguiente figura.

Aquí, tenemos tres implicantes principales WX ', WY e YZ'. Todos estos implicantes principales sonessential debido a las siguientes razones.

  • Dos unos (m8 & m9)de los grupos de cuarta fila no están cubiertos por ningún otro grupo. Solo el agrupamiento de la cuarta fila cubre esos dos.

  • Solo uno (m15)de agrupación de forma cuadrada no está cubierta por ninguna otra agrupación. Solo la agrupación de forma cuadrada cubre ese.

  • Dos unos (m2 & m6)de la agrupación de la cuarta columna no están cubiertos por ninguna otra agrupación. Solo el agrupamiento de la cuarta columna cubre esos dos.

Por lo tanto, los simplified Boolean function es

f = WX’ + WY + YZ’

Siga estos rules for simplifying K-maps para obtener un producto estándar en forma de sumas.

  • Seleccione el mapa K respectivo según el número de variables presentes en la función booleana.

  • Si la función booleana se da como producto de la forma de términos Max, coloque los ceros en las respectivas celdas de términos Max en el mapa K. Si la función booleana se da como producto de sumas, coloque los ceros en todas las celdas posibles de K-map para las que los términos de suma dados son válidos.

  • Verifique las posibilidades de agrupar el número máximo de ceros adyacentes. Deberían ser potencias de dos. Comience desde la potencia más alta de dos y hasta la potencia mínima de dos. La potencia más alta es igual al número de variables consideradas en el mapa K y la potencia mínima es cero.

  • Cada agrupación dará un término literal o de una suma. Es conocido comoprime implicant. Se dice que el principal implicante esessential prime implicant, si al menos un solo '0' no está cubierto por ninguna otra agrupación, sino solo por esa agrupación.

  • Anote todos los implicantes principales y los implicantes principales esenciales. La función booleana simplificada contiene todos los implicantes primos esenciales y solo los implicantes primos requeridos.

Note- Si los términos de indiferencia también están presentes, coloque la 'x' de indiferencia en las respectivas celdas de K-map. Considere solo las 'x' de no importa que sean útiles para agrupar el número máximo de ceros adyacentes. En esos casos, trate el valor de no importa como '0'.

Ejemplo

Nos deja simplify la siguiente función booleana, $ f \ left (X, Y, Z \ right) = \ prod M \ left (0,1,2,4 \ right) $ usando K-map.

La función booleana dada es producto de la forma de términos máximos. Tiene 3 variables X, Y y Z. Por lo tanto, necesitamos 3 K-map variables. Los términos Max dados son M 0 , M 1 , M 2 y M 4 . Los 3variable K-map con ceros correspondientes a los términos Max dados se muestra en la siguiente figura.

No hay posibilidad de agrupar 8 ceros adyacentes ni 4 ceros adyacentes. Hay tres posibilidades de agrupar 2 ceros adyacentes. Después de estas tres agrupaciones, no queda un solo cero sin agrupar. los3 variable K-map con estos tres groupings se muestra en la siguiente figura.

Aquí, tenemos tres implicantes primos X + Y, Y + Z y Z + X. Todos estos implicantes primos son essential porque un cero en cada grupo no está cubierto por ningún otro grupo, excepto con sus grupos individuales.

Por lo tanto, los simplified Boolean function es

f = (X + Y).(Y + Z).(Z + X)

De esta manera, podemos simplificar fácilmente las funciones booleanas hasta 5 variables usando el método K-map. Para más de 5 variables, es difícil simplificar las funciones usando K-Maps. Porque, el número decells en K-map obtiene doubled incluyendo una nueva variable.

Debido a esta comprobación y agrupación de unos adyacentes (términos mínimos) o ceros adyacentes (términos máximos) será complicado. DiscutiremosTabular method en el próximo capítulo para superar las dificultades del método K-map.