Mostrar el registro sencillo del ítem
Geração de circuitos a partir de BDDs : junção de funções booleanas incompletamente especificadas
dc.contributor.advisor | Kolberg, Mariana Luderitz | pt_BR |
dc.contributor.author | Peralta, Renato Donizete | pt_BR |
dc.date.accessioned | 2022-07-22T04:55:27Z | pt_BR |
dc.date.issued | 2022 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/10183/245356 | pt_BR |
dc.description.abstract | 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%. | pt_BR |
dc.description.abstract | Incompletely specified Boolean functions (a.k.a. Boolean Relations) are defined by their On-set, Off-set, and dc-set (don’t care set). As the dc-set can be assigned either to the On-set or to the Off-set, a Boolean relation can contain several completely specified functions that satisfy the original Boolean Relation. This work proposes an algorithm for the assignment of don’t cares for Boolean relations represented as a couple of Binary Decision Diagrams (BDDs). The algorithm consists of exploring the On-set and Off-set of the input Boolean relation represented as BDDs and join ing them into a third BDD, which will have a lower number of nodes. On average, our algorithm was able to generate coverage with 23.53% of the number of nodes compared to the BDDs of the on-sets of the original Boolean relations. While meth ods such as restrict, constrain and leaf-identifying compaction generated coverage with size around 30%. In addition, the algorithm proved to be effective in reducing the number of input variables, where it presented an average reduction of 15.67%. | en |
dc.format.mimetype | application/pdf | pt_BR |
dc.language.iso | por | pt_BR |
dc.rights | Open Access | en |
dc.subject | Funções booleanas | pt_BR |
dc.subject | Incompletely Specified Boolean Functions | en |
dc.subject | Diagramas : Decisao binaria | pt_BR |
dc.subject | Binary Decision Diagrams | en |
dc.subject | Boolean Relations | en |
dc.title | Geração de circuitos a partir de BDDs : junção de funções booleanas incompletamente especificadas | pt_BR |
dc.title.alternative | Generating circuits from BDDs: joining incompletely specified boolean functions | pt |
dc.type | Dissertação | pt_BR |
dc.contributor.advisor-co | Reis, André | pt_BR |
dc.identifier.nrb | 001145539 | pt_BR |
dc.degree.grantor | Universidade Federal do Rio Grande do Sul | pt_BR |
dc.degree.department | Instituto de Informática | pt_BR |
dc.degree.program | Programa de Pós-Graduação em Computação | pt_BR |
dc.degree.local | Porto Alegre, BR-RS | pt_BR |
dc.degree.date | 2022 | pt_BR |
dc.degree.level | mestrado | pt_BR |
Ficheros en el ítem
Este ítem está licenciado en la Creative Commons License
-
Ciencias Exactas y Naturales (5103)Computación (1758)