Métodos tabulares de simplificación

Existen varios métodos de simplificación de funciones tabulares. En este artículo estudiaremos dos de ellos: los mapas de Karnaugh y el Algoritmo de Quine-McCluskey.

Mapas de Karnaugh

El método tabular de simplificación más conocido y usado es el de los mapas de Karnaugh.

Maurice Karnaugh

Maurice Karnaugh, ingeniero eléctrico. Durante el periodo entre 1952 y 1966 trabajaba en los laboratorios Bell, y en 1954 inventó el método de simplificación de funciones booleanas que llevan su nombre.

Este método sirve para simplificar funciones de hasta seis variables de entrada, (aunque a mi sólo me explicaron hasta cuatro).

Existe un mapa para cada tipo de función, según el número de entradas.

Mapas de Karnaugh para 2, 3 y 4 variables de entrada:

Mapa 2 vbles Mapa 3 vbles Mapa 4 vbles
Mapas de Karnaugh para 2, 3 y 4 variables

Rellenar un mapa de Karnaugh

Para rellenar el mapa de Karnaugh correspondiente a una función, primero elegiremos el mapa adecuado al número de variables, y después, trasladaremos lo valores de los minterms a las posiciones adecuadas en el mapa, poniendo un '1'.

A veces, existen ciertas combinaciones de las variables de entrada que no se pueden dar en ningún caso real (veremos esto en algunos ejemplos). Para esos casos, la salida de la función puede quedar indeterminada, es decir, no nos importará si el valor de la función para esas combinaciones es uno o cero.

Esto nos puede ayudar a simplificar la función, y trasladaremos esas combinaciones al mapa poniendo una 'X' en las casillas correspondientes.

Un ejemplo

laboratorio
Laboratorio lunar

Tenemos que diseñar un sistema de control que permita el paso de personas desde un laboratorio lunar al exterior, y viceversa. Esto se hace mediante un sistema de esclusas, de modo que la presión a ambos lados de la puerta que se quiera abrir sea la misma.

Para poder controlar todas las posibilidades, disponemos de tres señales de entrada:

  • a: Petición de apertura de puerta A.
  • b: Petición de apertura de puerta B.
  • P: Presión de la cámara estanca.

Las funciones que tenemos que obtener son cuatro:

  • A: Permiso para abrir la puerta A.
  • B: Permiso para abrir la puerta B.
  • C: Puesta en marcha de la bomba C.
  • D: Puesta en marcha de la bomba D.

El funcionamiento es el siguiente. Una persona dentro del laboratorio quiere salir. Solicita la apertura de la puerta A. Si la presión en la cámara estanca es igual a la del laboratorio (1), se activa la apertura de la puerta A, si la presión es la del vacío (0), no se activa la puerta, pero se activa la bomba C, para igualar la presión de la cámara con la del laboratorio.

El funcionamiento para la otra puerta es análogo. Del mismo modo, las funciones para dar permisos para abrir puertas son las mismas independientemente del lado de la puerta desde el que se pida permiso.

Las tablas de verdad para todas las combinaciones posibles de las tres señales son:

 a  b  P  A  B  C  D 
0000000
0010000
0100100
0110001
1000010
1011000
1100100
1111000

Hemos decidido que si se pide la apertura de ambas puertas simultáneamente, el sistema permita abrir aquella para la que no haga falta presurizar o despresurizar la cámara estanca.

También podríamos añadir otra condición: que en el laboratorio sólo hay una persona, y por lo tanto, es imposible que se solicite la apertura de ambas puertas de forma simultánea. Las tablas de verdad, teniendo en cuenta esto, serían:

 a  b  P  A  B  C  D 
0000000
0010000
0100100
0110001
1000010
1011000
110XXXX
111XXXX

Veamos los mapas de Karnaugh correspondientes a las funciones A, B, C y D, para esta segunda versión:

Función A Función B Función C Función D
Mapas de Karnaugh para las funciones A, B, C y D

Simplificar un mapa de Karnaugh

Para simplificar un mapa, lo primero que hay que hacer es agrupar de forma gráfica las casillas con unos. Hay varias condiciones que se deben cumplir:

  • Los grupos tienen que tener un número de casillas que sea potencia de 2, es decir, 1, 2, 4, 8 ó 16 casillas.
  • Sólo se pueden agrupar casillas adyacentes, pero hay que tener en cuenta que en todos los mapas, las adyacencias también se producen entre la parte izquierda y derecha del mapa, y entre la parte superior e inferior.
  • La misma casilla puede integrarse en varios grupos, pero todas las casillas con unos deben pertenecer a algún grupo.
  • Para completar grupos se pueden incluir casillas con X.

El objetivo es obtener el menor número de grupos que contengan a todas las casillas con unos.

Por cada grupo se obtiene un término de la función de salida. Ese término corresponde a un minterm del que se eliminan las variables que cambian de valor en el grupo. De las variables que quedan, las que tengan valor "1" se incluyen en el minterm sin negar, y las que tengan valor "0", se incluyen negadas.

Simplificar los mapas del ejemplo

Grupos para las funciones del ejemplo:

Grupos función A Grupos función B Grupos función C Grupos función D
Grupos para los mapas de Karnaugh para las funciones A, B, C y D

En la función A, tenemos un único grupo en el que debemos eliminar la variable b. Las dos variables que quedan, a y P, valen "1", por lo que se incluyen en el minterm sin negar. La función queda:

A = a·P

Aplicando las mismas reglas a las otras tres funciones:

B = b·P'

C = a·P'

D = b·P

Si tuviéramos que incluir estas funciones en un programa C++, podría quedar algo como:

if(a && P) AbrirPuerta(A);
if(b && !P) AbrirPuerta(B);
if(a && !P) ActivarBomba(C);
if(b && P) ActivarBomba(D);

Ejemplo sentencia if

Antes obtuvimos una tabla de verdad para una función que provenía de una sentencia if. Vamos a aplicar este método para simplificarla:

 A  B  C  D  F 
00000
00010
00100
00111
01000
01010
01100
01111
10000
10010
10100
10111
11001
11011
11101
11111

Tenemos que usar un mapa de cuatro variables, lo rellenamos según esta tabla:

Función F
Mapa de Karnaugh para la función F

Ahora hacemos los grupos:

Grupos de función F
Grupos para el mapa de Karnaugh para la función F

En el grupo rojo, las variables C y D desaparecen del minterm, y las variables A y B se incorporan sin negar.

En el grupo verde, las variables A y B desaparecen y quedan las variables C y D sin negar.

El resultado es:

F = A·B + C·D

Que es el punto de partida, por lo que no se ha podido simplificar la función, aunque si partiéramos de la tabla de verdad, es una mejora con respecto a las formas canónicas.

BCD a 7 segmentos

Vamos con el ejemplo clásico para este tipo de problemas.

Display 7 seg
Display 7 segmentos
Dígitos
Dígitos 0 a 9
letras
Nombres

En electrónica, se usan dispositivos como el de la figura para mostrar números. A estos dispositivos se les suele llamar displays de siete segmentos, precisamente porque disponen de siete segmentos, de modo que encendiendo algunos de ellos se consiguen mostrar los diez dígitos de la numeración en base 10, es decir, los dígitos '0' a '9'.

Las combinaciones de los segmentos para conseguir cada dígito son las de la figura de la derecha, y a cada segmento se le asigna una letra, de la 'A' a la 'G':

El problema consiste en diseñar las siete funciones, una para cada segmento, en función de las cuatro variables de entrada correspondientes a un dígito BCD, o sea, decimal codificado en binario.

En la codificación BCD se usan los valores binarios del 0 (0000) al 9 (1001).

Tabla de verdad

La tabla de verdad para un codificador BCD a siete segmentos es:

 a  b  c  d   A  B  C  D  E  F  G 
00001111110
00010110000
00101101101
00111111001
01000110011
01011011011
01101011111
01111110000
10001111111
10011111011
1010XXXXXXX
1011XXXXXXX
1100XXXXXXX
1101XXXXXXX
1110XXXXXXX
1111XXXXXXX

Mapas de Karnaugh

Veamos los mapas de Karnaugh para estas funciones:

Función A
Función A
Función B
Función B
Función C
Función C
Función D
Función D
Función E
Función E
Función F
Función F
Función G
Función G

Y las funciones simplificadas quedan:

A = a+c+b·d+b'·d'

B = b'+c·d+c'·d'

C = b+c'+d

D = a+b'·c+b'·d'+c·d'+b·c'·d

E = c·d'+b'·d'

F = a+c'·d'+b·c'+b·d'

G = a+b'·c+b·c'+b·d'

Prueba

Display
0000
Display
0001
Display
0010
Display
0011
Display
0100
Display
0101
Display
0110
Display
0111
Display
1000
Display
1001


suministrado por FreeFind
Valid HTML 4.0! Valid CSS!