Ghent University Academic Bibliography

Advanced

Multiple-valued reversible logic circuits

Alexis De Vos UGent and Yvan Van Rentergem (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:
author
organization
year
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.