Karna Ugh
Karna Ugh
Karna Ugh
4.1.1.-
METODO DE CONSTRUCCION.
Por ser un mtodo grfico de simplificacin, el mapa de Karnaugh, basa su procedimiento en agrupar aquellos mintrminos o mxterminos donde se cumpla la expresin Booleana , para los mintrminos; , para los maxtrminos. 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 vendra dado de la forma como la mostrada en la figura # 4.1.
FIGURA # 4.1.
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 especfico 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 lgicas 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 combinacin origina una celda, obteniendose as cuatro; numeradas como: 0,1,2 y3. Por lo tanto, si son tres variables se obtendrn ocho celdas; si son cuatro, 16 celdas, etc.
EJEMPLO 4.1.
A continucin se darn algunos ejemplo para tres variables, figura # 4.3; adems de algunas variantes en la construccin 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
"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 posicin 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.
FIGURA # 4.7. d.Las variables dependientes se ubican en la celda del valor, en decimal, indicado por el mintrmino o maxtrmino que lo conforman. El mintrmino llena la celda con "uno" y el maxtrmino con "cero".
EJEMPLO # 4.3
a.Representar las siguientes funciones en mapas de Karnaugh. F(X,Y,Z)= m (0.3, 5, 6)
FIGURA # 4.8.
FIGURA # 4.10.
EJERCICIO # 4.3.
Represente en su correspondiente mapa de Karnaugh las siguientes funciones: a).b).c).d).e).f).-
f(a,b,c)=m(0,1,4,6,7). f(x,y,v,z)=m(8,9,10,12,13,14,15). f(A,B,C,D)=M(0,1,2,8,9,10,12,13). f(a,b,c,d,e)= m(0,1,2,3,8,9,14,15,16,18,28,29,30). f= AB'C+ A'BC' + A'B'C + A B'C' f= (a +b +c)( a + b' +c')(a' +b' + c)
SIMPLIFICACION DE FUNCIONES.
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.-
Para optimizar una funcin dada como suma de producto (mintrminos), se pueden enumerar los siguientes pasos: a.Se vaca la funcin 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 automtica 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 funcin dada en mintrminos.
f(A,B,C)=
m(1,2,4,5,7)
a).Se representa la funcin 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 construccin 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 ); y en las celdas 4 y 5, se observa que la variable "C" varia ( 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 conclusin, la expresin ptima quedara de la forma:
FIGURA # 4.13.
EJEMPLO # 4.5.
Obtener la expresin mnima dada como suma de producto para la funcin que se da acontinuacin:
f(a,b,c,d)= m(0,2,3,5,6,7,8,10,11,14,15)
FIGURA # 4.14. Observese que los mintrminos agrupados en el entorno sealado 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 expresin mnima encontrada es:
EJEMPLO # 4.6.
obtener la mnima expresin de la funcin dada a continuacin:
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 funcin ptima viene dada, por lo tanto, por los implicantes primos sealados en la figura # 4.15 con los literales a,b,c y d; como se muestra a continuacin:
4.1.5.-
Debido a que el sistema de minimizacin en estudio es del tipo visual e instuitivo, en algunos casos, no se obtiene la funcin ptima mas idnea en una nica inspeccin que se le haga al mapa de Karnaugh, aunque el diseador sea muy experto. Pus, es posible que existan celdas que representan mintrminos que al agruparse de dos o mas formas puedan dar origen a mas de un implicante primo que cumplan la misma funcin. DEFINCION: Los implicantes primos que cumplen una misma funcin 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 funcin. 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 mintrminos agrupados por "a" y "b" , es decir " ". En cambio, el mintrmino 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 tambin implicantes primos no esenciales.
En consecuencia, del mapa de Karnaugh anterior se producen dos funciones ptimas, de las cuales, se seleciona aquella que econmicamente 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 funcin obtenga la expresin mnima. f= m(1,2,3,4,5,6,10,11,12,13) RESPUESTA:
FIGURA # 4.17. Implicantes primos esenciales: Implicantes primos no esenciales: a).Mintrmino 2: b).Mintrmino 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. .
EJEMPLO # 4.9.
Encuentre una expresin ptima para la funcin dada a continuacin: f (a,b,c,d)= m(0,2,4,6,7,8)+ d(11,12,13,14,15) RESPUESTA: Construccin del mapa de Karnaugh y solucin en la figura # 18.
FIGURA # 4.18. Note que los "don't care" ubicados en las celdas 11 y 15 no se tomaron en consideracin. Para efecto de minimizar la funcin, se toman aquellos que solo convienen.
EJERCICIOS # 4.5.
Obtener la expresin ptima de las funciones que se dan a continuacin: a).f (v,w,x,y)= m(2,3,4,7,8,9,12,) + d(0,5,13,14,15) b).-
EJEMPLO # 4.10.
Se desea simplificar la siguiente funcin 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 maxtrminos al mapa de Karnaugh. Recuerdese que la funcin dada en maxtrminos da como resultado cero (0), para cada lugar sealado. Figura # 4.19.
FIGURA # 4.19. b.La ecuacin ptima dada como productos de suma se extrae de los ceros agrupados en las celdas adyacentes. De all se procede a formular la ecuacin. Cabe destacar que cuando la variable que sea constante tenga valor de cero en el mapa, se coloca sin negar en la ecuacin; y, cuando tenga como valor uno (1) se coloca negada. Por ejemplo, los maxtrminos ubicados en las celdas adyacentes "0,1,4 y 5", da como resultado la suma siguiente: . De la misma manera se hacen para los dems maxtrminos, dando como resultado la expresin:
EJEMPLO 4.10.
Obtener la expresin booleana mnima para la siguiente funcin:
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 solucin 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:
EJEMPLO # 4.12.
Dada la siguiente funcin espresada en mintrminos, encontrar la funcin mnima 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 solucin es la siguiente: figura # 4.21.
La ecuacin ptima:
EJERCICIOS 4.6.
4.6.1.a).b).c).d).Determine las soluciones mnimas de las siguientes funciones: F(A,B,C,D)= m(0,4,6,10,11,13) F (w,x,y,z)= m(3,4,5,7,11,12,14,15) F (w,x,y,z)= M(3,4,5,7,11,12,14,15) 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 disear un circuito de cinco bit's de entradas y una salida. La salida ser uno, si y solo si, se recibe un nmero en binario que en su equivalente decimal sea primo. Obtenga una espresin mnima 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 cdigo grey reflejado, se codificaron cada unos de los pasos como indica la figura # 4.22. Las combinaciones faltantes se suponen que nunca ocurren. Disee un circuito, utilizando soluciones mnimas 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.1.REGLAS MCKLUSKEY.
DEL
METODO
QUINE
Para determinar la expresin mnima por este mtodo, la funcin 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 notacin Booleana: " "; donde "A", representa un conjunto de un producto de variables, y "B" una sola . Se desprende, por lo tanto, que se agrupan mintrminos cuya combinacin difiere en una sola variable, es decir, que posean una distancia igual a uno (d=1). Como ejemplo, se demostrar con dos mintrminos de cuatro variables (a,b,c y d), dados a continuacin, con la finalidad de visualizar la regla. Sean los mintrminos "m11" y "m10" de una funcin de cuatro variables, donde: m11 se puede expresar como " "; y m10 como " " , sustituyendo en la notacin Booleana con su respectiva equivalencia binaria, se tiene:
De manera que para simplificar una funcin por el mtodo de Quine McKluskey, se siguen los siguientes pasos: a).Se construye una columna (columna de implicacin) , con los mintrminos de la funcin a simplificar colocados en forma binaria, agrupados de acuerdo a la cantidad de unos que contengan. Por ejemplo, sea la funcin: 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 posicin 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 continuacin.
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 mintrmino 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 smbolo colocado al lado derecho de la columna uno, es indicativo de que ese nmero, en particular, ha sido combinado; de igual manera hay que hacerlo para los dems, pero no para aquellos que en cuyo caso la combinacin no se de. Cuando esto ltimo sucede, se dice que estamos en presencia de un implicante primo y se seala con otro simbolo (en nuestro caso un astersco " *"). 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 astersco 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 implicacin. Esta tabla consiste en un arreglo de filas y columnas.Las columnas vienen a representar los mintrminos de la funcin a simplificar, y las filas , los implicantes primos encontrados en los pasos anteriores. Cada celda formada por filas (implicantes primos) y columna (mintrminos), se llenan con una equis (x) con el objeto de identificar los mintrminos que formaron el implicante primo resultante. Figura # 4.27.
FIGURA # 4.27. Note que existen columnas que estn ocupadas por una sola "x", y ha sido encerrada por un crculo; 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 trminos econmicos, se crea otra tabla de implicacin , y se seala 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 econmico a seleccionar es " ", implica una negacin adicional ", porque de tomarse a " en " ". Aunque a la hora de realizar un diseo prctico, si no influye en gran medida, cualquiera de las decisiones a tomar es buena. Una vez obtenidos los implicantes primos se construye la ecuacin:
EJEMPLO # 4.13.
Optimizar la siguiente funcin dada en mintrminos por el mtodo 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 mintrminos 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 mintrminos 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 (mintrminos) que no tuvieron mas combinacin. d.A continuacin 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 implicacin como muestra la figura # 4.33, con el fn de encontrar los implicantes primos esenciales.
FIGURA # 4.33. Los implicantes primos esenciales son aquellos que poseen mintrminos encerrados en un crculo en la tabla de implicacin; en nuestro caso " ". En esta ocacin se dice que estn libres; y, adems, son utilizados para "cubrir" los mintrminos de los otros implicantes primos no esenciales con la finalidad de eliminar a estos ltimos. f.Se crea una nueva tabla de implicacin con el objeto de escoger los implicantes primos no esenciales para obtener una funcin mas ptima. Figura # 4.34.
FIGURA # 4.34. En la figura anterior se puede determinar facilmante, que los implicantes primos no esenciales mas econmicos son:" ". Por lo tanto, agrupando los implicantes primos no esenciales y esenciales se obtiene la siguiente funcin ptima:
EJERCICIOS 4.7.
Minimizar las siguientes funciones, dadas en mintrminos por el mtodo 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)
EJEMPLO # 4.14.
Determine la solucin mnima de la siguiente funcin:
f(a,b,c,d)=m(2,8,11,15) + d(1,10,12,13). a.Se agrupan los mintrminos y los don't care en una columna I, y se ordenan segn la cantidad de unos que posean. Figura # 4.35.
FIGURA # 4.35. b.Construccin 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 smbolo colocado a la derecha, cules son lo nmeros binarios ( mintrminos y don't care) tomados en consideracin con la finalidad de hacer la minimizacin. 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 mintrmino u otro don't care, debido a que en vez de optimizar se estara creando otro implicante adicional. La combinacin "12,13",
aunque son don't care se hace debido a que existe la posibilidad de que la misma sea til para minimizar an mas otro mintrmino. c.Se trata de formar otra columna con nuevas combinaciones, sin embargo, se observa que es imposible realizarlas; en consecuencia, se procede a la construcin de una columna III para sealar los implicantes primos que va a contener la solucin ptima. Figura # 4.37.
FIGURA # 4.37. d.Ahora se construye la tabla de implicacin. Observe, que solo se colocan los mintrminos en la formacin de las columnas.
FIGURA # 4.38.
EJERCICIOS 4.8
4.8.1.- Optimizar las siguientes funciones por el mtodo de Quine McKluskey: f(A,B,C,D)=m(0,1,4,6,78,9,10,13,14) a.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 mtodo 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,5 6) 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.1.-
METODO DIRECTO.
Este mtodo consiste en optimizar cada una de las funciones que componen el circuito por separado; luego, se observan si existen compuertas comunes; o, aplicando leyes
EJEMPLO 4.15.
Las siguientes funciones pertenecen a una red de salida mltiple. Construya en circuito mas econmico. 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.
b.-
Cada una de las funciones tiene trminos comunes con " es comn en f1 y f3. El trmino " " es comn en f1 con f2. "
c.-
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:
FIGURA # 4.41.
b.Si se construye el circuito, tal y como viene determinado por las funciones:
FIGURA # 4.42. Se utilizaran 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 trminos comunes, como se muestra seguidamente, el circuito quedara 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 necesitaran tres chip; lo cual significa que este cicuito es mas econmico 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 nmeros de compuertas, se tendra el mismo costo que el circuito de la figura # 4.43. d.Otro mtodo de simplificacin es aplicando la propiedad Booleana " ". Para obtener la configuracin circuital, por ejemplo, sustituiremos a "A C D" de f1 de la forma: "CD= X" y "A=Y", y " " de f3 por " " ,lo "; como la expresin resultante cual se tiene: " est contenida en f2, tambin se puede susituir en esta funcin. El circuito queda como se muestra en la figura # 4.44.
FIGURA # 4.44. Se utilizaran 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 econmico 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.-
EJEMPLO 4.17.
Encontrar la red econmicamente ptima, dada las siguientes funciones para la cual est diseada. 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 trminos comunes en mapas de karnaugh. Se grafican individualmente cada funcin y se comparan entre s. Figura # 4.45. f1 f2 f3
b.-
c.-
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.
EJEMPLO # 4.18.
Dadas las siguientes funciones deducidas para diser 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 funcin. Figura # 4.47.
FIGURA # 4.47.
b.Se multiplican mutuamente cada funcin, 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 trminos adyacentes de cada grfico, empezando por f123; luego con f23, f13, f12; para terminar con f3, f2, f1. Los trminos que ya han sido agrupados en un grfico anterior, no se toman en cuenta en el grfico que le sigue. Figura # 4.49.
FIGURA # 4.49. d.Se crea una tabla para agrupar los implicantes primos de acuerdo a la funcin, o a la interseccin de funciones que la han generado, y a los mismos, se le asigna una prioridad desde un punto de vista econmico.Figura # 4.50.
FIGURA # 4.50. e.Se llevan los implicantes primos a una tabla de implicacin, donde estn involucrados todos los mintrminos 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.; ; .
FIGURA # 4.52.
EJEMPLO # 4.18.
Dadas las siguientes funciones de una red de mltiples 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 funcin en su respectivo mapa de Karnaugh.Figura # 4.53.
FIGURA # 4.53.
b.Se multiplica graficamente cada funcin entre s y entre todas. figura # 4.54.
FIGURA # 4.54. c.Se agrupan los trminos adyacentes, siguiendo el orden sealado 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 econmica. Figura # 4.56.
FIGURA # 4.56. e.Se llevan los implicantes primos encontrados a una tabla de implicacin. Se colocan segn la clasificacin 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 implicacin. 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 funcin y se construye el circuito. Figura # 4.59.
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)
REFERENCIAS BIBLIOGRAFICAS.
4.1.PETERSON, Gerald HILL, Frederick . Teora de Conmutacin y Diseo Lgico. ED. LIMUSA MEXICO 1988. Pp. 121 - 128. ROHT, Charles Jr. Fundamentals Of Logic Design. WEST PUBLISHING Co. SECOND EDITION. U.S.A. 1979. Pp. 94 - 145 p.178. LASO DE LA CRUZ, Cesar Ren. Fundamentos De Diseo Digital. ED. TRILLAS S.A. MEXICO 1988. Pp. 50 - 61. HERBERT, Taub. Circuitos Digitales y Microprocesadores. Mc.GRAW HILL MEXICO 1983 Pp. 83-93. ANGULO UZCATEGUI, Jos Mara. Electrnica Digital Moderna. ED. PARANINFO S.A. ESPAA 1990. Pp. 83 - 93. MORRIS, Mano. Diseo Digital. PRENTICE HALL HISPANOAMERICANA S.A. MEXICO. 1987. Pp. 73 - 114. TOCCI, Ronald. Sistemas Digitales.
4.2.-
4.3.-
4.4.-
4.5.-
4.6.-
4.7.-
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.