Novel Tree Structure Based Conservative Reversible Binary Coded Decimal Adder and Sequential Circuit with Added High Testability

Delivered by Ingenta to: ?
IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
Copyright: American Scientific Publishers
RESEARCHARTICLE
Copyright © 2017 American Scientific Publishers
All rights reserved
Printed in the United States of America
Journal of
Computational and Theoretical Nanoscience
Vol. 14, 2515–2527, 2017
Novel Tree Structure Based Conservative Reversible
Binary Coded Decimal Adder and Sequential Circuit with
Added High Testability
Neeraj Kumar Misra1 ∗
, Bibhash Sen2
, and Subodh Wairya1
1
Department of Electronics Engineering, Institute of Engineering and Technology, Lucknow 226021, India
2
Department of Computer Science and Engineering, National Institute of Technology, Durgapur 713209, India
Reversible logic has been recognized as one of the most promising technique for the realization
of the quantum circuit. In this paper, a cost effective conservative, reversible binary coded deci-
mal (BCD) adder is proposed for the quantum logic circuit. Towards the realization of BCD adder,
few novel gates, such as Half-Adder/Subtraction (HAS-PP), Full-Adder/Subtraction (FAS-PP) and
Overflow-detection (OD-PP) based on parity preserving logic are synthesized which incurs 7, 10 and
13 quantum cost respectively. Coupling these gates a novel tree-based methodology is proposed to
implement the required BCD Adder. Also, the BCD adder design has been optimized to achieve the
optimum value of quantum cost. In addition, the proposed BCD circuit is extended to n-bit adder
using replica based techniques. Experimental result establishes the novelty of the proposed logic,
which outperforms the conventional circuits in terms of logic synthesis and testability. The limitation
of detecting the missing gate and missing control point of the quantum circuit of overflow detection
is finally tackled this work by the proposed OD-PP with the application of the minimum test vector.
In addition, reversible circuits of control inputs based testable master-slave D-FF is intended. The
noted work on the testable sequential circuit presented here is to develop circuit using minimum
test vectors and can find diverse application in the testing paradigm.
Keywords: Conservative Logic, Fault Coverage, Reversible Logic, Master-Slave D Flip-Flop,
Quantum Computing, BCD Adder, Testability.
1. INTRODUCTION
Reversible logic has the promising feature of controllable
operations. A controllable operation has utilized the bijec-
tive property which is used for easy testing. The testing
cost is increased accordingly, which increase the size, and
delay of the system. Landauer’s theory shows that a logic
computation that is irreversible i.e., information loss will
dissipate a certain amount of energy (i.e., KTln2) for every
logic bit of information loss.1
Reversible logic computa-
tion has no loss of information that possible by reversible
logic gates.2
Further, it has very small energy dissipation
if a circuit includes of reversible gates. Reversible logic
has applications in the quantum logic circuit, which is
reversible by nature. The integration of reversible circuits
and quantum circuits has provides a strong motivation to
choose reversible logic for digital logic circuit synthesis.3
Logic synthesis of the reversible circuit is currently a pop-
ular area of research.
∗
Author to whom correspondence should be addressed.
In this paper, we construct conservative, reversible BCD
adder an algorithm and quantum circuit testing for over-
flow detection that uses the control gate and control point
missing fault. The BCD adder design is achieved by a syn-
thesis of three modules such as ripple carry adder, overflow
detection, and overflow correction to generate the correct
BCD result. An efficient algorithm for BCD adder design
has shown to share the functionality of logic synthesis.
The main achievement of the algorithm is to minimize
the reversible metrics (i.e., gate count, garbage output,
ancilla input, and quantum cost). The optimal metrics
have been achieved by proposing three new conservative,
reversible gates. Further, we have presented a synthesis
flows for overflow detection and overflow correction in
the reversible logic circuit based on Toffoli gates. The
synthesis flow investigates two modes i.e., no correction
and correction solutions. The use of decimal number after
9 leads to correction modes in overflow detection. In addi-
tion, conservative, reversible master-slave D-FF is intro-
duced. Further, the circuit of control inputs based testable
J. Comput. Theor. Nanosci. 2017, Vol. 14, No. 5 1546-1955/2017/14/2515/013 doi:10.1166/jctn.2017.6772 2515

IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
RESEARCHARTICLE
Novel Tree Structure Based Conservative Reversible BCD Adder and Sequential Circuit with Added High Testability Misra et al.
master-slave D-FF is designed. This work new sequential
master-slave D-FF is introduced that include the quantum
equivalent realization for the first time.
The major achievements of this work are given as
follows:
• We propose a BCD adder and master-slave D-FF cir-
cuits based on conservative, reversible gates. The synthesis
circuits currently target the reversible circuit based on the
Toffoli gate library.
• We present a synthesis flow of overflow detection and
overflow correction logic circuits based on the reversible
circuit.
• A new model of testable sequential master-slave D-FF
is introduced, which employed control input test vectors to
test a circuit accurately. Control output signals ensure the
testability of this circuit. This testing approach is incorpo-
rated with simple and efficient in the digital circuit testable
world.
• The proposed BCD adder and master-slave D-FF was
very efficient regarding the reported cost metrics such as
GC, CI, GO and QC.
The remainder of the paper is organized as fol-
lows: Section 2, discussed the basic terminologies.
In Sections 3–7, previous work, quantum circuit, the build-
ing block of BCD adder, the design of BCD adder, the
design of master-slave D-FF. Section 8 discussed the com-
parison results. Final Section 9 concludes the work.
2. BASIC TERMINOLOGIES
This section presents an introduction of some of the basic
details (what is reversible logic and need of it, the conser-
vative logic need of it, and some existing reversible gates)
for the understanding of work easily.
Definition 2.1. Reversible logic has dissimilar with
conventional circuits, which have a special bijective map-
ping between the inputs and outputs. Figure 1(a) shows
the reversible gate which have the same number of inputs
and outputs.4
Definition 2.2. In conservative, reversible gate the
hamming weight of input and output is equal, i.e., Ex-OR
of all inputs equals Ex-OR of all outputs.4
The integra-
tion of reversible logic and conservative logic is equal to
conservative reversible logic as shown in Figure 1(b).
Reversible
Gate
Bijective-mapping
Reversible Logic
Conservative Logic
Conservative Reversible Logic
(a) (b)
Fig. 1. An n ×n architecture of: (a) Reversible gate; (b) Conservative
reversible logic.
1 2 21
(a) (b)
43 5
1 2 3 4 5 6
(c)
Fig. 2. Existing conservative reversible gate: (a) F2G; (b) FRG;
(c) R-CQCA.
A reversible logic circuit which is employing quantum
gates in many logics bits are un-utilized. Therefore the
garbage bits in the circuit should be optimal. For design-
ing efficient reversible circuits, it is needed to minimize
garbage bits to an efficient design. In reversible logic cir-
cuits some constraints are highlighted below:
(1) In the reversible system model, both in no feedback
paths to ensure acyclic and fan-out free in case of cascade
gates.
(2) Reversible circuits have an equal count of inputs and
outputs.
2.1. Existing Conservative, Reversible Logic Gates
The existing conservative, reversible gates such as F2G,
FRG, and R-CQCA have attracted the researcher’s atten-
tion during the last decades for the synthesis and optimiza-
tion for various kinds of circuits.5 6
Figures 2(a)–(c) shows
the reversible circuit of F2G, FRG, and R-CQCA gates
respectively.
After introducing reversible logic, conservative logic,
and existing conservative, reversible gate are described
in this section. The organization of this paper is also
described in this section.
3. STUDY OF PREVIOUS WORK
A lot of research work on reversible computation has been
carried out in the area of logic synthesis, and optimization.
An extensive state-of-art-work of reversible BCD adder
and sequential circuits have already done.7–23
However,
there is not much work in testability of reversible BCD
adder circuit and sequential circuit. The scope of reversible
BCD adder and testable sequential circuit in the quantum
computing paradigm are finally tackled in this work.
In Valinataj et al.7
proposed a fault-tolerant BCD
adder using the LCG gate for optimizing the reversible
metrics. These designs are suffering more gate count.
A fault-tolerant BCD adder is implemented by ZPLG, ZC,
and ZQCG gates in RI-GUI Zhou et al.8
but suffered
from the quantum circuit of BCD adder. Ashish kumer
2516 J. Comput. Theor. Nanosci. 14, 2515–2527, 2017

IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
RESEARCHARTICLE
Misra et al. Novel Tree Structure Based Conservative Reversible BCD Adder and Sequential Circuit with Added High Testability
Biswas et al.9
presented reversible BCD adder using pro-
posed MTSG, FRG, TG, FG, PG gates. These designs are
not conservative approach but reversible and suffer more
quantum cost and garbage outputs.
Singh et al.,22
Hari et al.,23
presented the reversible
implementation of sequential logic circuits. They also
measure the sequential circuit parameters such as gate
count, garbage outputs, ancilla inputs, and quantum cost.
The conservative reversible sequential circuits along with
testability approach have been performed as reported by
Thapliyal et al.21
In this circuit construction framing, FRG
gate is utilized.
Therefore, after the careful reviewing the state-of-the-art
works on these reversible circuit synthesis of BCD adder
and testable sequential circuits. The limitations of most of
these works targeted the reversible gate based circuit syn-
thesis and optimizing reversible parameters, while lacking
work on quantum logic circuit construction, and testability.
The limitation of these works has finally tackled this work.
4. QUANTUM CIRCUIT
Quantum computing model is adopted for circuit construc-
tion such as the qubit transmission use of quantum wire
and quantum gates for qubit processing. Elemental quan-
tum gates (CNOT, NOT, C-V, and C-V+
) is used for QC
calculation.24
5. BUILDING BLOCKS FOR CONSERVATIVE,
REVERSIBLE BCD ADDER
This section introduces an optimal circuit of BCD
adder. To synthesize the optimal BCD adder three new
conservative reversible gates, namely HAS-PP (Half adder
subtraction parity preserving), FAS-PP (Full adder sub-
traction parity preserving), and OD-PP (Overflow detec-
tion parity preserving) are introduced. Sections 5.1–5.3
presents the design of HAS-PP, FAS-PP, and OD-PP gates
respectively. Section 6 presents the synthesis technique for
constructing BCD adder with lesser cost metrics compared
with previous works in the literature. The fault coverage
of the overflow detection gate is shown in Section 6.8.
5.1. Proposed HAS-PP Gates
Figure 3(a) shows the proposed HAS-PP gate; it maps
inputs (A B C D) to output A AC ⊕B A⊕C A ¯C ⊕D).
The bijective mapping is presented in Figure 3(b).
In Figure 3(c) shows that: By setting the second and fourth
input to ‘0’, the fan-out of circuit of A is realized in first
output. At the same time A·C , A⊕C , and A· ¯C are
realized in second, third, and fourth output, respectively.
The major advantage of these outputs is the realization
of the half-adder and half-subtraction circuit as shown in
Figure 3(c). It is interesting to realize the reversible and
quantum circuit for HAS-PP gate shown in Figure 3(d).
5.2. Proposed FAS-PP Gate
This section presented a conservative, reversible FAS-PP
gate as shown in Figure 4(a). The mapping is shown in
Figure 4(b). It is interesting to realize the full adder and
full subtraction. Figure 4(c) shows the procedure to use
FAS-PP for achieving the full adder and full subtraction.
Figure 4(c) indicates that: fourth and fifth input to ‘0’
the full adder function at the second and fourth output,
whereas full subtraction at the second and third output.
The reversible and quantum circuit of FAS-PP gate is pre-
sented in Figure 4(d).
HAS-PP
HAS-PP
HAS-PP
PG
1 2 3 4 5 0 6 7
(a) (b)
(c)
(d)
Fig. 3. Novel HAS-PP: (a) Functional schematic; (b) Truth table; (c) Implementation of Half addersubtraction; (d) QE.
J. Comput. Theor. Nanosci. 14, 2515–2527, 2017 2517

IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
RESEARCHARTICLE
FAS-PP
PG
1 2 3 4 5 6 7 8 9 10
(a) (b)
(c)
(d)
FAS-PP
FAS-PP
FAS-PP
Fig. 4. Novel FAS-PP: (a) Function schematic; (b) Truth table; (c) Implementation of Full addersubtraction; (d) QE.
5.3. Proposed OD-PP Gate
Figure 5(a) presents a functional schematic of OD-PP
gate. It is a 5 × 5 conservative reversible gate which
maps input vector A B C D E to output vector
P = B +C D ⊕AD ⊕DE ⊕A Q = B R = C S =
D T = B + C ⊕ E ⊕ AD ⊕ DE . The utility of OD-PP
as an overﬂow detection in the design of BCD adder.
Figure 5(b) shows that by setting E = 0, the fan-out of
OD-PP OD-PP
OD-PP
OD-PP
1 2 3 4 5 6 7 8 9 10 11 12 13
(a)
(d)
(b)
(c)
Fig. 5. Novel OD-PP: (a) Function schematic; (b) Implementation of OD; (c) QE, (d) Truth table.

IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
RESEARCHARTICLE
circuit of B C D are realized in second, third, and fourth
output respectively. At the same time B + C D ⊕ A is
realized in first output. The major advantage of these
outputs is the realization of BCD adder construction
(In Section 6.5). The bijective mapping as well as con-
servative property is shown in Figure 5(c). The reversible
and quantum circuit is presented in Figure 5(d).
6. THE PROPOSED CIRCUIT MODEL OF
BCD ADDER
In this section, we construct a BCD adder. The proposed
BCD adder based on three modules such as ripple carry
adder (module-1), overflow detection (module-2) and over-
flow correction (module-3) are constructed. These modules
are constructed using new gates. These new gates have
reduced the steps of logical computations required in mod-
ules construction.
6.1. Module-1 Design
Four FAS-PP gate designs the module-1. The QC of a
module-1 is 40. The working principles of the module-1
have utilized the 4-bit binary data, which comprises 12
garbage outputs as depicted in Figure 6. The one FAS-
PP can be setting the fourth and fifth inputs to be low.
The sum and carry are obtained at the second and fourth
output respectively. Figure 6 shows the reversible circuit
of module-1.
OD-PP gate designs the block of module-2 is shown in
Figure 7. The optimized QC of module-2 is 13. The
OD-PP gate is named as module-2. The module-2 has
5 inputs and 5 outputs which contain 1 garbage outputs g1.
The working on the module-2 is to utilize Cout logic bit.
The Cout logic bit specifies the overflow detection occur
or not. Module-2 synthesis the Cout logic bit was con-
structed from Figure 7, when setting the fourth input of
the module-2 to low the fan-out logic bits are generated
at second, third, and fourth output respectively. If the Cout
logic bit is high signifies that overflow correction and pass
Cout logic bit to the module-3, otherwise, no correction
required and collect the correct BCD sum results.
FAS-PP FAS-PP FAS-PP FAS-PP
Fig. 6. The proposed QE of a ripple carry adder.
Fig. 7. Overflow detection by OD-PP.
In Figure 8(b), integrate block OC cell (Overflow correc-
tion cell) is constructed by cascading the HAS-PP, FAS-
PP, and F2G gates. The OC cell is named as module-3.
The module-3 has 9 inputs and 9 outputs, which contain 5
garbage outputs (g1 to g5). Module-3 can be setting appro-
priately by ancilla inputs (1s and 0s) on the HAS-PP, FAS-
PP, and F2G gates as shown in Figure 8(a). The working
of module-3 is utilized outputs Z1, Z2, Z3 and Cout2. The
Z2, Z3 represent the final corrected bits, and Z4, will be
effective BCD sum results. The reversible circuit is shown
in Figure 8(c).
6.4. The Proposed Tree Structure of 4-Bit BCD Adder
The computational operation for executing the BCD adder
is the correct result within the decimal digit 9. The
reversible circuit of 4-bit BCD adder is presented in
Figure 9(a). The integrated block of 4-bit BCD adder
is constructed by cascading module-1, module-2, and
module-3. It can complete the 4-bit BCD adder design.
The module-1 contains four FAS-PP. The input includes
eight binary data inputs (A1, B1, A2, B2, A3, B3, A4, B4,)
including carry input Cin and 14 ancilla inputs as shown in
Figure 9(a). The working process is described as: First: the
sum is generated from the module-1. Second: module-2
circuit detects the overflow (Sum > 9) condition, then it
pass to the module-3. Finally: module-3 correct the logic
bits and generate the BCD sum results.
6.5. The Proposed Tree Structure of n-Digit
BCD Adder
In Figure 9(b), it consists of (n−1)-digit BCD adder, and
1-digit BCD adder. It can complete n-bit BCD adder func-
tions independently. The structure consists of an (n − 1)-
digit BCD adder with the extended factor of (n − 1 × 9
and 1-digit BCD adder with an extended factor of 8. The
extended factor means a number of gates utilized. Here
n-digit BCD adder design utilizes total extended factor of
n − 1 × 9 + 8 = 9n − 1 . The reversible metrics of n-
bit BCD adder is shown in Table I. The n-bit BCD adder
herein was constructed using the Algorithm 1.

IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
RESEARCHARTICLE
HAS-PP FAS-PP
F2G
OC
Cell
(a) (b)
(c)
Fig. 8. The proposed architecture of overflow correction: (a) Functional schematic; (b) OC cell; (c) QE.
6.6. Established Synthesis of Overflow Detection by
OD-PP Gate
OD-PP gate designs the block of overflow detection is
depicted in Figure 10. The working of the overflow detec-
tion is to utilize four outputs (C3, S2, S3, S4). The OD-PP
circuit generates the correct outputs in binary coded dec-
imal input range from 0 to 9. The correction is required
after decimal digit input of 9. The Cout logic bit is ‘0’ in
the case of decimal input less than 9. In the case, when
decimal digit greater than 9, three stages of overflow detec-
tion as Firstly: the S4 = S2 = 1 in the case of a decimal
digit in between 10 and 11. Secondly: S4 = S3 = 1 in the
case of the decimal digit in between 12 to 15. Thirdly: the
C3 = 1, for a decimal digit in between 16 to 19, as shown
in Figure 10.
6.7. Established Synthesis of Overflow Correction by
OC-PP Cell
The overflow correction is synthesized by 3 gates (1 ×
FAS-PP, 11 × HAS-PP, 11 × F2G), it requires 4 inputs
(Cout, S2, S3, S4) and 5 ancilla inputs. The circuit pro-
duces 4 outputs (Z1, Z2, Z3, Z4) as shown in Figure 11(a).
In order to established synthesis of overflow correction by
OD-PP cell the Cout logic bit is high value. The intermedi-
ate outputs are Cout1, and Cout2, it has the operation tables is
presented in Figures 11(b), (c). The computations of Cout,
S2, S3, and S4 generate the outputs such as Z2, Z3, and
Z4. The inputs of OC-PP cell and outputs are presented in
Figures 11(d), (e). The result of Z1, Z2, Z3, and Z4 are the
correct BCD sum. The complete structure of work done
around BCD adder is presented in Figure 12.
Algorithm 1 (BCD Adder Design (4-bit)).
Input, output: Binary input (A1, A2 An) and output
(Z1 Z2 Zn) for BCD operation
Begin
Stage-1: Require 4 unit of FAS-PP
Begin procedure
1: For i = 4 to 1
2: If i = 4 then
Si = Ai ⊕Bi ⊕Ci;
Ci = Ai ⊕Bi Ci ⊕AiBi
End if
End if
Stage-2: Require 1 unit of OD-PP
Take Si, and Ci logic bits from previous result outputs
and generate four outputs like Cout, S2, S3, and S4
for overflow detection stage.
Being procedure
3: For i = 3 to 0
If i = 3 then
O1 = Cout, O2 = S2, O3 = S3,
and O4 = S4, // Using OD-PP cell
End if
End procedure
Stage-3: Overflow detection
4: If i = 2 then
If O1 > 9 then
Pass the Cout, to
Stage-4 // Correction required
Else
Store the O2, O3, O4, and
S1 // Final BCD outputs

IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
RESEARCHARTICLE
Ripple carry full adder
BCD overflow detection
BCD overflow correction
(a)
(b)
i=4 to 1
i=4 to 1
Signal
duplication
m=3 to 1
n=3 to 1
j=4 to 3
j=4 to 3
Fig. 9. The proposed BCD adder: (a) 4-digit; (b) n-digit.
Table I. Reversible metric of proposed n-bit BCD.
Metrics Explanation Value
GC n−1 ×EFdesign +8 = n−1 × 5 EF design–FAS–PP +1 EF design–OD–PP n−1 ×9+8 = 9n−1
+2 EF design–F2G +1 EF design–HAS–PP +8
QC n−1 ×QCdesign +1×QCdesign n−1 × 5×10+13+2×2+7 + 5×10+13+7+2
= n−1 × 5× QCdesign–FAS–PP +1(QCdesign–OD–PP +2(QCdesign–F2G = n−1 ×74+72 = 74n−2
+1(QCdesign–HAS–PP + 5× QCdesign–FAS–PP +1 (QCdesign–OD–PP
+1(QCdesign–HAS–PP +1 (QCdesign–F2G
GO n−1 ×GOdesign +1×GOdesign n−1 × 5×3+1×1+2×1+1 + 5×3+1+1+1
= n−1 × 5× GOdesign–FAS–PP +1(GOdesign–OD–PP +2(GOdesign–F2G = n−1 ×19+18 = 19n−1
+1(GOdesign–HAS–PP + 5× GOdesign–FAS–PP +1(GOdesign–OD–PP
+1(GOdesign–HAS–PP +1(GOdesign–F2G
Notes: EF: Extended factor; GC: Gate count; QC: Quantum cost; GO: Garbage output.

IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
RESEARCHARTICLE
No correction required
Correction required
OD-PP circuit
Fig. 10. Synthesis flows circuit for overflow detection by using OD-PP
circuit.
End if
End if
Stage-4: Require 1 unit of OC-PP cell
Take O1, O2, O3, and O4 logic bits from previous
result outputs and generate four BCD outputs.
Begin procedure
5: If i = 1 then
Z1 = S1, Z2 = Cout ⊕S1, Z3 = S2 ⊕Cout1 ⊕Cout,
Z3 = Cout2 ⊕S3 //Using OC-PP cell
End if
End procedure
End for
End;
6.8. Fault Testing and Coverage
Fault-testing refers to the process of observing fault. The
aim of testing is to compute the output logic bit in the
circuit being developed. Testing in the reversible circuit is
a complicated process, and its various evolutions are under
research.24
The testing of reversible circuits is a complex
process that influences by ensuring the correct functioning
of the system design.24
In this work off-line and on-line testing, the methodol-
ogy has been adopted to cover the fault under different test
vectors. The fault-testing methodology such as online and
offline are described below:
On-Line Testing: In this method, fault detection is com-
putationally efficient and easy on applied test vectors and
also characterized by the system itself find fault quickly
follow the abrupt transition of bits. The online testing fault
detection base of the conservative logic has been utilized
for their parity bits conserved. Also, the reversible circuits
of control input based testable are also include in this fault-
testing methodology.
Off-Line Testing: The fault estimation is given by the
applied test vectors after looking at the output and then
match the known outputs. This testing is categorized as
stuck-at-fault and missing gate and missing control fault.
These faults are commonly used for efficient testing of
circuits.
Add (0110) = 6,
Using OC-PP circuit
OC-PP circuit
BCD
Sum
(a)
(b)
(d) (e)
(c)
Fig. 11. Synthesize flow circuit for overflow correction by OC-PP circuit; (a) Quantum circuit; (b) Input Cout1; (c) Input Cout2; (d) Circuit inputs;
(e) BCD outputs.

IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
RESEARCHARTICLE
Proposed HG-PP, FAS-
PP, OD-PP gates
Utilization of novel gates as
‘ripple carry adder’
Quantum
circuit of
overflow
detection
Reference set
as decimal 9
Sum pass
Normal procss generate
the BCD results
Sum< 9
Quantum circuit
of overflow
correction
Sum > 9
Add (0110) = 6
Generate the BCD results
Fig. 12. The structure of BCD adder design flow.
6.9. Fault Testing/Debugging in OD-PP Gate by
Stuck-at-Fault
The stuck-at fault testing approach is a two type such
as stuck-at-0 (s-a-0), and stuck-at-1 (s-a-1). The conven-
tional stuck-at-fault testing approach is applicable in the
reversible circuit. The overflow detection gate (OD-PP) has
illustrated the stuck-at-fault pattern as shown in Table II.
The procedure for fault patterns are generated in the fol-
lowing description: First, choose any test input vectors
and find the target output vectors. The test input fault
is s-a-0 and s-a-1. For s-a-0/1, flip the bit, then find the
Table II. Fault coverage in OD-PP.
Stuck-at-fault In/Out Test: In/Out Target out Fault pattern
s-a-0 A 11111 01110 01111
B 11111 01110 00110
C 11111 01110 01010
D 11111 01110 11101
E 11111 01110 11110
P 11101 11101 01101
Q 11111 01110 00110
R 11111 01110 01010
S 11111 01110 01100
T 11101 11101 11100
s-a-1 A 00000 00000 10000
B 00000 00000 01000
C 00000 00000 00100
D 00000 00000 00010
E 00000 00000 00001
P 00000 00000 10000
Q 00000 00000 01000
R 00000 00000 00100
S 00000 00000 00010
T 00000 00000 00001
Analysis: Minimal test vector = 3, Fault coverage = 11111 = 6/16×100 = 37 5%.
11101 = 2/16×100 = 12 5%, 00000 = 8/16×100 = 50%, Total Fault coverage =
37 5+12 5+50 ×100 = 100%
corresponding outputs and vice versa. In the case of out-
put, fault flips the output bit, then draw the fault pattern
according to stuck fault model either s-a-0/1.
6.10. Fault Testing/Debugging in OD-PP Gate by
Quantum Circuit Model
A large amount of works has been done in the reverse
circuit synthesis. Nevertheless, on that point is not much
Table III. Single missing gate fault in OD-PP.
SMGFs Marking method Test in Target out Fault pattern
1 [∗
a] 11111 01110 11110
2 [∗
cd] 11111 01110 11111
3 [∗
bcd] 11111 01110 11111
4 [∗
de] Fault-free
5 [∗
bd] 11111 01110 11111
6 [∗
a] Fault-free
Minimum test vector = 1, Fault coverage = 4/4×100 = 100%
Notes: ∗
Means missing control gate; SMGF: Single missing gate fault.
Table IV. Single missing control fault in OD-PP.
SMCFs Marking method Test in Target out Fault pattern
1 [e∗
] 11111 01110 11110
2 [ac∗
] Fault-free
3 [a∗
d] Fault-free
4 [abc∗
] Fault-free
5 [ab∗
d] Fault-free
6 [a∗
cd] Fault-free
7 [ad∗
] 11111 01110 11111
8 [ad∗
] Fault-free
9 [ab∗
] Fault-free
10 [a∗
d] Fault-free
11 [e∗
] Fault-free
Minimum test vector = 1, Fault coverage = 2/2×100 = 100%
Notes: ∗
Means missing control point; SMCF: Single missing control fault.

IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
RESEARCHARTICLE
[e a]
[acd]
[abcd]
[ade]
[abd]
[e a]
Single missing gate fault
1 2 3 4 5 6
Single missing control fault
(a) (b)
Fig. 13. Fault coverage in OD-PP: (a) SMGF; (b) SMCF.
research work in the field of BCD adder such as testing
quantum circuit. Most of the work in the area of reversible
BCD adder constructed the circuit.7–9 20
These works open
a door to go through the BCD adder and testing quantum
circuit. More recent work reported the parity preserving
circuits does not ensure the fault tolerant.25
These work
open a door to the essential the quantum circuit testing in
high testability area. In this work both control point and
control gate are tested independently and then integrated
for fault coverage. In addition, we target the maximum
fault coverage with minimum test vectors. The analysis of
overflow detection with OD-PP gate based on the single
missing gate and a single control point which covers the
100% with only two test. It is analyzed that according to
Tables III, IV that maximum 2 test vectors include the
complete testing. The testing, design stages that are being
presented in Figures 13(a), (b).
7. THE PROPOSED MASTER SLAVE D
FLIP-FLOP
A master-slave D Flip-flop consists of two units of
R-CQCA gate. The circuit construction is depicted in
Figure 14(a). Master-slave solves the difficulty of the race
around condition. In the Figure 14(a) master unit operates
with positive triggered and slave operate with negative trig-
ger. The quantum equivalent synthesizes the schematic dia-
gram in Figure 14(b). The third output of first R-CQCA is
X = Qt
¯Clk +Clk D . This third output of first R-CQCA
gate is associated as input to the first input of second
R-CQCA gate. When Clk = 1, the output X = D means
the master has passed the input, but slave output (Qt+1) is
the previous state. The master circuit work and slave hold
the previous state. Another case Clk = 0, the X becomes a
storage (Hold the previous state), whereas Qt+1 becomes
X means pass the output of the master. Where X is the
third output of first R-CQCA gate.
7.1. Testable Master-Slave D Flip-Flop
The testable master-slave D-FF contains 4 gates (2 × R-
CQCA, and 2 × FRG) it needs 8 inputs and 8 outputs as
shown in Figure 15(b). The inputs include Clock (Clk)
and Data (D), 2 constant inputs and 4 test vectors (I1, I2,
I3, and I4). The two test vectors (I1, I2) are employed for
the testable circuit of master, and other two test vectors
(I3 I4) are used for the testable circuit of a slave. The
test vectors are the notation of control inputs. This design
has the option to set a control input, which is compared
with three testing modes (normal, s-a-0, and s-a-1). If test-
ing vectors match any three modes, the design ensures
the testable feature and safely run the logic computation.
Testable modes are presented in Figure 15(b). The con-
struction of testable D flip-flop are utilized reversible met-
rics GC of 4, GO of 5, and QC of 22.
7.2. Behavioral Description of Testable
Master-Slave D Flip-Flop
The testable master-slave D-FF consists of two levels,
namely, the testable circuit of master and testable circuit
of the slave as shown in Figure 15(a). These level are
then extensively used to synthesize the testable circuit of
master-slave D-FF. These level are described below:
First level: In the first level is used of 1×R-CQCA, and
1 ×FRG to generate the O1, and O2 of the testable signal
for the master block. The first R-CQCA is generated the
two outputs as Q = Clk, and R = Qt
¯Clk +Clk D . The
R output of first R-CQCA is applied as input to the first
FRG gate. The second output of the FRG is feedback to
input of first R-CQCA.
Second level: In the second level is used of 1 × R-
CQCA, and 1 × FRG to generate the O3, and O4 of the
testable signal for the slave block. The output of first FRG
are O1 = I1
¯R +R I2 , and O2 = R I1 + ¯R I2 . Whereas
the output of second FRG are O3, and O4. The notation I1,
I2, I3, and I4 are the test vectors. The behavioral descrip-
tion for the testable master-slave D-FF is divided into three
steps are described below:
(a) If input control signal set as (I1, I2 = 0 1 the output
signal becomes O1 = ¯QtI1 ⊕ QtI2 = Qt. It means circuit
work in normal mode.
(b) If input control signals are applied to the individual
level as master block of (I1, I2 = 0 0 and slave block
of (I3, I4 = 0 0 the output signal becomes O1 = O2 = 0,
and O3 = O4 = 0 the circuit will scan all the 0’s logic input
signals. It means the circuit work in s-a-1 fault mode.
(c) If input control signals are applied to the individual
level as, master block of (I1, I2 = 1 1 and slave block
of (I3, I4 = 1 1 the output signal becomes O1 = O2 = 1,

IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
RESEARCHARTICLE
Fig. 14. The proposed master-slave D-FF, its QC is 8, (a) schematic diagram, (b) QE realization.
R-CQCA R-CQCAFRG
FRG
Testable circuit of Master Testable circuit of Slave
Normal mode
Stuck-at-1 fault
Stuck-at-0 fault
(a)
(b)
Fig. 15. Testable logic circuit: (a) Master-slave D Flip-ﬂop; (b) testable
modes.
and O3 = O4 = 1 the circuit will scan all the 1’s logic input
signals. It means the circuit work in s-a-1 fault mode.
8. REVERSIBLE COMPUTING
PERFORMANCE METRICS EXTRACTION
OF BCD ADDER CIRCUITS
Reversible metrics extraction is an essential of the
reversible circuit synthesize for the performance point.27 28
The reversible metrics provide several aspects i.e., GC,
QC, and GO. The reversible circuit synthesize depends on
the metrics that affect the circuit performance cost. The
proposed circuit is compact and less GC, as well as QC as
compared to other circuit designs. This work BCD adder
construction approach is introduced that include quantum
circuit realization for the ﬁrst time. Table V illustrated
the performance metrics of Full adderSubtraction with
existing circuits which shows the lower metrics with coun-
terpart circuit. Table VI shows the performance metrics
used in BCD adder as per existing circuit. The smaller
Table V. Comparison cost of reversible full adder/subtraction.
FA/FA on
Gate same
Circuit type GC CI GO QC QE RC FA/FS architecture
[7] LCG 1 2 3 10 Y Y/Y Y/N N
[8] ZPLG 1 2 3 8 Y Y/Y Y/N N
[9] MTSG 1 1 2 6 Y Y/N Y/N N
[10] FAST 1 2 2 10 Y Y/Y Y/Y Y
[11] PPFA/S 2 2 2 8 Y Y/Y Y/Y Y
[12] ZRQG 1 1 2 8 Y Y/N Y/Y N
[13] TSG 1 1 2 12 Y Y/N Y/N N
[14] PPRG 3 1 5 21 N Y/Y Y/N N
[15] PPR 1 2 3 9 Y Y/Y Y/N N
[16] F2G, NPPG, 3 2 3 10 Y Y/Y Y/N N
FRG
[17] HNG 1 1 2 6 Y Y/N Y/N N
[18] ZS2 1 2 2 – N Y/N Y/N N
[19] NFTFAG 1 2 3 9 Y Y/Y Y/N N
[20] BHPF, BHPS 2 2 2 8 Y Y/Y Y/Y Y
Novel FAS-PP 1 2 2 10 Y Y/Y Y/Y Y

IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
RESEARCHARTICLE
Table VI. Comparison cost of the reversible BCD adder.
Circuit Gate type GC CI GO QC QE RC
[7] circuit#1 LCG, FRG, 11 12 18 67 N YY
F2G, MIG
[7] circuit#2 ZPLG, FRG, 11 15 20 59 N YY
F2G, ZCG
[8] ZPLG, ZQCG, 8 14 18 61 N YY
ZCG, F2G
[9] MTSG, FRG, TG, 10 7 10 55 N YN
FG, PG
[20] BHPC, BHPB, BHPA, 11 10 14 54 N YY
BHPF, BHPS
Novel FAS-PP, HAS-PP, 8 14 18 72 Y YY
OD-PP, F2G
Table VII. Comparison cost of the reversible master-slave D-FF.
Design Gate type GC CI GO QC QER R/C
[21] FRG, FG 4 2 3 12 N Y/N
[22] MF, FG, NOT 5 2 3 11 N Y/N
[23] FRG, FG 4 2 3 12 N Y/N
[26] Pareek 2 2 3 14 N Y/Y
Novel R-CQCA 2 2 3 12 Y Y/Y
reversible metrics can be accepted in the reversible circuit
than in other competitive larger metrics reversible circuit
with same operations.
The existing master-slave D-FF utilizes the reversible
gates which result in more gate count, garbage output,
and quantum cost. It can be observed that present master-
slave D-FF based on conservative, reversible gates requires
50% less gate count than,21
and 14.28% less quantum cost
than.26
The proposed circuits have surpassed the existing
circuits and are optimized regarding reversible metrics.
Table VII shows the comparison cost result of the proposed
master-slave D-FF.
9. CONCLUSION
In this work, it is shown that conservative, reversible logic
is effective for ensuring the robustness of circuit in the
application of observation and controllable operation. Pre-
dominately, this work targets circuit of BCD adder and
master-slave D-FF using conservative, reversible gates.
The reduction in reversible metrics using the R-CQCA for
master-slave D-FF to meet the requirement of quantum
computing paradigm. Further, the testable master-salve D-
FF presented here is to develop circuits using minimum
test vectors and can find diverse applications in the test-
ing paradigm. In addition, low-cost conservative, reversible
BCD adder is established. It can find diverse applica-
tion in the reduction of quantum realization and quantum
cost optimization. Testing overhead is also mitigated by
means of effective stuck-at-fault coverage and quantum
circuit’s missing gate fault and missing control fault cov-
erage. Also, fault testing/debugging in a quantum circuit
related to adder has not been applied so far for the reliabil-
ity of the circuit is reported here with. The design capabil-
ity of the proposed BCD adder for complex logic circuits
such as an arithmetic logic unit which is also explored
here.
References
1. R. Landauer, IBM Journal of Research and Development 3, 183
(1961).
2. C. H. Bennett, IBM Journal of Research and Development 32, 16
(1988).
3. Neeraj Kumar Misra, Bibhash Sen, and Subodh Wairya, Journal of
Computational Electronics 16, 1 (2017).
4. Neeraj Kumar Misra, Bibhash Sen, and Subodh Wairya, Journal of
Nanoengineering and Nanomanufacturing 6, 201 (2016).
5. E. Fredkin and T. Toffoli, International Journal of Theoretical
Physics 21, 219 (1982).
6. Neeraj Kumar Misra, Subodh Wairya, and Bibhash Sen, Ain Shams
Engineering Journal Elsevier (2017), DOI: doi.org/10.1016/j.asej.
2017.02.005, In Press.
7. Mojtaba Valinataj, Mahboobeh Mirshekar, and Hamid Jazayeri,
Computers and Electrical Engineering 53, 56 (2016).
8. R.-G. Zhou, Y.-C. Li, and M.-Q. Zhang, International Journal of
Electronics 101, 1336 (2014).
9. Ashis Kumer Biswas, Md Mahmudul Hasan, Ahsan Raja
Chowdhury, and Hafiz Md Hasan Babu, Microelectronics Journal
39, 1693 (2008).
10. Ankur Sarker, Avishek Bose, and Shalini Gupta, Design of a com-
pact fault tolerant adder/subtractor circuits using parity preserving
reversible gates, IEEE 17th International Conference on Computer
and Information Technology (ICCIT) (2014), pp. 1–7.
11. Majid Haghparast and Ali Bolhassani, International Journal of The-
oretical Physics 55, 1423 (2016).
12. R. Zhou, M. Zhang, Q. Wu, and Y. Shi, International Journal of
Electronics 99, 1395 (2012).
13. Himanshu Thapliyal and M. B. Srinivas, A novel reversible TSG
gate and its application for designing reversible carry look-ahead and
other adder architectures, In Asia-Pacific Conference on Advances in
Computer Systems Architecture, Springer, Berlin, Heidelberg (2005),
pp. 805–817.
14. Arman Roohi, Ramtin Zand, Shaahin Angizi, and Ronald F. Demara,
IEEE Transactions on Emerging Topics in Computing (2016), DOI:
10.1109/TETC.2016.2593634, In Press.
15. Majid Haghparast and Soghra Shoaei, Journal of Circuits, Systems
and Computers 24, 1550006 (2015).
16. Soghra Shoaei and Majid Haghparast, Quantum Information Pro-
cessing 13, 1701 (2014).
17. Majid Haghparast, Majid Mohammadi, Keivan Navi, and Moham-
mad Eshghi, Journal of Circuits, Systems, and Computers 18, 311
(2009).
18. R. Zhou, Y. Shi, and J. Cao, Microelectronics Journal 42, 305
(2011).
19. Hafiz Md Hasan Babu and Md Solaiman Mia, Microelectronics Jour-
nal 51, 15 (2016).
20. Majid Haghparast and Ali Bolhassani, International Journal of The-
oretical Physics 55, 5118 (2016).
21. Himanshu Thapliyal and Nagarajan Ranganathan, ACM Journal on
Emerging Technologies in Computing Systems (JETC) 6, 14 (2010).
22. P. L Singh, A. Majumder, B. Chowdhury, A. J. Mondal, and T. S.
Shekhawat, Procedia Computer Science 57, 189 (2015).
23. Siva Kumar Sastry Hari, Shyam Shroff, S. K. Noor Mahammad, and
V. Kamakoti, Efficient building blocks for reversible sequential cir-
cuit design, 49th IEEE International Midwest Symposium on Circuits
and Systems 1, 437 (2006).

IP: 103.37.201.41 On: Mon, 25 Dec 2017 13:58:14
RESEARCHARTICLE
24. Hari Mohan Gaur, Ashutosh Kumar Singh, and Umesh Ghanekar,
Procedia Computer Science 70, 384 (2015).
25. Nils Przigoda, Gerhard Dueck, Robert Wille, and Rolf Drechsler,
Fault detection in parity preserving reversible circuits, IEEE 46th
International Symposium on Multiple-Valued Logic (ISMVL) (2016),
pp. 44–49.
26. Vishal Pareek, Shubham Gupta, Sushil Chandra Jain, and
Divya Jain, Fault tolerant and testable designs of reversible
sequential building blocks, IEEE International Conference on
Computer Science and Engineering Conference (ICSEC) (2014),
pp. 452–457.
27. Bibhash Sen, Manojit Dutta, Samik Some, and Biplab K. Sikdar,
ACM Journal on Emerging Technologies in Computing Systems
(JETC) 11, 30 (2014).
28. R. Zhou, Y. Shi, M. Zhang, and H. Wang, Journal of Circuits, Sys-
tems, and Computers 20, 1107 (2011).
Received: 12 November 2016. Accepted: 15 December 2016.

Novel Tree Structure Based Conservative Reversible Binary Coded Decimal Adder and Sequential Circuit with Added High Testability

Recommended

More Related Content

What's hot (20)

Similar to Novel Tree Structure Based Conservative Reversible Binary Coded Decimal Adder and Sequential Circuit with Added High Testability (20)

More from VIT-AP University (20)

Recently uploaded (20)

Novel Tree Structure Based Conservative Reversible Binary Coded Decimal Adder and Sequential Circuit with Added High Testability