Parallelization of Reversible Ripple-carry Adders

Research output: Contribution to journalJournal articleResearchpeer-review

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 \emph{garbage}.

Here, we present a novel parallelization scheme wherein $m$ parallel
$k$-bit reversible ripple-carry adders are combined to form a
reversible $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$-bit
ripple-carry adder logic depth $\mathcal{O}(m\cdot k)$. The
underlying mechanisms of the parallelization scheme are formally
proven correct. We also show designs for garbage-less reversible
comparison circuits.

We compare the circuit costs of the resulting ripple-block carry
adder with known optimized reversible ripple-carry adders in
measures of circuit delay, width, gate, transistor count, and
relative power efficiency, and find that the parallelized adder
offers significant speedups at realistic word sizes with modest
parallelization overhead.
Original languageEnglish
JournalParallel Processing Letters
Issue number2
Pages (from-to)205-222
Number of pages18
Publication statusPublished - 2009

    Research areas

  • Faculty of Science - reversible circuits, ripple-carry adders, parallelization, comparison circuits, ripple-block carry adder

ID: 12704396