Dissertação de Mestrado de Renato Donizete Peralta

DEFESA DE DISSERTAÇÃO DE MESTRADO

Aluno: Renato Donizete Peralta
Orientadora: Profª. Drª. Mariana Luderitz Kolberg Fernandes
Coorientador: Prof. Dr. André Inácio Reis

Título: Geração de Circuitos a Partir de BDDs: Junção de Funções Booleanas Incompletamente Especificadas.
Linha de Pesquisa: Ferramentas para Automação de Projeto Eletrônico

Data: 17/05/2022
Horário: 10h
Esta banca ocorrerá excepcionalmente de forma totalmente remota. Interessados em assistir a defesa poderão acessar a sala virtual através do link: https://mconf.ufrgs.br/webconf/00047815

Banca Examinadora:
Prof. Dr. Felipe de Sousa Marques (UFPEL)
Prof. Dr. José Rodrigo Furlanetto Azambuja (UFRGS)
Prof. Dr. Claudio Machado Diniz (UFRGS)

Presidente da Banca: Profª. Drª. Mariana Luderitz Kolberg Fernandes

Resumo: Funções booleanas especificadas incompletamente (também conhecidas como relações booleanas) são definidas por seu On-set, Off-set e Dc-set (Don’t care set). Como o conjunto DC-set pode ser atribuído ao On-set ou ao Off-set, uma relação booleana pode conter várias funções completamente especificadas que satisfaçam a relação booleana original. Este trabalho propõe um algoritmo para a atribuição de don’t cares para relações booleanas representadas como um par de Binary Decision Diagrams (BDDs). O algoritmo consiste em explorar o On-set e Off-set da relação booleana de entrada representada como BDDs e juntá-los em um terceiro BDD, que terá um número menor de nodos. Em média, nosso algoritmo foi capaz de gerar coberturas com 23,53% do número de nodos comparado aos BDDs dos On-sets das relações booleanas originais. Enquanto que métodos como restrict, constrain e leaf-identifying compaction geraram coberturas com tamanho em torno de 30%. Além disso, o algoritmo mostrou-se eficaz na redução do número de variáveis de entrada, onde apresentou uma redução média de 15,67%.

Palavras-chave: Funções Booleanas Incompletamente Especificadas. Diagrama de Decisão Binária. Relações Booleanas.