Design and Implementation of Low Power Generic Reversible Binary-Coded Decimal Adder on Artix-7 FPGA

In the era of energy-efficient computing, minimizing power consumption has become a critical priority, particularly for applications in portable electronics, IoT devices, and green technology. Reversible logic has emerged as a key enabler for achieving this goal, addressing energy dissipation by preventing information loss during computation.

Mollick [1] formulated a hypothesis suggesting that computing power would experience significant growth while costs would decrease proportionately. His forecasting predicted that all the transistors present on a semiconductor chip shall get two folded in every one and a half or two years, maintaining minimal cost increments. This forecast was known to be Moore's law and it also anticipated that substantial amount of heat would be generated as a result of certain information being lost. This heat dissipation, in turn, could lead to a drastic reduction in circuit performance and lifespan. Keeping that in mind, Landauer's [2] research elucidated that conventional gates dissipate energy at a minimum rate of kTln2 joules per bit of information loss, wherein k represents the Boltzmann constant (1.38064852×10⁻²³ joule/kelvin) and T signifies absolute temperature in kelvin during operations. Following this, Bennett [3] demonstrated in 1973 that to circumvent this energy dissipation, circuits must be constructed using reversible logic. Consequently, various reversible gates namely the Fredkin Gate, Peres Gate, Toffoli Gate and Feynman Gate were devised with the intention of achieving this objective [4]. Unlike traditional logic circuits, which generate heat by erasing information, reversible gates allow input data to be fully reconstructed from outputs, adhering to Landauer's principle. This reduces energy dissipation to negligible levels, making reversible logic a cornerstone of sustainable computing.

A reversible gate establishes a bijective relationship between the input and output vectors. This capability allows for the generation of inputs from outputs and the ability to backtrack to any point in the computation. This characteristic is termed logical reversibility. However, the advantages of this are contingent upon achieving physical reversibility, which refers to a procedure that expends nil energy as heat. While achieving total perfect physical reversibility is nearly unattainable, efforts can be made to minimize or even eliminate energy dissipation by ensuring that computations are information lossless [5]. A qubit represents a fundamental unit of information, capable of existing in a state of 0, 1, or a superposition of both [6]. Any manipulation performed on individual qubits can be designed to be reversible, allowing for the preservation of information integrity. This is explained with an example given below in Figure 1.

Upon examining the AND Gate shown in Figure 1, which comprises two inputs and one output, and referring to the corresponding truth table given in Table 1, it is evident that an input combination, such as '00,' yields an output of '0,' as does '01' and '10.' Consequently, discerning the specific input combination resulting in the output '0' proves challenging.

Contrary to the CNOT Gate as depicted in Figure 2, this is additionally known as the Feynman Gate features two inputs and two outputs. Notably, when the inputs are '00,' the output is exclusively '00,' and no other input configuration produces this output. Similarly, for input '01,' the output is '01.' Thus, each input corresponds to a distinct output, unlike the conventional AND Gate, mitigating the complexity of prediction. This characteristic aligns with the principle of reversibility. Its truth table is shown in Table 2.

1.png

Figure 1. AND Gate

Table 1. AND Gate truth table

2.png

Figure 2. CNOT Gate

Table 2. CNOT Gate truth table

3.png

Figure 3. Basic reversible gate

In an N×N reversible gate, as shown in Figure 3, the input vector (Iv) and output vector (Ov) are represented as sequences of elements (I₁, I₂, I₃, ... I_N) and (O₁, O₂, O₃, ... O_N) respectively. To construct reversible circuits, a set of reversible gates is required, ensuring that each input vector corresponds uniquely to an output vector, and vice versa, thus maintaining a one-to-one mapping between them. This distinction between reversible and arbitrary logic circuits rests on the key properties:

(i) The equality of input and output bit counts,

(ii) The guarantee that each input pattern corresponds to a unique output pattern,

(iii) No fan-out allowed.

According to the study conducted by Nayak et al. [7], there exist various terminologies and parameters associated with reversible logics.

Constant Inputs (CI): Inputs set to 0 or 1 to synthesize non-reversible Boolean functions into reversible forms.

Garbage Outputs (GO): Unused outputs essential for achieving reversibility, ensuring the sum of inputs and constant inputs equals the sum of outputs and garbage outputs.

Gate Count: The number of reversible logic gates used in the circuit.

Quantum Cost (QC): Indicates the overall usage of 2×2 quantum primitives to form an equivalent circuit.

Delay. Based on the majority of gates from an input line to an output line, assuming that each gate operates in a single time unit and all inputs are available before computation starts.

Hardware Complexity. The number of logical operations (AND, OR, EX-NOR) within the circuit.

Flexibility. Indicates the universality of reversible logic gates, aiming for minimal garbage output, minimal delay, and no feedback/loops to achieve reversibility.

In hardware design, the preference for binary computing over decimal computing arises from the simplicity of constructing hardware based on the binary number system. Despite the convenience of building binary hardware, challenges emerge when representing fractional decimal numbers, like 0.110, precisely in binary form. Consequently, approximate values are employed for computational purposes within binary hardware. Acknowledging the limited tolerance of commercial, financial, and net-based platforms for blunders stemming from conversions among binary and decimal formats, there has been a significant shift towards prioritizing decimal arithmetic. Binary Coded Decimal (BCD) is a representation technique utilized for encoding decimal digits (0-9) in binary form. Ongoing efforts are aimed at accelerating the development of dedicated hardware specifically designed for decimal arithmetic. So, there is great emphasis on the design of low-power hardware implementation of decimal arithmetic circuits based on reversible logic.

The Binary-Coded Decimal (BCD) adder, a fundamental arithmetic component, is widely used in digital systems that require precise decimal computations, such as financial systems, digital clocks, IoT devices, quantum computing, and calculators. However, traditional BCD adders, designed using irreversible logic, are inherently energy-intensive and face scalability challenges. These limitations hinder their deployment in power-sensitive applications and emerging fields like quantum computing. A reversible BCD adder provides a compelling solution by combining the benefits of energy efficiency, scalability, and minimal hardware overhead.

This paper presents a low-power reversible BCD adder implemented on an Artix-7 FPGA, designed to address these limitations. Existing methods [8-13] have utilized various reversible gates such as the Toffoli Gate (TG) [14], New Gate (NG) [15], HNFG Gate [11], Feynman Gate [16], etc., for the implementation of a reversible BCD adder. The implementation of the BCD adder typically involves three key stages. First, a binary-centric 4-bit parallel adder performs addition on the two BCD numbers in their binary representation. Next, the result is evaluated by a Six Converter Module (SCM) to ensure accuracy [17]. If the outcome exceeds '1001' or generates a carry, it is identified as invalid and requires adjustment. Finally, the correction is made by adding '0110' to the sum using a 4-bit parallel adder.

The proposed architecture utilizes a combination of Fredkin, Toffoli, and Peres Gate, ensuring a bijective mapping between inputs and outputs while minimizing quantum cost (QC), garbage output (GO), and constant input (CI). The modular design is scalable to input sizes up to 512 bits, enabling seamless adaptation to various applications without frequent redesigns.

Compared to conventional designs [18, 19], the proposed BCD adder achieves a 70% reduction in power dissipation while maintaining comparable delay performance, enhanced scalability for large datasets, and applications requiring high precision, and simplified arithmetic processes for frequent decimal computations.

By implementing the design on an Artix-7 FPGA, this study combines energy efficiency with the benefits of high performance, flexibility, and rapid prototyping. The FPGA's architecture further enables potential parallel processing, making it ideal for applications such as financial systems, IoT devices, and advanced embedded systems.

The proposed design addresses the trade-offs in existing approaches, which often compromise on key metrics like QC and GC. It sets a benchmark for energy-efficient computing, paving the way for future advancements in reversible arithmetic circuits and their integration into low-power digital systems.

The structure of this paper is as follows: Section 2 provides an overview of reversible logic gates and prior work. Section 3 details the design methodologies of the proposed BCD adder. Section 4 discusses the verification and implementation using VHDL, and Section 5 concludes with key findings and future directions.

This paper discusses the design and implementation of a generic reversible BCD adder using four different architectures. BCD addition involves the addition of two BCD digits to yield an output BCD digit, each within the range of 0 to 9. This addition process adheres to specific rules of binary-centred addition, wherein correction logic is only required if the sum exceeds 9 or if a carry is present. Unlike traditional binary adders, BCD addition requires additional correction logic due to the limited range of BCD numbers (0 to 9). Nevertheless, challenges arise in the context of BCD addition, necessitating the incorporation of correction logic. The proposed design emphasizes modularity and scalability, making it adaptable for higher bit-widths beyond 8 bits. The foundation of the design lies in the use of a 4-bit reversible BCD adder as a building block, which can be combined iteratively to construct adders of larger sizes. For example, an 8-bit BCD adder is implemented by cascading two 4-bit BCD adders, as shown in Figure 13 and Figure 14. This hierarchical approach enables scalability to higher bit widths, such as 16-bit or 32-bit, by simply integrating additional blocks. The major advantages of scalability are:

Modular design: The use of 4-bit adders as primitive blocks simplifies the construction of higher-order adders without significant redesign.

Reusability: The correction logic and carry propagation mechanism remain consistent across different bit-widths.

Reduced development effort: The same design methodology can be extended to larger sizes, reducing implementation complexity.

The limitations and challenges in scaling are:

Delay accumulation: As shown in Table 4, the combinational path delay increases with the bit-width due to the propagation of carry signals across multiple blocks. For instance, the delay for a 64-bit adder is significantly higher compared to smaller sizes. This limits the practicality of the design for applications requiring ultra-low latency.

Power dissipation: Power consumption grows as additional blocks are added. Although reversible logic reduces overall power dissipation, the complexity of managing carry and correction logic in higher-order designs results in incremental power usage, as indicated in Table 5.

Increased resource utilization: Scaling requires more gates, leading to an increase in garbage outputs, constant inputs, and quantum costs. While the design strives for optimization, these parameters grow linearly or sub linearly with the number of bits, impacting efficiency. Table 6 highlights the resource usage for smaller designs, which would proportionally increase for larger sizes.

FPGA resource constraints: Larger bit-width designs may exceed the available hardware resources of certain FPGAs, such as the Artix-7 board used for implementation. Optimizing the design to fit within these constraints could require additional effort or design trade-offs.

To address these challenges and facilitate future improvements in scalability, the following strategies can be explored:

Optimized gate design: Developing more efficient reversible gates with reduced quantum costs and garbage outputs.

Parallel carry management: Employing carry-look ahead or carry-save methods in reversible logic to minimize delay.

Resource-aware mapping: Tailoring the design for specific FPGA architectures to maximize resource utilization efficiency.

Table 4. Combinational path delay for all design

	Combinational Path Delay (ns)
Adder Size	Conventional Adder	Algorithm 1	Algorithm 2	Algorithm 3	Kogge Stone Adder
4	2.267	2.537	2.34	2.256	0.948
8	3.468	3.743	3.96	3.721	1.555
16	5.605	8.682	7.781	6.653	2.901
32	9.905	15.51	10.192	12.517	6.001
64	18.494	30.492	19.015	24.244	12.11

Table 5. Power dissipation for all design

Sr. No.	Adder Type	Power Dissipation (mW)
1	Conventional (Irreversible)	80.2
2	Algorithm1	78
3	Algorithm 2	189
4	Algorithm 3	90
5	Kogge Stone BCD adder	55
6	Reversible Kogge Stone BCD adder	24

Table 6. Comparison of reversible adder algorithms

Algorithms	Garbage Output	Quantum Cost	Constant Inputs	Gate Count
Algorithm 1	24	60	24	16
Algorithm 2	22	55	30	12
Algorithm 3	10	45	21	8
Reversible Kogge Stone adder (Proposed)	14	37	14	11

Overall, the proposed design is inherently generic and scalable but requires careful consideration of resource usage, delay, and power as bit widths increase. By addressing these limitations through optimization strategies, the design can be effectively extended to higher-order BCD adders.

3.1 BCD adder design 1: Implementation details

Figure 13 illustrates the block diagram of the basic 4-bit reversible BCD adder. In this design, both the input and output have an equal bit count. The inputs, labelled as A, B, C, and D, each consist of four bits, while the outputs, represented by W, X, Y, and Z, also consist of four bits. In this configuration, Y denotes the sum, Z represents the carry, and W and X are garbage outputs. The implementation of the proposed reversible BCD adder follows a systematic, multi-stage design process. It begins with the construction of a single-bit adder using HNG gates, followed by the development of a 4-bit adder using four HNG gates. This initial 4-bit BCD adder serves as a foundational building block for higher-order BCD adders. In addition, a correction logic block, comprising NG, FG, and TG gates, is added to refine the output for BCD correctness.

13.jpg

Figure 13. 4-bit reversible BCD adder

14.jpg

Figure 14. 4-bit parallel adder

15.jpg

Figure 15. Decomposition of an 8-bit reversible Binary-Coded Decimal (BCD) using two 4-bit reversible BCD adders

16.jpg

Figure 16. Correction logic

Each HNG gate functions as a full adder, producing both sum and carry outputs akin to a conventional full adder, thereby constituting a one-bit adder. By connecting four such one-bit adders, a four-bit adder is formed. This is shown in Figure 14. However, to adapt this binary adder into a BCD adder, integration of correction logic becomes necessary.

Block diagram shown in Figure 15 comprises of two 4-bit inputs labelled "A" and "B." The reversible adder block operates by adding the individual bits of the inputs. Specifically, it adds A (0) with B (0), and if there's a carry resulting from the addition, it's internally propagated, as illustrated in the "4-bit Parallel Adder" section. Any temporary carry generated is directed to the NG gate. Another 4-bit reversible adder block is employed, which takes inputs from the sum output of the first adder block and four inputs from the FG gate. The output comprises 4 bits of sum and 1 bit of carry. Furthermore, two NG gates and one TG gate function as correction logic for the BCD adder. Correction logic is designed using NG, TG and FG gates as shown in Figure 16. The main purpose of correction logic is to add “0110”, whenever sum is greater than 9 or carry is generated [34, 35].

The diagram shown in Figure 15 illustrates the decomposition of an 8-bit BCD adder using two 4-bit Reversible BCD adders. The initial adder computes the partial sum and carry, directing the partial carry to the subsequent BCD adder. Concurrently, the second BCD adder processes the inputs, generating the final sum and carry. The higher order adders can be subsequently created using this basic building block as shown in Figure 17.

17.jpg

Figure 17. 8-bit reversible BCD adder using 4-bit BCD adder

18.png

19.png

20.png

3.3 BCD adder design 3: Implementation details

The design in Figure 20 features a four-bit reversible adder, which employs four HNG gates, along with additional elements such as a Peres Gate, a Feynman Gate, and an SCLG. Moreover, it integrates an extra HNG Gate, expanding its capability to process information effectively. One notable advantage of this design is its ability to address the fan-out limitation. By utilizing six ancillary input lines and generating ten garbage output lines, it demonstrates a marked improvement in handling data flow and output distribution. It’s worth mentioning that the quantum cost of this circuit remains unspecified, leaving room for further evaluation and optimization. Nonetheless, its innovative configuration showcases a promising approach to mitigating computational constraints and advancing quantum computing capabilities.

Components

1. HNG Gate Based 4-bit Reversible Adder:
   
   • Inputs: X3, X2, X1, X0 (first BCD number) and Y3, Y2, Y1, Y0 (second BCD number).
   • Outputs: S3', S2', S1', S0' (intermediate sum) and CARRYout (carry out from the 4-bit adder).
   • Description: This block consists of 4 HNFG gates, each taking four constant inputs and producing eight garbage outputs, to perform the 4-bit addition. The intermediate sum (S3', S2', S1', S0') and the carry output (CARRYout) are generated here.
2. SCL Gate:
   
   • Inputs: S3', S2', S1', S0' (intermediate sum) and CARRYout.
   • Outputs: Q, R, S, P.
   • Description: The SCL gate performs correction logic to ensure the sum is within the BCD range. If the intermediate sum exceeds 9, correction logic is applied.
3. Peres Gate (as Half Adder):
   
   • Inputs: S1', S2' and constant 0.
   • Outputs: P, Q, R.
   • Description: This gate is used to perform the half addition needed during the correction process. It generates a partial corrected sum and intermediate carry.
4. HNG Gate (as Full Adder):
   
   • Inputs: The outputs of the Peres Gate, the intermediate sum S2', and the carry output from the SCL gate.
   • Outputs: P, Q, R, S (final corrected sum).
   • Description: This gate finalizes the BCD correction by acting as a full adder, combining partial sums and carries to produce the final corrected BCD output.
5. CNOT Gate:
   
   • Inputs: Outputs from the HNG gate.
   • Outputs: Corrected sum bits.
   • Description: The CNOT gate is used for further logical operations necessary for the BCD correction and final sum generation.

Output

The final outputs of the circuit are the corrected BCD sum (C4, S3, S2, S1, and S0).

3.4 BCD adder design 4: Implementation details

Ripple Carry Adders (RCA) are simple but slow due to linear carry propagation. Their delay is linear, O(n). Carry-Lookahead Adders (CLA) improve speed by computing carries in advance, reducing delay but increasing complexity. Carry-Save Adders (CSA) are efficient for multi-operand addition, though additional steps are needed for the final sum. Parallel prefix adders, including Kogge-Stone, Brent-Kung, and Sklansky, offer logarithmic delay (O(logn)) by computing carries in parallel, with Kogge-Stone being the fastest due to minimal logic depth and balanced load, albeit at a higher gate count. Kogge-Stone is particularly superior for high-speed applications, offering significant performance improvements over other adders.

Figure 21 represents a 4-bit Kogge-Stone adder, which is a type of parallel prefix adder used for binary addition. The Kogge-Stone adder is known for its logarithmic depth and regular structure, making it efficient for high-speed arithmetic operations. The Kogge-Stone Adder (KSA) operates in three distinct stages: pre-processing, carry look-ahead computation, and post-processing.

21.png

Figure 21. 4-bit Kogge Stone adder

22.png

Figure 22. 4-bit reversible Kogge Stone adder

Each stage plays a critical role in the overall functionality and high performance of the adder. In this paper binary Kogge Stone adder is designed using reversible gates as shown in Figure 22. The output is converted in BCD form using a binary to BCD module. A detailed explanation of each stage is as follows:

1. Pre-processing

In the pre-processing stage, generate (G) and propagate (P) signals are computed for each bit pair in the input numbers A and B. This is implemented using Peres Gate.

$\bullet$ Generate Signal (G): This signal indicates whether a given bit pair will generate a carry.

Gi=Ai.Bi

• If both bits Ai and Bi are 1, a carry will be generated, thus Gi=1.
• If either bit is 0, Gi=0.

$\bullet$ Propagate Signal (P): This signal indicates whether a given bit pair will propagate a carry from a lower bit to a higher bit.

Pi=Ai $\oplus$ Bi

• If Ai and Bi different, Pi=1 meaning the carry from the previous bit will be propagated.
• If Ai and Bi are the same, Pi=0.

2. Carry look-ahead computation

This stage is the core of the Kogge-Stone adder, enabling fast carry computation by combining generate and propagate signals using a parallel prefix network. The network consists of multiple levels of logic that combine these signals over increasing ranges of bits. This is implemented using three UPG gates.

$\bullet$ Combine Propagate Signals (P):

P_i:j=Pi:k−1 and Pk:j

• This formula computes the propagate signal for a range of bits from i to j.
• If all bits in the range propagate a carry, then the overall propagate signal for the range is 1.

$\bullet$ Combine Generate Signals (G):

Gi:j=Gi:k−1 or (Pi:k−1 and Gk:j)

• This formula computes the generate signal for a range of bits from i to j.
• A carry is generated for the range if either:
• A carry is generated within the lower part of the range (Gi:k−1).
• Or a carry is propagated through the lower part (Pi:k−1) and generated in the upper part (Gk:j).

3. Post-processing

In the post-processing stage, the final sum bits are calculated using the propagate signals and the carry-in values computed in the carry look-ahead stage. This is implemented using Peres Gates.

$\bullet$ Sum Bit (S): Si=Pi $\oplus$ Ci−1

• The sum for each bit position i is calculated by XORing the propagate signal for that bit with the carry-in from the previous bit position.

Binary to BCD Converter: This module converts the final sum and carry in BCD form using state machine for segregating digits of different places.

The 4-bit Kogge-Stone adder is designed to perform fast binary addition through efficient carry propagation across multiple stages. Initially, in Stage 0, the adder computes the generate (G[i]=A[i] & B[i]) and propagate (P[i]=A[i]^B[i]) signals for each bit using Peres Gates. These signals indicate whether a carry is generated or propagated for each bit of the input operands A and B. In Stage 1, UPG gates are used to combine the generate and propagate signals from adjacent bits, producing new generate and propagate signals (G1 and P1) for pairs of bits. This process is further refined in Stage 2, where UPG gates combine the results from Stage 1 to handle carry propagation over wider groups of bits, producing G2 and P2 signals. In Stage 3, the final carry signals are determined using AND and OR gates based on the outputs from Stage 2 and the initial carry input (Cin). The final carry-out is produced from these signals. Lastly, in the Sum Calculation stage, the sum for each bit is computed using XOR gates. The propagate signals from Stage 0 are XORed with the carry-out signals to produce the final sum (Sum). This method ensures a fast and efficient addition process by minimizing the delay typically caused by carry propagation, making the Kogge-Stone Adder a highly effective design for high-speed arithmetic operations in digital circuits.