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