Multiple-Valued Reversible Logic Circuits

摘要

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 S_r~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.