Heurystyczny algorytm syntezy quasi-optymalnych układów odwracalnych

W artykule przedstawiono nową metodę syntezy układów odwracalnych. Polega ona na stopniowym porządkowaniu bitów w kolejnych kolumnach części wyjściowej tablicy prawdy odwracalnej funkcji boolowskiej, aż do momentu zrównania części wyjściowej tablicy z jej częścią wejściową. Długość szacunkowej sekwencji bramek, która uporządkowałaby bity we wszystkich kolumnach wyjściowych, stanowi kryterium wyboru bramki w każdym kroku iteracji proponowanego algorytmu. Dla ponad 80% funkcji odwracalnych trzech zmiennych algorytm ten generuje układy optymalne.

---

In this paper a new method of reversible circuits synthesis is presented. The method is based on iterative ordering of bits in subsequent output columns of the truth table of a reversible function until the output part of the truth table becomes identical with the input part. The length of the estimated shortest sequence which would guarantee the proper order of bits in all output columns is a criterion for choosing a gate at each step of the proposed algorithm. For over 80% of 3-variable reversible functions the algorithm generates optimal circuits.