Tesis de algebra booleana

Dise˜ o de Circuitos L´gicos n o Combinatorios utilizando Programaci´n o Gen´tica e

Eduardo Serna P´rez e
Maestr´ en Inteligencia Artificial ıa
Universidad Veracruzana - LANIA

Asesora: Dra. Katya Rodr´ ıguez V´zquez a Departamento de Ingenier´ de Sistemas Computacionales ıa y Automatizaci´n IIMAS-UNAM o Co-asesor: Dr. Carlos A. Coello Coello Centro de Investigaci´n y Estudios Avanzados delIPN o u a e Revisor: Dr. Sa´l Daniel Santill´n Guti´rrez Centro de Dise˜o y Manufactura, Facultad de Ingenier´ UNAM n ıa

Enero, 2001

Resumen
El dise˜o de circuitos l´gicos combinatorios ha sido una de las ´reas n o a abiertas a la investigaci´n en los ultimos a˜os. Este inter´s es debido a lo o ´ n e complejo que resulta su dise˜o y especialmente su simplificaci´n. Por a˜os n o n se hautilizado el ´lgebra booleana como la manera m´s sencilla de elaborar a a e implementar el dise˜o de circuitos l´gicos. Posteriormente se desarrollaron n o diversos m´todos de inspecci´n visual que fueron dirigidos principalmente e o a facilitar su simplificaci´n como los mapas de Karnaugh y el m´todo de o e Quine-McCluskey. En a˜os recientes distintas t´cnicas de b´squeda, optimizaci´n y aprenn e u odizaje, cuya inspiraci´n radica en las teor´ de la evoluci´n y la selecci´n o ıas o o natural, han sido aplicadas para resolver este tipo de problemas. A estas t´cnicas se les conoce como Computaci´n Evolutiva. e o Las t´cnicas evolutivas han comenzado a incursionar en el dise˜o de e n circuitos debido principalmente a su poder exploratorio, ya que permiten evaluar diversas regiones de un espaciode dise˜o y encontrar varias solucion nes a problemas complejos con relativa eficiencia. Actualmente a esta ´rea a se le conoce como Hardware Evolutivo. Diversas t´cnicas evolutivas han sido empleadas en hardware evolutivo. e La implementaci´n presentada en este trabajo esta situada dentro de la Proo gramaci´n Gen´tica, la cual propone la utilizaci´n de cadenas prefijas como o e o individuos parael dise˜o de circuitos l´gicos combinatorios. La programan o ci´n gen´tica es un paradigma interesante y adecuado para este problema o e debido principalmente a su alto poder exploratorio. En la implementaci´n propuesta se realiza una serie de experimentos o con distintos tipos de circuitos, los cuales var´ en grado de complejidad ıan y dimensionalidad. Dichos experimentos tienen como objetivoverificar la capacidad de elaboraci´n de dise˜os l´gicos factibles, que finalmente ser´n o n o a comparados con otras t´cnicas tradicionales y evolutivas. Adem´s, el algoe a ritmo propuesto muestra una gran capacidad para simplificar dise˜os l´gicos n o en un tiempo bastante razonable y un uso de recursos computacionales bajo. i

Agradecimientos
Agradezco a Dolores y Judith su apoyo, amor ycomprensi´n. o A Guadalupe, Fernando, Ximena y Fersillo les expreso un especial agradecimiento por su apoyo continuo y permitirme vivir en Coatepec y convivir en la Ciudad de M´xico. e Gracias a mis dos supervisores, Dra. Katya Rodr´ ıguez V´zquez y Dr. a Carlos Coello Coello por su ayuda y orientaci´n a lo largo de este o trabajo de tesis. Tambi´n quiero darles las gracias a Narely y Nora, por siempre deemostrarme su amistad. Agradezco el apoyo otorgado por CONACyT a trav´s de una beca e para cursar la Maestr´ en Inteligencia Artificial del LANIA y la Uniıa versidad Veracruzana. Gracias al Departamento de Ingenier´ de Sistemas Computacionales ıa y Automatizaci´n del IIMAS-UNAM, por permitirme realizar mi trao bajo de tesis en sus instalaciones. As´ como a todas aquellas personas ı que tuve el agradode conocer en el IIMAS-UNAM. Asimismo, agradezco la beca terminal otorgada por CONACyT para concluir esta tesis de maestr´ a trav´s del proyecto CONACyT ıa, e No. J34900-A.

ii

´ Indice general
Resumen Agradecimientos ´ Indice general ´ Indice de figuras ´ Indice de tablas 1. Introducci´n o 1.1. Motivaci´n . . . . . . . . . . . . . . . . . . . . . . . . . . . . o 1.2. Objetivo . . . . ....