PaperlayerView exact revision on arXiv

Source-linked AI summary

Design of Efficient Reversible Logic Based Binary and BCD Adder Circuits

Himanshu Thapliyal, Nagarajan Ranganathan

arXiv:1712.02630v1quant-phcs.ET

TL;DR

Binary hardware can approximate some decimal fractions, while software decimal arithmetic is usually slower than hardware. This paper proposes reversible binary and BCD adders that prioritize ancilla and garbage counts, and reports lower quantum cost and delay for its no-ancilla ripple-carry designs than existing counterparts.

  • Problem

    Some decimal fractions cannot be exactly represented in binary, and software decimal arithmetic is usually 100 to 1000 times slower than hardware.

    Source: §1 · p. 2

  • Method

    The paper designs reversible ripple-carry adders without ancilla inputs and four BCD adders using binary addition followed by conditional correction or binary-to-BCD conversion.

    Source: §1 · pp. 2–3

  • Results

    The proposed no-ancilla reversible ripple-carry adders have less quantum cost and delay than existing counterparts.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The designs prioritize ancilla inputs and garbage outputs while also considering quantum cost and delay.

    Source: §1 · pp. 2–3

Abstract

from arXiv · show

In this work, we present a class of new designs for reversible binary and BCD adder circuits. The proposed designs are primarily optimized for the number of ancilla inputs and the number of garbage outputs and are designed for possible best values for the quantum cost and delay. First, we propose two new designs for the reversible ripple carry adder: (i) one with no input carry $c_0$ and no ancilla input bits, and (ii) one with input carry $c_0$ and no ancilla input bits. The proposed reversible ripple carry adder designs with no ancilla input bits have less quantum cost and logic depth (delay) compared to their existing counterparts in the literature. In these designs, the quantum cost and delay are reduced by deriving designs based on the reversible Peres gate and the TR gate. Next, four new designs for the reversible BCD adder are presented based on the following two approaches: (i) the addition is performed in binary mode and correction is applied to convert to BCD when required through detection and correction, and (ii) the addition is performed in binary mode and the result is always converted using a binary to BCD converter. The proposed reversible binary and BCD adders can be applied in a wide variety of digital signal processing applications and constitute important design components of reversible computing.

1. INTRODUCTION

Binary hardware is convenient, but decimal values may require approximation and software decimal arithmetic is usually much slower than hardware. The paper proposes reversible binary and BCD adders that prioritize ancilla inputs and garbage outputs while also considering quantum cost and delay.

1. INTRODUCTION

  • Software decimal arithmetic is usually 100 to 1000 times slower than hardware, while some decimal fractions cannot be represented exactly in binary.Using binary hardware for decimal data also requires conversion between decimal and binary formats.Source: §1 · pp. 1–2
  • Reversible circuits preserve information through a one-to-one mapping between input and output vectors, and quantum-circuit qubit constraints make ancilla inputs and garbage outputs key optimization targets.An ancilla is a constant input; a garbage output is neither a primary input nor a useful output and exists to preserve the one-to-one mapping.Source: §1 · p. 2
  • The proposed reversible binary and BCD adders primarily optimize ancilla inputs and garbage outputs, while also considering quantum cost and delay.The paper notes that optimizing ancilla inputs and garbage outputs may affect quantum cost and delay.Source: §1 · p. 2
  • The paper proposes two no-ancilla ripple-carry adders and four BCD adder designs, with the ripple-carry designs reporting lower quantum cost and delay than existing counterparts.The BCD designs either correct a binary sum when required or always convert the binary result to BCD; the designs use Peres and TR gates to reduce ripple-carry cost and delay.Source: §1 · p. 3

2. BACKGROUND

The background defines quantum cost as a gate-implementation measure for reversible logic. It explains how the cost is assigned and calculated from elementary gates.

2. BACKGROUND

  • Quantum cost counts the 1x1 and 2x2 reversible or quantum gates required to implement a reversible gate.Each 1x1 and 2x2 gate is assigned a cost of one.Source: §2 · p. 3
  • The background describes realizing 3x3 reversible gates with 1x1 NOT and 2x2 gates, including Controlled-V, Controlled-V+, and Feynman gates.The Feynman gate is also called the Controlled NOT gate.Source: §2 · p. 3
  • A reversible gate’s quantum cost is calculated by counting the NOT, Controlled-V, Controlled-V+, and CNOT gates in its implementation.Source: §2 · p. 3

A NOT gate is a 1x1 gate represented as shown in Fig. 1(a). Since it is a 1x1 gate, its quantum cost is unity.

The section introduces reversible gates and prior reversible-adder designs, then frames the paper’s focus on optimizing BCD adders for ancilla inputs and garbage outputs while considering quantum cost and delay. It also describes the gate-depth measure used for delay.

2.2 The Controlled-V and Controlled-V + Gates

  • Two controlled-V gates in series act as NOT, while a controlled-V and controlled-V+ in series act as identity.The controlled-V+ gate applies V+ when its control is 1; the controlled-V gate applies V.Source: §2.2 · p. 4

2.3 The Feynman Gate (CNOT Gate)

  • The Feynman (CNOT) gate maps (A, B) to (P=A, Q=A ⊕ B) and has quantum cost 1.It is a 2-input, 2-output reversible gate.Source: §2.3 · p. 4

2.4 The Toffoli Gate

  • The Toffoli gate maps (A, B, C) to (A, B, A·B ⊕ C) and has quantum cost 5.Its quantum implementation uses 2 V gates, 1 V+ gate, and 2 CNOT gates.Source: §2.4 · p. 5

2.5 The Peres Gate

  • The Peres gate maps (A, B, C) to (A, A ⊕ B, A·B ⊕ C) and has quantum cost 4.Among 3x3 reversible gates, the Peres gate has the minimum quantum cost in the existing literature.Source: §2.5 · p. 5

2.6 Delays of the Reversible Gates

  • Delay is measured as logical depth, with unit delay ∆ for 1x1 and 2x2 gates; Toffoli and Peres delays are 5∆ and 4∆, respectively.The delay of a 3x3 gate is computed from its implementation using smaller gates.Source: §2.6 · pp. 5–6

2.7 Prior Works

  • Prior reversible-logic synthesis work addressed quantum cost and garbage outputs, while ancilla-input and delay optimization received less attention.The cited exception is post-synthesis work on reducing circuit lines (qubits).Source: §2.7 · p. 6
  • Earlier quantum ripple-carry adders include designs with one ancilla input bit and designs without ancilla bits and with improved delay.The paper identifies prior BCD-adder work but says it had not primarily focused on optimizing ancilla inputs and garbage outputs.Source: §2.7 · p. 6

3. PROPOSED DESIGN OF THE TR GATE

The proposed TR gate implementation uses 2×2 quantum gates to realize a reversible 3-input, 3-output mapping. Its quantum cost and delay are lower than the earlier estimates.

3. PROPOSED DESIGN OF THE TR GATE

  • The TR gate maps (A, B, C) to (P=A, Q=A ⊕ B, R=A · ¬B ⊕ C) and is shown with an improved quantum implementation.The figure presents the gate and its implementation using 2×2 quantum gates.Source: §3 · p. 7, Figure 5 · p. 7
  • Quantum cost falls from 6 to 4, and delay from 6∆ to 4∆, for the improved TR gate implementation.The implementation uses 1 Controlled-V gate, 1 CNOT gate, and 2 Controlled-V+ gates.Source: §3 · p. 7
  • The TR gate realizes A · ¬B ⊕ C and A ⊕ B, and can implement A · ¬B when C is tied to 0.The paper identifies these functions as useful properties for reversible arithmetic units.Source: §3 · p. 7

4. DESIGN METHODOLOGY OF PROPOSED REVERSIBLE RIPPLE CARRY ADDER WITH NO INPUT CARRY

The proposed no-input-carry ripple-carry adder uses no ancilla inputs or garbage outputs. It generates carry bits, uses them to produce sums, then restores the input locations while reducing quantum cost and delay relative to several existing designs.

4. DESIGN METHODOLOGY OF PROPOSED REVERSIBLE RIPPLE CARRY ADDER WITH NO INPUT CARRY

  • The design generates carry bits in locations initially holding a_i, then restores those locations and stores sum bits in locations holding b_i, avoiding ancilla inputs and garbage outputs.The restored input locations help minimize garbage outputs; no constant-zero input is needed.Source: §4 · pp. 7, 8, 12
  • The six-step method transforms the inputs, generates carries with Toffoli gates, uses Peres gates to prepare sums, and applies CNOT gates to produce the final sum outputs.The final locations retain a_i, store s_i in B_i, and transform z to z ⊕ s_n.Source: §4 · pp. 8, 9, 11, 12
  • A 4-bit version without input carry is illustrated because it is used in the proposed reversible BCD-adder design.The no-input-carry BCD design uses this adder and has one ancilla input bit and zero garbage outputs.Source: §4 · p. 10, Figure 8 · p. 11
  • For n-bit inputs, the design is functionally correct: B_i holds s_i, A_i is restored to a_i, and the output location holds z ⊕ s_n.The method is presented as generic for adders of any size.Source: §4 · pp. 8, 11, 12
  • Quantum cost is 13n − 8 and delay is (11n − 4)∆; quantum cost improves by 22.5%–23.51%, 46.36%–49.95%, and 13.37%–13.33% against the three cited designs.Delay improves by 49.09%–54.09% and 13.40%–15.35% against two designs, while the Cuccaro et al. design is 4.7%–9.02% faster.Source: §4 · p. 13, Table I · p. 13, Table II · p. 14

5. DESIGN METHODOLOGY OF PROPOSED REVERSIBLE RIPPLE CARRY ADDER WITH INPUT CARRY

The input-carry reversible ripple-carry adder uses no ancilla inputs or garbage outputs, while restoring the operand and carry locations after producing the sum. Selective use of Peres and TR gates is reported to reduce quantum cost and delay relative to existing designs.

5. DESIGN METHODOLOGY OF PROPOSED REVERSIBLE RIPPLE CARRY ADDER WITH INPUT CARRY

  • The design uses no ancilla inputs or garbage outputs, generating carries in memory locations initially holding a_i and later restoring those locations.The sum bits are stored where b_i was initially held; the input carry location is also restored.Source: §5 · pp. 14, 15, 18
  • The gate sequence generates carries with Toffoli gates and a final Peres gate, then uses TR gates and CNOT operations to complete the adder.The reported method selectively uses Peres and TR gates to improve quantum cost and delay.Source: §5 · pp. 15, 19
  • The six-step methodology produces sum bits s_i in the original B_i locations, restores each A_i to a_i, and transforms the z location to z ⊕ s_n.The location holding input carry c_0 is restored to c_0.Source: §5 · pp. 18, 20
  • For the n-bit reversible ripple-carry adder, the reported total quantum cost is 15n − 6, and the propagation delay is (9n + 1)∆.Source: §5 · p. 21
  • 10.97%–10.01% and 0%–9.83% delay improvement ratios, and 12.3%–11.77% and 0%–11.61% quantum-cost improvement ratios, are reported versus the designs in Cuccaro et al. (2004).The comparison describes the proposed input-carry adder; Table IV also compares it with existing designs.Source: §5 · p. 21, Table IV · p. 21

6. DESIGN OF REVERSIBLE BCD ADDER

The paper develops reversible BCD adders using either conditional detection and correction or binary-to-BCD conversion after binary addition. It presents input-carry and no-input-carry variants and compares their resource costs with existing designs.

6.1 Basics

  • A BCD adder adds two BCD digits and produces a BCD sum; the paper adapts two conventional approaches into reversible designs optimized for ancilla inputs and garbage outputs.One approach detects when correction is needed; the other converts the binary result to BCD.Source: §6 · p. 21, §6.1 · pp. 22–23

6.2 Design of Reversible BCD Adder Based on Approach 1

  • 88 and 73∆ are the quantum cost and delay of one RBCD-1 digit; cascading n digits gives 2n ancilla inputs, 2n − 1 garbage outputs, cost 88n, and delay 73n∆.RBCD-1 uses a reversible binary adder, detection unit, correction unit, and a Feynman gate to copy OC.Source: §6.2.1 · p. 24
  • 80 and 80∆ are the quantum cost and delay of one RBCD-2 digit; its n-digit version has 2n ancilla inputs, 2n − 1 garbage outputs, cost 88n − 18, and delay 73n − 1∆.RBCD-2 has no input carry and uses two ancilla inputs and one garbage output per single-digit design.Source: §6.2.1 · p. 25

6.3 Design of Reversible BCD Adder Based on Approach 2

  • 70 and 57∆ are the quantum cost and delay of one RBCD-3 digit; cascading n digits gives n ancilla inputs, n − 1 garbage outputs, cost 70n, and delay 57n∆.RBCD-3 uses a binary-to-BCD converter; its single-digit design has one ancilla input and no garbage outputs.Source: §6.3 · p. 26, §6.3.1 · p. 27
  • 62 and 54∆ are the quantum cost and delay of one RBCD-4 digit; its n-digit version has n ancilla inputs, n − 1 garbage outputs, cost 70n − 8, and delay 57n − 3∆.RBCD-4 has no input carry and uses the reversible binary-to-BCD converter.Source: §6.3.1 · p. 28, §6.3.2 · p. 30

6.4 Comparison of n digit Reversible BCD Adders

  • Among the proposed input-carry designs, RBCD-3 has the minimum ancilla inputs, garbage outputs, quantum cost, and delay; prior designs’ delays are unknown, preventing delay comparison with them.RBCD-3’s ancilla-input improvement ratios are 75% and 50% versus Thomsen and R. Glück (2008) and Mohammadi et al. (2009), respectively.Source: §6.4 · p. 30

7. SIMULATION AND VERIFICATION

The proposed reversible adders and BCD-adder components were functionally verified through Verilog HDL simulations. Exhaustive tests covered the specified smaller adder designs, using ModelSim and SynaptiCAD simulators.

7. SIMULATION AND VERIFICATION

  • The proposed reversible ripple-carry adders, BCD-adder components, and complete BCD adders were functionally verified through simulation.The designs were coded in Verilog HDL using a library of reversible gates.Source: §7 · pp. 31–32
  • Exhaustive simulations checked correctness for 4-bit and 8-bit binary adders and 1-digit BCD adders.Test benches were created for each proposed reversible circuit.Source: §7 · p. 32
  • ModelSim and SynaptiCAD were used for functional verification, and SynaptiCAD generated the waveforms.Source: §7 · p. 32

8. CONCLUSIONS

The paper presents reversible ripple-carry binary and BCD adders, prioritizing fewer ancilla inputs and garbage outputs while also considering quantum cost and delay. The designs were logically verified using Verilog HDL and simulators.

8. CONCLUSIONS

  • The proposed reversible binary and BCD adders prioritize minimizing ancilla inputs and garbage outputs, while also considering quantum cost and delay.Source: §8 · p. 32
  • The conclusion reports that the proposed designs improve on existing designs in ancilla inputs and garbage outputs while maintaining lower quantum cost and delay.Source: §8 · p. 32
  • All proposed designs were functionally verified at the logical level using Verilog HDL and HDL simulators.The paper identifies reversible and quantum computing as application areas for the designs.Source: §8 · p. 32
Loading 1712.02630v1…