Bijective mapping of arbitrary finite state machine
Satrajit Ghosh, Biswanath Sen, Rajib Das · 2014
Reversible Computation is of interest, because it is associated with ultra low power computing. Design and analysis of a reversible sequential circuit is an interesting research problem. State of the art design decomposes a sequential circuit into smaller modules. Then each module is implemented using known reversible circuits like Toffoli Gate, Peres Gate, Fredkin Gate, Picton Gate, and Rice Gate. This approach is inherently intractable in nature. In this work a more efficient approach is proposed that performs a detail analysis of the State Diagram. Redundancy in a state diagram arises if a “next-state” is attained from more than one “present state”. Irredundant description of such a state diagram is possible, if each state is encoded with a binary number and some ancillary bits are used to distinguish the “identical states”. This is helpful in designing a complex system that involves complex interconnection of a large number of sequential circuits.