Designing Parity Preserving Reversible Circuits

With the emergence of reversible circuits as an energy-efficient alternative of classical circuits, ensuring fault tolerance in such circuits becomes a very important problem. Parity-preserving reversible logic design is one viable approach towards fault detection. Interestingly, most of the existing designs are ad hoc, based on some pre-defined parity preserving reversible gates as building blocks. In the current work, we propose a systematic approach towards parity preserving reversible circuit design. We prove a few theoretical results and present two algorithms, one from reversible specification to parity preserving reversible specification and another from irreversible specification to parity preserving reversible specification. We derive an upper-bound for the number of garbage bits for our algorithm and perform its complexity analysis. We also evaluate the effectiveness of our approach by extensive experimental results and compare with the state-of-the-art practices. To our knowledge, this is the first work towards systematic design of parity preserving reversible circuit and more research is needed in this area to make this approach more scalable.