Parallel Optimization of a Reversible (Quantum) Ripple-Carry Adder

TY - GEN

T1 - Parallel Optimization of a Reversible (Quantum) Ripple-Carry Adder

AU - Thomsen, Michael Kirkedal

AU - Axelsen, Holger Bock

N1 - Conference code: 7

PY - 2008

Y1 - 2008

N2 - The design of fast arithmetic logic circuits is an important research topic for reversible and quantum computing. A special challenge in this setting is the computation of standard arithmetical functions without the generation of garbage. The CDKM-adder is a recent garbage-less reversible (quantum) ripple-carry adder. We optimize this design with a novel parallelization scheme wherein m parallel k-bit CDKM-adders are combined to form a reversible mk-bit ripple-block carry adder with logic depth O(m+k) for a minimal logic depth O(\sqrt{mk}), thus improving on the mk-bit CDKM-adder logic depth O(mk). We also show designs for garbage-less reversible set-less-than circuits. We compare the circuit costs of the CDKM and parallel adder in measures of circuit delay, width, gate and transistor count, and find that the parallelized adder offers significant speedups at realistic word sizes with modest parallelization overhead.

AB - The design of fast arithmetic logic circuits is an important research topic for reversible and quantum computing. A special challenge in this setting is the computation of standard arithmetical functions without the generation of garbage. The CDKM-adder is a recent garbage-less reversible (quantum) ripple-carry adder. We optimize this design with a novel parallelization scheme wherein m parallel k-bit CDKM-adders are combined to form a reversible mk-bit ripple-block carry adder with logic depth O(m+k) for a minimal logic depth O(\sqrt{mk}), thus improving on the mk-bit CDKM-adder logic depth O(mk). We also show designs for garbage-less reversible set-less-than circuits. We compare the circuit costs of the CDKM and parallel adder in measures of circuit delay, width, gate and transistor count, and find that the parallelized adder offers significant speedups at realistic word sizes with modest parallelization overhead.

U2 - 10.1007/978-3-540-85194-3_19

DO - 10.1007/978-3-540-85194-3_19

M3 - Article in proceedings

SN - 978-3-540-85193-6

T3 - Lecture notes in computer science

SP - 228

EP - 241

BT - Unconventional Computing

A2 - Calude, Cristian S.

A2 - Costa, José Felix

A2 - Freund, Rudolf

A2 - Oswald, Marion

A2 - Rozenberg, Grzegorz

PB - Springer

T2 - International Conference on Unconventional Computing

Y2 - 25 August 2008 through 28 August 2008

ER -