Show simple item record

dc.contributor.advisorReis, Andre Inaciopt_BR
dc.contributor.authorBrandão, Eduarde David Freitaspt_BR
dc.date.accessioned2024-08-15T06:31:09Zpt_BR
dc.date.issued2021pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/277380pt_BR
dc.description.abstractEsta dissertação apresenta uma contribuição para a geração de circuitos digitais a partir de diagramas de decisão binários (BDDs). Existe um método trivial para síntese de circuitos digitais a partir de BDDs onde cada nodo do BDD é mapeado diretamente para um multiplexador em uma correspondência um para um, ou seja: um nodo, um multiplexador. Este método é possível porque cada nodo do BDD é uma decomposição de Shannon que pode ser implementada como um multiplexador. Porém, simplificações podem ser aplicadas no circuito do multiplexador de nodos específicos, dependendo de propriedades da função Booleana representada em cada nodo específico. Esta dissertação cataloga e apresenta simplificações para o circuito do multiplexador baseado em condições apresentadas por nodos de BDDs. Foi também implementado um método para gerar circuitos a partir de BDDs usando a correspondência um para um com os multiplexadores simplificados (conforme o caso) ao invés de utilizar os multiplexadores completos. O método utilizando as simplificações leva a uma redução no número de portas lógicas necessárias para implementar o circuito final, quando comparado com a versão que implementa multiplexadores completos (sem as simplificações). Para os benchmarks apresentados, o método apresenta uma redução de 27.9% no número total de nodos, quando comparado com a versão que não utiliza as simplificações.pt_BR
dc.description.abstractThis dissertation presents a contribution to the generation of digital circuits from binary decision diagrams (BDDs). There is a trivial method for synthesizing digital circuits from BDDs where each node of the BDD is mapped directly to a multiplexer in a one-to-one correspondence, that is: one node, one multiplexer. This method is possible because each BDD node is a Shannon decomposition that can be implemented as a multiplexer. However, simplifications can be applied to the multiplexer circuit of specific nodes, depending on properties of the Boolean function represented in each specific node. This dissertation catalogs and presents simplifications for the multiplexer circuit based on conditions presented by BDD nodes. A method was also implemented to generate circuits from BDDs using one-to-one correspondence with simplified multiplexers (as applicable) instead of using full multiplexers. The method using simplifications leads to a reduction in the number of logic gates required to implement the final circuit, when compared to the version that implements complete multiplexers (without simplifications). For the benchmarks presented, the method presents a reduction of 27.9% in the total number of nodes, when compared to the version that does not use the simplifications.en
dc.format.mimetypeapplication/pdfpt_BR
dc.language.isoporpt_BR
dc.rightsOpen Accessen
dc.subjectAnd inverter graphs (AIGs)en
dc.subjectDiagramas de decisão bináriapt_BR
dc.subjectSíntese lógicapt_BR
dc.subjectShannon decompositionen
dc.subjectMapeamento tecnologicopt_BR
dc.subjectMultiplexorsen
dc.subjectCircuitos digitaispt_BR
dc.subjectFunções booleanaspt_BR
dc.titleGeração de circuitos a partir de BDDs : simplificações possíveis a partir da decomposição de shannonpt_BR
dc.typeDissertaçãopt_BR
dc.identifier.nrb001208902pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Informáticapt_BR
dc.degree.programPrograma de Pós-Graduação em Computaçãopt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2024pt_BR
dc.degree.levelmestradopt_BR


Files in this item

Thumbnail
   

This item is licensed under a Creative Commons License

Show simple item record