a general decomposition for reversible logic m perkowsk：可逆逻辑m perkowsk一般分解

A General Decomposition for Reversible LogicM. Perkowski, L. Jozwiak#, P. Kerntopf+, A. Mishchenko, A. Al-Rabadi, A. Coppola, A. Buller*, X. Song, M. Md. Mozammel Huq Azad Khan thus the vector of input states can be always reconstructed from the vector of output states. 000 000001 001010 010011 011100 100101 101 110 110111 111INPUTS OUTPUTS2 43 64 25 36 5(2,4)(365)Reversible logicReversible are circuits (gates) that have the same number of inputs and outputs and have one-to-one mapping between vectors of inputs and outputs; thus the vector of input states can be always reconstructed from the vector of output states. 000 000001 001010 010011 011100 100101 101 110 110111 111INPUTS OUTPUTSFeedback not allowedFan-out not allowed2 43 64 25 36 5(2,4)(365)Reversible logic constraintsFeedback not allowed in combinational partFan-out not allowedIn some papers allowed under certain conditionsIn some papers allowed in a limited way in a “near reversible” circuitTo understand reversible logic, it is useful to have intuitive feeling of various models of its realization.Conservative Reversible GatesDefinitions A gate with k inputs and k outputs is called a k*k gate. A conservative circuit preserves the number of logic values in all combinations. In balanced binary logic the circuit has half of minterms with value 1.Billiard Ball Model DEFLECTIONSHIFTDELAY This is described in E. Fredkin and T. Toffoli, “Conservative Logic”, Int. J.Theor. Phys. 21,219 (1982).Billiard Ball Model (BBM)Input outputA B 1 2 3 40 0 0 0 0 00 1 0 1 0 01 0 0 0 1 01 1 1 0 0 1A and BAB A and B B and NOT AA and NOT BThis is called interaction gateThis illustrates principle of conservation (of the number of balls, or energy) in conservative logic. Interaction gateInput outputA B z1 z2 z3 z40 0 0 0 0 00 1 0 1 0 01 0 0 0 1 01 1 1 0 0 1Z1= A and BABZ4 = A and B Z2 = B and NOT AZ3 = A and NOT BABZ1= A and BZ2 = B and NOT AZ3 = A and NOT BZ4 = A and B Inverse Interaction gateoutputinputA Bz1 z2 z3 z40 0 0 0 0 00 1 0 0 0 10 0 1 0 1 01 0 0 1 1 1Z1= A and BABZ4 = A and B Z2 = B and NOT AZ3 = A and NOT BOther input combinations not allowedz1z3z2z4ABDesigning with this types of gates is difficultBilliard Ball Model (BBM)Input outputA B z1 z2 z3 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 0 1 1 1AB23Z1 = NOT A * BZ2 = A * BZ3 = A switchPriese Switch GateInput outputA B z1 z2 z3 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 1 1 0 1 1 1AB23Z1 = NOT A * BZ2 = A * BZ3 = A ABInverse Priese Switch GateoutputinputA B z1 z2 z3 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 1 1 z1ABz2z3Z3 Z1 ABZ2 Inverter and Copier Gates from Priese GateZ1 = NOT A * 1garbagegarbage A1garbageV2 = B * 1V3 = B B1 Garbage outputs shown in greenInverter realized with two garbagesCopier realized with one garbageInput constants The 2*2 Feynman gate, called also controled-not or quantum XOR realizes functions P = A, Q = A B, where operator denotes EXOR When A = 0 then Q = B, when A = 1 then Q = B. Every linear reversible function can be built by composing only 2*2 Feynman gates and inverters With B=0 Feynman gate is used as a fan-out gate. (Copying gate)Feynman Gate+A BP QFeynman Gate from PrieseZ1 = NOT A * BZ2 = A * BZ3 = A ABV1 = NOT B * AV2 = B * AV3 = B BABABFan-out 1Garbage outputs Z2 and V2 shown in greenFredkin GateFredkin Gate is a fundamental concept in reversible and quantum computing. Every Boolean function can be build from 3 * 3 Fredkin gates: P = A, Q = if A then C else B, R = if A then B else C. Notation for Fredkin GatesA 0 1 0 1C B PQ RA 0 1PB C Q R A circuit from two multiplexersIts schemataThis is a reversible gate, one of manyC