Design of Digital Multiplier with Reversible Logic by Using the Ancient Indian Vedic Mathematics Suitable for Use in Hardware of Cryptosystems

Veiw figure View Figure

2.1. Comparison between Normalmethod of Multiplication and Vedic Mathematics Multiplication

Table 1. Comparision between normal method multiplication & vedic mathematics multiplication

Download as

View current table in a new window

Tables index

Veiw figure View Table

2.2. Multiplier Implementation

In this paper, the proposed multiplier architecture is implemented in VHDL (Very High Speed Integrated Circuited Hardware Description Language) and the FPGA synthesis is done using Xilinx ISE 8.2i. The design is optimized for speed and area using Xilinx, device family: Virtex XC4VLX15, package SF363,speed grade-12. The Xilinx Virtex XC4VLX15-12 device is to be applied and the device contains 6144 slices and 12288 input Look Up Tables and 240 bonded Input/output pads.

The implementation style is the Fully partitioned Vedic multiplier. Here for 8*8 multiplier implementation, 4x4bits multiplier units have been used as components. Then the reversible ripple carry adders are implemented for addition need. Finally, the result of the multiplier is displayed through adequate size of output port ^[5].

Figure 2.2. Figure of architecture of 4 bit vedic multiplier

Download as

Veiw figure View Figure

Figure 2.3. Circuit generation of reversible 8 bit ripple carry adder with no input carry

Download as

Veiw figure View Figure

Figure 2.4. Circuit generation of 8 bit reversible vedic multiplier

Download as

Veiw figure View Figure

We present the design of reversible ripple carry adder with no input carry(c0) and is designed without any ancilla inputs and the garbage outputs. The proposed method improves the quantum cost and the delay of the reversible ripple carry adder compared to the existing design approaches which have optimized the adder design in terms of number of ancilla inputs. Consider the addition of two n bit numbers ai and bi stored at memory locations Ai and Bi, respectively, where 0 ≤ i ≤ n−1. Further, consider that memory location An is initialized with z ∈ {0, 1}. At the end of the computation, the memory location Bi will have si, while the location Ai keeps the value ai. The additional location An that initially stores the value z will have the value z sn at the end of the computation. Thus An will have the value of sn when z=0. Here, s_iis the sum bit produced and is defined as:

where c_i is the carry bit and is defined as:

The proposed design methodology of generating the reversible ripple carry adder with no input carry minimizes the garbage outputs by producing the carry bits ci based on the inputs ai-1, b i-1 and the carry bit c i-1 from the previous stage. Once all the carry bits ci are generated they are stored at memory location A i-1 which was initially used for storing the input a i-1 for 0 ≤ i ≤ n − 1. After the generated carry bits are used for further computation, the location Ai are restored to the value ai while the location Bi stores the sum bit si for 0 ≤ i ≤ n − 1. Thus restoring of location Ai to the value ai helps in minimizing the garbage outputs. Since no constant input having the value as 0 is needed in the proposed approach, it saves the ancilla inputs. The proposed methodology of generating the reversible ripple adder circuit without input carry is referred as methodology 1 in this work. The proposed methodology is generic in nature and can design the reversible ripple carry adder circuit with no input carry of any size. The steps involved in the proposed methodology is explained for addition of two n bit numbers ai and bi, where 0 ≤ i ≤ n−1. An illustrative example of generation of reversible ripple carry adder circuit that can perform the addition of two 8 bit numbers a=a0:::a7 and b=b0:::b7 is also shown.

2.3. Steps of Methodlogy (Reversible Adder Circuits with no Input Carry)

(1) For i=1 to n-1:

At pair of locations Ai and Bi apply the CNOT gate such that the location Ai will maintain the same value, while location Bi transforms to (*Ai *Bi), where *Ai and *Bi represent the values stored at location Ai and Bi. The step 1 is shown for reversible ripple carry adder circuit that can perform the addition of two 8 bit numbers in Figure 2.5(a).

(2) For i=n-1 to 1:

At pair of locations Ai and Ai+1 apply the CNOT gate such that the location Ai will maintain the same value, while the location Ai+1 transforms to (*Ai *Ai+1). The step 2 is shown for reversible 8 bit adder circuit in Figure 2.5(b).

(3) For i=0 to n-2:

At locations Bi, Ai and Ai+1 apply the Toffoli gate such that Bi, Ai and and Ai+1 are passed to the inputs A, B, C, respectively, of the Toffoli gate. The step 3 is shown for reversible 8 bit adder circuit in Figure 2.5(c).

Figure 2.5. Circuit generation of reversible 8 bit adder with no input carry: Steps 1-3

Download as

Veiw figure View Figure

(4) For i=n-1 to 0:

At locations Ai, Bi and and Ai+1 apply the Peres gate such that Ai, Bi and and Ai+1 are passed to the inputs A, B, C, respectively, of the Peres gate. The step 4 is shown for reversible 8 bit adder circuit in Figure 2.6(a).

(5) For i=1 to n-2:

At pair of locations Ai and Ai+1 apply the CNOT gate such that the location Ai will maintain the same value, while location Bi transforms to the value (*Ai *Bi). The step 5 is shown for reversible 8 bit adder circuit in Figure 2.6(b).

(6) For i=1 to n-1:

At pair of locations Bi and Ai apply the CNOT gate such that the location Ai will maintain the same value, while location Bi transforms to the value (*Ai *bi). This final step will result in a reversible adder circuit that can perform the addition of two n bit numbers. For reversible 8 bit adder circuit, the design is shown in Figure 2.6 (c).

Figure 2.6. Circuit generation of reversible 8 bit ripple carry adder with no input carry

Download as

Veiw figure View Figure

3. Simulation Results & Analysis

The synthesis & simulation is performed by using softwares like Xilinx ISE 8.2i. which is further used for coding, testing and simulation of VHDL programs. The design is optimized for speed and area using Xilinx, device family: Virtex XC4VLX15, package SF363,speed grade-12.

Figure 3.1. Simulation result of 8 bit reversible vedic multiplier

Download as

Veiw figure View Figure