Esta dissertação investiga a aplicação dos algoritmos evolucionários inspirados na computação quântica na síntese de circuitos sequenciais. Os sistemas digitais sequenciais representam
uma classe de circuitos que é capaz de executar operações em uma determinada sequência.
Nos circuitos sequenciais, os valores dos sinais de saída dependem não só dos valores dos sinais
de entrada como também do estado atual do sistema. Os requisitos cada vez mais exigentes
quanto à funcionalidade e ao desempenho dos sistemas digitais exigem projetos cada vez mais
eficientes. O projeto destes circuitos, quando executado de forma manual, se tornou demorado
e, com isso, a importância das ferramentas para a síntese automática de circuitos cresceu rapidamente.
Estas ferramentas conhecidas como ECAD (Electronic Computer-Aided Design) são
programas de computador normalmente baseados em heurísticas. Recentemente, os algoritmos
evolucionários também começaram a ser utilizados como base para as ferramentas ECAD. Estas
aplicações são referenciadas na literatura como eletrônica evolucionária. Os algoritmos mais
comumente utilizados na eletrônica evolucionária são os algoritmos genéticos e a programação
genética. Este trabalho apresenta um estudo da aplicação dos algoritmos evolucionários inspirados
na computação quântica como uma ferramenta para a síntese automática de circuitos
sequenciais. Esta classe de algoritmos utiliza os princípios da computação quântica para melhorar
o desempenho dos algoritmos evolucionários. Tradicionalmente, o projeto dos circuitos
sequenciais é dividido em cinco etapas principais: (i) Especificação da máquina de estados;
(ii) Redução de estados; (iii) Atribuição de estados; (iv) Síntese da lógica de controle e (v)
Implementação da máquina de estados. O Algoritmo Evolucionário Inspirado na Computação
Quântica (AEICQ) proposto neste trabalho é utilizado na etapa de atribuição de estados. A
escolha de uma atribuição de estados ótima é tratada na literatura como um problema ainda
sem solução. A atribuição de estados escolhida para uma determinada máquina de estados
tem um impacto direto na complexidade da sua lógica de controle. Os resultados mostram que
as atribuições de estados obtidas pelo AEICQ de fato conduzem à implementação de circuitos
de menor complexidade quando comparados com os circuitos gerados a partir de atribuições
obtidas por outros métodos. O AEICQ e utilizado também na etapa de síntese da lógica de
controle das máquinas de estados. Os circuitos evoluídos pelo AEICQ são otimizados segundo
a área ocupada e o atraso de propagação. Estes circuitos são compatíveis com os circuitos
obtidos por outros métodos e em alguns casos até mesmo superior em termos de área e de
desempenho, sugerindo que existe um potencial de aplicação desta classe de algoritmos no
projeto de circuitos eletrônicos. / This thesis investigates the application of quantum inspired evolutionary algorithms in
the synthesis of sequential circuits. Sequential digital systems represent a class of circuit that
is able to execute operations in a particular sequence. In sequential circuits, the values of
output signals not only depend on the values of input signals but also on the current state of
the system. The increasingly high requirements regarding the functionality and performance of
digital systems demand more efficient designs. The design of these circuits, when implemented
manually, became slow and thus the importance of tools for automatic synthesis of circuits
grew rapidly. These tools known as ECAD (Electronic Computer-Aided Design) are computer
programs usually based on heuristics. Recently, evolutionary algorithms also began to be
used as a basis in ECAD tools developing. These applications are referenced in literature as
evolutionary electronics. The algorithms most commonly used in evolutionary electronics are
genetic algorithms and genetic programming. This work presents a study of the application
of quantum inspired evolutionary algorithms as a tool for automatic synthesis of sequential
circuits. This class of algorithms uses the principles of quantum computing to improve the
performance of evolutionary algorithms. Traditionally, the design of sequential circuits is divided
into five main steps: (i) State machine specification; (ii) Reduction of states; (iii) State
assignment; (iv) Control logic synthesis and (v) Implementation of the state machine. The
proposed algorithm AEICQ is used in the state assignment design step. The choice of an
optimal state assignment is treated in the literature as an issue still unresolved. The state
assignment chosen for a particular state machine has a direct impact on the complexity of its
control logic. The results show that the state assignment obtained by AEICQ in fact leads
to the implementation of circuits of less complexity when compared with the ones generated
from assignments obtained by other methods. The AEICQ is also used in the control logic
synthesis of the state machine. The circuits evolved by AEICQ are optimized according to
the area occupied and the propagation delay. These circuits are compatible with the circuits
obtained by other methods and in some cases even higher in terms of area and performance,
suggesting that there is a potential for application of this class of algorithms in the design of
electronic circuits.
| Identifer | oai:union.ndltd.org:IBICT/urn:repox.ist.utl.pt:BDTD_UERJ:oai:www.bdtd.uerj.br:4965 |
| Date | 04 December 2008 |
| Creators | Marcos Paulo Mello Araujo |
| Contributors | Nadia Nedjah, Luiza de Macedo Mourelle, Marley Maria Bernardes Rebuzzi Vellasco, Leandro dos Santos Coelho |
| Publisher | Universidade do Estado do Rio de Janeiro, Programa de Pós-Graduação em Engenharia Eletrônica, UERJ, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UERJ, instname:Universidade do Estado do Rio de Janeiro, instacron:UERJ |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0029 seconds