Оглавление
Hafiz M. H. Babu. Reversible and DNA Computing
Table of Contents
List of Tables
List of Illustrations
Guide
Pages
Reversible and DNA Computing
List of Figures
List of Tables
About the Author
Preface
Acknowledgments
Acronyms
Introduction
Part I Reversible Circuits. An Overview About Reversible Circuits
1 Reversible Logic Synthesis
1.1 Reversible Logic
1.2 Reversible Function
1.3 Reversible Logic Gate
Property 1.3.1
Example 1.1
1.4 Garbage Outputs
Example 1.2
1.5 Constant Inputs
Example 1.3
1.6 Quantum Cost
Example 1.4
Example 1.5
1.7 Delay
Example 1.6
1.8 Power
Example 1.7
1.9 Area
Example 1.8
1.10 Hardware Complexity
Example 1.9
1.11 Quantum Gate Calculation Complexity
Example 1.10
1.12 Fan‐Out
Example 1.11
1.13 Self‐Reversible
Example 1.12
1.14 Reversible Computation
1.15 Area
1.16 Design Constraints for Reversible Logic Circuits
1.17 Quantum Analysis of Different Reversible Logic Gates
Property 1.17.1
1.17.1 Reversible NOT Gate (Feynman Gate) Example 1.13
1.17.2 Toffoli Gate
1.17.3 Fredkin Gate
1.17.4 Peres Gate
1.18 Summary
2 Reversible Adder and Subtractor Circuits
2.1 Reversible Multi‐Operand n‐Digit Decimal Adder
2.1.1 Full Adder
The FAG Gate
Reversible FAG Gate as Full Adder
Property 2.1.1.1
Proof
Example 2.1.1.1
2.1.2 Carry Skip Adder
2.1.2.1 Design of Carry Skip Adder
Property 2.1.2.1.1
Proof
Property 2.1.2.1.2
Proof
Property 2.1.2.1.3
Property 2.1.2.1.4
Proof
Property 2.1.2.1.5
Proof
2.1.3 Carry Look‐Ahead Adder
Property 2.1.3.1
Proof
2.2 Reversible BCD Adders
Property 2.2.1
Example 2.2.1
Property 2.2.2
Example 2.2.2
Property 2.2.3
2.2.1 Design Procedure of the Reversible BCD Adder
Example 2.2.1.1
Example 2.2.1.2
Example 2.2.1.3
2.2.1.1 Properties of the Reversible BCD Adder
Property 2.2.1.1.1
Proof
Property 2.2.1.1.2
Proof
Property 2.2.1.1.3
Proof
Property 2.2.1.1.4
Proof
Property 2.2.1.1.5
Proof
2.2.2 Design Procedure of the Reversible Carry Skip BCD Adder
Example 2.2.2.1
2.2.2.1 Properties of the Reversible Carry Skip BCD Adder
Property 2.2.2.1.1
Proof
Property 2.2.2.1.2
Proof
Property 2.2.2.1.3
Proof
Property 2.2.2.1.4
Proof
2.3 Reversible BCD Subtractor
2.3.1 Carry Look‐Ahead BCD Subtractor
2.3.2 Carry Skip BCD Subtractor
2.3.3 Design of Conventional Reversible BCD Subtractor
2.3.3.1 Reversible Nine's Complement
2.3.3.2 Reversible BCD Subtractor
2.3.3.3 Reversible Design of Carry Look‐Ahead BCD Subtractor
2.3.3.4 Reversible Design of Carry Skip BCD Subtractor
2.4 Summary
3 Reversible Multiplier Circuit
3.1 Multiplication Using Booth's Recoding
3.2 Reversible Gates as Half Adders and Full Adders
3.3 Some Signed Reversible Multipliers
3.4 Design of Reversible Multiplier Circuit
3.4.1 Some Quantum Gates
3.4.2 Recoding Cell
3.4.3 Partial Product Generation Circuit
3.4.4 Multi‐Operand Addition Circuit
3.4.5 Calculation of Area and Power of Multiplier Circuit
Property 3.4.5.1
Proof
Example 3.4.5.1
Property 3.4.5.2
Proof
Example 3.4.5.2
Property 3.4.5.3
Proof
Example 3.4.5.3
Property 3.4.5.4
Proof
Example 3.4.5.4
Property 3.4.5.5
Proof
Property 3.4.5.6
Proof
Property 3.4.5.7
Proof
Property 3.4.5.8
Proof
Property 3.4.5.9
Proof
Property 3.4.5.10
Proof
Property 3.4.5.11
Proof
Property 3.4.5.12
Proof
Property 3.4.5.13
Proof
3.5 Summary
4 Reversible Division Circuit
4.1 The Division Approaches
4.1.1 Restoring Division
4.1.2 Nonrestoring Division
4.2 Components of Division Circuit
4.2.1 Reversible MUX
4.2.2 Reversible Register
4.2.3 Reversible PIPO Left‐Shift Register
4.2.4 Reversible Parallel Adder
4.3 The Design of Reversible Division Circuit
Property 4.3.0.1
Proof
4.4 Summary
5 Reversible Binary Comparator
5.1 Design of Reversible ‐Bit Comparator
5.1.1 BJS Gate
5.1.2 Reversible 1‐Bit Comparator Circuit
5.1.3 Reversible MSB Comparator Circuit
5.1.4 Reversible Single‐Bit Greater or Equal Comparator Cell
5.1.5 Reversible Single‐Bit Less Than Comparator Cell
5.1.6 Reversible 2‐Bit Comparator Circuit
5.1.7 Reversible ‐Bit Comparator Circuit
Property 5.1.7.1
Proof
Property 5.1.7.2
Proof
Property 5.1.7.3
Proof
Property 5.1.7.4
Proof
Property 5.1.7.5
Proof
Property 5.1.7.6
Proof
Example 5.1.7.1
5.2 Summary
6 Reversible Sequential Circuits
6.1 An Example of Design Methodology
6.2 The Design of Reversible Latches
6.2.1 The SR Latch
6.2.2 The D Latch
6.2.2.1 The D Latch with Outputs and
6.2.2.2 The Negative Enable Reversible D Latch
6.2.3 T Latch
6.2.4 The JK Latch
6.3 The Design of Reversible Master–Slave Flip‐Flops
6.4 The Design of Reversible Latch and the Master–Slave Flip‐Flop with Asynchronous SET and RESET Capabilities
6.5 Summary
7 Reversible Counter, Decoder, and Encoder Circuits
7.1 Synthesis of Reversible Counter
7.1.1 Reversible T Flip‐Flop
7.1.2 Reversible Clocked T Flip‐Flop
7.1.3 Reversible Master–Slave T Flip‐Flop
7.1.4 Reversible Asynchronous Counter
Property 7.1.4.1
Proof
Property 7.1.4.2
Proof
7.1.5 Reversible Synchronous Counter
Property 7.1.5.1
Proof
Property 7.1.5.2
Proof
7.2 Reversible Decoder
7.2.1 Reversible Encoder
7.3 Summary
8 Reversible Barrel Shifter and Shift Register
8.1 Design Procedure of Reversible Bidirectional Barrel Shifter
8.1.1 Reversible 3 3 Modified BJN Gate
8.1.2 Reversible 2's Complement Generator
Property 8.1.2.1
8.1.3 Reversible Swap Condition Generator
Property 8.1.3.1
8.1.4 Reversible Right Rotator
8.1.4.1 (4, 3) Reversible Right Rotator
8.1.4.2 Generalized Reversible Right Rotator
Property 8.1.4.2.1
8.1.5 Reversible Bidirectional Barrel Shifter
Property 8.1.5.1
8.2 Design Procedure of Reversible Shift Register
8.2.1 Reversible Flip‐Flop
8.2.1.1 Reversible SISO Shift Register
8.2.1.2 Reversible SIPO Shift Register
8.2.1.3 Reversible PISO Shift Register
8.2.1.4 Reversible PIPO Shift Register
Property 8.2.1.4.1
Proof
Property 8.2.1.4.2
Proof
Property 8.2.1.4.3
Proof
8.2.1.5 Reversible Universal Shift Register
Property 8.2.1.5.1
Proof
Property 8.2.1.5.2
Proof
Property 8.2.1.5.3
Proof
8.3 Summary
9 Reversible Multiplexer and Demultiplexer with Other Logical Operations
9.1 Reversible Logic Gates
9.1.1 RG1 Gate
9.1.2 RG2 Gate
9.2 Designs of Reversible Multiplexer and Demultiplexer with Other Logical Operations
9.2.1 The R‐I Gate
9.2.2 The R‐II Gate
9.3 Summary
10 Reversible Programmable Logic Devices
10.1 Reversible FPGA
10.1.1 Reversible NH Gate
10.1.2 4 4 Reversible BSP Gate
10.1.3 4‐to‐1 Reversible Multiplexer
Property 10.1.3.1
Proof
10.1.4 Reversible D Latch
Property 10.1.4.1
Proof
10.1.5 Reversible Write‐Enabled Master–Slave Flip‐Flop
10.1.6 Reversible RAM
10.1.7 Design of Reversible FPGA
Property 10.1.7.1
Proof
Property 10.1.7.2
Proof
Property 10.1.7.3
Proof
10.2 Reversible PLA
10.2.1 The Design Procedure
Property 10.2.1.1
Example 10.2.1.1
Property 10.2.1.2
Property 10.2.1.3
Proof
Property 10.2.1.4
Proof
Property 10.2.1.5
Proof
Property 10.2.1.6
Proof
Property 10.2.1.7
Proof
10.2.1.1 Delay Calculation of a Reversible PLA
10.2.1.2 Delay Calculation of AND Plane
10.2.1.3 Delay Calculation of Ex‐OR Plane
10.2.1.4 Delay of Overall Design
10.3 Summary
11 Reversible RAM and Programmable ROM
11.1 Reversible RAM
11.1.1 Reversible FS Gate
Property 11.1.1.1
Proof
11.1.2 Reversible Decoder
Property 11.1.2.1
Proof
Property 11.1.2.2
Proof
11.1.3 Reversible D Flip‐Flop
11.1.4 Reversible Write‐Enabled Master–Slave D Flip‐Flop
11.1.5 Reversible Random Access Memory
Property 11.1.5.1
Proof
Property 11.1.5.2
Proof
11.2 Reversible PROM
11.2.1 Reversible Decoder
11.2.2 Design of Reversible PROM
Property 11.2.2.1
Example 11.2.2.1
Property 11.2.2.2
Example 11.2.2.2
Property 11.2.2.3
Example 11.2.2.3
11.3 Summary
12 Reversible Arithmetic Logic Unit
12.1 Design of ALU
12.1.1 Conventional ALU
12.1.2 The ALU Based on Reversible Logic
12.1.2.1 The Reversible Function Generator
12.1.2.2 The Reversible Control Unit
12.2 Design of Reversible ALU
12.3 Summary
13 Reversible Control Unit
13.1 An Example of Control Unit
13.2 Different Components of a Control Unit
13.2.1 Reversible HL Gate
13.2.2 Reversible BJ Gate
13.2.3 Reversible 2‐to‐4 Decoder
13.2.4 Reversible 3‐to‐8 Decoder
13.2.5 Reversible ‐to‐ Decoder
Property 13.2.5.1
Proof
Property 13.2.5.2
Proof
13.2.6 Reversible JK Flip‐Flop
13.2.7 Reversible Sequence Counter
13.2.8 Reversible Instruction Register
13.2.9 Control of Registers and Memory
13.2.10 Construction Procedure and Complexities of the Control Unit
Property 13.2.10.1
Proof
Property 13.2.10.2
Proof
13.3 Summary
Part II Reversible Fault Tolerance. An Overview About Fault‐Tolerance and Testable Circuits
14 Reversible Fault‐Tolerant Adder Circuits
14.1 Properties of Fault Tolerance
Property 14.1.1
14.1.1 Parity‐Preserving Reversible Gates
14.2 Reversible Parity‐Preserving Adders
14.2.1 Fault‐Tolerant Full Adder
Property 14.2.1.1
Proof
14.2.2 Fault‐Tolerant Carry Skip Adder
Property 14.2.2.1
Property 14.2.2.2
Property 14.2.2.3
Property 14.2.2.4
Proof
Property 14.2.2.5
14.2.3 Fault‐Tolerant Carry Look‐Ahead Adder
Property 14.2.3.1
Property 14.2.3.2
Property 14.2.3.3
Proof
Property 14.2.3.4
Property 14.2.3.5
14.2.4 Fault‐Tolerant Ripple Carry Adder
14.3 Summary
15 Reversible Fault‐Tolerant Multiplier Circuit
15.1 Reversible Fault‐Tolerant Multipliers
15.1.1 Reversible Fault‐Tolerant Multiplier
15.1.2 LMH Gate
15.1.3 Partial Product Generation
15.1.4 Multi‐Operand Addition
Property 15.1.4.1
Proof
Property 15.1.4.2
Proof
Property 15.1.4.3
Proof
15.2 Summary
16 Reversible Fault‐Tolerant Division Circuit
16.1 Preliminaries of Division Circuits
16.1.1 Division Algorithms
16.2 The Division Method
16.2.1 Floating‐Point Data and Rounding
16.2.2 Correctly Rounded Division
Property 16.2.2.1
Proof
16.2.3 Correct Rounding from One‐Sided Approximations
16.2.4 The Algorithm for Division Operation
Property 16.2.4.1
Proof
16.3 Components of a Division Circuit
16.3.1 Reversible Fault‐Tolerant MUX
16.3.2 Reversible Fault‐Tolerant D Latch
16.4 The Design of the Division Circuit
16.4.1 Reversible Fault‐Tolerant PIPO Left‐Shift Register
16.4.2 Reversible Fault‐Tolerant Register
16.4.3 Reversible Fault‐Tolerant Rounding Register
16.4.4 Reversible Fault‐Tolerant Normalization Register
16.4.5 Reversible Fault‐Tolerant Parallel Adder
Property 16.4.5.1
Proof
16.4.6 The Reversible Fault‐Tolerant Division Circuit
16.5 Summary
17 Reversible Fault‐Tolerant Decoder Circuit
17.1 Transistor Realization of Some Popular Reversible Gates
17.1.1 Feynman Double Gate
17.1.2 Fredkin Gate
17.2 Reversible Fault‐Tolerant Decoder
Property 17.2.1
Proof
Example 17.2.1
Property 17.2.2
Proof
Example 17.2.2
Property 17.2.3
Proof
Example 17.2.3
Property 17.2.4
Proof
Example 17.2.4
17.3 Summary
18 Reversible Fault‐Tolerant Barrel Shifter
18.1 Properties of Barrel Shifters
Property 18.1.1
Proof
18.2 Reversible Fault‐Tolerant Unidirectional Logarithmic Rotators
Property 18.2.1
Property 18.2.2
Property 18.2.3
Property 18.2.4
Proof
Property 18.2.5
Proof
18.3 Fault‐Tolerant Unidirectional Logarithmic Logical Shifters
Property 18.3.1
Proof
Property 18.3.2
Proof
18.4 Summary
19 Reversible Fault‐Tolerant Programmable Logic Devices
19.1 Reversible Fault‐Tolerant Programmable Logic Array
Property 19.1.1
Property 19.1.2
Property 19.1.3
Example 19.1.1
19.1.1 The Design of RFTPLA
Property 19.1.1.1
Proof
Property 19.1.1.2
Example 19.1.1
Property 19.1.1.3
Example 19.1.2
Proof
Example 19.1.3
Property 19.1.1.4
Proof
Example 19.1.4
19.2 Reversible Fault‐Tolerant Programmable Array Logic
19.2.1 The Design of AND Plane of RFTPAL
19.2.2 The Design of Ex‐OR Plane of RFTPAL
19.3 Reversible Fault‐Tolerant LUT‐Based FPGA
19.3.1 Reversible Fault‐Tolerant Gates
19.3.2 Proof of Fault‐Tolerance Properties of the MSH and MSB Gates
19.3.3 Physical Implementation of the Gates
19.3.4 Reversible Fault‐Tolerant D Latch, Master–Slave Flip‐Flop and Multiplexer
Property 19.3.4.1
Property 19.3.4.2
Property 19.3.4.3
19.3.5 Reversible Fault‐Tolerant ‐Input Look‐Up Table
19.3.6 Reversible Fault‐Tolerant CLB of FPGA
19.4 Summary
20 Reversible Fault‐Tolerant Arithmetic Logic Unit
20.1 Design of ‐bit ALU
20.1.1 A Parity‐Preserving Reversible Gate
Property 20.1.1.1
Proof
Property 20.1.1.2
Proof
Property 20.1.1.3
Proof
Property 20.1.1.4
Proof
20.1.2 1‐Bit ALU
20.1.2.1 Group‐1 PP Cell
20.1.2.2 Group‐2 PP Cell
20.1.2.3 Group‐3 PP Cell
20.1.2.4 ‐bit ALU
Property 20.1.2.1
Proof
Property 20.1.2.2
Proof
Property 20.1.2.3
Proof
20.2 Summary
21 Online Testable Reversible Circuit Using NAND Blocks
21.1 Testable Reversible Gates
21.2 Two‐Pair Rail Checker
21.3 Synthesis of Reversible Logic Circuits
21.4 Summary
22 Reversible Online Testable Circuits
22.1 Online Testability
22.1.1 Online Testable Approach Using R1, R2, and R Gates
22.1.2 Online Testable Approach Using Testable Reversible Cells (TRCs)
22.1.3 Online Testable Circuit Using Online Testable Gate
22.1.4 Online Testing of ESOP‐Based Circuits
22.1.5 Online Testing of General Toffoli Circuit
22.2 The Design Approach
22.2.1 The UFT Gate
Property 22.2.1.1
Proof
Property 22.2.2
Proof
Property 22.2.3
Proof
22.2.2 Analysis of the Online Testable Approach
Example 22.2.2.1
Example 22.2.2.2
22.3 Summary
23 Applications of Reversible Computing
Why We Need to Use Reversible Circuits
Applications of Reversible Computing
23.1 Adiabatic Systems
23.2 Quantum Computing
23.3 Energy‐Efficient Computing
23.4 Switchable Program and Feedback Circuits
23.5 Low‐Power CMOS
23.6 Digital Signal Processing (DSP) and Nano‐Computing
Part II DNA Computing. An Overview About DNA Computing
24 Background Studies About Deoxyribonucleic Acid
24.1 Structure and Function of DNA
24.2 DNA Computing
24.2.1 Watson‐Crick Complementary
24.2.2 Adleman's Breakthrough
24.3 Relationship of Binary Logic with DNA
24.4 Welfare of DNA Computing
24.5 Summary
25 A DNA‐Based Approach to Microprocessor Design
25.1 Basics of Microprocessor Design
25.2 Characteristics and History of Microprocessors
25.3 Methodology of Microprocessor Design
25.4 Construction of Characteristic Tree
25.5 Traversal of the Tree
25.6 Encoding of the Traversed Path to the DNA Sequence
25.6.1 Gene Pool
25.6.2 Potency Factor
25.7 Combination of DNA Sequences
25.8 Decoding the Output String
25.9 Processor Evaluation
25.10 Post‐Processing
25.11 Gene Pool Update
25.12 Summary
26 DNA‐Based Reversible Circuits
26.1 DNA‐Based Reversible Gates
26.2 DNA‐Based Reversible NOT Gate
Example 26.2.1
26.3 DNA‐Based Reversible Ex‐OR Gate
Example 26.3.1
26.4 DNA‐Based Reversible AND Gate
Example 26.4.1
26.5 DNA‐Based Reversible OR Gate
Example 26.5.1
Property 26.5.1
Proof
Example 26.5.2
26.6 DNA‐Based Reversible Toffoli Gate
Example 26.6.1
26.6.1 Fan‐out Technique of a DNA‐Based Toffoli Gate
Property 26.6.1.1
Proof
26.6.2 DNA‐Based Reversible NOT Operation
26.6.3 DNA‐Based Reversible AND Operation
26.6.4 DNA‐Based Reversible OR Operation
26.6.5 DNA‐Based Reversible Ex‐OR Operation
26.6.6 Properties of DNA‐Based Reversible Toffoli Gate
26.6.7 DNA‐Based Reversible Fredkin Gates
26.7 Realization of Reversible DNA‐Based Composite Logic
26.8 Summary
27 Addition, Subtraction, and Comparator Using DNA
27.1 DNA‐Based Adder
Property 27.1.1
Proof
Example 27.1.1
Property 27.1.2
Proof
Example 27.1.2
Example 27.1.3
27.2 DNA‐Based Addition/Subtraction Operations
27.2.1 Addition and Subtraction Operations
27.2.2 Procedures of DNA‐Based Reversible Addition/ Subtraction Operations
Property 27.2.2.1
Proof
27.3 DNA‐Based Comparator
27.3.1 Sequence Design
27.3.2 Estimation of Rate Constant
27.4 Summary
28 Reversible Shift and Multiplication Using DNA
28.1 DNA‐Based Reversible Shifter Circuit
28.1.1 Procedures of DNA‐Based Shifter Circuit
28.2 DNA‐Based Reversible Multiplication Operation
Example 28.2.1
28.3 Summary
29 Reversible Multiplexer and ALU Using DNA
29.1 DNA‐Based Reversible Multiplexer
29.1.1 The Working Procedures of DNA‐Based Multiplexer Circuit
29.2 DNA‐Based Reversible Arithmetic Logic Unit
29.2.1 Procedures of DNA‐Based ALU
29.2.2 Properties of the DNA‐Based ALU
Property 29.2.2.1
Proof
Property 29.2.2.2
Proof
Property 29.2.2.3
Proof
Property 29.2.2.4
Proof
Property 29.2.2.6
Proof
Property 29.2.2.6
Proof
29.3 Summary
30 Reversible Flip‐Flop Using DNA
30.1 The Design of a DNA Fredkin Gate
30.2 Simulating the Fredkin Gate by Sticking System
30.2.1 Simulating the Fredkin Gate by Enzyme System
30.3 Simulation of the Reversible D Latch Using DNA Fredkin Gate
30.3.1 Simulation of the Reversible Sequential Circuit Using DNA Fredkin Gate
30.4 DNA‐Based Biochemistry Technology
30.5 Summary
31 Applications of DNA Computing
How DNA Computing Works
Applications of DNA Computing
31.1 Solving the Optimization and Scheduling Problems Like the Traveling Salesman Problem
31.2 Parallel Computing
31.3 Genetic Algorithm
31.4 Neural System
31.5 Fuzzy Logic Computation and Others
31.6 Lift Management System
31.7 DNA Chips
31.8 Swarm Intelligence
31.9 DNA and Cryptography Systems
31.10 Monstrous Memory Capacity
31.11 Low‐Power Dissipation
31.12 Summary
Conclusion
Copyright Permission of Third‐Party Materials
Bibliography
Index
WILEY END USER LICENSE AGREEMENT
