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

Datalogisk Institut

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.

Originalsprog	Engelsk
Titel	Reversible Computation : 4th International Workshop, RC 2012, Copenhagen, Denmark, July 2-3, 2012. Revised Papers
Redaktører	Robert Glück, Tetsuo Yokoyama
Antal sider	12
Forlag	Springer
Publikationsdato	2013
Sider	171-182
ISBN (Trykt)	978-3-642-36314-6
ISBN (Elektronisk)	978-3-642-36315-3
DOI	https://doi.org/10.1007/978-3-642-36315-3_14
Status	Udgivet - 2013
Begivenhed	4th International Workshop on Reversible Computation - København, Danmark Varighed: 2 jul. 2012 → 3 jul. 2012 Konferencens nummer: 4

Konference

Konference	4th International Workshop on Reversible Computation
Nummer	4
Land/Område	Danmark
By	København
Periode	02/07/2012 → 03/07/2012

Navn	Lecture notes in computer science
Vol/bind	7581
ISSN	0302-9743

Emneord

Reversible circuits
logic design
constant multipliers
garbage-free

Adgang til dokumentet

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

Citationsformater

Axelsen, H. B., & Thomsen, M. K. (2013). Garbage-free reversible integer multiplication with constants of the form 2^k±2^l±1. I R. Glück, & T. Yokoyama (red.), Reversible Computation: 4th International Workshop, RC 2012, Copenhagen, Denmark, July 2-3, 2012. Revised Papers (s. 171-182). Springer. Lecture notes in computer science Bind 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. red. / Robert Glück; Tetsuo Yokoyama. Springer, 2013. s. 171-182 (Lecture notes in computer science, Bind 7581).

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

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

@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 -