Repositório Digital

A- A A+

Um método de equivalência de funções Booleanas através de grafos bipartidos

.

Um método de equivalência de funções Booleanas através de grafos bipartidos

Mostrar registro completo

Estatísticas

Título Um método de equivalência de funções Booleanas através de grafos bipartidos
Outro título A method for Boolean functions equivalence through bipartite graphs
Autor Silva, Anderson Santos da
Orientador Ribas, Renato Perez
Data 2013
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Assunto Funções booleanas
Grafos
[en] Bipartirte graph
[en] Boolean mathcing
[en] Graph isomorphism
[en] P-matching
[en] Technology mapping
Resumo Atualmente uma das etapas mais críticas no fluxo de projeto de circuitos integrados é a etapa denominada mapeamento tecnológico. Essa dificuldade se deve ao fato que esta etapa precisa resolver um problema NP-completo denominado equivalência Booleana. A proposta deste trabalho é a de acelerar esse processo representando uma função Booleana através de um grafo bipartido, e utilizar esta estrutura para calcular Pequivalência por permutação, uma etapa da equivalência Booleana. O grafo bipartido gerado é denominado Grafo Bipartido Booleano, ou GBB. Diversos métodos de resolução são apresentados e uma discussão quanto à qualidade deles é exposta. Os resultados mostram que essa estrutura é correta e que pode ser utilizada para calcular eficientemente equivalência por permutação. Trabalhos futuros vão desde estender esta abordagem para outros tipos de equivalência até a utilização do GBB para resolução de outros problemas na área de síntese de circuitos digitais.
Abstract Currently one of the most critical steps in the design flow of integrated circuits is the step called technology mapping. This difficulty is due to the fact that this step needs to solve an NP-complete problem called Boolean matching. The purpose of this work is to accelerate this process representing a Boolean function by a bipartite graph, and use this approach to calculate Boolen equivalence by permutation, a step of Boolean matching. The bipartite graph generated is called Bipartite Boolean Graph, or GBB. Various methods of resolution are presented and a discussion about the quality of them is exposed. The results show that this structure is correct and can be used to efficiently compute equivalence by permutation. Future work will extend from this approach to other types of equivalence to the use of GBB to solving other problems in the field of synthesis of digital circuits.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/86280
Arquivos Descrição Formato
000909809.pdf (516.2Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.