Lucio V. Velasco P. - Repositorio Digital EPN
Contents
1. m OO 0000000 O OOO m FUNCION IMPLEMENTADORA NUMERO B8 mmm mem 10 01 01 01 O1 01 10 00 10 00 00 10 01 10 01 00 00 10 01 01 10 00 01 00 10 01 10 00 00 10 01 z 10 00 10 00 10 10 00 00 FUNCION BOOLEANA A MINIMIZAR ESTA REPRESENTADA POR LA SUMA DE LOS SIGUIENTES PRODUCTOS 01 01 01 01 01 01 10 O1 01 01 10 10 01 10 01 10 01 10 10 01 10 01 01 01 10 0 1 10 10 LAS SIGUIENTES SON CONDICIONES INDEFINIDAS TABLA DE IMPLICANTES PRIMOS METODO DE MOTT 3 x lt RA ARE c SR EOF E E E FE LD R SE 1 kE kR 1113 5 E 1 113 1 127 0 10 01 10 10 10 01 10 01 O1 00 01 00 01 10 10 00 10 10 0 00 01 01 01 10 00 10 10 03 00 10 01 01 01 10 00 10 10 10 00 TABLA DE IMPLICANTES PRIMOS ESENCIALES o ade ate aie ako ote oe ao ole oko o Ff ae e doe ok olo obo o e 01 10 01 10 00 Ol ul t IMPLENENTADORA NUM NCION OOOO OOOO O O m O O mO 00 10 00 10 01 01 00 UNC2. NINO 30 0 11 1 A ASNIDVA B0 10 00 JA11 NOULLVIIGADO qv 101 9S 2 C Los resultados nos indican que no existen picantes primos elegibles y que por lo tanto la funci n est cubierta unica mente por los implicantes primos esenciales La salida 512 viene expresada en l gica combinada como 812 Ph Ph H H5M4 E Ph Ph H H Mo t S m 1 jPhjPh y en l gica NAND ser 19 t m 3 Realizaci n en l gica NAND del Ejemplo N 1 _ 75 EJEMPLO N 2 La Fig representa un Display de 7 elementos de un Decodi ficador Digital Anal gico En el van a representarse los n me ros 1 2 3 4 5 6 7 8 9 y O y las letras E error pr lleno y el simbolo negativo Representaci n Representaci n digital Sie 0 1 o 0 1 1 2 0 0 1 2 3 0 0 1 1 3 4 O uke O o 4 0 1 0 1 5 6 0 1 1 O 6 T 0 1 1 1 7 8 1 0 0 0 8 9 1 0 0 1 9 10 ks O Y O i 11 1 0 l l E 12 l 1 0 F 13 1 1 0 1 i indefinido 14 1 1 1 0 i indefinido 16 de GE i indefinido ud x De la tabla anterior en la que constan las relaciones d gito anal gicas del Decodificador en menci n obtenemos la Tabla de Verdad correspondiente a los si te elementos Entradas Salidas X1 X gt a b fc da Ze Z g 0 0 O 1 0 1 1 1 1 1 0 0 0 1 0 1 1 0 1 1 1 1 O 1 1 O 0 0 1 1 1 1 1 0 1 0 1 0 1 0 O O 1
3. XjX9X 10 10 00 01 fig 13 Con los datos de la fig 13 procedemos a determinar la mi nima expresi n de la funci n dada Para 0 los si 000 pasos 1 ds enia el conjunto de implicantes primos esenciales Esto se lleva a cabo separando un implicante primo del resto de implicantes y aplicando la siguiente regla El implicante primo separado es esencial si no es generado por aplicaci n del consensus iterado al resto de implicantes Repitiendo el procedimiento con todos y cada uno de los implicantes primos se obtiene el conjunto de implicantes primos esenciales Para aplicar este primer paso al ejemplo separemos el implicante x4x5X4 de la fig 13 y realicemos la operaci n de consensus con 56 implicantes x X x y x4x4X lo que nos da como re Sultado X XoX2 con lo que hemos generado el t rmino previa mente separado hecho que significa que ste no ds primo esencial Ahora separamos del grupo al t rmino x Xs y sobre el grupo restante aplicamos la operaci n de consensus esto solo es posible con xjx4x y X1 produci ndose el t rmino x1X5X4 esto os indica que el termino separado 65 esencial De igual manera encontramos que el t r mino X X X es un implicante primo esencial Veamos si los resultados anteriores son esperados mediante el m todo de Mott En la fig 14 consta la matriz de cubrimien to de la funci n del ejemplo es facil visu
4. 61 x x X1X5X4X La primera tarjeta de datos llevar a en la columna 1 y 2 01 la segunda tarjeta llevar a en las columnas 1 y 2 05 en las columnas 3 y 4 02 y en las columnas 5 y 6 02 La tarjeta N 3 llevar a desde la columna 1 1o siguiente 0101100001010010001001011010100110010110 La cuarta tarjeta llevar a a partir de la columna 1 lo siguien te 0010101010011001 El programa nos dar como resultado lo siguiente 1 Tabla de Implicantes Primos 2 Tabla de Implicantes Primos Esenciales 3 Un grupo de funciones que implementen a la funci n origi nal 0001 0002 0003 0004 0005 0006 0007 0008 0009 0010 0011 0012 0013 0014 0015 0016 0017 0018 0019 0020 0021 0022 0023 0024 0025 0026 0027 0028 0029 0030 0031 0032 0033 0034 0035 0036 0037 0038 0039 0040 0041 0042 0043 0044 0045 0046 0047 0048 0049 0050 0051 0052 0053 0054 0055 0056 0057 0058 nana 100 101 102 103 105 106 107 108 109 C 200 201 4 PROGRAMA PARA MINIMIZAR UNA FUNCION BOOLEANA POR EL METODO DE MOTT CONSENSUS DIMENSION KA 20 201 K 50 10 KB 20 20 IK 50 IBC20 2 DIMENSION KM 30 NK 30 DATA K1 K2 K3 K4 7 00 01 1 0 11 FORMAT 312 FORMAT 50A2 FORMAT 10X 3212 FORMAT 1 0 4 2 2 2X A2 2X A2 2X A2 2X A2 s2X A2 FORMAT C 2X TABLA DE INPLICANTES PRIMOS ESEN
5. NS om Ded i i i H lb ale 1 H 5 NOANA iJ N t T 1 Wt E le A 1 A Z E LO 00 HE i le Q 5 gt i le mM H O Om uz lt oy 2 1 Jy E Ku 1 VIUJ 1 In Hi j oca O Or Oo j 2 7 r1 9 1 6 m 2 ir a NL 1 Z nz 7 Alia m 5 Celo C l m 7 za 5 il FA 5 i o zi tn A EVE 1 l l H 105vw aNLIOO a mm et oce p min t us x k 135 JU VvUlOfl Hdd v 8 1 V M arme nus 2 C FUNCION A MINTATZAR POR EL METODO DE QUINE MACIIUSKF Y 1 0 o 0 0 TS Ne em 11 _0 E 3 0 0 1 1 4 0 1 0 ALD NE 5 0 1 1 0 ON E 0 0 7 1 0 1 1 LAS SIGUIENTES SON CONE INDEFINIDAS A E Z LP 8 1 1 0 Nay k vt CI 1 E 1 D 10 1 1 1 1 71 j 233 L a TABLA DE IMPLICANIFS PRIMOS MEMO ZA 1 0 xo 0 19 gt 0 0 3 0 0 1 e 4 0 1 0 E 5 0 1 l 1 0 1 7 lt I 1 o
6. Las dimensiones correspondientes a las matrices y a los vecto h res constan en el listado del programa EMPEZAR LEER EL NUMERO DE EJEMPLOS A SER PROCESADOS LEER EL NUMERO DE TERMINOS PRO DuCTO EL NUMERO DE CONDICIO NES INDEFINIDAS Y EL NUMERO DE VARIABLES LEER E IMPRIMIR LOS TERMINOS PRODUCTO Y ALMACENARLOS EN ny E ID 5 44 LEER E IMPRIMIR LAS CONDICIONES INDEFINIDAS Y ANADIRLAS EN K COMPARAR CADA TERMINO DE LA MATRIZ K SI ES POSIBLE APLICAR LA REDUCCION XY XY X A LOS NUEVOS TERMINOS ASI FORMADOS Y A LOS TERMINOS QUE NO HAN INTERVENIDO EN AL GUNA REDUCCION ALMACENARLOS EN LA MATRIZ KR OSIBLE ALGUNA REDUC CION EN EL PASO ANTE TRANSFERIR LOS DATOS DE LA MATRIZ KR A LA MATRIZ K IMPRIMIR DATOS DE LA MATRIZ KR EN TABLA DE IMPLICANTES PRI MOS DETERMINANDO CUALES TERMINOS DE LA MATRIZ KR CUBREN A LOS TERMINOS DE ID FOR MAR EN LA MATRIZ ICHOI LA TABLA DE SE LECCION DETERMINAR CUALES SON LOS IMPLICANTES PRI MOS ESENCIALES EN KR Y TRANSFERIRLOS A ET COMO IMPRIMIR LA MATRIZ Kk ITA BLA DE IMPLICANTES PRIMOS ESEN CIALES TRANSFERIR LOS TERMINOS NO ESENCIALES DE KR A KE LOS TERMINOS ASI REORDENA DOS TRANSFERIRLOS NUEVAMENTE A KR 46 FORMAR NUEVAMENTE LA TABLA DE SELEC
7. LEER E IMPRIMIR LAS CONDICIONES INDEFINIDAS Y ANADIRLAS EN K 56 REALIZAR LA EXPANSION CANONICA DE LA FUN CION LOS NUEVOS DATOS REDEFINEN A IB COMPARAR CADA TERMINO DE LA MATRIZ K CON LOS SUBSIGUIENTES Y ELIMINAR SI ES POSIBLE LOS TERMINOS CONTENIDOS EN OTROS SI POSIBLE ALGUNA ELIMI NACION EN EL PASO COMPARAR CADA TERMINO DE LA MATRIZ K CON CON LOS SUBSIGUIENTES Y ENCONTRAR SI EXIS TEN TERMINOS DE CONSENSUS A LOS QUE SE AL MACENARAN A CONTINUACION DE LOS ELEMENTOS PRIMITIVOS DE LA FUNCIUN EN LA MATRIZ ERMINO DE CONSENSUS EL PASO ANTERIOR IMPRIMIR LA MATRIZ K COMO TA BLA DE IMPLICANTES PRIMOS DETERMINAR CUALES TERMINOS DE K CUBREN A LOS TERMINOS DE IB FORMAR LA MATRIZ DE CUBRIMIENTO DE LA FUNCION _ DETERMINAR EN K LOS IMPLICANTES PRIMOS ESENCIALES IMPRIMIR LOS TERMINOS DE K CO RRESPONDIENTES A LOS IMPLICAN TES PRIMOS ESENCIALES 58 ORDENAR LA TABLA DE IMPLICANTES PRIMOS DE TAL FORMA QUE EN SU PARTE SUPERIOR SE SI TUEN LOS IMPLICANTES PRIMOS ESENCIALES ORDENAR LA MATRIZ DE CUBRIMIENTO DE TAL SUERTE QUE LOS ELEMENTOS CORRESPONDIENTES A LOS IMPLICANTES PRIMOS ESENCIALES SE SI TUEN EN SU PARTE SUPERIOR y SELECCIONAR UN GRUPO DE IMPLICANTES PRI MOS EL GR
8. 132 8 1 1 1 x a GP 19 B PE TASLA DE IMPLICANTES PRIMOSIESENCIADES 75 4 op is O ot u c i TABLA DE IMPLICANTES PRIMOS ELEGIBLES f m HO i E 5 TABLA REDUCIDA DE SELECCTON l LL B LL 5 de e 0 TIN O EE A A 7 0 2 0 0 1 0 3 0 1 1 0 4 1 0 0 0 PIT 5 A HUP EQ m ec PON rc MM M 6 1 1 0 0 LAS SIGUIENTES SON CONDICTONES INDEFINTDAS 1 amp AN TABLA DF IMPLICANTES PRIMNS miu ms um rm 7 mu ee mm smo mm me EET 1 0 k o i i 2 x 0 0 0 3 0 1 0 ET de 1 1 0 5 4 0 k e 6 1 x 1 1 7 1 1 TABLA DE TMPLICANTES PRIMOS FLFSIOLOST DE Eg 4 1 0 Q 0 2 6 0 0 4 1 1 0 5 1 2 Xx 0 SQ 6 1 1 LLL UID LL uABLA C RIEDUCIIA DESPRLECCI ON A 2 3 d o5 04 d ES D 5 Y 6 Es FUMCTON A MINIVTZAP POR
9. 10 10 10 O1 10 01 01 10 10 01 10 10 10 10 01 01 LAS SIGUIENTES SUN CONDICIONES INDEFINIDAS TABLA DE IMPLICANTES PRIMOS METODO DE 7 TIPP TP REA REA afe E 3 3k te a e ameo voja ae ansta ap RR RARA F de de E 10 01 01 01 Ev 017 00 01 Port 2162 01 OO 00 00 10 00 OO 10 10 00 00 TABLA DE IMPLICANTES PRIMOS ESENCIALES IDIOT aja a tee aka oke ote aka oka a e e ta de ok se aj ke kate 10 01 01 01 01 00 01 01 01 10 00 01 00 10 01 00 10 00 00 10 NCION TMPLEFENTADCRA NUMERO 1 10 01 00 Ol 01 10 00 i 00 10 01 00 10 00 00 10 10 01 01 01 01 00 01 01 1 01 10 0 0 01 00 10 01 00 10 00 00 10 10 10 00 00 EPN MSJ5 TIEMPO DE UCP UTILIZADO POR PROGRAMA LUCIO gt 96 CONCLUSIONES En el presente trabajo se han estudiado m todos d minimiza ci n de la Funci n Booleana y m todos de minimizaci n en L gi ca NAND De los primeros se han seleccionado para ser progra mados a los m s representativos el M todo Tabular o de Quine MacCluskey y el M todo de Moot basado en el Consensus Iterado En la parte de minimizaci n en L gica NAND se han estudiado dos m todos el M todo de Dietmeyer Su de realizaci n suma mente dif cil y engorrosa que no justifica su programaci n el M todo de Muro
10. B 1 1 1 9 1 1 ste 1 10 1 1 1 Cr T R A QUIPO LD E Ip IO TABLA 1 DE TYD TdCAWTESO ESENCIALE 1 2 1 0 1 2 0 0 0 TABLA DE IMPLICA TES DRIVAS FLEGIALFS _ I M c gi 2 0 0 1 3 0 o 1 0 1 4 x 0 1 1 HET 5 2 i ik kosto 1 met Ep 7 6 1 1 1 e n Y Y 2 3 4 7 CES ek sp 6 i FUNCION A MINIMIZAR POR EL METODN DE QUINE MACLUSKES 1 0 0 0 r 2 0 1 0 ss I O D 7 zii 392 LAS SIGUIENTES SON conf Taurs TNDEFIMIDAS troo 1 A Du a o 2 0 90 TABLA DE IMPLICANTES PRIMOS ESEN Si t 1 0 0 2 1 0 Z si A E 0 NS 0 2 4 1 1 2 1 0 0 0 0 2 0 9 0 1 3 3 aD on Oa z S LR 9 4 0 0 1 1 5 Q 1 6 0 1 1 1 7 x 1 0 0 0 E i a 1 0 0 1 9 1 1 0 A EE a NO I MESAS PEO Z em 11 1 1 1 1 A r UM SE P TR a S TABLA PE TMPLICANTES PRIMOS 1 0 0 o on 0 O 3 O 0 i 4 0 1 Y 5 1 1 1 O A x O Y o 7 1 1
11. En el paso 3 a los nuevos terminos resultantes del paso ante rior aplicamos el principio de reducci n hasta cuando no en contremos m s posibilidades de simplificaci n obteniendo en consecuencia el conjunto de implicantes primos de la funci n tratada En la tabla de la fig 5 se muestran los resultados de los pasos 2 y 3 en la primera columna se encuentra el 0 to original con las condiciones incluidas en la segunda los resultados de la primera reducci n y en la tercera columna la reducci n final Se ha cologado una marca V en aquellos ter minos que se han utilizado en alguna reducci n y por Jo tanto no constituyen implicantes primos Se ahn se alado com aquellos t rminos que no han tomado parte en una reducci n constituyendo en si implicantes primos Con la tabla de duplicantes primos obtenida en los pasos an teriores se proceder a determinar la minima expresi n de la 14 funci n original a ser minimizada PROCESO DE REDUCCION Y CALCULO DE IMPLICANTES PRIMOS PRIMERA SEGUNDA REDUCCION REDUCCION poo Zi Xj Xa ES 0 0 o OV 0 l OV 0 0 OV O 1 1 0 0 0V 0 0 1 V 1 1 0 0 1 l1yvV 0 1 1 1 0 12 0 17 de 0 OV 1 0 1 0 31 O 0 1 1 0 07 430 1 1 V 0 1 1 1vV 0 1 1V E 1 02 27 OL 1V 1 10 1v 1 0 1V 1 1 1 EY 1 0 1 7V l l 0 o 1 1 l 1 1 d l l 1v EUH 15 Para la determinac
12. En general estos requisitos se reducen al encuen tro de una m xima figura de merito Los autores presentan para la resoluci n del problema tres algoritmos y algunas sofisticaciones de los mismos El algo ritmo a usarse depende del problema y los tres pueden o no dar resultados diferentes El m todo es sumamente complejo y las subrutinas que los au tores dan como referencia estan compilados en una obre de di f cil consecuci n en nuestro Pa s Por estas razones y por el hecho de que el m todo solo es til cuando el n mero de varia bles es grande se ha desistido de una programaci n del mismo METODO DE MUROGA IBARAKI El m todo capaz de resolver problemas de minimizaci n tanto en L gica NAND NOR o L gica Combinada tiene como puento de partida un c digo de Programaci n Entera denominado ILLIP 39 Illinois Integer Programming Code y que 3 basado en la enumeraci n implicita consiste en la transformaci n del pro blema de minimizaci n a un problema de programaci n meat en tera y como tal es luego implementado y resuelto Al parecer este m todo es bastante versatil ya que puede resolver proble mas con Cualquier tipo de Este m todo no se program por d s razones 1 Como ya se anot anteriormente el m todo precisa de una codificaci n especial por 10 que se requiere de informa ci n adicional cuya consecuci n se lograr a en un tiempo no razonable 2
13. ciety 1968 Saburo Muroga Toshihide Ibaraki DESIGN OF OPTIMAL SWITCHING NETWORKS BY INTEGER PROGRAMING IEEE Tran sactions on Computers Vol C 21 N 6 Junio 1972 lt memoria para su realizaci n en efecto son mecesarios cator ce mil ochocientos bytes para este programa en comparaci n con los treinta y seis mil novecientos noventa y cuatro bytes requeridos por el M todo de Quine McCluskey es decir menos del 50 para resolver problemas de igual embergadura En el ejemplo N l es necesario una mayor capacidad de memoria debi do su particular magnitud En el Ejemplo n mero no el programa del m todo tabular uti liza 102 53 segundos para minimizar una funci n de cincuenta y nueve productos de los cuales cincuenta y seis son condicio nes indefinidas con siete variables En el Ejemplo No 2 el mismo programa emplea 55 68 segundos para minimizar siete fun ciones de cuatro variables En el Ejemplo N 3 el programa correspondiente al M todo de Mott utiliza 59 99 segundos en simplificar cuatro funciones de cuatro variables Estos tiempos han sido logrados por un computador I B M 370 125 en el cual ban sido corridos los programas 7 8 9 10 i 99 Daniel D McCracken PROGRAMACION FORTRAN IV Limusa Wiley 1967 IBM S A E Departamento de Traducciones y Ediciones IBM SISTEMA 360 Y SISTEMA 370 LENGUAJE FORTRAN IV In ternational Business Machines Co
14. 01 10 10 10 10 SUN CUNDICIUNLES TABLA DE IMPLICANTES PRIMGS k Sob e doloe E FOR kok kokon keto 16 01 01 01 01 01 10 00 0 160 01 00 00 10 01 Ol 01 10 00 01 00 10 01 10 00 00 10 01 10 00 00 10 10 00 10 00 10 10 00 00 METODO DE MOTT TABLA DE IMPLICANTES PRIMOS ESENCIALES OE e E 10 O1 0 01 01 01 10 0 0 10 00 00 10 INDEFINIDAS FUNCION IMPLEXYENTADORA 10 01 01 01 01 10 00 10 00 00 10 01 10 01 00 00 10 01 01 00 00 10 01 FUNCION IMPLEMENTADORA 10 01 01 01 01 01 10 00 10 00 00 10 01 10 01 00 00 10 01 01 01 10 00 01 00 00 10 01 FUNCION NPLENENTADGEA 10 01 01 01 01 01 10 00 10 00 00 10 01 10 01 00 00 10 01 01 01 10 00 01 10 00 10 00 FUNCION IMPLEMENTADCRA NUMERO mOOOmm Orn QO 0 0O0 mm OOOOOO O O O m i 000 000 O 000000 000 mm O 0 FUNCION IMPLENENTADGRA NUMERO 000 oO mH OoOOOPPODPO OO O O O Or O n O Ooooo FUNCION IMPLEMENTADORA NUMERO mOOOmM O
15. 270 J 1 MJ IF K LV J EG KL GO TO 221 IF K LV J F0G K2 GO TO 222 IF K LV 2 EG K4 GO TO 3 000000000 mu et mi A m UN O N O 0 x IF K N3 J EQ K1 GO TO 223 TF K N3 J E0 K2 60 TO 225 GO TO 221 222 IF K N3 J EO K1 GO TO 223 IFEK NZ J EQ K2 GO TO 221 GO TO 225 LO 221 KAI LV J ZKUN3 J GO TO 270 223 KA LV J K LV oJ GO TO 270 225 KA LV JI K4 270 CONTINUE Zi N1 0 t N2 0 DO 276 J 1 MJ IF KA LV J EO K LV J GO TO 272 IFIKA LV J EO K N3 J GO TO 275 GO TO 276 272 IF KA LV J EO KINI J GO TO 273 i GO TO 274 273 N1 N1 1 N2 N2 1 GO TO 276 2 74 N1 N1 1 GO TO 276 275 N2 N2 1 276 CONTINUE IF NI EC MJ GO TO 278 IF N2 EO MJ GO TO 284 GG TO 280 278 IF N2 E0 MJJ GO TO 283 DO 310 I LV L3 DO 210 J 1 MJ 310 K T J K T 1 J KAPA KAPA 1 IF LV GE L3 GO TO 282 MI LV N N L2 N 1 GO TO 217 282 N N 1 L2 N 1 GG TO 1000 283 NUS B9 I 284 IF N3 GE N GO TO 287 DO 286 I N3 L 3 DO 2E6 J 1 MJ 286 K 1 J3 K 1 13J 5 287 IF LV GE L3 GO TO 282 N N 1 L3 N 1 L2 N KAPA KAPA 1 MI LV TO 218 rn 280 CONTINUE 1000 CONTINUE IF KAPA EO O GO TO 232 IF NUS EO 89 GO TO 293 GG TO 295 292 GO TO 296 293 NASA 293 IFCNK2 GE N GO TO 400 GO TO 294 z 294 KAP NK2 1 CO TO 2 7 295 KAPENKZ GG TO 297 296 M2 1 NASA 2 L2 N 1 DO 450 MAN M2 L2 KAP MAN 1 297 DO 4
16. EL METONO DE QUINE MACLUSKEY E QUITO 1 4 0 0 A 2 u O qQ EPS gt 3 0 0 1 1 4 0 1 0 9 5 0 1 0 1 a 0 A 2 NND TT 7 0 1 1 1 A 1 0 0 0 1 9 1 0 0 1 LAS SIGUIENTES SON CONDICIONES 535 uas a TABLA DE IMPLICANTES PRIMOS mM 4 e 1 0 E o 2 0 3 1 5 EMEN 2 5 o 1 f x 1 x 1 7 1 1 ABLA DE I NOLECANTESBSTUOS ESENCIALES Gu epe mere en o 2 TABLA REDUCIDA DE SELECCION S TIEMPO DE UCP UTILIZADO PORFA PROGRAMA LUCIO s 555 UM 2 E QUIERO e 5 am _ 84 Nos resta interpretar las Tablas de Selecci n generadas por el Computador y determinar las minimas coberturas para las siete funciones del ejemplo A continuaci n se da las minimas expresiones correspondien tes las funciones representativas del Decodificador Za XX X XX4 XX Zy XoXg 6 xx x a X4X Ze XXX gt n s XX Xy Za x X XoXz xx XX I Z x x 5 Xo Xa X4X4X X XaX XoXo X XXX Xx X 2 Zn 7 EE I ss 5857 EJEMPLO N 3 Este e
17. Resolver una programaci n lineal entera est fuera del al cance y perspectivas de este trabajo Considero que un estudio ampliado puede ser de inter s y uti lidad TRANSFORMACION DE LOGICA AND OR A LOGICA NAND Una de las reglas b sicas del Algebra Booleana denominada Teorema de Morgan nos ayuda a transformar una expresi n de L gica AND OR a L gica NAND En efecto estos teoremas vienen expresados por Y H I pd 1 X 4 1 pd 2 x Y donde X y Y son literales o expresiones booleanas Si la expresi n 1 la complementamos en sus dos lados tene mos X Y XY lo cual da como resultado X Y XY Con lo gue se ha logrado la transformaci n deseada Ejemplo x Xox Sea F x 4 t la funci n que deseamos transformar entonces F x X X5X Xa xA x X ser la expresi n de F en l gica NAND m Mi XA l Xi x3 L L pes gt i fig 15 De 1o anterior podemos deducir las siguientes reglas para la transformaci n AND OR a NAND 1 Invertir todos los productos 2 Transformar las sumas a productos 3 Invertir la expresi n reoni tute de los pasos Las reglas anteriores pueden reducirse a remplazar las com puertas AND OR por opuestas NAND Este tipo de transformaci n es v lida cuando no se tiene nin gun tipo de restricci n Podemos aplicar esta transformaci n a una
18. bla fig 8 en la que cada fila representa un t rmino pro ducto Se va a tomar cada uno de los t rminos y se proceder a probar el criterio de Subsuma con todos los restantes Si un t rmino queda as eliminado este ya no interviene en las siguientes pruebas 2 TABLA DE TERMINOS PRODUCTO CODIFICADOS i VARIABLES PRODUCTOS f xy Xo Xs X X 10 oo 00 xXx 10 01 01 00 00 10 1 E n 01 01 00 Ol 01 10 01 00 S 8 Para esto escribimos cada pareja de t rminos de acuerdo a los codigos anteriores y procedemos a sumar verticalmente todos los simbolos individuales existentes recordando que 05 00 1 16 1 1 L Tomemos el primero y segundo t rmino y apliquemos la opera ci n descrita a esta pareja 10 00 00 10 01 01 00 10 01 01 00 n con la consecuci n del segundo t rmino reproducido en el re sultado lo que significa que est contenido en el primero y que por lo tanto podemos eliminarlo Do pe igual manera eliminamos el tercer t rmino xiX4X y la funci n toma la forma de Fon Ax Xa po que en forma codificada est representada en la tabla de la fig 9 TABLA DE TERMINOS PRODUCTO GODI RECADOS NPO VARIABLES PRODUCTOS Xj X Xa Xy EE 10 00 01 00 EX Xy 20 01 00 01 10 01 00 fig 9 al primero y segundo t rmino de la tabla anterior aplicamos la segunda par
19. contiene cuatro compuertas l gi cas y su costo es de US 0 49 lo que nos da US 0 12 por com puerta un m dulo tal como el CD4014C que contiene setenta y cinco compuertas y su costo es de US 1 51 con un costo por compuerta de US 0 02 Ha existido pues una notable re ducci n del costo por compuerta al fabricar un circuito l gi co mediante 15 t cnica MSI Exi ste una nueva t cnica denominada LSI LARGE SCALE INTEGRA TION que logra costos m nimos 8 elevad simos niveles de com plejidad Aunque estos circuitos LSI son usados restringida mente todav a nos dan una idea de la proyecci n que tiene en el futuro el Circuito Integrado Lo expuesto anteriormente nos lleva a una conclusi n en la actualidad una Minimizaci n que tienda a encontrar expresio nes minimas con compuertas individuales es obsoleta pero si cuitos integrados MSI y mientras esto ocurra la minimiza ci n de circuitos l gicos con ayuda de un computador seguir en vigencia lt Debe atlararse que aunque los m todos de minimizaci n autom tica constituyen una efectiva ayuda est n siempre sujetos a serias limitaciones Corroboran 10 antedicho el sinn mero de trabajos realizados por estudiosos de la materia sin lo grarse a n un algoritmo de caracter universal dentro de es ta rama de la ciencia En el presente trabajo no se pretende agregar un algoritmo m s a los
20. de Flujo Cu a del usuario 8 Listados EJEMPLOS Ejemplo N 1 7 1 Ejemplo N 2 Ejemplo N 3 CONCLUSIONES m m BIBLIOGRAFIA 54 55 60 62 68 68 TS 85 96 98 INTRODUCCION Las actuales presiones de la competencia en el mercado obli gan al dise ador a utilizar t cnicas cada vez m s eficaces de minimizaci n Dichas t cnicas deben ser espadis de proporcio nar resultados que se sometan a las especificaciones restric ciones y limitaciones impuestas por la tecnolog a moderna la cual ha mostrado un inter s cada vez creciente por el dise o con ayuda de un computador Si damos una mirada a la historia dei dise o l gico vemos que sta va paralela a la historia del desarrollo de los cir cuitos integrados As en sus comienzos el dise o l gico estaba circunscrito a la utilizaci n de compuertas logica individuales construidas a partir de elementos concentrados tales como transistores diodos resistencias etc por lo cual una minimizaci n ten a un caracter eminentemente pr cti co ya que reduc a considerablemente el costo de fabricaci n de un aparato l gico Con la introducci n de los circuitos integrados esta t cnica ha sido desplazada y actualmente el Ingeniero utiliza en sus dise os funciones dadas por m dulos monoliticamente constru dos y no ya circuitos de compuertas individuales Podemos apreciar la incidencia del desarrollo de los
21. ginal del ejemplo S TC X X5X4 X1XoX4X x x MI gea t Continuando de la misma manera con los restantes t rminos que no est n en su forma can nica obtenemos la expansi n de la funci n origina como la ilustrada por la tabla de la fig 10 En esta operaci n ya no intervienen los productos de condici n indefinida 1 2 3 E 4 5 6 T PRODUCTO X1X5T4X 4 X Eo o Ti TABLA DE TERMINOS PRODUCTO DE LA FUNCION EXPANDIDA S t 01 01 01 10 10 10 10 fig 10 VARIABLES Xo E 01 01 10 01 10 01 01 01 01 01 10 01 10 01 3 01 01 01 01 10 01 lo _ 26 La atria de Cubrimiento es una matriz M x N donde M es el n mero de productos de la funci n expandida can nicamente y N es el n mero de Implicantes Primos de la funci n Si mij es un elemento de dicha matriz y si X y Y son un t rmino pro ducto y un implicante primo respectivamente j l M i 1 N entonces 1 si Y cubre a Xj Mj j O si Yi no cubre a X Para clarificar la forma de obtener cada elemento de la Matriz de Cubrimiento se encontrar n los elementos La Big 49545 fig 11 contiene al conjunto de implicantes primos de la fun ci n del ejemplo IABLA DE IMPLICANTES PRIMOS VARIABLES IMPLICANTES
22. para 7 variables se requieren 128 cuadros el m todo deja de ser pr ctico para seis o mas variables El m todo del mapa de Karnaugh no presenta caracter sticas optimas para una programacion por dos razones primero el me todo es visual y al programarlo pierde esta caracter stica y segundo demanda un consumo exagerado de tiempo y posiciones de memoria METODO DE QUINE MCCLUSKEY El m todo TABULAR o de QUINE MCCLUSKEY consiste en una tec nica sistem tica de enumerac n basada en la relaci n Xy Xy x donde x es cualquier expresi n producto representando una m s variables y y es una sola variable El proceso de minimizaci n se lleva a cabo siguiendo el algo ritmo detallado a continuaci n l Formar la expansi n can nica en suma de productos de la funci n a minimizar 2 Examinar todos los productos y aplicar la reducci n Xy Xy x 1T x tantas veces como sea posible Los nuevos t rminos as forma dos tandr n una variable menos que los t rminos originales 3 Al nuevo conjunto de t rminos aplicar nuevamente el paso 2 Cuando ya no existan m s reducciones posibles con los pasos l y 2 obtendremos el conjunto de implicantes primos asociados a la funci n a ser minimizada 4 De este conjunto de implicantes primos se obtendr la m nima expresi n de la funci n booleana A continuaci n se ilustra el m todo mediante un ejemplo Partimos del hecho
23. presenta la ventaja de que no est limitada por el n mero de variables al menos si de programa ci n se trata Cuando se intenta programar este m todo se aprecia su adapta bilidad al lenguaje de m quina y su sencillez de algoritmiza ci n Sin embargo puede acarrear dificultades si no se cuen ta con un computador de mediana o gran capacidad de memoria Pese a sus limitaciones podemos considerar a este m todo como 36 til eficaz y versatil que en la generalidad de los casos nos lleva a soluciones m nimas muy aceptables El m todo de Mott reune las cualidades y ventajas del m todo tabular sin embargo el m todo u si mismo es menos directo y cuando se lo programa se encuentra mayor dificultad Una caracter stica por la cual el m todo de Mott aventaja al de Quine MacCluskey es el hecho de que la funci n no necesaria mente debe estar en su forma can nica lo cual en algunas ocasiones resulta muy ventajoso por el BEES de tiempo y trabajo demandados al expandir la funci n a su forma can ni ca Al respecto hay que aclarar lo siguiente el m todo de Mott como se ha visto en el cap tulo anterior requiere pa ra la obtenci n de la m nima expresi n que la funci n est en su forma can nica raz n por la cual si ej m todo es rea lizado a mano no existe tal ventaja pero cuando el m todo est ya programado esta ventaja se hace realidad puesto que el programa se encargar de realizar la
24. ya existentes sin demostrar la factibilidad del uso del computador como herramienta de dise o l gico Para cumplir este cometido ste estudio estar dividido en dos ta ses intla primera se intentar la Minimizaci n de la funci n Booleana como tal y en e studa la minimizaci n en L gica NAND de C I en c Sist e complejidad fig la costo de c C I HL i complejidad fig 19 costo del sistema complejidad CRITERIO DE MINIMILIDAD Existen varios criterios los cuales tienden a determinar cual de las expresiones equivalentes de una funci n l gica es minima Los criterios m s usados son tres 1 18 expresi n minima es la expresi n con el MENOR NU MERO DE LITERALES 2 La minima expresi n es la expresi n con el MENOR NU MERO DE TERMINOS con tal que no exista otra expre si n con el mismo n mero de terminos y menor n mero de literales 3 La expresi n minima es la expresi n que requiere el ME NOR NUMERO DE ELEMENTOS LOGICOS para su construcci n El n mero de elementos l gicos est determinado por la suma del n mero t rminos con el n mero de literales con tenidos en la funci n De estos tres criterios el tercero que contiene a los otros dos es el generalmente m s usado Se puede afirmar que todos los criterios provienen de un criterio m s general y practico y que es el criterio del menor c
25. 0 1 1 0 1 O 1 O 1 1 1 1 1 0 O 1 1 1 0 1 1 1 0 1 1 0 1 1 1 i 0 0 0 1 0 1 1 0 O O 1 1 1 1 1 1 1 1 0 0 1 1 1 0 1 0 1 1 0 1 O 1 0 0 0 0 O idu 1 1 1 1 O 1 O 1 139394 Y 1 0 1 0 1 O 1 1 0 1 indefinido dx indefinido l 1 1 1l indefinido Podemos ahora obtener las funciones implementadoras de las salidas para ser procesadas por el computador AUT a zr Xa True as 2 e t E 8 r y too gt o a E TR TS AA komo moor ee tenkn malama e 0 gt i M E re G a Bo H 2 E e Y k 85 10 56 02 TOTAL COMPI LATLON T IME 00 004 58 iu r 0212 FUMCION A MINIMLIZAR POR EL METODO DE QUINE MACLUSKEY Ly VEZ 0 220 x o H Par 4 oko I XAU UN imt TABLA IMPLICANTES PRIMAS ESENCIALES SSS SS np F p P pig mie Fg t n F gt gt J rl D idel 30 Sa 18 158422 uv 30 V 13 1 Sun Id 5310 21 Sua M M JM a E EE E 5 1 T 0 1 nra
26. 00 NK2 KAP N NCNCE 0 DO 307 J 1 MJ Doom 1F K MAN J EG K1 GO TO 304 IFCK MAN J EG K220GO TO 302 1 J EC K4 GQ TO 305 IF K NK2 J EO K1 GO TO 305 IF KCNK2 J EG K2 GO TO 306 0000000000000 i 0161 0162 0163 0 p NOR UN O O O YM ON 0c0000000000000 J 0194 0195 60196 0197 0198 0199 0200 0201 0202 0203 0204 0205 0206 0207 0208 0209 Owvo0 mubuuN odgo 326 CONTINUE GO 304 302 TF K NK2 J EQ K1 GO 305 IF KLNK2 J EOC K2 GO TO 304 GO TO 306 Li 304 KA MAN J K NK2 J GO TO 307 MES 305 KA MAN J K MAN J 8 GD TQ 7 s 306 KA MAN J K4 NACHO J NONCE NDNCE 1 UL 307 CONTINUE IF NCNCE E0 13G0 TO 308 GO TO 400 308 DO 309J2 1 MJ 309 K N 1 J2 KA KMAN J2 K N 1 gt NACHD K1 N N 1 L2 N GO TO 216 400 CONT ENUE 450 CONT INUE C IMPRIME TABLA DE IMPLICANTES PRIMOS el WRITE 3 106 DO 311LO 1 N 311 WRITE Z 103 KCLO JO 370 71 MJ C c FORMA LA MATRIZ DE CUBRIMIENTO a DO 327 DO 326 NO 1 NUDO NSTER 0 DO 323 J MJ YFiK M J EQ K1 GO0 TO 318 IFLK EM J EQ K2 GU TO 216 TF K M J E0 K4 3G0 TO 319 TFIISINOS J EG KI GO TO 319 IFCIE NOJ EQ K2 GO0 TO 0 GU TO 218 316 JFUIEKNO J EQG K11 GO TO 319 IFCIB ND
27. ATRIZ DE CUBRIMIENTO 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 0 TERMINOS PRODUCTO 1 x 2 XjX5X4X 3 X XoX2Xy 4 XjX4X4X 9 IMPLICANTES PRIMOS 1 xiXo2X3 2 X1X3X4 l 3 x2X3x4 EN rq fig 14 IH O o 70837 consensus iterado S1 todos los implicantes primos son obteni I l dos de esta operaci n el conjunto tomado es una expresi n m nima de la funci n 81 procedimiento se repite tomando cada vez un implicante eliminable y el conjunto esencial esto es necesario puesto que la funci n puede tener una m s expresio nes con igual n mero de t rminos Si no se ha obtenido todos los implicantes primos de la operaci n de consensus entonces el procedimiento se contin a b Se realiza el mismo paso anterior pero esta vez tomando dos implicantes primos eliminables Si aun as no se en cuentra todos los implicantes primos eliminables de la opera ci n de consensus desi necesario tomar tres implicantes pri mos eliminables y en algunos casos hasta cuatro Generalmente Siguiendo este procedimiento se llega a obtener una expresi n minima Para aplicar esta parte del m todo en nuestro ejemplo tome mos los dos implicantes primos esenciales x4x4x4 y x5oX4X m s el t rmino eliminable xix5x4 De este grupo con los t rminos x X5x4 y xix4x realizamos la operaci n de con Sensus lo que nos da como resultado x4x x qu
28. CIALES 17 1X 40 x FORMAT 7 2X5 TABLA DE IMPLICANTES PRIMOS 4x 1 METODO DE MOTT 1X 7O x FORMAT 2X 70 7 2X FUNCION IMPLEMENTADORA N 1 MERQO I3 5X 35 77 7 FORMAT 1H gt 1X FUNCION BOULEANA A MINIMIZAR 6X 1 ESTA REPRESENTADA POR LA SUMA DE LOS SIGUIENTES 1 PRODUCTOS 5X 50 777 FORMAT 10X LAS SIGUIENTES SON CONDICTONES 1 INDEFINIDAS 5X 50 777 READ 1 100 NEJ DO 7000 NTR 1 NEJ READ 1 100 NI ND MJ IRDZ NI 41 N NI ND CC LEE E IMPRIME LA FUNCION A SER MINIMIZADA READ 1 101 K M J J 1 gt MJ 4M 1 N1 YRITE 3 108 DO 200 NAL 1 NI WRITE 3 103 K NAL J J 1 gt MJ DO 201 LU 1 NI DO 201 J 1 MJ IB LU JO K LU J TE ND EC O GO TO 210 5 C LEE E IMPRIME LAS CONDICIONES INDEFINIDAS 230 204 212 211 214 c C S C 215 216 217 218 READ 1 1012 K M J NC IROZ N WRITE 3 09 EC A DO 220 NAL TROZ N WRITE 341032 K NAL J J 1 NJ REALIZA LA EXPANSION DE LA FUNCION A SU FORNA ESTANDAR NUD ZNI ISA NUD DO 211 LU 1 NUD DO 212 J 1 MJ QIFCIB LU J EQ0 K1 GO0 TO 230 GO TO 212 IB LU J K2 DO 204 KAS 1 MJ IE ISA 1 KAS IB LU KAS IE ISA 1 J K3 TSA ISA 1 CONTINUE CONTINUE IFCYSA EQ NUDIGG TO 215 NUD ISA GO TO 202 E INICIA EL CALCULO DE IMPLICANTES PRIMOS NUS 0 NCK N NASA 1 Mi 1 2 KAPA 0 N 1 DO 1000 LV M1 L3 KP2 LV41 DO 280 N3 KP2 N DG
29. CION P DETERMINAR A LOS IMPLICANTES PRIMOS ELE GIBLES Y ALMACENARLOS EN KR ELIMINAR A LOS IMPLICANTES PRIMOS ABSOLUTAMENTE E LIMINABLES IMPLICANTES PRIMOS E LEGIBLES IMPRIMIR LA MATRIZ KR COMO TA BLA DE IMPLICANTES PRIMOS E LEGIBLES EN ID ELIMINAR LOS TERMINOS PRODUCTO QUE ESTEN CUBIERTOS POR LOS IMPLICANTES PRIMOS ESENCIALES CON LOS DATOS DE ID FORMAR LA MATRIZ ICHOI COMO TABLA REDUCIDA DE SELECCION EJEMPLOS PARA PROCESAR TERMINAR u 48 GUTA DEL USUARIO DEL PROGRAMA CORRESPONDIENTE AL METODO DE QUINE MACCLUSKEY El usuario de este programa debe atenerse a las siguientes instrucciones La primera tarjeta de datos llevar perforado en las co lumnas 1 y 2 el n mero de ejemplos a ser procesados A vendr n grupos de tarjetas correspondientes a cada ejemplo a procesar Estos 0 estar n compuestos de una tarjeta que en las columnas 1 y 2 lleve el n mero de variables de la funci n en las columnas 3 y 4 el n mero de productos que hacen la funci n gui a 1 en las 080 5 y 6 el n mero de eondiciones indefinidas luego vendr la s tarjeta s que con formato 80 31 contendr n los datos corres oA et a los t rminos producto de acuerdo al siguiente c digo B 1 representa una variable afirmada O representa aks variable negada X representa una variable ausente Completando cada grupo ir la s tar
30. FACULTAD DE INGENIERIA ELECTRICA ESCUELA POLITECNICA NACIONAL OPTIMIZACION DE CIRCUITOS LOGICOS CON AYUDA DEL COMPUTADOR DIGITAL EN LOGICA NAND DE HASTA TRES NIVELES Lucio V Velasco P 6 CERTIFICO que el presente trabajo ha sido realizado en su totalidad por el se or LUCIO V VELASCO P Sr Ing Ja into Jij n DIRECTOR DE TESIS A EIN ELEME Octubre de 1 976 Dd 31 AGRADECIMIENTO Expreso mi reconocimiento y gratitud a los se Rores Profesores Ingeniero Herbert Jacobson e Ingeniero Jacinto Jij n por su valiosa ayuda como Directores de Tesis yal Cuerpo Docente de la Facultad de Ingenier a El ctrica y Elec tr nica por haberme transmitido sus conocimien tos a lo largo toda mi carrera estudiantil INDICE GENERAL INTRODUCCION CRITERIO DE MINIMALIDAD METODOS DE MINIMIZACION DE LA FUNCION BOOLEANA M todo del Mapa de Karnaugh M todo de Quine McCluskey M todo de Mott consensus M todo de Perlowski ESTUDIO COMPARATIVO DE LOS PRINCIPALES METODOS MINIMIZACION EN LOGICA NAND M todo de Dietmeyer Su M todo de Muroga Ibaraki Transformaci n de L gica AND OR a L gica NAND PROGRAMAS Programa correspondiente al M todo de Quine McCluskey Mecrodiagrama de Flujo Gu a del usuario Listados 10 19 29 35 38 38 38 39 42 4 2 43 48 50 Programa correspondiente al M todo de Mott 4 1 gt _ Macrodiagrama
31. ION IMPLEMENTADOFA NUMERO m O O O O Lim 0000 IMPLEMENTADCRA NUMERO UNCION OOOO m uQOPO O moro DO m mC OOO 0000 O C OO O OoOJODO 01 10 210 y 00 01 01 O1 10 10 00 00 10 10 2 00 10 10 00 10 10 00 10 Ol 01 10 O1 10 00 OI 01 01 10 10 01 10 01 01 00 01 00 01 10 10 00 10 10 10 00 10 10 01 01 10 00 INCTON IMPLEMENTADORA NUMERO S 01 10 01 10 00 10 10 10 00 00 O1 10 10 00 10 10 O1 10 00 10 10 10 10 10 00 I DATA TTD a SS OTO a lt x amma praa repa amma pam rue arica INCION TMPLEMENTADORA NUMERO 10 o o o o OO OmOp Oo OH FUNCION MPLEMENTADCRA NUMEFO 11 01 10 QI 10 00 Oi 10 10 O1 IO O00 e E 00 01 10 10 00 10 00 10 0 01 OO 10 Ol 10 10 00 01 160 01 10 00 01 01 01 10 10 03 10 01 01 00 01 00 01 10 10 00 10 10 01 10 00 10 10 01 00 10 01 01 01 10 00 10 10 FUNCION EOOLESNA A MINTMIZAR E ESTA REPRESENTADA PDR LA SUMA DE LOS SIGUIENTES PRODUCTOS 01 10 01 10 10
32. ION SYMBOL K1 444 K2 446 K3 NTR 458 NI 45C ND N 46C M 470 J NUD 480 ISA 484 KAS NASA 494 MI 498 KAPA KP2 4AB N3 4AC N1 L2 4BC NK2 4CO KAP NONCE 4DO NACHO 404 J2 NO 4E8 NSTER 4E8 KNM KOLA 4F8 KARA AFC NIMPR JR soc NPRIM 510 NFUN KRGCA 520 NMA 524 ARRAY MAP SYMBOL LOCATION SYMBOL LOCATION SYMBOL KA 528 K 8 B68 KB KM 2080 NK 20 SUBPROGRAMS CALLED SYMBOL LOCATION SYMBOL LOCATTON SYMBDL IBCOMS 2170 FGRMAT STATEMENT MAP SYMBOL LGCAT ION SYMBOL LOCATION SYMBOL 100 2174 101 217A 102 106 21E0 107 2224 zou 2 108 DATE 21 10776 DATE 21 10 76 LOCATION 445C 460 474 488 49C 480 4C4 48 4EC 500 S14 LOCATION 1338 LOCATION LOCATION 2180 2264 AZAUXZUZZXAU Ui EJEMPLOS Ejemplo N 1 Se trata de disefiar un conmutador telef nico hipot tico ca paz de comunicar entre si a los tel fonos denominados Ne 1 y N 2 que cumpla con las siguientes condiciones 1 si el conmutador conecta N 1 con N 2 sia O si no conecta N l con N 2 l si el auricular 1 est levantado Eng c O si el auricular N 1 est colgado 1 si el auricular N 2 est levantado 0 si el auricular N 2 esta colgado l si el tel fono N 1 est hablando O si el tel fono N l no est hablando 1 si el tel fono N 2 est hablando H2 O si ei tel fono N 2 no est hablando 1 si M4 E O si l si O si 1 si s m 1 15 O si Vemos entonces que riables incluyendo
33. J EG K2 GO TO 318 GO TO 320 318 KA M J IB ND J GO TO 2321 31g KACM S J K M J GO TO 32 320 KATM J3 K4 321 IF KACM 2 EQ EBC NO J GO TO 322 GO TO 323 322 NSTEP NSTER341 223 CONTINUE IJIF NSTER EGQ MJ GO TO 324 324 KETM gt NO 1 TO 326 325 KA M NO 0 327 CONT INUE WRITE 3 105 C C SELECCIONA LOS IMPLICANTES PRIMOS ESCENCTALES DO 331 KNN 1 4N 331 DO 325 NS 1 NUD KSUCO 0 DO 333 IF KE M NO EO 1 GO TO 232 GO TO 333 332 NUMER M KSUCO KSUCD 1 333 CONTINUE IF KSUCO EQ 1 GO0 TO 334 GO TO 325 334 IK NUMER 1 335 CONTINUE DO 236 KOLA 1 N 336 KMIKOLA 9999 0210 0211 0212 0213 0214 0215 0216 0217 0218 0219 0220 0221 0222 0223 0224 0225 0226 0227 0228 0229 0230 0231 02 32 0233 0234 0235 0236 0237 0238 0239 0240 0241 0242 0243 0244 0245 0246 0247 0248 0249 0250 0251 0252 6253 0254 0255 0256 0257 0258 0259 0260 0261 0262 0263 0264 0255 0266 0267 0268 0269 0270 0271 0272 0273 0274 0275 0276 0277 0278 0279 0280 KARA 1 DO 338 KNM I N IF IK KNM EQ 1 6GO TD 337 GO TO 3238 gana 37 WRITE 3 103 K KNM JJ MJ KM KARA KNM 7 KARA KARA 1 NIMPR KARA NUIPR KARA 338 CONTINUE JN 0 EE DO 343 J 1 N IF IK M E6 1 G0 TO 341 DO 340 J l WJ 340 TECKARA J K1M gt J KARA KARA 1 GO TO 343 341 JN JN31 DO 342 J 1 MJ 342 JECIJIN gt J K1M J I gt 343 C
34. N N N 519 Su 69 1 es l no llamado es llamado 2 es llamado 2 no es llamado rl y Ne l y NO que es propio Con estas condiciones podemos De los 128 t rminos posibles 8 1 2 est n conectados previamente 2 no est n conectados previamente la salida depende de siete va estado anterior construir una tabla de verdad s lo 3 nos dan una salida igual y corresponden a las siguientes situaciones l Los tel fonos N l y N 2 no han sido previamente conecta dos entre si s m 1 15 0 Los auriculares N l y 2 estan levantados Ph 1 Por ninguno de los tel fonos se est hablando TO Telefono N l no es llamado M O Tel fono N 2 es llamado 1 M 2 Los tel fonos N 1 y N 2 no han sido previamente conecta dos entre si S m 1 i 0 Los auriculares l y N 2 estan levantados Ph Ph 1 1 2 Por ninguno de los tel fonos se est hablando Tel fono N 1 es llamado 1 E Tel fono N 2 no es llamado 3 La conecci n entre N l y N 2 es mantenida ot A ius Auriculares N 1 y N 2 estan levantados Ph4 Ph 1 Por los dos tel fonos se est hablando H H 1 Ning n tel fono es llamado M 0 Existen adem s 56 condiciones indefinidas debido a situaciones que no pueden darse v g no pueden existir dos tel fonos lla mados simu
35. ONTINUE JR 0 DO 348 M l N IF TK M 1 G0 TO 346 DO 345 J 1 NUD E 345 KINIMPRoJ KE M J NIMPR NIMPR4 1 GO TO 348 346 JR JR 1 DO 347 J 1 NUD 347 K JR J KB M 4 J 348 CONT INUE c C SELECCIONA UN GRUPO DE IMPLICANTES Y PRUBA SI C NPR TM NUIPR NEUN 0 DO 349 NO 0 1 NUD 349 NK NO 0 KOMTA 1 MA NUIPR 1 MEL E DO 351 DO 350 NO x1 NUD 350 NK ND NK NO K Ms ND 351 CONTINUE 352 DG 353 NO I NUD IF NK NO LE O GO TO 357 353 CONTINUE NFUN NFUN 1 C IMPRIME UNA FUNCION IMPLIMENTADORA WRITE 4 107 NFUN KROCA NUIPR 1 DO 354 NMA 1 KROCA 354 WRITE 3 103 IBINMA J J 14MJ DO 3565 J 1 MJ h IF CIB KROCA J EG IB MA J GO TO 355 GG TO 356 355 CONTINUE GO TO 357 356 WRITE Zs 103 IBIMAS I SL J c1 MJ 357 IF NUIPR 1 GE sNJGO TO 7000 IF KOMTA EQ 1 0GQ0 TO 361 DO 360 NO 1 NUD 360 NKINOC NK NO K Ma NO 361 IF MA GE NOGO TO 370 368 MASMA 1 K OMTA J3 DO ZES NO 1 NUD 366 NKTNO NK NO K MA NO G TO 352 370 NUIPR NUIPR 1 KGWNTA 1 MA NUIPR 1 DO 271 P 1 gt MA DO 371 ND 1 NUD IMPRIME TABLA DE PRIMOS ESCENCIALES CUBREN LA BY DOS FDRTRAN IV 360N FQ 479 3 8 MAINPGM 0281 371 NK NO ZNK NOGO 4K M ND 0282 IF MA GE N GO TO 7000 gt 0283 TO 368 m 0284 7000 CONTINUE 0285 END 7 COS FORTRAN IV 360N FO0 479 3 8 MAT NPGM SCALAR SYMBOL LOCATION SYMBOL LOCAT
36. PRIMOS l X2 23 Xi 1j dx 10 00 01 00 2 XX 00 00 01 01 3 ux 00 10 01 00 fig 11 Investiguemos si el Implicante Primo l fig 11 cubre al t r mino producto l fig 10 sumando dichos t rminos en la for re 27 ma acordada X4X4X4X 01 01 01 01 i Xx JX 10 00 01 00 11 01 Ol Ol El resultado nos indica que los elementos sumados no se sub suman y por lo tanto el implicante x X no contiene o cubre a X Kox XaX y en consecuencia el elemento matricial my es 0 Tomemos luego el implicante 2 y el t rmino producto 1 X4X5X4X 01 01 01 01 00 00 01 01 01 01 01 01 y el resultado nos indica que el t rmino producto est cubier to por el implicante primo por 1o tanto moj l MATRIZ DE CUBRIMIENIO IRSA fig 12 El siguiente paso previo aja de la m nima expresi n es el de determinar cuales son los iudicatus primos esencia les Si existe uno o m s terminos producto de la expresi n ex pandida que est n cubiertos por un solo implicante primo este implicante ser esencial puesto que no existe posibilidad de que sea reemplazado por otro implicante primo Esta condici n es visible en la matriz de cubrimiento de la fig 12 cuando al guna columna contiene solamente un l el implicante primo esencial ser el correspondiente al de la fila en la que se en cuentra ese l as columnas l 3 y 5 contienen solamente un nl en las filas 2 3 y 1 respectiva
37. S PRIMOS EXHERA RECERERAREL E A de ER o Ro 10 01 00 10 01 00 10 00 10 01 OI 10 o1 10 00 00 01 00 01 10 10 00 00 10 METODO DE MOTT 01 01 OI 00 00 10 10 10 TABLA DE IMPLICANTES PRIMOS ESENCIALES te sk RARA ok dok sk kodon dok ok Xe 10 00 00 10 10 01 10 00 01 01 00 00 01 01 10 10 1 SS uaj zwak IT IIILITLLLLLLTILTILLL A A ILIL TTT SSK ETAIT STT FUNCION IMPLEMENTADORA NUMERO 5 10 O01 01 01 00 10 00 10 10 00 00 10 00 10 10 10 00 00 00 10 10 FUNCION IMPLEMENTADORA NUMERO gt E 10 10 01 00 Ol 01 Ol 00 10 00 10 10 00 00 10 OL 10 10 10 Ol 10 00 00 OO 10 10 i FUNCION BOOLEANA A MINIMIZAR o 0 O H e O ka i O O Oc Om O m m LAS SIGUIENTES 10 LO 10 10 10 10
38. UCTO PRIMOS 0011 1000 1010 1011 1100 Para encontrar la m nima expresi n con la ayuda de esta tabla 18 debemos seleccionar grupos de implicantes rius de tal suer te que todos los t rminos producto qu han formado parte en esta tabla esten cubiertos por dichos grupos Aquel grupo que unido al conjunto de implicantes bios rs cumpla con kos criterios de minimalidad dados en el capitulo anterior constituir n la minima expresi n de la funci n Procediendo de la manera indicada obtendremos en el ejemplo los siguientes grupos Grupo 1 1 00 01 Grupo 2 1 00 0 0 11 Grupo 3 110 0 0 01 1 7 110 0 0 11 Obviamente existen otros grupos a m s de los cuatro anterio res por ejemplo tomemos el grupo formado por los implican tes 110 0 0 01 y 11 Si examinamos la fig 7 vemos que la fila correspondiente al implicante primo 11 esta completamente cubierta por la fila correspondiente al implicante 01 por lo tanto ser a redundante considerar al implicante 11 como miembro de este grupo El grupo l cumple con el tercer criterio de minimalidad y por lo tanto constituye junto con el implicante primo esencial 1 1 la m nima expresi n que representa la funci n en suma de productos quedando esta como sigue n 4 5 koko En muchos casos la selecci n de los grupos necesarios para completar la m nima repr
39. UPO NO CUBRE LA FUNCION L IMPRIMIR LA FUNCION IMPLEMENTADORA p COMBINACIONES DE I P QUE HACER EJEMPLOS PARA PROCE TERMINAR SI SI 60 GUIA DEL USUARIO DEL PROGRAMA CORRESPONDIENTE AL METODO DE MOTT El usuario de este programa debe atenerse a las siguientes instrucciones La primera tarjeta de datos llevar perforada en las colum nas Y y 2 el n mero de ejemplos a ser procesados A continuaci n vendr n grupos de tarjetas correspondientes a cada ejemplo Estos grupos estar n compuestos de una tar jeta que en las columnas 1 y 2 lleve el n mero de productos implementadores en las columnas 3 y 4 el n mero de produc tos de condici n indefinida en las columnas 5 y 6 el n mero de variables Luego vendr la s tarjeta s que con formato 40A2 contendr los datos correspondientes a los productos im plementadores de acuerdo al siguiente c digo 10 representa una variable afirmada OI representa una variable negada OO representa una variable ausente Completando cada grupo de las tarjetas que contenga los datos correspondientes a cada ejemplo vendran tarjeta s que conten ga n a Yos productos de condici n indefinida dichas tarjetas estar n perforadas de acuerdo al formato y c digo indicados Ejemplo Si F x XX XX Xy XXX y Xx XoX y si los siguientes productos son de condici n indefinida
40. alizar en ella que el segundo y tercer implicante constituyen implicantes primos esenciales rosulvadocuHe coincide con Ej en estza o por el m todo de Perlowski 3 2 Determinar los implicantes primos slininsbies Son eliminables los implicantes primos que no son esenciales Por lo tanto basta con separar los implicantes primos esen ciales del conjunto de implicantes primos para obtener los eliminables En el ejemplo x4X5X4 y son elimina bles 3 Determinar los implicantes absolutamente eliminables Un procedimiento del consensus iterado sobre el conjunto de implicantes primos esenciales nos indica cuales de los im plicantes primos eliminables son 9 eliminables Si la operaci n de consensus nos genera un implicante elimi nable luego este ser absolutamente eliminable pues estar contenido en el conjunto de esenciales Los implicantes x x4x y XoX4x del ejemplo son esenciales y sobre es tos no es posible aplicar la operaci n de consensus lo que nos indica que ninguno de los implicantes eliminables es ab solutamente eliminable 4 Eliminar los implicantes primos absolutamente eliminables De esta manera la expresi n de la funci n estar dada por los implicantes primos esenciales y los condicionalmente eli minables 5 Obtener la expresi n minima a Tomar el conjunto de implicantes primos esenciales m s un eliminable y sobre este conjunto aplicar el 32 M
41. circui tos integrados sobre el costo de fabricaci n de un sistema en las figuras la 19 y lc 18 figura la representa el n mero de circuitos integrados de un sistema l gico como funci n de la complejidad n mero de e lementos de cada circuito integrado En ella es evidente que la relaci n es lineal e inversamente proporcional Bl costo de cada circuito integrado como funci n de la comple jidad est dado en la figura 1b La curva a corresponde a circuitos SSI SHORT SCALE INTEGRATION y lal curva b co rresponde a circuitos MSI MIDDLE SCALE INTEGRATION Se ve claramente que en los circuitos integrados MSI se ha logra do extender la zona de costos bajos hasta niveles elevados de complejidad Dicho en otras palabras para un mismo costo con los circuitos MSI se logra un n mero mucho mayor de compuertas por circuito integrado que con la t cnica SSI En la figura 1c tenemos las curvas correspondientes a cos to de un sistema como funci n de la complejidad la curva a para circuitos MSI y la curva b para MST El m nimo pa ra circuitos MSI es menor y est corrido hacia una mayor complejidad lo que nos indica que el costo por compuerta se r much simo menor con cesta t cnica que con la de los circui tos SSI i Veamos en forma pr ctica las diferencias arriba anotadas un circuito tal como el CD001C
42. de que disponemos de la tabla de verdad de la fig 4 Con el fin de generalizar el m todo se ha escogi do una funci n de cuatro variables donde se ha inclu do con diciones no implementadoras o indefinidas La expansi n can nica de la funci n a ser minimizada es la si guiente FO CXQXQX4X XQyXQXQX X XXX x 4 Son condiciones indefinidas los productos SAE ka TO o TABLA DE VERDAD DE UNA FUNCION BOOLEANA X Xo X3 F 0 i 0 0 1 0 o 1 0 i 0 1 1 1 D du 705 0 go 0 1 0 1 1 0 l l 0 0 1 1 1 1 1 O 0 0 1 m l O 0 1 0 1 1 1 1 0 1 1 1 1 1 0 O 1 lJ l O 1 l 1 l 1 0 T Wu 7 2 1 fig 4 Para la ejecuci n del segundo paso tabulamos los t rminos productos a adiendo a la lista las condiciones indefinidad 7 y aplicando al conjunto la relaci n xy o xy x 19 tantas veces como fuese necesario Gonpatodos pues el primer t rmino de la primera columna de la fig 5 00 0 O con los dem s t rminos de la misma columna vemos que es posible aplicar la reducci n solamente con el segundo y E termi no 0 0 1 0 y 10 0 0 obteniendo asi los t rminos reduci dos 0 0 gt 0 y 00 0 a los que les colocamos en la co lumna 2 de la misma figura Continuamos la operaci n con to dos los t rminos originales
43. e es el otro implicante primo eliminable raz n por la cual el grupo que hemos escogido constituye ya una m nima expresi n Tomemos aho ra el grupo formado por xyx4x x4X4xX X X9X4 5 un consen sus entre estos dos ltimos nos restituye xiX9X4 el impli cante eliminable sobrante y en consecuencia este grupo elegi Ads do es tambi n una expresi n m nima La funci n nos quedar a reducida a cualquiera de las dos expresiones siguientes F i XXX X9X4X XXX 1 XXX XXX 2 el procedimiento termina aqu 35 S ESTUDIO COMPARATIVO DE LOS PRINCIPALES METODOS Como hemos visto en el cap tulo anterior el m todo del Mapa de Karnaugh es un m todo visual bastante eficaz siempre y cuando se cuente con funciones de no m s de cuatro variables lo que constituye una seria limitaci n Podemos anotar otra desventaja y es el hecho de que nada nos dice este m todo bre la m nima expresi n de 4 funci n puesto que solo nos genera el conjunto de implicantes ON siendo preciso re currir a otros m todos para resolver el problema de la m ni ma cobertura El uso de las condiciones no implementadoras o indefinidad en el m todo de Karnaugh resulta ser una caracteristica in teresante del mismo El m todo tabular al igual que el de Karnaugh usa las con diciones no implementadoras para la obtenci n de la tabla de implicantes primos pero
44. e perfilarse la posibilidad de una programaci n de alguno 6 algunos de los m todos METODO DEL MAPA DE KARNAUGH Basicamente el Mapa de KARNAUGH es una forma gr fica de re presentaci n de la misma informaci n contenida en la tabla de verdad que define dicha funci n Para una funci n de r varia bles el mapa contiene ar cuadros uno por eada combinaci n posible de las urn variables de entrada A cada cuadro se de signan valores particulares de dichas combinaciones Bajo esta convenci n se coloca un 1 en cada cuadro que representa una combinaci n para la cual la funci n toma el valor uno 1 se coloca un cero 0 en cada cuadro que represente a una combi naci n para la cual la funci n toma el valor cero y se coloca una i en aquellos cuadros correspondientes a condiciones de entrada indefinidas Don t care EJEMPLO Sea F x X x4 una funci n booleana representada por la ta bla de verdad de la figura 2 El Mapa de Karnaugh para dicha funci n se ilustra en la figura 3 Siguiendo ciertas reglas es facil visualizar los agrupa mien zu tos que nos lleven a una soluci n m nima D y TABLA DE VERDAD DE UNA FUNCION BDOLEANA X X Xs F 0 0 0 1 0 E 1 1 0 1 0 i 0 1 1 1 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0 fig 2 MAPA DE KARNAUGH DE UNA FUNCION BOOLEANA 10 Como el n mero de combinaciones y por lo tanto el de cuadros crece exponencialmente con el n mero de variables
45. esentaci n de la Pana en es obvia Sin embargo en algunas situaciones se necesita de un algo ritmo capaz de generar en forma sistem tica el grupo de cober tura m nima Taylos L Booth presenta un algoritmo alg brico para la soluci n de este problema Este m todo como se puede apreciar en su estudio resulta bas tante claro y sencillo presentando buenas caracter sticas para una posible programaci n METODO DE MOTT CONSENSUS Por el mismo tiempo que Quine MacCluskey desarrollaban el m todo tabular de minimizaci n Samson y Mills trabajaban sobre una nueva t cnica denominada de Consensus que Quine la define como CONSENSUS ITERADO M s tarde Mott combin el m todo de Consensus con el Tabular y consigui una minima expresi n de la funci n booleana al mismo tiempo que puso en evidencia la posibilidad de adaptar este m todo para la programaci n El Consensus Iterado consiste en dos operaciones b sicas una es la operaci n de consensus y otra es la relaci n de subsuma Operaci n de Consensus Si dos t rminos X y Y contienen una y solo una variable afir mada en el uno y negada en el otro se puede escribir un nue vo t rmino Z de consensus formado por el producto de todas 20 las variables restantes eliminando aquella que est afirmada en el uno y negada en el otro Entonces se puede escribir que X Y X Y Z donde el simbolo significa equivalencia booleana Ejem
46. expansi n El m todo de Mott combina el consensus iterado con 1a tabula ci n Perlowski en su m todo elimina esta mescla pues encuen tra la m nima expresi n aplicando en forma reiterada el prin cipio dei nS Si el m todo de Perlowski es programado se logra ahorrar tiempo y memoria de computaci n ya que una misma Subrutina puede ser utilizada tanto para la determina ci n de los implicantes primos como de la m nima expresi n Aun asi el m todo de Mott es preferido en raz n de que utili 37 za las condiciones no implementadoras por lo cual los resulta dos son m s optimos cuando el problema a tratarse contiene di chas condiciones De lo anterior puede deducirse que los m todos m s representa tivos y utilizados son el m todo tabular o de Quine MacCluskey y el m todo de Mott Tambi n en este trabajo han sido preferi dos y escogidos para una ulterior programaci n A partir de los resultados de cualquiera de estos dos m todos J Se proceder a encontrar una soluci n del problema en l gica NAND de hasta tres niveles 38 MINIMIZACION EN LOGICA NAND En el presente cap tulo se estudiar n m todos de simplifica ci n en L gica NAND propiamente dicha METODO DE DIETMEYER SU Este es un m todo utilizado cuando existe restricci n del n mero de entradas por compuerta Fan in limitado Consiste en la b squeda de un factor com n que cumpla adem s con ciertos requisitos
47. funci n minimizada por cualquiera de los m todos estudiados en el cap tulo ante rior El resultado que obtendriamos ser a una implementaci n m nima o cuasi m nima en L gica NAND de hasta tres niveles considerando un nivel m s debido a la inversi n en las entra das Esta transformaci n la vamos a utilizar en nuestro problema de Minimizaci n en L gica NAND ya que resulta sumamente sen cillo y no precisa de una variaci n o ampliaci n de los pro gramas para minimizaci n de la Funci n Booleana PROGRAMAS Programa correspondiente al M todo de Quine MacCluskey Para cumplir con los objetivos de este trabajo se program el M todo de Quine Mac Cluskey en FORTRAM IV 360 370 En este programa las matrices usadas no son significativas pues pierden su informaci n inicial y su uso cambia de acuer do a las necesidades del programa La Matriz K almacena en un principio los elementos corres pondientes a la funci n a ser minimizada Las condiciones in definidas tambien son guardadas en esta Matriz La Matriz K junto con la Matriz KR y el Vector NP se utiliza para la obtenci n de los implicantes primos La Matriz ICHOI esta encargada de contener los datos de las Tablas de Selecci n Para la formaci n de estas tablas de se lecci n se utiliza la Matriz K Para la selecci n de los Implicantes Primos Esenciales y Ele gibles se ntiliz n las Matrices K KR ICHOI y KES
48. ga Ibaraki muy interesante y versatil pero que lastimosamente est basado en una codificaci n desarrolla da en la Universidad de Urbana cuya consecuci n no ha sido posible y que adem requiere de programaci n lineal entera tampoco justifica su programaci n Una transformaci n basada en los teoremas de Morgan ha sido expuesta Su sencillez y simplicidad m s el hecho de no re querir variaci n alguna de los programas de simplificaci n de la funci n Booleana demuestran su utilidad para los fines que persigue este trabajo De los ejemplos se desprende la eficacia de los programas se observa tambi n que uno de ellos el correspondiente al M to do Tabular supera al otro en efectividad En compensaci n el programa correspondiente al M todo de Mott requiere menos BIBLIOGRAFIA 1 2 3 4 5 6 Bartee Lebow Reed THEORY AND DESIGN OF DIGITAL MACHINES McGraw Hill 1 962 P g 49 69 Taylos L Booth DIGITAL NETWORKS AND COMPUTER SYS TEMS John Wiley and Sons Inc 1 971 P g 122 145 E J M Van Lantschoot A PDP S PROGRAM FOR MINIMI SATION OF LOGICAL FUNCTIONS Art culo presentado en el International Symposium Bruselas Septiembre 17 1969 Andrew A Perlowski A MINIMIZATION OF BOOLEAN FUNCTION USING A DIGITAL COMPUTER IEEE Computer So ciety 1970 D L Dietmeyer and Y H Su LOGICAL DESIGN AUTOMATION OF GAN IN LIMITED NAND NETWORKS IEEE Computer So
49. i n de la m nima expresi n de la funci n se seguir el siguiente vrocedtsdento a Formar la tabla de Selecci n Determinar los implicantes primos esenciales Determinar y eliminar aquellos implicantes que sean ab solutamente eliminables d Seleccionar los lupiicadten primos elegibles e Formar la Tabla Reducida de Selecci n XL Seleccionar el grupo o grupos de implicantes primos que cubran la funci n en forma m nima La Tabla de Selecci n para el problema del ejemplo se ilustra en la fig 6 TABLA DE SELECCION IMPLICANTES TERMINOS PRODUCTO PRIMOS 9047 0 n 1000 1010110111 11001110111113 1 00 110 _0 0 ol v v v xi 1 L TA En la tabla de la fig 6 cada columna corresponde a un t r mino 010 de la expresi n original y dada fila correspon de a un implicante primo Notese que no se han incluf o los de condici n indefinida Se ha colocado una marca v para cada implicante primo en las columnas cuyos cri nos producto estan contenidos en ese implicante primo as por ejemplo el implicante primo 1 00 contiene a los t rminos producto 1000 y 1100 De la misma tabla podemos extraer el conjunto de implicantes primos esenciales absolutamente eliminables y elegibles to mando en consideraci n las siguientes observaciones Un implicante primo que no contenga contiene a un so lo t rmino producto s
50. i contiene una dos terminos pro ducto estar n implicados por l En general un implicante que contenga s implicar a 2 t rminos producto Es posible tener uno m s t rmino producto que est n con tenidos en un solo implicante primo Los implicantes pri mos que cumplan esta funci n se denominan implicantes primos esenciales En el ejemplo 1 1 es esencial Un implicante primo es absolutamente eliminable si todas las columnas que han sido marcadas en la fila correspondien te a este implicante primo est n tambi n marcadas en una o m s filas correspondientes a los implicantes primos esencia les En el ejemplo no existe ning n implicante primo que cum pla este requisito 17 Los implicantes primos que no se encuentren en ninguna de las dos clases definidas anteriormente constituyen el con junto de implicantes primos elegibles Por lo tanto son ele gibles los implicantes 1 00 110 0 0 01 y 11 La tabla reducida de selecci n nos permite determinar que con junto de implicantes representar n a la funci n su forma m s simple Esta tabla es la misma Tabla de selecci n en la que constan solamente las filas y columnas correspondientes a los implicantes primos elegibles y a los t rminos productos impli cados por stos respectivamente La fig 7 ilustra a la ta bla reducida de selecci n del ejemplo TABLA REDUCIDA DE SELECCION A IMPLICANTES TERMINOS PROD
51. jemplo tiene por objeto utilizar el programa correspon diente al m todo de Mott y comparar los resultados obtenidos mediante el de Quine McCluskey Para ello usamos cuatro de las funciones del ejmploN 2 y son aquellas que corresponden a Za Zy Z6 Y Za El programa de Mott nos da los siguientes resultados para estas cuatro funciones Eae XQX9X4X le LRA KR XX X XoX 7 7 E Za cest peu lt Los resultados anteriores provienen de la menor funci n implementardora de las generadas para cada caso Si comparamos los resultados obtenidos por los dos progra 86 imas salta a la vista que el pr grama correspondiente al M to do Tabular ha generado en todos los cuatro casos funciones implementadoras menores lo que nos lleva a pensar que este programa cuando se parte de la funci n expandida da mejores resultados FUNCION BOOLEANA A MINIMIZAR ESTA REPRESENTADA POR LA SUMA DE LOS SIGUIENTES 000 000 O m e OO SIGUIENTES OO O O SON CONDICIGNES PRODUCTOS W i P A T sd n T x rvF E YF P w lt s TABLA DE IMPLICANTE
52. jeta s que contenga n los datos correspondientes a las condiciones indefinidas Estas tarjetas estar n perforadas de acuerdo al formato y c digo indicados d Ejemplo Sea F X Ko Xa XX cx x 49 con las siguientes condiciones indefinidas La primera tarjeta llevar a en la columna ly 2 01 la segun da tarjeta llevar a en la columna 1 y 2 04 en las columnas 3 y 4 05 en las columnas 5 y 6 02 La tarjeta N 3 ii esa r a desde la columna 1 lo siguiente 000001011110111 La cuarta tarjeta llevar a a partir de la columna l lo si guiente 010101 El programa nos dar como resultado lo siguiente 1 Tabla de Implicantes Primos 2 Tabla de Implicantes Primos Esenciales 3 Tabla de Implicantes Primos Elegibles Solamente si existe 4 Tabla Reducida de Selecci n si existe Implicantes Primos Elegibles Como puede observarse este programa no nos d directamente la s m nima s expresion es en su lugar la tabla reducida de selecci n impresa nos permitir encontrar la m nima expre si n de acuerdo con lo estudiado en capitulos previos EE EMPEZAR gt LEER EL NUMERO DE EJEMPLOS A SE PROCESADOS 0 LEER EL NUMERO DE TERMINOS PRO EL NUMERO DE CONDICIO DUCTO NES INDEFINIDAS Y EL NUMERO DE VARIABLES LEER E IMPRIMIR LOS TERMINOS PRODUCTO Y ALMACENARLOS EN Kn Y IR CONDICIONES INDEFINI
53. ltaneamente entre si etc Este ejemplo fue corrido en el programa correspondiente al M todo de Quine MacCluskey ON mi hi mi i uJ ua pd mo ki hm pun jud o mm I jmo mu po i o mu i pi ma pli me pu O RR 0 0 Pm ms OOOOOND O r i D OS O O O OO 2 O O O O O gt i O0 0 0 9o0 0 0 0 0 o o o 2o o o pe i me 525 YO o00U Jou m em hu RO A e e A O meme OO OO HIGH O O OOO OTC OMG HO OOOO 44099 mm 5v1 SvdIN133GNI S3SNOIDIOHO NOS SALNYINDIS o o oor 30d UVZIHININ V 1
54. mente en consecuen cia los implicantes correspondientes a las filas anteriormente mencionadas ser n esenciales Nuestro paso final ser seleccionar grupos de implicantes pri mos en los cuales est n involucrados todos los implicantes primos esenciales y que cumplan con el requisito de que al su mar las filas correspondientes al grupo escogido en la matriz de cubrimiento se obtenga un vector cubierto de unos Si es ta restricci n no se cumple entonces aquel grupo no formar la m nima expresi n de la funci n tratada y por 10 tanto se de ber escoger otro 29 4 METODO DE PERLOWSKI Este m todo est basado en el consensus iterado La diferen cia principal con el m todo de Mott radica en la forma de ob tenci n de la m nima expresi n de la funci n a partir del conjunto de implicantes primos En efecto como hemos visto Mott combina el consensus con el m todo tabular mientras Perlowski aplica la teor a del consensus hasta alba Zar la m nima cobertura Por esta raz n nuestra atenci n d a dirigir se hacia el 09086 de la minima 600059 de la funci n Buponiendo que contamos con el conjunto de daplicantes primos previamente obtenido por aplicaci n del consensus iterado Sea la funci n a minimizar EL We O Y A E cuya tabla de implicantes primos es la siguiente TABLA DE IMPLICANTES PRIMOS 1 3 4 10 10 01 00 zx 10 00 10 01 lO 01 10 00
55. osto LA Veamos como inciden en la reducci n de costos estos criterios Sea la funci n F X1X5X4 pra X1 5X4 X1X5X4 que puede ser implementada por las siguientes expresiones 1 F XX XX XX XX 27 Tanto la expresi n 2 como 14 3 contiene el menor n mero de literales y el menor n mero de terminos por lo tanto de acuerdo al primero y segundo criterio estas dos expresiones son igualmente minimas Si queremos implementar la funci n utilizando elementos concentrados necesitamos para la expre si n 1 doce diodos y dos transistores mientras que para las expresiones 2 6 3 solamente precisamos de nueve diodos y dos transistores En consecuencia nuevamente las expresiones 2 y 3 son igualmente minimas esta vez de acuerdo con el tercer criterio Es evidente que un n mero menor de elementos conlleva un me nor costo y por lo tanto cualquiera de los criterios anota dos tienden a reducir el costo Sin embargo cuando se trata de una construcci n utilizando circuitos integrados estos tres criterios no pueden ser extrictamente aplicados limita ciones intrinsicas en n mero de entradas y compuertas en los modulos dificultan la formulaci n de un criterio m s general B METODOS DE MINIMIZACION DE LA FUNCION BOOLEANA Un estudio de algunos de los M todos de Minimizaci n de la Funci n Booleana como tal Ser abordado en este cap tulo De ste ha d
56. plos XjX9X4 XXX XjXjX4 XJX Xj donde XX Z t rmino de consensus XX XjX4 XX XX donde X4x4 Z t rmino de consensus No existe consensus cuando 1 No hay un par de variables opuestas Ejemplo f 2 Cuando hay m s de una varia ble opuesta Ejemplo XXoXg XX 2 3 Relaci n de Subsuma Si cada variable de X est contenida en Y y Y contiene varia bles adicionales luego Y subsuma a X Un t rmino que subsu ma a otro puede ser eliminado sin alterar la funci n Ej S SEXES 175 X1X5X4 subsuma a y por lo tanto X X5X4 puede ser elimina 51 de quedando F Xo Xa 1 5 El consensus iterado es un proceso por el cual una expresi n dada puede ser transformada en un conjunto de implicantes primos El procedimiento es llevado a cabo en dos pasos en el primero se remueven los t rminos contenidos en otros re laci n de s bsuma en el segundo a los t rminos resultantes del primer paso se aplica la operaci n de consensus Para aclarar el m todo apliquemoslo a un ejemplo pero antes debemos hacer las siguientes anotaciones Una variable afirmada es representada por 10 Una variable complementada por 01 Una variable ausente por 00 La funci n que queremos minimizar es X xx x ptt Xi o X1X5X4 F XX 1 13 Si hacemos uso del convenio anterior obtenemos la siguiente ta
57. rporation USA 1971 David Gordon Dutra COMPUTER REDUCTION OF BOOLEAN EXPRE SSIONS IEEE Computer Society 1967 Pierre Tison APLICATION OF COVCENSUS THEORY TO THE MINIMIZATION OF BOOLEAN FUNCTIONS IEEE Computer Socie ty 1966
58. te del m todo y para ello sumamos en la forma ya descrita y obtenemos 10 00 01 00 01 01 00 01 11 01 01 01 De la definici n de operaci n de consensus podemos deducir 24 que si existe 0 80 un t rmino ll existir consensus y ste puede ser obtenido facilmente reemplazando ll por OO En el ejemplo X Xx X 00 01 01 01 ser el t rmino de consensus A este t rmino lo dR h al final de la lista de la figura 9 y nuevamente aplicamos la primera parte del m todo con el fin de eliminar si existen t rminos que sub sumen a otros La lista final una vez que no existan t rminos de consensus y t rminos que subsumen a otros es la lista de Implicantes Primos de la funci n tratada En nuestro problema del ejemplo la funci n queda reducida a XX XX3 Si en el problema aparecen condiciones indefinidas stas son incluidas y tratadas junto a los productos implementado res con el procedimiento anterior Una vez obtenido el conjunto de implicantes primos se proce de a determinar la m nima expresi n de la funci n Mott propo ne para la rsoluci n de este problema la creaci n de una ma triz denominada Matriz de Cubrimiento muy similar a la ta bla de Selecci n del m todo tabular Para formar esta matriz hay que expandir la funci n original a su forma con nica apli cando en ella la relaci n k X X XY Realicemos la expansi n del primer t rmino de la funci n ori
Download Pdf Manuals
Related Search