Algoritmos para a síntese de circuitos reversíveis ternários: análise comparativa

• Ano de defesa: 2018
• Autor(a) principal: Barbieri, Caroline Domingues Porto do Nascimento
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Estadual Paulista (Unesp)
• Palavras-chave em Português: Lógica ternária; Computação quântica; Síntese de circuitos reversíveis; Permutação; Ciclos de permutação disjuntos; Algoritmo genético; Ternary logic; Quantum computation; Synthesis of reversible circuits; Permutation; Disjunct permutation cycles; Genetic algorithm
• Link de acesso: http://hdl.handle.net/11449/157098

A lógica de múltiplos valores, em especial a ternária, apresenta inúmeras vantagens sobre a lógica binária em circuitos reversíveis/quânticos. A realização de funções usando a lógica reversível ternária é conhecida por requerer um menor número de linhas em comparação com a lógica reversível binária convencional. Este aspecto tem motivado as pesquisas em abordagens de síntese. A grande maioria dos métodos existentes requerem entradas adicionais, denominadas de ancillary lines, durante o processo de síntese, o que é dispendioso para implementação em tecnologias quânticas, quando disponíveis. Neste trabalho, foram propostas diferentes metodologias e análises comparativas para o problema da síntese de circuitos reversíveis ternários sem a adição de ancillary lines. A metodologia de síntese proposta, denominada de MMD plus, foi aplicado nos modos backward e top-down como referência a todas as 362880 possíveis funções reversíveis ternárias de 2 variáveis. Além do processamento top-down originário do algoritmo MMD, um processamento bottom-up é implementado e sua eficiência comparativa é avaliada. Por definição, as funções reversíveis ternárias são permutações. Realiza-se a decomposição das permutações em ciclos disjuntos de ordem natural, em ciclos de permutação com 3 elementos, e em transposições, para obtenção dos circuitos reversíveis ternários. Uma métrica é introduzida para mensurar a complexidade e custo dos circuitos, com base nas portas reversíveis de múltiplos valores Muthukrishnan-Stroud (MS). A eficiência do procedimento de síntese do MMD plus empregado aos ciclos de permutação é avaliada e comparada com a aplicação direta, isto é, sem decomposição das permutações em ciclos. Em seguida, propõem-se duas metodologias com base em Algoritmos Genéticos para o projeto de circuitos reversíveis ternários como um problema de otimização, utilizando-se, também, das portas MS. A influência de diferentes tipos de seleção e variação do tamanho dos indivíduos é avaliada em relação à quantidade de portas e custos dos circuitos resultantes da síntese.