Lógico combinatorios

´ CENTRO DE INVESTIGACION Y DE ESTUDIOS AVANZADOS ´ DEL INSTITUTO POLITECNICO NACIONAL ´ IA DEPARTAMENTO DE INGENIER´ ELECTRICA ´ DE COMPUTACION ´ SECCION

Dise˜ o de circuitos l´gicos combinatorios n o usando optimizaci´n mediante c´ mulos de o u part´ ıculas
Tesis que presenta Erika Hern´ndez Luna a Para obtener el grado de Maestro en Ciencias En la especialidad de Ingenier´ El´ctrica ıa eOpci´n Computaci´n o o

Director de Tesis: Dr. Carlos A. Coello Coello M´xico, D.F., febrero 2004 e

Resumen
En esta tesis se propone un algoritmo para el dise˜ o y la posterior optin mizaci´n de circuitos l´gicos combinatorios a nivel de compuertas usando un o o algoritmo de optimizaci´n mediante c´ mulos de part´ o u ıculas y tres enfoques de representaci´n distintos: binaria, entera A yentera B . A pesar de que o existen muchos criterios para determinar cual es el dise˜o de costo m´ n ınimo de un circuito, en este trabajo se utiliza una m´trica basada en el n´ mero de e u compuertas necesarias para la implementaci´n en hardware del circuito. o El algoritmo de optimizaci´n mediante c´ mulos de part´ o u ıculas (Particle Swarm Optimization PSO) es una t´cnica de optimizaci´nnum´rica de fune o e ciones no lineales que se encuentra influenciada fuertemente por algunas otras corrientes como vida artificial, psicolog´ social, ingenier´ y ciencias de la ıa ıa computaci´n, que ha conseguido su ´xito gracias a que tiene un bajo costo o e computacional, una f´cil implementaci´n y un excelente desempe˜ o. a o n Las t´cnicas evolutivas han sido sumamente utiles en el proceso de dise˜ oe ´ n de circuitos electr´nicos debido a su poder exploratorio, pues al contar con o una poblaci´n de soluciones potenciales permiten evaluar diversas regiones o del espacio de dise˜ o. n e n n Tambi´n se ha visto a los largo de los a˜os que el dise˜ o de circuitos mediante las metodolog´ tradicionales es un proceso complejo que requieıas re de tiempo y experiencia por parte del dise˜ador humano,por lo que se n pretende que al utilizar t´cnicas evolutivas puedan hallarse dise˜os que son e n radicalmente diferentes que los encontrados hasta el momento por estos dise˜ adores. n El PSO ha utilizado una representaci´n binaria y frecuentemente una reo presentaci´n real para codificar las soluciones de los problemas, sin embargo o en este trabajo adem´s de presentarse una versi´n binaria, sehicieron los a o ajustes necesarios para presentar tambi´n una propuesta basada en dos enfoe ques distintos de una versi´n entera del algoritmo de optimizaci´n mediante o o c´ mulos de part´ u ıculas para el dise˜ o de circuitos l´gicos combinatorios a nivel n o de compuertas. Los dos enfoques de la representaci´n entera y el de la versi´n binaria o o del algoritmo propuesto se validaron usandoalgunos ejemplos tomados de la literatura y comparados contra otros tres enfoques: el dise˜o realizado por n un experto humano, el dise˜ o resultante de aplicar el algoritmo gen´tico de n e cardinalidad N (NGA), y el dise˜ o obtenido aplicando el algoritmo gen´tico n e multiobjetivo (MGA). iii

iv

Abstract
This thesis presents an algorithm for the design and the optimization of combinationallogic circuits at gate-level using a particle swarm optimization algorithm and three different representation approaches: binary, integer A and integer B. Although there are many criteria to determine the minimalcost circuit design, in this work we used a metric based on the number of gates necessaries for the hardware implementation of the circuit. The Particle Swarm Optimization (PSO) algorithm isa numerical optimization technique for nonlinear functions that is strongly influenced by other areas such as artificial life, social psychology and computer science. PSO has been very successful because it has a low computacional cost, an easy implementation and an excellent performance. Evolutionary techniques have been very useful for designing electronic circuits due to their exploratory...