Síntese de Circuitos para Computação Reversível Usando Portas Toffoli Generalizadas
Autores
|
7011 |
2026,257,2733,3115
|
|
|
7012 |
2026,257,2733,3115
|
|
|
7013 |
2026,257,2733,3115
|
|
|
7014 |
2026,257,2733,3115
|
Informações:
Publicações do PESC
Apresentamos um novo algoritmo para síntese de circuitos reversíveis a partir de funções bijetivas. O algoritmo proposto usa portas Toffoli generalizadas, que incluem controles positivos e negativos. O algoritmo está dividido em duas partes. Primeiro, usamos portas Toffoli parcialmente controladas, com aumento progressivo do número de controles. Segundo, explorando propriedades de representação de permutações através de ciclos disjuntos, aplicamos portas Toffoli generalizadas com controles em todas as linhas exceto pela linha alvo. Portanto, uma das principais vantagens do algoritmo consiste no fato de obtermos circuitos que primeiro usam portas com custo baixo. Além disso, empregamos estratégias de síntese bidirecional para melhorar o número de portas. Comparamos os resultados obtidos pelo nosso algoritmo de síntese com os melhores resultados conhecidos usando a biblioteca de portas Toffoli generalizadas. Para o conjunto formado por todas as funções bijetivas com 3 bits, obtivemos a média de 5,23 portas por função, que é a melhor média de portas até onde sabemos, exceto para procedimentos que dão resultado exato mas não funcionam com funções bijetivas com mais bits. Isso significa uma melhora de 2,8% quando comparado ao melhor resultado conhecido obtido por uma heurística. Para os experimentos com vinte funções usadas como benchmark, obtivemos resultados semelhantes aos encontrados pelos melhores algoritmos da literatura. Além disso, nosso algoritmo de síntese funciona para um número n qualquer de bits. Propomos também uma nova regra e um novo algoritmo para otimização pós-síntese de circuitos reversíveis usando portas Toffoli generalizadas.
We present a new algorithm for synthesis of reversible circuits from bijective functions. This algorithm uses generalized Toffoli gates, which include positive and negative controls. Our algorithm is divided into two parts. First, we use partially controlled generalized Toffoli gates, progressively increasing the number of controls. Second, exploring the properties of the representation of permutations in disjoint cycles, we apply generalized Toffoli gates with controls on all lines except for the target line. Therefore, new in the method is the fact that the obtained circuits use first low cost gates and consider increasing costs towards the end of the synthesis. In addition, we employ two bidirectional synthesis strategies to improve the gate count, which is the metric used to compare the results obtained by our algorithm with the results presented in the literature. Our experimental results consider all 3-bit bijective functions and twenty widely used benchmark functions. The results obtained by our synthesis algorithm are competitive when compared with the best results known in the literature, considering as a complexity metric just the number of gates, as done by alternative best heuristics found in the literature. For example, for all 3-bit bijective functions using generalized Toffoli gates library, we obtained the best so far average count of 5.23. Our method gives an improvement of 2.8% over the best known result obtained by an heuristic. We also propose a new rule and a new algorithm for post-synthesis optimization of reversible circuits composed of generalized Toffoli gates.