Master the subjects of reversible computing and DNA computing with this expert volume
Reversible and DNA Computing offers readers new ideas and technologies in the rapidly developing field of reversible computing. World-renowned researcher and author Hafiz Md. Hasan Babu shows readers the fundamental concepts and ideas necessary to understand reversible computing, including reversible circuits, reversible fault tolerant circuits, and reversible DNA circuits.
Reversible and DNA Computing contains a practical approach to understanding energy-efficient DNA computing. In addition to explaining the foundations of reversible circuits, the book covers topics including:
- Advanced logic design
- An introduction to the fundamentals of reversible computing
- Advanced reversible logic synthesis
- Reversible fault tolerance
- Fundamentals of DNA computing
- Reversible DNA logic synthesis
- DNA logic design
This book is perfect for undergraduate and graduate students in the physical sciences and engineering, as well as those working in the field of quantum computing. It belongs on the bookshelves of anyone with even a passing interest in nanotechnology, energy-efficient computing, and DNA computing.
Table of Contents
List of Figures xvii
List of Tables xxix
About the Author xxxi
Preface xxxiii
Acknowledgments xxxv
Acronyms xxxvii
Introduction xxxix
Part I Reversible Circuits 1
An Overview About Reversible Circuits 1
1 Reversible Logic Synthesis 5
1.1 Reversible Logic 5
1.2 Reversible Function 5
1.3 Reversible Logic Gate 6
1.4 Garbage Outputs 6
1.5 Constant Inputs 7
1.6 Quantum Cost 7
1.7 Delay 8
1.8 Power 8
1.9 Area 8
1.10 Hardware Complexity 9
1.11 Quantum Gate Calculation Complexity 9
1.12 Fan-Out 10
1.13 Self-Reversible 10
1.14 Reversible Computation 10
1.15 Area 11
1.16 Design Constraints for Reversible Logic Circuits 11
1.17 Quantum Analysis of Different Reversible Logic Gates 12
1.17.1 Reversible NOT Gate (Feynman Gate) 12
1.17.2 Toffoli Gate 12
1.17.3 Fredkin Gate 13
1.17.4 Peres Gate 13
1.18 Summary 13
2 Reversible Adder and Subtractor Circuits 15
2.1 Reversible Multi-Operand n-Digit Decimal Adder 15
2.1.1 Full Adder 15
2.1.2 Carry Skip Adder 19
2.1.2.1 Design of Carry Skip Adder 20
2.1.3 Carry Look-Ahead Adder 24
2.2 Reversible BCD Adders 26
2.2.1 Design Procedure of the Reversible BCD Adder 27
2.2.1.1 Properties of the Reversible BCD Adder 28
2.2.2 Design Procedure of the Reversible Carry Skip BCD Adder 31
2.2.2.1 Properties of the Reversible Carry Skip BCD Adder 32
2.3 Reversible BCD Subtractor 34
2.3.1 Carry Look-Ahead BCD Subtractor 36
2.3.2 Carry Skip BCD Subtractor 36
2.3.3 Design of Conventional Reversible BCD Subtractor 37
2.3.3.1 Reversible Nine’s Complement 37
2.3.3.2 Reversible BCD Subtractor 38
2.3.3.3 Reversible Design of Carry Look-Ahead BCD Subtractor 40
2.3.3.4 Reversible Design of Carry Skip BCD Subtractor 40
2.4 Summary 41
3 Reversible Multiplier Circuit 43
3.1 Multiplication Using Booth’s Recoding 43
3.2 Reversible Gates as Half Adders and Full Adders 44
3.3 Some Signed Reversible Multipliers 45
3.4 Design of Reversible Multiplier Circuit 45
3.4.1 Some Quantum Gates 46
3.4.2 Recoding Cell 46
3.4.3 Partial Product Generation Circuit 49
3.4.4 Multi-Operand Addition Circuit 52
3.4.5 Calculation of Area and Power of n × n Multiplier Circuit 52
3.5 Summary 64
4 Reversible Division Circuit 67
4.1 The Division Approaches 67
4.1.1 Restoring Division 67
4.1.2 Nonrestoring Division 67
4.2 Components of Division Circuit 68
4.2.1 Reversible MUX 68
4.2.2 Reversible Register 68
4.2.3 Reversible PIPO Left-Shift Register 68
4.2.4 Reversible Parallel Adder 70
4.3 The Design of Reversible Division Circuit 71
4.4 Summary 74
5 Reversible Binary Comparator 75
5.1 Design of Reversible n-Bit Comparator 75
5.1.1 BJS Gate 75
5.1.2 Reversible 1-Bit Comparator Circuit 76
5.1.3 Reversible MSB Comparator Circuit 77
5.1.4 Reversible Single-Bit Greater or Equal Comparator Cell 78
5.1.5 Reversible Single-Bit Less Than Comparator Cell 79
5.1.6 Reversible 2-Bit Comparator Circuit 79
5.1.7 Reversible n-Bit Comparator Circuit 79
5.2 Summary 85
6 Reversible Sequential Circuits 87
6.1 An Example of Design Methodology 87
6.2 The Design of Reversible Latches 89
6.2.1 The SR Latch 89
6.2.2 The D Latch 91
6.2.2.1 The D Latch with Outputs Q and Q 91
6.2.2.2 The Negative Enable Reversible D Latch 92
6.2.3 T Latch 93
6.2.4 The JK Latch 93
6.3 The Design of Reversible Master-Slave Flip-Flops 94
6.4 The Design of Reversible Latch and the Master-Slave Flip-Flop with Asynchronous SET and RESET Capabilities 95
6.5 Summary 97
7 Reversible Counter, Decoder, and Encoder Circuits 99
7.1 Synthesis of Reversible Counter 99
7.1.1 Reversible T Flip-Flop 99
7.1.2 Reversible Clocked T Flip-Flop 99
7.1.3 Reversible Master-Slave T Flip-Flop 100
7.1.4 Reversible Asynchronous Counter 101
7.1.5 Reversible Synchronous Counter 102
7.2 Reversible Decoder 103
7.2.1 Reversible Encoder 104
7.3 Summary 106
8 Reversible Barrel Shifter and Shift Register 107
8.1 Design Procedure of Reversible Bidirectional Barrel Shifter 107
8.1.1 Reversible 3 × 3 Modified BJN Gate 108
8.1.2 Reversible 2’s Complement Generator 109
8.1.3 Reversible Swap Condition Generator 110
8.1.4 Reversible Right Rotator 111
8.1.4.1 (4, 3) Reversible Right Rotator 112
8.1.4.2 Generalized Reversible Right Rotator 112
8.1.5 Reversible Bidirectional Barrel Shifter 113
8.2 Design Procedure of Reversible Shift Register 113
8.2.1 Reversible Flip-Flop 113
8.2.1.1 Reversible SISO Shift Register 114
8.2.1.2 Reversible SIPO Shift Register 114
8.2.1.3 Reversible PISO Shift Register 115
8.2.1.4 Reversible PIPO Shift Register 115
8.2.1.5 Reversible Universal Shift Register 118
8.3 Summary 121
9 Reversible Multiplexer and Demultiplexer with Other Logical Operations 123
9.1 Reversible Logic Gates 123
9.1.1 RG1 Gate 123
9.1.2 RG2 Gate 123
9.2 Designs of Reversible Multiplexer and Demultiplexer with Other Logical Operations 124
9.2.1 The R-I Gate 124
9.2.2 The R-II Gate 126
9.3 Summary 128
10 Reversible Programmable Logic Devices 129
10.1 Reversible FPGA 129
10.1.1 3 × 3 Reversible NH Gate 130
10.1.2 4 × 4 Reversible BSP Gate 130
10.1.3 4-to-1 Reversible Multiplexer 130
10.1.4 Reversible D Latch 131
10.1.5 Reversible Write-Enabled Master-Slave Flip-Flop 132
10.1.6 Reversible RAM 132
10.1.7 Design of Reversible FPGA 132
10.2 Reversible PLA 134
10.2.1 The Design Procedure 134
10.2.1.1 Delay Calculation of a Reversible PLA 139
10.2.1.2 Delay Calculation of AND Plane 139
10.2.1.3 Delay Calculation of Ex-OR Plane 140
10.2.1.4 Delay of Overall Design 140
10.3 Summary 141
11 Reversible RAM and Programmable ROM 143
11.1 Reversible RAM 143
11.1.1 3 × 3 Reversible FS Gate 143
11.1.2 Reversible Decoder 144
11.1.3 Reversible D Flip-Flop 145
11.1.4 Reversible Write-Enabled Master-Slave D Flip-Flop 146
11.1.5 Reversible Random Access Memory 146
11.2 Reversible PROM 148
11.2.1 Reversible Decoder 149
11.2.2 Design of Reversible PROM 149
11.3 Summary 154
12 Reversible Arithmetic Logic Unit 155
12.1 Design of ALU 155
12.1.1 Conventional ALU 155
12.1.2 The ALU Based on Reversible Logic 155
12.1.2.1 The Reversible Function Generator 156
12.1.2.2 The Reversible Control Unit 156
12.2 Design of Reversible ALU 158
12.3 Summary 159
13 Reversible Control Unit 161
13.1 An Example of Control Unit 161
13.2 Different Components of a Control Unit 161
13.2.1 Reversible HL Gate 161
13.2.2 Reversible BJ Gate 162
13.2.3 Reversible 2-to-4 Decoder 163
13.2.4 Reversible 3-to-8 Decoder 165
13.2.5 Reversible n-to-2n Decoder 165
13.2.6 Reversible JK Flip-Flop 168
13.2.7 Reversible Sequence Counter 168
13.2.8 Reversible Instruction Register 168
13.2.9 Control of Registers and Memory 169
13.2.10 Construction Procedure and Complexities of the Control Unit 170
13.3 Summary 172
Part II Reversible Fault Tolerance 173
An Overview About Fault-Tolerance and Testable Circuits 173
14 Reversible Fault-Tolerant Adder Circuits 177
14.1 Properties of Fault Tolerance 177
14.1.1 Parity-Preserving Reversible Gates 178
14.2 Reversible Parity-Preserving Adders 180
14.2.1 Fault-Tolerant Full Adder 180
14.2.2 Fault-Tolerant Carry Skip Adder 181
14.2.3 Fault-Tolerant Carry Look-Ahead Adder 183
14.2.4 Fault-Tolerant Ripple Carry Adder 184
14.3 Summary 185
15 Reversible Fault-Tolerant Multiplier Circuit 187
15.1 Reversible Fault-Tolerant Multipliers 187
15.1.1 Reversible Fault-Tolerant n × n Multiplier 187
15.1.2 LMH Gate 188
15.1.3 Partial Product Generation 188
15.1.4 Multi-Operand Addition 190
15.2 Summary 192
16 Reversible Fault-Tolerant Division Circuit 193
16.1 Preliminaries of Division Circuits 193
16.1.1 Division Algorithms 193
16.2 The Division Method 194
16.2.1 Floating-Point Data and Rounding 195
16.2.2 Correctly Rounded Division 195
16.2.3 Correct Rounding from One-Sided Approximations 196
16.2.4 The Algorithm for Division Operation 196
16.3 Components of a Division Circuit 199
16.3.1 Reversible Fault-Tolerant MUX 200
16.3.2 Reversible Fault-Tolerant D Latch 200
16.4 The Design of the Division Circuit 201
16.4.1 Reversible Fault-Tolerant PIPO Left-Shift Register 201
16.4.2 Reversible Fault-Tolerant Register 203
16.4.3 Reversible Fault-Tolerant Rounding Register 204
16.4.4 Reversible Fault-Tolerant Normalization Register 204
16.4.5 Reversible Fault-Tolerant Parallel Adder 204
16.4.6 The Reversible Fault-Tolerant Division Circuit 205
16.5 Summary 210
17 Reversible Fault-Tolerant Decoder Circuit 211
17.1 Transistor Realization of Some Popular Reversible Gates 211
17.1.1 Feynman Double Gate 211
17.1.2 Fredkin Gate 211
17.2 Reversible Fault-Tolerant Decoder 213
17.3 Summary 219
18 Reversible Fault-Tolerant Barrel Shifter 221
18.1 Properties of Barrel Shifters 221
18.2 Reversible Fault-Tolerant Unidirectional Logarithmic Rotators 222
18.3 Fault-Tolerant Unidirectional Logarithmic Logical Shifters 224
18.4 Summary 229
19 Reversible Fault-Tolerant Programmable Logic Devices 231
19.1 Reversible Fault-Tolerant Programmable Logic Array 231
19.1.1 The Design of RFTPLA 232
19.2 Reversible Fault-Tolerant Programmable Array Logic 235
19.2.1 The Design of AND Plane of RFTPAL 236
19.2.2 The Design of Ex-OR Plane of RFTPAL 238
19.3 Reversible Fault-Tolerant LUT-Based FPGA 240
19.3.1 Reversible Fault-Tolerant Gates 240
19.3.2 Proof of Fault-Tolerance Properties of the MSH and MSB Gates 240
19.3.3 Physical Implementation of the Gates 241
19.3.4 Reversible Fault-Tolerant D Latch, Master-Slave Flip-Flop and 4 × 1 Multiplexer 242
19.3.5 Reversible Fault-Tolerant n-Input Look-Up Table 244
19.3.6 Reversible Fault-Tolerant CLB of FPGA 244
19.4 Summary 246
20 Reversible Fault-Tolerant Arithmetic Logic Unit 249
20.1 Design of n-bit ALU 249
20.1.1 A 4 × 4 Parity-Preserving Reversible Gate 249
20.1.2 1-Bit ALU 251
20.1.2.1 Group-1 PP Cell 251
20.1.2.2 Group-2 PP Cell 252
20.1.2.3 Group-3 PP Cell 253
20.1.2.4 n-bit ALU 255
20.2 Summary 259
21 Online Testable Reversible Circuit Using NAND Blocks 261
21.1 Testable Reversible Gates 261
21.2 Two-Pair Rail Checker 265
21.3 Synthesis of Reversible Logic Circuits 266
21.4 Summary 268
22 Reversible Online Testable Circuits 269
22.1 Online Testability 269
22.1.1 Online Testable Approach Using R1, R2, and R Gates 269
22.1.2 Online Testable Approach Using Testable Reversible Cells (TRCs) 270
22.1.3 Online Testable Circuit Using Online Testable Gate 271
22.1.4 Online Testing of ESOP-Based Circuits 271
22.1.5 Online Testing of General Toffoli Circuit 272
22.2 The Design Approach 272
22.2.1 The UFT Gate 272
22.2.2 Analysis of the Online Testable Approach 276
22.3 Summary 278
23 Applications of Reversible Computing 279
Why We Need to Use Reversible Circuits 280
Applications of Reversible Computing 280
23.1 Adiabatic Systems 281
23.2 Quantum Computing 282
23.3 Energy-Efficient Computing 283
23.4 Switchable Program and Feedback Circuits 283
23.5 Low-Power CMOS 284
23.6 Digital Signal Processing (DSP) and Nano-Computing 284
Part III DNA Computing 287
An Overview About DNA Computing 287
24 Background Studies About Deoxyribonucleic Acid 291
24.1 Structure and Function of DNA 291
24.2 DNA Computing 293
24.2.1 Watson-Crick Complementary 294
24.2.2 Adleman’s Breakthrough 294
24.3 Relationship of Binary Logic with DNA 295
24.4 Welfare of DNA Computing 295
24.5 Summary 297
25 A DNA-Based Approach to Microprocessor Design 299
25.1 Basics of Microprocessor Design 299
25.2 Characteristics and History of Microprocessors 300
25.3 Methodology of Microprocessor Design 301
25.4 Construction of Characteristic Tree 302
25.5 Traversal of the Tree 302
25.6 Encoding of the Traversed Path to the DNA Sequence 304
25.6.1 Gene Pool 305
25.6.2 Potency Factor 305
25.7 Combination of DNA Sequences 305
25.8 Decoding the Output String 306
25.9 Processor Evaluation 307
25.10 Post-Processing 307
25.11 Gene Pool Update 309
25.12 Summary 309
26 DNA-Based Reversible Circuits 311
26.1 DNA-Based Reversible Gates 311
26.2 DNA-Based Reversible NOT Gate 311
26.3 DNA-Based Reversible Ex-OR Gate 311
26.4 DNA-Based Reversible AND Gate 312
26.5 DNA-Based Reversible OR Gate 313
26.6 DNA-Based Reversible Toffoli Gate 315
26.6.1 Fan-out Technique of a DNA-Based Toffoli Gate 316
26.6.2 DNA-Based Reversible NOT Operation 317
26.6.3 DNA-Based Reversible AND Operation 317
26.6.4 DNA-Based Reversible OR Operation 318
26.6.5 DNA-Based Reversible Ex-OR Operation 318
26.6.6 Properties of DNA-Based Reversible Toffoli Gate 319
26.6.7 DNA-Based Reversible Fredkin Gates 319
26.7 Realization of Reversible DNA-Based Composite Logic 321
26.8 Summary 322
27 Addition, Subtraction, and Comparator Using DNA 323
27.1 DNA-Based Adder 323
27.2 DNA-Based Addition/Subtraction Operations 325
27.2.1 Addition and Subtraction Operations 325
27.2.2 Procedures of DNA-Based Reversible Addition/ Subtraction Operations 325
27.3 DNA-Based Comparator 329
27.3.1 Sequence Design 330
27.3.2 Estimation of Rate Constant 331
27.4 Summary 331
28 Reversible Shift and Multiplication Using DNA 333
28.1 DNA-Based Reversible Shifter Circuit 333
28.1.1 Procedures of DNA-Based Shifter Circuit 333
28.2 DNA-Based Reversible Multiplication Operation 336
28.3 Summary 339
29 Reversible Multiplexer and ALU Using DNA 341
29.1 DNA-Based Reversible Multiplexer 341
29.1.1 The Working Procedures of DNA-Based Multiplexer Circuit 342
29.2 DNA-Based Reversible Arithmetic Logic Unit 345
29.2.1 Procedures of DNA-Based ALU 345
29.2.2 Properties of the DNA-Based ALU 347
29.3 Summary 349
30 Reversible Flip-Flop Using DNA 351
30.1 The Design of a DNA Fredkin Gate 351
30.2 Simulating the Fredkin Gate by Sticking System 351
30.2.1 Simulating the Fredkin Gate by Enzyme System 353
30.3 Simulation of the Reversible D Latch Using DNA Fredkin Gate 355
30.3.1 Simulation of the Reversible Sequential Circuit Using DNA Fredkin Gate 355
30.4 DNA-Based Biochemistry Technology 356
30.5 Summary 357
31 Applications of DNA Computing 359
31.1 Solving the Optimization and Scheduling Problems Like the Traveling Salesman Problem 360
31.2 Parallel Computing 362
31.3 Genetic Algorithm 363
31.4 Neural System 363
31.5 Fuzzy Logic Computation and Others 364
31.6 Lift Management System 364
31.7 DNA Chips 364
31.8 Swarm Intelligence 365
31.9 DNA and Cryptography Systems 365
31.10 Monstrous Memory Capacity 366
31.11 Low-Power Dissipation 367
31.12 Summary 367
Conclusion 369
Copyright Permission of Third-Party Materials 371
Bibliography 373
Index 389
