Open AccessThe subject of study of this paper is reversible logic circuits. The irreversibility of computation can lead in the future to significant energy loss during the calculation process. Reversible circuits can be widely used in devices operating under conditions of limited computational resources.
Presently, the problem of reversible logic synthesis is widely studied. The task a synthesis algorithm can face with is to reduce the gate complexity of synthesized circuit. One way to solve this problem is to use equivalent replacement tables for the gate compositions. The disadvantage of this approach is that it is necessary to build replacement tables, it takes a long time to find the replacement in the table, and there is no way to build an appropriate universal replacement table for arbitrary reversible circuit. The aim of this paper is to develop the solution for the problem of gate complexity reduction for the reversible circuits without using equivalent replacement tables for the gate compositions.
This paper makes a generalization of the k-CNOT gate for the case of zero value at some of the gate control inputs. To describe such gates it suggests using a set of direct control inputs and a set of inverted ones. A definition of the independence of two reversible gates is introduced. Two independent gates standing next to each other in the circuit can be swapped without changing the circuit result transformation. Various conditions of the independence of two reversible gates are considered including conditions imposed to the set of direct control inputs and the set of inverted ones. It is proved that two gates are independent if there is, at least, one common control input, which differs only by the type (direct or inverted).
Various equivalent replacements of two k-CNOT gates compositions and its conditions imposed to the set of direct control inputs and to the set of inverted ones are considered. The proof of correctness for such replacements is provided by comparing result transformations of the gate compositions before and after replacement. Operations on the set of direct control inputs and on the set of inverted ones are widely used in the proof. The paper shows that two identical gates being nearby in the circuit can be excluded from it. It also shows that sometimes a composition of two gates can be replaced with the one gate, if the gates differ from each other by only one control input. The part of the equivalent replacements suggests in the paper does not reduce the gate complexity, but allows the new reversible gates to be available. In some cases after applying such replacements a new pair of gates can be found to satisfy the condition of another replacement reducing the gate complexity. The set of equivalent replacements proposed in this paper is significantly expanded comparing to the sets of equivalent replacements described in other papers.
The paper describes the algorithm to reduce the reversible circuit gate complexity using the conditions of the gates independence and the proposed equivalent replacements of gate compositions. The algorithm is based on searching the pair of gates, which satisfy a condition of some replacement and which can be moved to each other without changing the circuit resultant transformation (conditions of gates independence proposed in this paper are checked). An example of using this algorithm in some abstract reversible circuit is offered.
The advantage of the proposed approach is that it does not require replacement tables to be built, and the gate complexity can be reduced for the arbitrary circuit consisted of k-CNOT gates. Further, an assessment of the time complexity of the proposed algorithm of the gate complexity reduction is supposed to be given.