Multiple-Valued Reversible Logic Circuits
Alexis De Vos and Yvan Van Rentergem
We consider the symmetric group Sn in the special case where n = pq (both p and q being integer). Applying Birkhoff’s theorem, we prove that an arbitrary element of Spq can be decomposed into a product of three permutations, the first and the third being elements of the Young subgroup Sqp, whereas the second one is an element of the dual Young subgroup Spq . This leads to synthesis methods for arbitrary multiple-valued reversible logic circuits of logic width ω. These circuits indeed form a group isomorphic to Srω , where r is the radix of the multiple-valued logic. A particularly efficient decomposition is found by choosing p = r and thus q = rω−1. As a result, an arbitrary reversible logic circuit of radix r and width ω is decomposed into a cascade of 2ω -1 control gates, i.e. logic building blocks, which manipulate only one of the ω dits.
Keywords: Multiple-valued logic, reversible computing, group theory, Young subgroup, Birkhoff’s theorem, Clos network.