Karna Ugh

SIMPLIFICACION DE FUNCIONES LOGICAS

4.1.- MAPAS DE KARNAUGH.

Como se ha visto hasta ahora, las funciones lógicas se pueden simplificar, generalmente, por medio del uso de técnica algebraicas basadas en las reglas de Boole. Sin embargo, surgen dos problemas: El proceso se dificulta si se quiere una sistematización. Es dificil decir cuando se ha llegado a una solución óptima.

El mapa de Karnaugh y el método Quine McCluskey sobre pasan estas dificultades, los cuales proveen un método visual o gráfico, para simplificar de manera óptima funciones Booleanas. El mapa de Karnaugh es una herramienta útil para simplificar funciones hasta de cinco variables, sim embargo se puede extender a seis. Generalmente se encuentra que el mapa de Karnaugh es un método sencillo y mas rápido que el Quine McCluskey.

4.1.1.- METODO DE CONSTRUCCION.

Por ser un método gráfico de simplificación, el mapa de Karnaugh, basa su procedimiento en agrupar aquellos mintérminos o máxterminos donde se cumpla la expresión Booleana , para los mintérminos; ó, para los maxtérminos. La forma de graficar un mapa de Karnaugh se puede desglosar de la siguiente manera: Supongase que se desea representar una única variable binaria graficamente, variable "C" por ejemplo; debido a que posee dos posibilidades ( cero "0" ó uno "1" ; o, dicho de otra manera, ); entonces será subconjunto de un universo, tal que vendría dado de la forma como la mostrada en la figura # 4.1.

FIGURA # 4.1.

SIMPLIFICACION DE FUNCIONES LOGICAS PAGINA Nro. 112

Surge por lo tanto, un par de áreas, subconjunto de la variable "C" indicativas de las posibilidades binarias de la variable que representa. Cada una de estas áreas la llamaremos celdas, y se le asignará un peso específico de acuerdo al valor de las posibles combinaciones binarias. Como por ejemplo en la figura 4.1, se observa que hay una celda cuyo peso es "0" y otra con peso de "1". Ahora, supongase un conjunto de dos variables lógicas independientes (A y B), estas se grafican de las forma siguiente: ver figura # 4.2.

FIGURA # 4.2.

Cuando son dos variables, se puede observar que cada combinación origina una celda, obteniendose así cuatro; numeradas como: 0,1,2 y3. Por lo tanto, si son tres variables se obtendrán ocho celdas; si son cuatro, 16 celdas, etc.

EJEMPLO 4.1. A continución se darán algunos ejemplo para tres variables, figura # 4.3; además de algunas variantes en la construcción de mapa de Karnaugh.

FIGURA # 4.3.

En la figura # 4.3-a, la variable "X" que posee el peso mas significativo, representa las columnas; y las variable "Y" y

Ing Rodrigo Machado.


"Z", de menor peso, las filas; De esta manera se crea un mapa de Karnaugh de ocho celdas. En la figura # 3-c, en cambio, se toma la variable de menor peso significativo para formar las filas; y, XY, de mayor valor significativo para las columnas; sin embargo, se originan la misma cantidad de celdas, solo que la posición que ocupan en el mapa es diferente a la de la figura # 4.3-a. La figura # 4.3-b, es otra forma útil de representar un mapa de Karnaugh, con la diferencia de que no se escriben las posibles combinaciones binarias, sino que se colocan las variables literalmente, generando de esta forma las celdas apropiadas.

EJEMPLO 4.2. Las figuras # 4.4, 4.55 y 4.6, para cuatro cinco y seis variables, indicandose numericamente sus respectivas celdas. Es de destacar que en la última figura existen 64 celdas.

FIGURA # 4.4.



FIGURA # 4.5.

MAPA DE SEIS VARIABLES

FIGURA # 4.6. EJERCICIOS # 4.1. 4.1.1.- Construir un mapa de Karnaugh para las siguientes variables: X, Y y Z. 4.1.2.- Construir un mapa de Karnaugh para las siguientes variables: a, b, c, d, e. 4.1.3.- Construir un mapa de Karnaugh para las siguientes variables:f,g,h,i. 4.1.4.- Construir un mapa de Karnaugh para las siguientes variables:A, B ,D, E, F, G.



4.1.2.- CELDAS ADYACENTES

El hecho de colocar la combinacion binaria para un par de variables cualquiera de la forma indicada como : 00, 01, 11 y 10; es con la finalidad de que cada celda vecinas sean adyacentes. DEFINICION: Una celda es adyacente a otra, cuando la distancia binaria entre las combinaciones que representan sean igual a la unidad. (d=1). Como ejemplo vamos a referirnos al mapa de Karnaugh de la figura # 4.4. En el mismo se puede observar que la celda cinco tiene como adyacentes a las celdas 1, 4, 7 y 13. Sin embargo, para la celda 10 son: 2, 8,11,14 y 15. Para dejar mas claro el significado de celdas adyacentes, nos referiremos ahora, a la figura # 4.5; las celdas adyacentes de 6 son:2, 4, 7, 14 y 22.

EJERCICIOS # 4.2. 4.2.1.- Cuales son las celdas adyacentes de la celda 0, en el mapa de Karnaugh de la figura : # 4.3; #4.4; # 4.5 y # 4.6 4.2.2.- Cuales son las adyacentes de la celda 38 de la figura # 4.6. 4.2.3.- Cuales son adyacentes de la celda 31 de la figura # 4.5. 4.1.3.-REPRESENTACION DE UNA FUNCION EN UN

MAPA DE KARNAUGH. Para representar una función en un mapa de Karnaugh, primeramente, hay que tener en mente los siguientes aspectos: a.- Toda función, sea dada en mintérminos o maxtérminos, está compuesta por variables dependientes y por variables independientes. b.- Las variables independientes, son todas aquellas combinaciones posibles, que colocadas con una distancia de uno, forman celdas ordenadas por filas y columnas. c.- Como regla, las combinaciones de las variables de mayor peso formarán las columnas, y las de menor peso las filas. Ver figura # 4.7.



FIGURA # 4.7.

d.- Las variables dependientes se ubican en la celda del valor, en decimal, indicado por el mintérmino o maxtérmino que lo conforman. El mintérmino llena la celda con "uno" y el maxtérmino con "cero". EJEMPLO # 4.3 Representar las siguientes funciones en mapas de Karnaugh. a.- F(X,Y,Z)= Σm (0.3, 5, 6) Respuesta figura # 4.8.

FIGURA # 4.8.



b.- F(X,Y,Z)= Π M( 0,3,5,6) Respuesta figura # 4.9.

FIGURA # 4.9.

c.- F(a,b,c,d)= Σm(0,1,2,7,8,9,13,14) Respuesta figura # 4.10.

FIGURA # 4.10.

EJERCICIO # 4.3. Represente en su correspondiente mapa de Karnaugh las siguientes funciones: a).- f(a,b,c)=Σm(0,1,4,6,7). b).- f(x,y,v,z)=Σm(8,9,10,12,13,14,15). c).- f(A,B,C,D)=ΠM(0,1,2,8,9,10,12,13). d).- f(a,b,c,d,e)=Σ m(0,1,2,3,8,9,14,15,16,18,28,29,30). e).- f= AB'C+ A'BC' + A'B'C + A B'C' f).- f= (a +b +c)( a + b' +c')(a' +b' + c) g).-f(A,B,C,D,E,F)=Σm(0,8,9,10,28,29,30,31,42,43,44,55,56,57). 4.1.4.- SIMPLIFICACION DE FUNCIONES.



Para optimizar una función dada como suma de producto (mintérminos), se pueden enumerar los siguientes pasos: a.- Se vacía la función en el mapa de Karnaugh. b.- Se agrupan la celdas adyacentes que en su interior tengan un uno. La finalidad de agrupar estas celdas consiste en aplicar de manera automática la regla Booleana

: , por lo que esto origina a: c.- Se escoje la variable independiente que se mantenga constante.

EJEMPLO # 4.4. Optimizar la siguiente función dada en mintérminos. f(A,B,C)= Σ m(1,2,4,5,7) a).- Se representa la función en un mapa de Karnaugh. (figura # 4.11.) NOTA: Se grafican dos mapas de Karnauhg, figura # 4.11-a y 4.11-b para mostrar dos formas de construcción de mapas.

FIGURA # 4.11.

b).- Se agrupan las celdas adyacentes que en su interior posean un uno (1). En el mapa de Karnaugh se puden observar las siguientes celdas adyacentes: (1 y 5), (4 y 5), (5 y 7) ; la "2" no es adyacente a ninguna. Figura # 4.12.



FIGURA # 12.

c).- Si consideramos las celdas adyacentes "1" y "5", se puede notar que la variable "A" sufre un cambio que va de cero a uno (

); quedando por lo tanto las variable "B" y "C" constantes, formando así un implicante primo ( ). De igual manera,en las celdas 4 y 5, se observa que la variable "C" varia ( ); y en las celdas 5 y 7, varia la variable "B" ( ), generando los implicantes primos respectivamente. La celda 2 como no es adyacente a ninguna otra, las variables que la forman son de hecho implicante primo ( ). En conclusión, la expresión óptima quedaría de la forma:

FIGURA # 4.13.

EJEMPLO # 4.5. Obtener la expresión mínima dada como suma de producto para la función que se da acontinuación:

f(a,b,c,d)=Σ m(0,2,3,5,6,7,8,10,11,14,15)



FIGURA # 4.14.

Observese que los mintérminos agrupados en el entorno señalado con la letra "a" ,(celdas 0,2,8,10), generan los implicantes primos " "; los agrupados por el entorno "b" (celdadas 5 y 7), proporcionan " "; y los encerrados en "c" ( celdas 2,3,6,7,10,11,14 y 15), proporcionana el implicante primo "c". Por lo tanto, la expresión mínima encontrada es:

EJEMPLO # 4.6.

obtener la mínima expresión de la función dada a continuación:

f(w,x,y,z)=Σ m(0,1,2,5,7,8,9,10,13,14) El mapa de Karnauhg queda:

FIGURA # 4.15.

La función óptima viene dada, por lo tanto, por los implicantes primos señalados en la figura # 4.15 con los literales a,b,c y d; como se muestra a continuación:

4.1.5.- IMPLICANTES PRIMOS NO ESENCIALES.



Debido a que el sistema de minimización en estudio es del tipo visual e instuitivo, en algunos casos, no se obtiene la función óptima mas idónea en una única inspección que se le haga al mapa de Karnaugh, aunque el diseñador sea muy experto. Pués, es posible que existan celdas que representan mintérminos que al agruparse de dos o mas formas puedan dar origen a mas de un implicante primo que cumplan la misma función. DEFINCION: Los implicantes primos que cumplen una misma función se les denomina implicantes primos redundantes. IMPLICANTES PRIMOS ESENCIALES: Son aquellos que son únicos en un mapa de Karnaugh, es decir, no existe otro implicante primo que haga la misma función. Son no redundante. En el siguiente ejemplo se muestra un mapa de Karnaugh donde se recogen implicantes primos redundantes. EJEMPLO # 4.7. Sea el mapa de Karnaugh:

FIGURA # 4.16

Se puede deducir rapidamente que los implicantes primos esenciales son los formados por los mintérminos

agrupados por "a" y "b" , es decir " ". En cambio, el mintérmino que ocupa la celda "1", indicado por "R", produce dos implicantes primos redundantes que son " ", por lo tanto, cualquiera de los dos que se escoja produce el mismo efecto; se les denomina también implicantes primos no esenciales.



En consecuencia, del mapa de Karnaugh anterior se producen dos funciones óptimas, de las cuales, se seleciona aquella que económicamente sea la mas indicada desde el punto de vista de cantidad de compuertas a utilizar, chip's y entradas negadas. Las funciones son:

EJEMPLO # 4.8. Dada la siguiente función obtenga la expresión mínima.

f=Σ m(1,2,3,4,5,6,10,11,12,13) RESPUESTA:

FIGURA # 4.17.

Implicantes primos esenciales:

Implicantes primos no esenciales: a).- Mintérmino 2:

b).- Mintérmino 6:

Por lo tanto, se obtienen las siguientes expresiones óptimas, de las cuales se puede escoger una para construir el circuito:



EJERCICIO # 4.4. Obtener las soluciones óptimas de las funciones propuestas por los literales "a,b, y d" de los ejercicios # 4.3. .

4.1.6.-FUNCIONES INCOMPLETAMENTE

ESPECIFICADAS. Este tipo de funciones son aquellas que durante su construcción o en su enunciado, no se consideraron o no fueron necesarios, algunos parámatros o alternativas. Por ejemplo, que se desearan detectar los números pares del código BCD presente en cuatro líneas; en consecuencia, los números binarios que van desde el 102 al 152 nunca van a ocurrir, y por lo tanto, estos "no importan" que sean ceros o unos al graficarse en el mapa "k". El término "no importa" es muy utilizado; y aún mas, su procedencia anglosajona: "don't care"; y se acostumbra comunmente a denotarlo en el mapa o en la función con una "d" o una equis "x". EJEMPLO # 4.9. Encuentre una expresión óptima para la función dada a continuación:

f (a,b,c,d)=Σ m(0,2,4,6,7,8)+Σ d(11,12,13,14,15) RESPUESTA: Construcción del mapa de Karnaugh y solución en la figura # 18.



FIGURA # 4.18.

Note que los "don't care" ubicados en las celdas 11 y 15 no se tomaron en consideración. Para efecto de minimizar la función, se toman aquellos que solo convienen. EJERCICIOS # 4.5. Obtener la expresión óptima de las funciones que se dan a continuación: a).- f (v,w,x,y)=Σ m(2,3,4,7,8,9,12,) +Σ d(0,5,13,14,15) b).- f(a,b,c,d) =Σ m(0,1,2,5,6,7,8)+Σ d(10,12,13,15).

4.1.7.-SIMPLIFICACION DE FUNCIONES DADAS EN MAXTERMINOS. Algunas veces es necesario simplificar funciones dadas en maxtérminos, o visto desde otro ángulo, se desea obtener una mínima expresión como producto de sumas. Para lograr lo antes mencionado, a través de mapas de Karnaugh, se recurre a la regla algebraica booleana " " , es decir, que una variable que realiza un producto por su complemento da cero como resultado : "0 . 1= 0". A continuación se un ejemplo para detallar de forma explicita el procedimiento. EJEMPLO # 4.10. Se desea simplificar la siguiente función y obtener el resultado como producto de suma:

f (a,b,c,d)=Π M(0,1,2,4,5,67,8,11,14,15) El procedimiento es el siguiente:



a.- Se llevan los maxtérminos al mapa de Karnaugh. Recuerdese que la función dada en maxtérminos da como resultado cero (0), para cada lugar señalado. Figura # 4.19.



FIGURA # 4.19.

b.- La ecuación óptima dada como productos de suma se extrae de los ceros agrupados en las celdas adyacentes. De allí se procede a formular la ecuación. Cabe destacar que cuando la variable que sea constante tenga valor de cero en el mapa, se coloca sin negar en la ecuación; y, cuando tenga como valor uno (1) se coloca negada. Por ejemplo, los maxtérminos ubicados en las celdas adyacentes "0,1,4 y 5", da como resultado la suma siguiente: . De la misma manera se hacen para los demás maxtérminos, dando como resultado la expresión:

4.1.8.- FUNCIONES DE CINCO Y MAS

VARIABLES. A la hora de realizar, manualmente por medio de mapas, la simplificación de funciones de mas de seis variables se hace tedioso y no se obtienen soluciones óptimas adecuadas; por lo tanto, para ello se recurre a métodos que puedan ser usados en computadoras. Sin embargo, para cinco y seis variables aún se pueden obtener soluciones, que pudiesen acercarse a la mejor, como se verá en los siguientes ejemplos:



EJEMPLO 4.10. Obtener la expresión booleana mínima para la siguiente función:

f(v,w,x,y,z)=Σm(1,2,3,6,7,8,9,12,13,15,16,17,18,24,25,28,29,30,31)

La solución es: figura # 4.20.

FIGURA # 4.20.

Las expresiones booleanas óptimas vienen dadas por aquellas que salen de los unos encerrados en el mapa de Karnauhg, por los contornos cerrados demarcados por letras. Los cuales son:

Por lo que resulta la expresión:

EJEMPLO # 4.12. Dada la siguiente función espresada en mintérminos, encontrar la función mínima como suma de productos.

F(a,b,c,d,e,f)=Σm(2,3,6,7,10,14,18,19,22,23,27,37,42,43,45,46)

La solución es la siguiente: figura # 4.21.



FIGURA # 4.21.

Los implicantes primos:

La ecuación óptima:

EJERCICIOS 4.6. 4.6.1.- Determine las soluciones mínimas de las siguientes funciones: a).- F(A,B,C,D)=Σ m(0,4,6,10,11,13) b).- F (w,x,y,z)=Σ m(3,4,5,7,11,12,14,15) c).- F (w,x,y,z)=Π M(3,4,5,7,11,12,14,15) d).- F(a,b,c,d,e)=Σ m(0,2,3,4,5,11,12,15,18,19,24,28,29,31)



4.6.2.- Determine las soluciones óptimas de las siguientes funciones a).- F(w,x,y,z)=m(1,2,3,5,8,9,11,15)+Σ d(0,4,12,14) b).-F(a,b,c,d,e)=Σm(0,2,3,4,11,18,19,20,21,23,28,29)+Σd(1,5,12,15) c).-F(u,v,w,x,y,z)=Σm(14,18,21,25,32,34,49,52,53,62)+

Σd(0,2,6,9,27,41,55,57,61) 4.6.3.- Se desea diseñar un circuito de cinco bit's de entradas y una salida. La salida será uno, si y solo si, se recibe un número en binario que en su equivalente decimal sea primo. Obtenga una espresión mínima que sea útil para realizar el circuito.

4.6.4.- El eje de un motor paso a paso, utilizado para mover un mecanismo de un robot, gira en posiciones de treinta grado; utilizando código grey reflejado, se codificaron cada unos de los pasos como indica la figura # 4.22. Las combinaciones faltantes se suponen que nunca ocurren. Diseñe un circuito, utilizando soluciones mínimas de sumas de producto, que sea capaz de detectar cuando el eje del motor se encuentre en el primer cuadrante.

FIGURA # 4.22.



4.2.- METODO DE QUINE-MCKLUSKEY. El método de mapa de Karnaugh, es una forma efectiva de simplificar funciones lógicas que posean pocas variables. Cuando la cantidad de variable es muy grande, o si muchas funciones deben ser simplificadas, se desea el uso de una computadora. El método de Quine Mckluskey provee un procedimiento sistemático que se puede implementar a través de un programa a través de un computador. El método de Quine-McKluskey reduce la expansión dada en mintérminos (suma de productos) de una función para obtener la mínima expresión. El procedimiento consiste en dos pasos fundamentales, que son:

a.- Eliminar tanto literales (variables) como sea posible de cada término, al aplicar sistemáticamente el teorema " " .Del resultado se obtiene un implicante primo.

b.- El uso de una tabla de implicación para seleccionar una mínima cantidad de implicantes primos, los cuales al ser clasificados tanto esenciales como los redundantes, vienen a conformar la ecuación simplificada.

4.2.1.- REGLAS DEL METODO QUINE MCKLUSKEY.

Para determinar la expresión mínima por este método, la función debe estar dada como suma de productos, de no ser así, hay que transformarla a esta forma por cualquiera de los procedimientos conocidos. Comos se debe aplicar la notación Booleana: " "; donde "A", representa un conjunto de un producto de variables, y "B" una sola . Se desprende, por lo tanto, que se agrupan mintérminos cuya combinación difiere en una sola variable, es decir, que posean una distancia igual a uno (d=1). Como ejemplo, se demostrará con dos mintérminos de cuatro variables (a,b,c y d), dados a continuación, con la finalidad de visualizar la regla. Sean los mintérminos "m11" y "m10" de una función de cuatro variables, donde: m11 se puede expresar como " "; y m10 como " " , sustituyendo en la notación Booleana con su respectiva equivalencia binaria, se tiene:



De manera que para simplificar una función por el método de Quine McKluskey, se siguen los siguientes pasos:

a).- Se construye una columna (columna de implicación) , con los mintérminos de la función a simplificar colocados en forma binaria, agrupados de acuerdo a la cantidad de unos que contengan. Por ejemplo, sea la función:

f(a,b,c,d)=Σm(0,1,3,4,5,7,8,9,10,14,15) Como "m0" no posee unos (0000), se agrupa en la posición cero; el "m1" y " m4" se ubican en el grupo 1 por poseer solo un "1",(0001, 0100), etc. Como se observa en la figura dada a continuación.

FIGURA # 4.22.

b).- Ahora se combinan cada grupo con el consiguiente, y se elimina el lugar de la variable donde existe la diferencia binaria ( distancia de uno). Por ejemplo: el grupo cero (0000), se puede combinar con cualquier mintérmino del grupo uno, no así, con los del grupo 2 debido a que existe una distancia mayor que



uno; entonces al combinar cero (0000) con uno (0001) da como resultado como (000-), de igual manera se procede para las demas combinaciones, como se observa en la columna II dada n la figura # 4.23.

FIGURA # 4.23.

El símbolo colocado al lado derecho de la columna uno, es indicativo de que ese número, en particular, ha sido combinado; de igual manera hay que hacerlo para los demás, pero no para aquellos que en cuyo caso la combinación no se de. Cuando esto último sucede, se dice que estamos en presencia de un implicante primo y se señala con otro simbolo (en nuestro caso un asterísco " *"). Luego, con la columna II se construye la columna III, procediendo de la misma manera como se ha venido haciendo en los pasos anteriores. Figura # 4.24.



FIGURA # 4.24

. Se puede observar que las combinaciones de la columna III y las de la columna II que poseen asterísco no originan una nueva, significa esto por lo tanto, que son implicantes primos

c).- Se procede a determinar la forma en que vienen dado literalmente los implicantes primos. En la columna III , se observa que algunas combinaciones se repiten, por lo que se puede resumir de la siguiente forma: figura # 4.25.

FIGURA # 4.25.

Se crea una columna IV, donde se agrupen todos los implicantes primos. Figura # 4.26.



FIGURA # 4.26.

d).- Se construye una tabla de implicación. Esta tabla consiste en un arreglo de filas y columnas.Las columnas vienen a representar los mintérminos de la función a simplificar, y las filas , los implicantes primos encontrados en los pasos anteriores. Cada celda formada por filas (implicantes primos) y columna (mintérminos), se llenan con una equis (x) con el objeto de identificar los mintérminos que formaron el implicante primo resultante. Figura # 4.27.

FIGURA # 4.27.

Note que existen columnas que están ocupadas por una sola "x", y ha sido encerrada por un círculo; esto significa, que el implicante primo que representa esa fila es esencial. Por lo tanto, se deduce que se poseen los siguientes implicantes primos esenciales:



Los implicantes primos no esenciales son:

Para escoger entre los implicantes primos no esenciales , en términos económicos, se crea otra tabla de implicación , y se señala las equis "x" que no han sido cubiertas por implicantes primos escenciales.Figura # 4.28.

FIGURA # 4.28.

Se puede escojer a "a b c " ó "b c d" . Si se selecciona a " a b c" el siguiente grupo económico a seleccionar es " ", porque de tomarse a " ", implica una negación adicional en " ". Aunque a la hora de realizar un diseño práctico, si no influye en gran medida, cualquiera de las decisiones a tomar es buena. Una vez obtenidos los implicantes primos se construye la ecuación:

EJEMPLO # 4.13. Optimizar la siguiente función dada en mintérminos por el método de Quine McKluskey. f(w,v,x,y,z)=Σm(0,1,3,8,9,11,15,16,17,19,24,25,29,30,31)

a.- Se agrupan los mintérminos en una columna I, ordenados de acuerdo a la cantidad de unos que posean en binario.Figura # 4.29.



FIGURA # 4.29.

b.- Se construye una columna II, a aprtir de un grupo superior de mintérminos con uno inferior. Figura # 4.30.

FIGURA # 4.30.

c.- Ahora combinando las filas, de la misma forma como se hizo anteriormente, de cada subgrupo de la columna II, surge una columna III. Figura # 4.31.



FIGURA # 4.31.

En la figura # 4.31, se puede observar que al combinar las filas de la columna III, resulta una columna IV, donde se eliminan las variables "w,v e y". Al mismo tiempo se muestran los implicantes primos con un asterisco, que son aquellas filas (mintérminos) que no tuvieron mas combinación. d.- A continuación se procede a determinar como viene formado cada implicante primo, para ello se usa una columna adicional, columna V.Figura # 4.32.

FIGURA # 4.32.



e.- Luego, los implicantes primos encontrados se llevan a una tabla de implicación como muestra la figura # 4.33, con el fín de encontrar los implicantes primos esenciales.

FIGURA # 4.33.

Los implicantes primos esenciales son aquellos que poseen mintérminos encerrados en un círculo en la tabla de implicación; en nuestro caso " ". En esta ocación se dice que están libres; y, además, son utilizados para "cubrir" los mintérminos de los otros implicantes primos no esenciales con la finalidad de eliminar a estos últimos.

f.- Se crea una nueva tabla de implicación con el objeto de escoger los implicantes primos no esenciales para obtener una función mas óptima. Figura # 4.34.

FIGURA # 4.34.

En la figura anterior se puede determinar facilmante, que los implicantes primos no esenciales mas económicos son:" ". Por lo tanto, agrupando los implicantes primos no esenciales y esenciales se obtiene la siguiente función óptima:



EJERCICIOS 4.7. Minimizar las siguientes funciones, dadas en mintérminos por el método Quine McKluskey. a).- f(a,b,c,d)= Σm(0,1,2,5,7,8,9,10,14) b).- f(x,y,z)=Σm(0,1,2,5,6,7) 4.2.2.-QUINE MCKLUSKEY Y FUNCIONES INCOMPLETAMENTE ESPECIFICADAS.

El procedimiento viene a ser el mismo, con la diferencia que se considera la situiación de "no importa" (don't care) como si fuese otro mintérmino mas; solo que se han de tomar en cuenta aquellos que sirvan para eliminar una variable y de esta manera determinar un implicante primo. A la hora de construir la tabla de implicación, no se colocan los don't care para crear las columnas, solo se colocan los mitérminos de la función. Sea el siguiente ejemplo:



EJEMPLO # 4.14. Determine la solución mínima de la siguiente función:

f(a,b,c,d)=Σm(2,8,11,15) + Σd(1,10,12,13). a.- Se agrupan los mintérminos y los don't care en una columna I, y se ordenan según la cantidad de unos que posean. Figura # 4.35.

FIGURA # 4.35.

b.- Construcción de la columna II, con las posibles combinaciones de la columna I.Figura # 4.36.

FIGURA # 4.36.

En la figura # 4.36, se ha representado nuevamente la columna I con la finalidad de hacer notar, por medio del símbolo colocado a la derecha, cuáles son lo números binarios ( mintérminos y don't care) tomados en consideración con la finalidad de hacer la minimización. En este caso, como se puede constatar en la figura, no se considera el uno (12), debido a que es un don't care y no tiene sentido combinarlo con un mintérmino u otro don't care, debido a que en vez de optimizar se estaría creando otro implicante adicional. La combinación "12,13",



aunque son don't care se hace debido a que existe la posibilidad de que la misma sea útil para minimizar aún mas otro mintérmino. c.- Se trata de formar otra columna con nuevas combinaciones, sin embargo, se observa que es imposible realizarlas; en consecuencia, se procede a la construción de una columna III para señalar los implicantes primos que va a contener la solución óptima. Figura # 4.37.

FIGURA # 4.37.

d.- Ahora se construye la tabla de implicación. Observe, que solo se colocan los mintérminos en la formación de las columnas.

FIGURA # 4.38.



EJERCICIOS 4.8 4.8.1.- Optimizar las siguientes funciones por el método de Quine McKluskey: a.- f(A,B,C,D)=Σm(0,1,4,6,78,9,10,13,14) b.- f(a,b,c,d,e,f)=Σm(0,2,4,5,7,8,16,18,24,32,36) c.- f(w,x,y,z)=Σm(0,1,3,5,7,8,10,14,15) d.- f(V,W,X,Y,Z)=ΠM(0,1,2,3,6,7,8,9,10,11,14,15,16,17,20,21,22,23,25)

4.8.2.- Encontrar las soluciones óptimas de las siguientes funciones incompletamente especificadas por el método Quine McKluskey. a.- f(a,b,c,d)=Σm(1,3,4,5,6,7,10,12,13)+Σd(2,9,15) b.- f(w,x,y,z)=Σm(2,3,4,7,9,11,12,13,14)+Σd(1,10,15) c.- f(v,w,x,y)=Σm(1,4,8,913,14,15)+Σd(2,3,11,12) d.- f(a,b,c,d,e,f)=Σm(0,2,4,7,8,16,24,32,36,40,48)+Σd(5,18,22,23,54,56) e.- f(A,B,C,D,E)=Σm(0,2,3,6,9,15,16,18,20,23,26)+ +Σd(1,4,10,17,19,25,31).

4.3.- FUNCIONES DE SALIDAS MULTIPLES. A la hora de construir redes de salidas múltiples, se hace necesario adoptar un criterio técnico de optimización con la finalidad de minimizar la cantidad de compuertas a utilizar. Lo dicho anteriormente, se debe, a que ninguna de las técnicas que se mencionan a continuación garantiza que sea mejor que otra, en función de los costos o cantidad de compuertas a utilizar; pués, algunas veces puede resultar mas costoso concebir un circuito al implementarse con una técnica mas sistemática que otra mas directa; como por ejemplo, la de optimizar cada función individualmente. Los métodos de optimización de redes de salidas múltiple que se describen a continuación son los siguientes: El método directo, el de mapas de Karnaugh y uno mixto (karnaugh-Quine McKluskey).

4.3.1.- METODO DIRECTO.

Este método consiste en optimizar cada una de las funciones que componen el circuito por separado; luego, se observan si existen compuertas comunes; o, aplicando leyes



booleanas se construyen compuertas comunes sin modificar ninguna función.



EJEMPLO 4.15. Las siguientes funciones pertenecen a una red de salida múltiple. Construya en circuito mas económico.

f1(a,b,c)= Σm(0,1,3,5) f2(a,b,c)= Σm(2,3,5,6) f3(a,b,c)= Σm(0,1,6)

a.- Se minimiza cada una de las funciones por separado con mapas de Karnaugh. Figura # 4.39.

FIGURA # 4.39.

Donde:

b.- Cada una de las funciones tiene términos comunes con respecto a la otra, " " es común en f1 y f3. El término " " es común en f1, f2. Por último, " " es común en f1 con f2.



c.- El circuito queda de la forma siguiente:

FIGURA # 4.40.

Como se pude observar, se requieren dos chip de compuertas AND de dos entradas y un chip de compuertas OR de dos entradas. (Ver anexos II)

EJEMPLO 4.16. Sean las siguientes funciones que pertenecen a una sola red: f1(A,B,C,D)=Σm(11,12,13,14,15); f2(A,B,C,D)=Σm(3,7,11,12,13,15); f3(A,B,C,D)=Σm(3,7,12,13,14,15).

a.- Mapas de Karnaugh: Figura # 4.41.

FIGURA # 4.41.



b.- Si se construye el circuito, tal y como viene determinado por las funciones:

FIGURA # 4.42.

Se utilizarían 4 chip distribuidos de la siguiente forma: Dos compuertas AND de dos entradas (un chip). Tres compuertas AND de tres entradas (dos chip). Tres compuertas OR de dos entradas (un chip). Total ocho compuertas.

c.- En cambio si se buscan términos comunes, como se muestra seguidamente, el circuito quedaría como el de la figura # 4.43.



FIGURA # 4.43.

Se tiene un total de cinco compuertas AND de dos entradas, y tres compuertas OR de dos entradas, por lo que se necesitarían tres chip; lo cual significa que este cicuito es mas económico que el anterior, aunque se sub utlicen tres compuertas AND. Sin embargo, si las compuertas AND de tres entradas de la figura # 4.42 se sustituyen por las de dos entradas, el cicuito se reduce a tres chip; y, aunque existen mayor números de compuertas, se tendría el mismo costo que el circuito de la figura # 4.43. d.- Otro método de simplificación es aplicando la propiedad Booleana " ". Para obtener la configuración circuital, por ejemplo, sustituiremos a "A C D" de f1 de la forma: "CD= X" y "A=Y", y " " de f3 por " " ,lo cual se tiene: " "; como la expresión resultante está contenida en f2, también se puede susituir en esta función. El circuito queda como se muestra en la figura # 4.44.



FIGURA # 4.44.

Se utilizarían por lo tanto, dos compuertas AND de dos entradas (un chip); dos compuertas AND de tres entradas (un chip) y cuatro compuertas OR de dos entradas (un chip). Total tres chip's.

EJERCICIO 4.13. Encontrar el circuito mas económico dadas las siguientes funciones de una red de salida multiple. F1(a,b,c,d)= Σm(0,1,2,3,6,7). F2(a,b,c,d)=Σm(0,1,6,7,14,15). F3(a,b,c,d)=Σm(0,1,2,3,8,9).

4.3.2.- METODO DEL MAPA DE KARNAUGH. Esta es otra forma visual de simplificación de redes de salidas múltiples, que se aprovecha del método gráfico para obtener resultados óptimos. El procedimiento consiste en seleccionar los términos comunes entre un mapa de una función y otra, sin considerar la optimización de una función en específico, para luego llevarlo a su forma circuital.

EJEMPLO 4.17. Encontrar la red económicamente óptima, dada las siguientes funciones para la cual está diseñada. F1(a,b,c,d)=Σm(11,12,13,14,15); F2(a,b,c,d)=Σm(3,7,11,12,13,15);



F3(a,b,c,d)=Σm(3,7,12,13,14,15). a.- Se buscan los términos comunes en mapas de karnaugh. Se grafican individualmente cada función y se comparan entre sí. Figura # 4.45. f1 f2 f3

FIGURA # 4.45.

b.- Se obtienen las siguientes ecuaciones:

c.- El circuito queda de la forma:Figura # 4.46.

FIGURA # 4.46.



EJERCICIO 4.10 Encontrar el circuito óptimo de la red que realiza las siguientes funciones: f1(w,x,y,z)=Sm(4,5,10,11,12); f2(w,x,y,z)=Sm(0,1,3,4,8,11); f3(w,x,y,z)=Sm(0,4,10,12,14). NOTA: Se pueden encontrar mas de un circuito óptimo.

4.3.3.- METODO MIXTO. QUINE MCKLUSKEY- MAPAS DE KARNAUGH Este procedimiento garantiza una solución óptima a través de un método sistemático. Aquí se combina el uso de mapas de Karnaugh y las tablas de implicación de Quine McKluskey. El procedimiento se describirá paso a paso con el siguiente ejemplo.

EJEMPLO # 4.18. Dadas las siguientes funciones deducidas para diseñr una red combinacional de varias salidas, obtener el circuito óptimo: f1(a,b,c,d)=Σm(11,12,13,14,15); f2(a,b,c,d)=Σm(3,7,11,12,13,15); f3(a,b,c,d)=Σm(3,7,12,13,14,15). a.- Se grafican independientemente cada función. Figura # 4.47.

FIGURA # 4.47.



b.- Se multiplican mutuamente cada función, es decir, se realizan intersecciones entre sí, combinando una con otra, y luego entre todas, por ejemplo, f1 con f2 dando f12, f1 con f3 (f1,3), f2 con f3 (f2,3); y, f1 con f2 y f3(f1,2,3). Figura # 4.48.

FIGURA # 4.48.

c.- Se agrupan los términos adyacentes de cada gráfico, empezando por f123; luego con f23, f13, f12; para terminar con f3, f2, f1. Los términos que ya han sido agrupados en un gráfico anterior, no se toman en cuenta en el gráfico que le sigue. Figura # 4.49.



FIGURA # 4.49.

d.- Se crea una tabla para agrupar los implicantes primos de acuerdo a la función, o a la intersección de funciones que la han generado, y a los mismos, se le asigna una prioridad desde un punto de vista económico.Figura # 4.50.



FIGURA # 4.50.

e.- Se llevan los implicantes primos a una tabla de implicación, donde estén involucrados todos los mintérminos de las funciones. Los implicantes primos se colocan en orden de acuerdo a su costo. Figura # 4.51.

FIGURA # 4.51.

Implicantes primos esenciales:

f13 con m(12,13,14,15) : " " f12 con m(11,15) : " " f23 con m(3,7) : " "

f123 con m(12,13) : " " f.- Debido a que no existen implicantes primos no esenciales las ecuaciones quedan de la forma:



f1 = f13+ f12+ f123; f2= f12 + f23 + f123; f3 = f13 + f23 + f123;

Es decir, f1(a,b,c,d)= a b + a c d + ; f2(a,b,c,d)= a c d + + ; f3(a,b,c,d)= a b + a c d + .

g.- Por último el la red óptima. Figura # 4.52.

FIGURA # 4.52.

EJEMPLO # 4.18. Dadas las siguientes funciones de una red de múltiples salidas, obtener su circuito óptimo. f1(a,b,c,d) = Σm(2,4,10,11,12,13,); f2(a,b,c,d) =Σm(4,5,10,11,13); f3(a,b,c,d)= Σm(1,2,3,10,11,12). a.- Se grafican independientemente cada función en su respectivo mapa de Karnaugh.Figura # 4.53.

FIGURA # 4.53.



b.- Se multiplica graficamente cada función entre sí y entre todas. figura # 4.54.

FIGURA # 4.54.

c.- Se agrupan los términos adyacentes, siguiendo el orden señalado en el ejemplo anterior (ejemplo 4.17), para encontrar los implicantes primos.Figura # 4.55.



FIGURA # 4.55.

d.- Se construye una tabla para clasificar los implicantes primos de acuerdo a su prioridad económica. Figura # 4.56.

FIGURA # 4.56.

e.- Se llevan los implicantes primos encontrados a una tabla de implicación. Se colocan según la clasificación anterior.



Figura # 4.57.

FIGURA # 4.57.

Implicantes primos esenciales: f123 : m(10,11);

f3: m(1,3); f13: m(2,10);

f13: m(12)

f.- Como existen implicantes primos no esenciales, se crea otra tabla de implicación. Figura # 4.58.

FIGURA # 4.58.

La letra "e" , significa que ese implicante ya no es tomado en cuenta (eliminado), para construir el circuito.

g.- Se extraen las ecuaciones óptimas de cada función y se construye el circuito. Figura # 4.59.



El circuito que de la forma:

FIGURA # 4.59.

EJERCICIOS 4.11 Resolver: 4.11.1.- F1(a,b,c,d)=Σm(4,5,10,11,12) F2(a,b,c,d)=Σm(0,1,3,4,8,11) F3(a,b,c,d)=Σm(0,4,10,12,14) 4.11.2.- f1(w,x,y,z)=Σm(0,2,9,10)+Σd(1,8,13); f2(w.x.y.z)=Σm(1,3,5,13)+Σd(0,7,9); f3(w,x,y,z)=Σm(2,8,10,11,13)+Σd(3,9,15)



4.11.3.- F1(x,y,z)=Σm(0,1,3,5) F2(x,y,z)=Σm(2,3,5,6) F3(x,y,z)=Σm(0,1,6)



REFERENCIAS BIBLIOGRAFICAS.

4.1.- PETERSON, Gerald

HILL, Frederick . Teoría de Conmutación y Diseño Lógico. ED. LIMUSA MEXICO 1988. Pp. 121 - 128.

4.2.- ROHT, Charles Jr. Fundamentals Of Logic Design. WEST PUBLISHING Co. SECOND EDITION. U.S.A. 1979. Pp. 94 - 145 p.178.

4.3.- LASO DE LA CRUZ, Cesar René. Fundamentos De Diseño Digital. ED. TRILLAS S.A. MEXICO 1988. Pp. 50 - 61.

4.4.- HERBERT, Taub. Circuitos Digitales y Microprocesadores. Mc.GRAW HILL MEXICO 1983 Pp. 83-93.

4.5.- ANGULO UZCATEGUI, José María. Electrónica Digital Moderna. ED. PARANINFO S.A. ESPAÑA 1990. Pp. 83 - 93.

4.6.- MORRIS, Mano. Diseño Digital. PRENTICE HALL HISPANOAMERICANA S.A. MEXICO. 1987. Pp. 73 - 114.

4.7.- TOCCI, Ronald. Sistemas Digitales.



PRENTICE HALL HISPANOAMERICANA. S.A. MEXICO 1987. Pp. 87 - 117.

4.8.- HOERNES, Gerald. HEILWEIL, Melvin. Introduction to Boolean Algebra And Logic. A Program For Self Instruction. Mc. GRAW HILL U.S.A. 1964. Pp. 131 - 299.


Documents

Karna Ugh