### Multiple-valued reversible logic circuits

(2009) JOURNAL OF MULTIPLE-VALUED LOGIC AND SOFT COMPUTING. 15(5-6). p.489-505- abstract
- 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.

Please use this url to cite or link to this publication:
http://hdl.handle.net/1854/LU-818124

- author
- Alexis De Vos UGent and Yvan Van Rentergem
- organization
- year
- 2009
- type
- journalArticle (original)
- publication status
- published
- subject
- keyword
- ALGORITHMS, GATES, UNIVERSALITY, CLOS NETWORKS, SWITCHING-NETWORKS, Clos network, Birkhoff's theorem, reversible computing, multiple-valued logic, Young subgroup, group theory
- journal title
- JOURNAL OF MULTIPLE-VALUED LOGIC AND SOFT COMPUTING
- J. Mult.-Valued Log. Soft Comput.
- volume
- 15
- issue
- 5-6
- pages
- 489 - 505
- Web of Science type
- Article
- Web of Science id
- 000271530500005
- JCR category
- COMPUTER SCIENCE, ARTIFICIAL INTELLIGENCE
- JCR impact factor
- 0.343 (2009)
- JCR rank
- 96/102 (2009)
- JCR quartile
- 4 (2009)
- ISSN
- 1542-3980
- language
- English
- UGent publication?
- yes
- classification
- A1
- copyright statement
*I have transferred the copyright for this publication to the publisher*- id
- 818124
- handle
- http://hdl.handle.net/1854/LU-818124
- date created
- 2010-01-05 14:52:44
- date last changed
- 2010-01-18 16:39:56

@article{818124, abstract = {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.}, author = {De Vos, Alexis and Van Rentergem, Yvan}, issn = {1542-3980}, journal = {JOURNAL OF MULTIPLE-VALUED LOGIC AND SOFT COMPUTING}, keyword = {ALGORITHMS,GATES,UNIVERSALITY,CLOS NETWORKS,SWITCHING-NETWORKS,Clos network,Birkhoff's theorem,reversible computing,multiple-valued logic,Young subgroup,group theory}, language = {eng}, number = {5-6}, pages = {489--505}, title = {Multiple-valued reversible logic circuits}, volume = {15}, year = {2009}, }

- Chicago
- De Vos, Alexis, and Yvan Van Rentergem. 2009. “Multiple-valued Reversible Logic Circuits.”
*Journal of Multiple-valued Logic and Soft Computing*15 (5-6): 489–505. - APA
- De Vos, Alexis, & Van Rentergem, Y. (2009). Multiple-valued reversible logic circuits.
*JOURNAL OF MULTIPLE-VALUED LOGIC AND SOFT COMPUTING*,*15*(5-6), 489–505. - Vancouver
- 1.De Vos A, Van Rentergem Y. Multiple-valued reversible logic circuits. JOURNAL OF MULTIPLE-VALUED LOGIC AND SOFT COMPUTING. 2009;15(5-6):489–505.
- MLA
- De Vos, Alexis, and Yvan Van Rentergem. “Multiple-valued Reversible Logic Circuits.”
*JOURNAL OF MULTIPLE-VALUED LOGIC AND SOFT COMPUTING*15.5-6 (2009): 489–505. Print.