Difference method of reversible circuits synthesis

W niniejszej pracy przedstawiony jest prosty algorytm projektowania układów odwracalnych. Proponowany algorytm polega na wyznaczeniu dla danej funkcji zbioru bramek (nazywanego zbiorem bramek pierwszych), które mogą znajdować się na początku układu kaskadowego realizującego zadaną funkcję. Po wyznaczeniu takiego zbioru można wybrać jeden z jego elementów, a następnie powtórzyć algorytm dla tzw. funkcji resz-towej. Postępuje się tak, aż do momentu, gdy funkcja resztowa stanie się funkcją identycznościową. Liczba iteracji algorytmu jest równa liczbie bramek projektowanej kaskady.Research on reversible logic circuits is motivated by advances in quantum computing, nanotechnology and low-power design. Im-plementation of such functions is realized by special gates. These gates always form a cascade circuit. Minimization of such circuits is a very difficult problem. In this paper a novel concept of synthesis of reversible logic is presented. For simplicity, the method is described for three variables only but it is scalable for more variables. The proposed method is based on XOR function applied to input and output sides of the truth table of a function to be synthesized. The result of applying XOR function indicates bits in the truth table which have to be changed by reversible gates. Due to this property the number of analyzed gates is small. We present the comparison of three variants of the difference method. Each of them leads to different numbers of 3-variable functions for which exact optimal circuits have been found