Garbage-free reversible integer multiplication with constants of the form 2k±2l±1

Holger Bock Axelsen; Michael Kirkedal Thomsen

doi:10.1007/978-3-642-36315-3_14

Garbage-free reversible integer multiplication with constants of the form 2^k±2^l±1

Holger Bock Axelsen, Michael Kirkedal Thomsen

Department of Computer Science

Abstract

Multiplication of integers is non-injective and, thus, requires garbage lines for any reversible logic implementation. However, multiplying with a fixed constant is injective, and should therefore be implementable in reversible logic without garbage. Despite this, the only reported circuits for constant multiplication without garbage are restricted to powers of 2, i.e., the multiplication is a simple bit-shift. Here, we show how to generate a garbage-free linear-depth reversible logic circuit for multiplying an input integer with a constant of the form 2^k ±1 or 2^k ±2^l ±1, by building on a simple strength reduction to addition. Using several such circuits in sequence allows us to support a greater variety of constants. This enables wider use of constant multiplication in garbage-free reversible circuits than was previously possible.

Original language	English
Title of host publication	Reversible Computation : 4th International Workshop, RC 2012, Copenhagen, Denmark, July 2-3, 2012. Revised Papers
Editors	Robert Glück, Tetsuo Yokoyama
Number of pages	12
Publisher	Springer
Publication date	2013
Pages	171-182
ISBN (Print)	978-3-642-36314-6
ISBN (Electronic)	978-3-642-36315-3
DOIs	https://doi.org/10.1007/978-3-642-36315-3_14
Publication status	Published - 2013
Event	4th International Workshop on Reversible Computation - København, Denmark Duration: 2 Jul 2012 → 3 Jul 2012 Conference number: 4

Conference

Conference	4th International Workshop on Reversible Computation
Number	4
Country/Territory	Denmark
City	København
Period	02/07/2012 → 03/07/2012

Series	Lecture notes in computer science
Volume	7581
ISSN	0302-9743

Access to Document

10.1007/978-3-642-36315-3_14

Cite this

Axelsen, H. B., & Thomsen, M. K. (2013). Garbage-free reversible integer multiplication with constants of the form 2^k±2^l±1. In R. Glück, & T. Yokoyama (Eds.), Reversible Computation: 4th International Workshop, RC 2012, Copenhagen, Denmark, July 2-3, 2012. Revised Papers (pp. 171-182). Springer. Lecture notes in computer science Vol. 7581 https://doi.org/10.1007/978-3-642-36315-3_14

Garbage-free reversible integer multiplication with constants of the form 2^k±2^l±1. / Axelsen, Holger Bock; Thomsen, Michael Kirkedal.

Reversible Computation: 4th International Workshop, RC 2012, Copenhagen, Denmark, July 2-3, 2012. Revised Papers. ed. / Robert Glück; Tetsuo Yokoyama. Springer, 2013. p. 171-182 (Lecture notes in computer science, Vol. 7581).

Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review

Axelsen, HB & Thomsen, MK 2013, Garbage-free reversible integer multiplication with constants of the form 2^k±2^l±1. in R Glück & T Yokoyama (eds), Reversible Computation: 4th International Workshop, RC 2012, Copenhagen, Denmark, July 2-3, 2012. Revised Papers. Springer, Lecture notes in computer science, vol. 7581, pp. 171-182, 4th International Workshop on Reversible Computation, København, Denmark, 02/07/2012. https://doi.org/10.1007/978-3-642-36315-3_14

Axelsen, Holger Bock ; Thomsen, Michael Kirkedal. / Garbage-free reversible integer multiplication with constants of the form 2^k±2^l±1. Reversible Computation: 4th International Workshop, RC 2012, Copenhagen, Denmark, July 2-3, 2012. Revised Papers. editor / Robert Glück ; Tetsuo Yokoyama. Springer, 2013. pp. 171-182 (Lecture notes in computer science, Vol. 7581).

@inproceedings{0690af6f4fc448198c8fa15501b28fa2,

title = "Garbage-free reversible integer multiplication with constants of the form 2k±2l±1",

abstract = "Multiplication of integers is non-injective and, thus, requires garbage lines for any reversible logic implementation. However, multiplying with a fixed constant is injective, and should therefore be implementable in reversible logic without garbage. Despite this, the only reported circuits for constant multiplication without garbage are restricted to powers of 2, i.e., the multiplication is a simple bit-shift. Here, we show how to generate a garbage-free linear-depth reversible logic circuit for multiplying an input integer with a constant of the form 2k ±1 or 2k ±2l ±1, by building on a simple strength reduction to addition. Using several such circuits in sequence allows us to support a greater variety of constants. This enables wider use of constant multiplication in garbage-free reversible circuits than was previously possible.",

keywords = "Reversible circuits, logic design, constant multipliers, garbage-free",

author = "Axelsen, {Holger Bock} and Thomsen, {Michael Kirkedal}",

year = "2013",

doi = "10.1007/978-3-642-36315-3_14",

language = "English",

isbn = "978-3-642-36314-6",

series = "Lecture notes in computer science",

publisher = "Springer",

pages = "171--182",

editor = "Robert Gl{\"u}ck and Tetsuo Yokoyama",

booktitle = "Reversible Computation",

note = "4th International Workshop on Reversible Computation, RC 2012 ; Conference date: 02-07-2012 Through 03-07-2012",

}

TY - GEN

T1 - Garbage-free reversible integer multiplication with constants of the form 2k±2l±1

AU - Axelsen, Holger Bock

AU - Thomsen, Michael Kirkedal

N1 - Conference code: 4

PY - 2013

Y1 - 2013

N2 - Multiplication of integers is non-injective and, thus, requires garbage lines for any reversible logic implementation. However, multiplying with a fixed constant is injective, and should therefore be implementable in reversible logic without garbage. Despite this, the only reported circuits for constant multiplication without garbage are restricted to powers of 2, i.e., the multiplication is a simple bit-shift. Here, we show how to generate a garbage-free linear-depth reversible logic circuit for multiplying an input integer with a constant of the form 2k ±1 or 2k ±2l ±1, by building on a simple strength reduction to addition. Using several such circuits in sequence allows us to support a greater variety of constants. This enables wider use of constant multiplication in garbage-free reversible circuits than was previously possible.

AB - Multiplication of integers is non-injective and, thus, requires garbage lines for any reversible logic implementation. However, multiplying with a fixed constant is injective, and should therefore be implementable in reversible logic without garbage. Despite this, the only reported circuits for constant multiplication without garbage are restricted to powers of 2, i.e., the multiplication is a simple bit-shift. Here, we show how to generate a garbage-free linear-depth reversible logic circuit for multiplying an input integer with a constant of the form 2k ±1 or 2k ±2l ±1, by building on a simple strength reduction to addition. Using several such circuits in sequence allows us to support a greater variety of constants. This enables wider use of constant multiplication in garbage-free reversible circuits than was previously possible.

KW - Reversible circuits

KW - logic design

KW - constant multipliers

KW - garbage-free

U2 - 10.1007/978-3-642-36315-3_14

DO - 10.1007/978-3-642-36315-3_14

M3 - Article in proceedings

SN - 978-3-642-36314-6

T3 - Lecture notes in computer science

SP - 171

EP - 182

BT - Reversible Computation

A2 - Glück, Robert

A2 - Yokoyama, Tetsuo

PB - Springer

T2 - 4th International Workshop on Reversible Computation

Y2 - 2 July 2012 through 3 July 2012

ER -