@article{dc8d10a05cb211dea8de000ea68e967b,
title = "Parallelization of Reversible Ripple-carry Adders",
abstract = "The design of fast arithmetic logic circuits is an importantresearch topic for reversible and quantum computing. A specialchallenge in this setting is the computation of standardarithmetical functions without the generation of \emph{garbage}.Here, we present a novel parallelization scheme wherein $m$ parallel$k$-bit reversible ripple-carry adders are combined to form areversible $mk$-bit \emph{ripple-block carry adder} with logic depth$\mathcal{O}(m+k)$ for a \emph{minimal} logic depth$\mathcal{O}(\sqrt{mk})$, thus improving on the $mk$-bitripple-carry adder logic depth $\mathcal{O}(m\cdot k)$. Theunderlying mechanisms of the parallelization scheme are formallyproven correct. We also show designs for garbage-less reversiblecomparison circuits.We compare the circuit costs of the resulting ripple-block carryadder with known optimized reversible ripple-carry adders inmeasures of circuit delay, width, gate, transistor count, andrelative power efficiency, and find that the parallelized adderoffers significant speedups at realistic word sizes with modestparallelization overhead.",
keywords = "Faculty of Science, reversible circuits, ripple-carry adders, parallelization, comparison circuits, ripple-block carry adder",
author = "Thomsen, {Michael Kirkedal} and Axelsen, {Holger Bock}",
year = "2009",
doi = "10.1142/S0129626409000171",
language = "English",
volume = "19",
pages = "205--222",
journal = "Parallel Processing Letters",
issn = "0129-6264",
publisher = "World Scientific Publishing Co. Pte. Ltd.",
number = "2",
}