Reversible Computing: Review of the Problem and New Results (Fault Tolerance and Cryptography)

Abstract

The paper considers the main provisions of reversibility as a new paradigm for the development of computer technology. The first sections are of an overview nature. The inevitability of the so-called “heat curse” while maintaining the traditional paradigm of creating means of computer engineering. The fundamentals of reversible logic are presented, the main reversible logic elements and models of reversible computations, including reversible cellular automata, are considered. Reversible pro-gramming languages are briefly reviewed. The second part addresses the basic issues of the logical synthesis of circuits from reversible elements and the physical implementation of reversible circuitry. The synthesis of fault-tolerant circuits in the paradigm of reversible circuitry is briefly described. A technique for synthesizing fault-tolerant reversible elements in a hamming space is proposed and some such schemes are described. Next, the problems of using circuits of reversible logic elements in cryp-tography are considered. The proposed general scheme for creating reversible schemes with “garbage collection” intended for cryptographic applications is described.

Keywords

• reversible logic
• reversible logic elements
• fault-tolerant circuits
• hamming space
• information protection
• reversible circuits with “garbage collection”