Abstract
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.
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 language | English |
|---|---|
| Journal | Parallel Processing Letters |
| Volume | 19 |
| Issue number | 2 |
| Pages (from-to) | 205-222 |
| Number of pages | 18 |
| ISSN | 0129-6264 |
| DOIs | |
| Publication status | Published - 2009 |
Keywords
- Faculty of Science
- reversible circuits
- ripple-carry adders
- parallelization
- comparison circuits
- ripple-block carry adder