Reversible and DNA Computing
, by Babu, Hafiz M. H.
- ISBN: 9781119679424 | 1119679427
- Cover: Hardcover
- Copyright: 11/9/2020
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.
HAFIZ MD. HASAN BABU is the Pro-Vice-Chancellor of National University in Bangladesh. He received his M.Sc degree in computer science and engineering from the Brno University of Technology in the Czech Republic in 1992. He has written over 100 research articles for reputable international journals.
Preface
Acknowledgments xlvii
Acronyms xlix
Introduction liii
1 Reversible Logic Synthesis 7
1.1 Reversible Logic 7
1.2 Reversible Function 8
1.3 Reversible Logic Gate 8
1.4 Garbage Outputs 10
1.5 Constant Inputs 10
1.6 Quantum Cost 11
1.7 Delay 12
1.8 Power 12
1.9 Area 13
1.10 Hardware Complexity 14
1.11 Quantum Gate Calculation Complexity 15
1.12 Fan-Out 16
1.13 Self-Reversible 16
1.14 Reversible Computation 17
1.15 Area 17
1.16 Design Constraints for Reversible Logic Circuits 18
1.17 Quantum Analysis of Different Reversible Logic Gates 19
1.17.1 Reversible NOT Gate (Feynman Gate) 20
1.17.2 Toffoli Gate 20
1.17.3 Fredkin Gate 21
1.17.4 Peres Gate 21
1.18 Summary 21
2 Reversible Adder and Subtractor Circuits 23
2.1 Reversible Multi-Operand n-Digit Decimal Adder 23
2.1.1 Full Adder 25
2.1.2 Carry Skip Adder 30
2.1.3 Carry Look-Ahead Adder 37
2.2 Reversible BCD Adders 40
2.2.1 Design Procedure of the Reversible BCD Adder 42
2.2.2 Design Procedure of the Reversible Carry Skip BCD Adder 48
2.3 Reversible BCD Subtractor 54
2.3.1 Carry Look-Ahead BCD Subtractor 56
2.3.2 Carry Skip BCD Subtractor 56
2.3.3 Design of Conventional Reversible BCD Subtractor 58
2.4 Summary 64
3 Reversible Multiplier Circuit 65
3.1 Multiplication Using Booth's Recoding 65
3.2 Reversible Gates as Half Adders and Full Adders 66
3.3 Some Signed Reversible Multipliers 68
3.4 Design of Reversible Multiplier Circuit 69
3.4.1 Some Quantum Gates 70
3.4.2 Recoding Cell 71
3.4.3 Partial Product Generation Circuit 77
3.4.4 Multi-Operand Addition Circuit 82
3.4.5 Calculation of Area and Power of n n Multiplier Circuit 83
3.5 Summary 104
4 Reversible Division Circuit 105
4.1 The Division Approaches 105
4.1.1 Restoring Division 105
4.1.2 Non-Restoring Division 106
4.2 Components of Division Circuit 106
4.2.1 Reversible MUX 106
4.2.2 Reversible Register 107
4.2.3 Reversible PIPO Left Shift Register 108
4.2.4 Reversible Parallel Adder 111
4.3 The Design of Reversible Division Circuit 111
4.4 Summary 115
5 Reversible Binary Comparator 117
5.1 Design of Reversible n-Bit Comparator 117
5.1.1 BJS Gate 118
5.1.2 Reversible 1-Bit Comparator Circuit 120
5.1.3 Reversible MSB Comparator Circuit 122
5.1.4 Reversible Single-Bit Greater or Equal Comparator Cell 122
5.1.5 Reversible Single-Bit Less Than Comparator Cell 124
5.1.6 Reversible 2-Bit Comparator Circuit 125
5.1.7 Reversible n-Bit Comparator Circuit 125
5.2 Summary 134
6 Reversible Sequential Circuits 135
6.1 An Example of Design Methodology 135
6.2 The Design of Reversible Latches 138
6.2.1 The SR Latch 138
6.2.2 The D Latch 142
6.2.3 T Latch 145
6.2.4 The JK Latch 147
6.3 The Design of Reversible Master-Slave Flip Flops 147
6.4 The Design of Reversible Latch and the Master-Slave Flip-Flop with Asynchronous SET and RESET Capabilities 150
6.5 Summary 153
7 Reversible Counter, Decoder and Encoder Circuits 155
7.1 Synthesis of Reversible Counter 156
7.1.1 Reversible T Flip-Flop 156
7.1.2 Reversible Clocked T Flip-Flop 156
7.1.3 Reversible Master Slave T Flip-Flop 157
7.1.4 Reversible Asynchronous Counter 159
7.1.5 Reversible Synchronous Counter 160
7.2 Reversible Decoder 162
7.2.1 Reversible Encoder 164
7.3 Summary 166
8 Reversible Barrel Shifter and Shift Register 169
8.1 Design Procedure of Reversible Bidirectional Barrel Shifter 169
8.1.1 Reversible 3 3 Modified BJN Gate 171
8.1.2 Reversible 2's Complement Generator 172
8.1.3 Reversible Swap Condition Generator 174
8.1.4 Reversible Right Rotator 176
8.1.5 Reversible Bidirectional Barrel Shifter 178
8.2 Design Procedure of Reversible Shift Register 179
8.2.1 Reversible Flip-Flop 179
8.3 Summary 191
9 Reversible Multiplexer and Demultiplexer with Other Logical Operations 193
9.1 Reversible Logic Gates 193
9.1.1 RG1 Gate 194
9.1.2 RG2 Gate 194
9.2 Designs of Reversible Multiplexer and Demultiplexer with Other Logical Operations 195
9.2.1 The R-I Gate 195
9.2.2 The R-II Gate 196
9.3 Summary 199
10 Reversible Programmable Logic Devices 201
10.1 Reversible FPGA 202
10.1.1 3 3 Reversible NH Gate 202
10.1.2 4 4 Reversible BSP Gate 203
10.1.3 4-to-1 Reversible Multiplexer 203
10.1.4 Reversible D-Latch 205
10.1.5 Reversible Write Enabled Master Slave Flip-Flop 205
10.1.6 Reversible RAM 206
10.1.7 Design of Reversible FPGA 206
10.2 Reversible PLA 209
10.2.1 The Design Procedure 210
10.3 Summary 219
11 Reversible RAM and Programmable ROM 221
11.1 Reversible RAM 221
11.1.1 3 3 Reversible FS Gate 222
11.1.2 Reversible Decoder 223
11.1.3 Reversible D Flip-Flop 226
11.1.4 Reversible Write-Enabled Master-Slave D Flip-Flop 226
11.1.5 Reversible Random Access Memory 227
11.2 Reversible PROM 230
11.2.1 Reversible Decoder 230
11.2.2 Design of Reversible PROM 231
11.3 Summary 238
12 Reversible Arithmetic Logic Unit 239
12.1 Design of ALU 239
12.1.1 Conventional ALU 240
12.1.2 The ALU Based on Reversible Logic 241
12.2 Design of Reversible ALU 243
12.3 Summary 246
13 Reversible Control Unit 247
13.1 An Example of Control Unit 247
13.2 Different Components of a Control Unit 248
13.2.1 Reversible HL Gate 249
13.2.2 Reversible BJ Gate 250
13.2.3 Reversible 2-to- 4 Decoder 251
13.2.4 Reversible 3- to-8 Decoder 251
13.2.5 Reversible n-to-2n Decoder 253
13.2.6 Reversible J-K Flip-Flop 257
13.2.7 Reversible Sequence Counter 258
13.2.8 Reversible Instruction Register 258
13.2.9 Control of Registers and Memory 260
13.2.10 Construction Procedure and Complexities of the Control Unit 261
13.3 Summary 264
14 Reversible Fault Tolerant Adder Circuits 271
14.1 Properties of Fault Tolerance 272
14.1.1 Parity Preserving Reversible Gates 273
14.2 Reversible Parity Preserving Adders 275
14.2.1 Fault Tolerant Full Adder 276
14.2.2 Fault Tolerant Carry Skip Adder 278
14.2.3 Fault Tolerant Carry Look-Ahead Adder 281
14.2.4 Fault Tolerant Ripple Carry Adder 283
14.3 Summary 284
15 Reversible Fault Tolerant Multiplier Circuit 285
15.1 Reversible Fault Tolerant Multipliers 285
15.1.1 Reversible Fault Tolerant n n Multiplier 286
15.1.2 LMH Gate 286
15.1.3 Partial Product Generation 288
15.1.4 Multi-Operand Addition 290
15.2 Summary 293
16 Reversible Fault Tolerant Division Circuit 295
16.1 Preliminaries of Division Circuits 295
16.1.1 Division Algorithms 296
16.2 The Division Method 297
16.2.1 Floating-Point Data and Rounding 299
16.2.2 Correctly Rounded Division 300
16.2.3 Correct Rounding from One-Sided Approximations 301
16.2.4 The Algorithm for Division Operation 301
16.3 Components of a Division Circuit 306
16.3.1 Reversible Fault Tolerant MUX 307
16.3.2 Reversible Fault Tolerant D-Latch 308
16.4 The Design of the Division Circuit 308
16.4.1 Reversible Fault Tolerant PIPO Left Shift Register 309
16.4.2 Reversible Fault Tolerant Register 312
16.4.3 Reversible Fault Tolerant Rounding Register 312
16.4.4 Reversible Fault Tolerant Normalization Register 313
16.4.5 Reversible Fault Tolerant Parallel Adder 313
16.4.6 The Reversible Fault Tolerant Division Circuit 318
16.5 Summary 322
17 Reversible Fault Tolerant Decoder Circuit 323
17.1 Transistor Realization of Some Popular Reversible Gates 323
17.1.1 Feynman Double Gate 324
17.1.2 Fredkin Gate 324
17.2 Reversible Fault Tolerant Decoder 326
17.3 Summary 335
18 Reversible Fault Tolerant Barrel Shifter 337
18.1 Properties of Barrel Shifters 337
18.2 Reversible Fault Tolerant Unidirectional Logarithmic Rotators 338
18.3 Fault Tolerant Unidirectional Logarithmic Logical Shifters 344
18.4 Summary 350
19 Reversible Fault Tolerant Programmable Logic Devices 351
19.1 Reversible Fault Tolerant Programmable Logic Array 351
19.1.1 The Design of RFTPLA 352
19.2 Reversible Fault Tolerant Programmable Array Logic 360
19.2.1 The Design of AND Plane of RFTPAL 361
19.2.2 The Design of Ex-OR Plane of RFTPAL 363
19.3 Reversible Fault Tolerant LUT-Based FPGA 364
19.3.1 Reversible Fault Tolerant Gates 366
19.3.2 Proof of Fault Tolerance Properties of the MSH and MSB Gates 366
19.3.3 Physical Implementation of the Gates 368
19.3.4 Reversible Fault Tolerant D-Latch, Master Slave Flip-Flop and 4-to-1 Multiplexer 371
19.3.5 Reversible Fault Tolerant Look-Up-Table 373
19.3.6 Reversible Fault Tolerant CLB of FPGA 374
19.4 Summary 375
20 Reversible Fault Tolerant Arithmetic Logic Unit 377
20.1 Design of n-bit ALU 377
20.1.1 A 4 4 Parity Preserving Reversible Gate 378
20.1.2 1-bit ALU 381
20.2 Summary 393
21 Online Testable Reversible Circuit Using NAND Blocks 395
21.1 Testable Reversible Gates 396
21.2 Two-Pair Rail Checker 401
21.3 Synthesis of Reversible Logic Circuits 402
21.4 Summary 404
22 Reversible Online Testable Circuits 407
22.1 Online Testability 407
22.1.1 Online Testable Approach Using R1, R2 and R Gates 408
22.1.2 Online Testable Approach Using Testable Reversible Cells 409
22.1.3 Online Testable Circuit Using Online Testable Gate 411
22.1.4 Online Testing of ESOP-based Circuits 411
22.1.5 Online Testing of General Toffoli Circuit 412
22.2 The Design Approach 413
22.2.1 The UFT Gate 413
22.2.2 Analysis of the Online Testable Approach 420
22.3 Summary 422
23 Applications of Reversible Computing 425
23.1 Adiabatic Systems 428
23.2 Quantum Computing 431
23.3 Energy-Efficient Computing 431
23.4 Switchable Program and Feedback Circuits 432
23.5 Low Power CMOS 433
23.6 Digital Signal Processing and Nano-Computing 434
24 Background studies about Deoxyribonucleic Acid 441
24.1 Structure and Function of DNA 441
24.2 DNA Computing 445
24.2.1 Watson-Crick Complementary 445
24.2.2 Adleman's Breakthrough 446
24.3 Relationship of Binary Logic with DNA 448
24.4 Welfare of DNA Computing 449
24.5 Summary 451
25 A DNA-Based Approach of Microprocessor Design 453
25.1 Basics of Microprocessor Design 453
25.2 Characteristics and History of Microprocessors 455
25.3 Methodology of Microprocessor Design 457
25.4 Construction of Characteristic Tree 459
25.5 Traversal of the Tree 462
25.6 Encoding of the Traversed Path to the DNA Sequence 463
25.6.1 Gene Pool 464
25.6.2 Potency Factor 464
25.7 Combination of DNA Sequences 464
25.8 Decoding the Output String 467
25.9 Processor Evaluation 467
25.10 Post Processing 467
25.11 Gene Pool Update 469
25.12 Summary 470
26 DNA-Based Reversible Circuits 471
26.1 DNA-Based Reversible Gates 471
26.2 DNA-Based Reversible NOT Gate 472
26.3 DNA-Based Reversible Ex-OR Gate 473
26.4 DNA-Based Reversible AND Gate 474
26.5 DNA-Based Reversible OR Gate 476
26.6 DNA-Based Reversible Toffoli Gate 477
26.6.1 Fan-out Technique of DNA-Based Toffoli Gate 479
26.6.2 DNA-Based Reversible NOT Operation 480
26.6.3 DNA-Based Reversible AND Operation 481
26.6.4 DNA-Based Reversible OR Operation 482
26.6.5 DNA-Based Reversible Ex-OR Operation 482
26.6.6 Properties of DNA-Based Reversible Toffoli Gate 483
26.6.7 DNA-Based Reversible Fredkin Gate 484
26.7 Realization of Reversible DNA-Based Composite Logic 486
26.8 Summary 487
27 Addition, Subtraction and Comparator Using DNA 489
27.1 DNA-Based Adder 489
27.2 DNA-Based Addition/Subtraction Operations 492
27.2.1 Addition and Subtraction Operations 492
27.2.2 Procedures of DNA-Based Reversible Addition/Subtraction Operations 493
27.3 DNA-Based Comparator 498
27.3.1 Sequence Design 500
27.3.2 Estimation of Rate Constant 502
27.4 Summary 503
28 Reversible Shift and Multiplication Using DNA 505
28.1 DNA-Based Reversible Shifter Circuit 506
28.1.1 Procedures of DNA-Based Shifter Circuit 506
28.2 DNA-Based Reversible Multiplication Operation 511
28.3 Summary 514
29 Reversible Multiplexer and ALU Using DNA 517
29.1 DNA-Based Reversible Multiplexer 518
29.1.1 The Working Procedures of DNA-Based Multiplexer Circuit 518
29.2 DNA-Based Reversible Arithmetic Logic Unit 522
29.2.1 Procedures of DNA-Based ALU 523
29.2.2 Properties of the DNA-Based ALU 525
29.3 Summary 529
30 Reversible Flip-Flop Using DNA 531
30.1 The Design of DNA Fredkin Gate 531
30.2 Simulating the Fredkin Gate by Sticking System 532
30.2.1 Simulating the Fredkin Gate by Enzyme System 535
30.3 Simulation of the Reversible D Latch Using DNA Fredkin Gate 538
30.3.1 Simulation of the Reversible Sequential Circuit Using DNA Fredkin Gate 539
30.4 DNA-Based Bio-Chemistry Technology 540
30.5 Summary 541
31 Applications of DNA Computing 543
31.1 Solving the Optimization and Scheduling Problems like the Traveling Salesman Problem 545
31.2 Parallel Computing 547
31.3 Genetic Algorithm 549
31.4 Neural System 550
31.5 Fuzzy Logic Computation and Others 550
31.6 Lift Management System 550
31.7 DNA Chips 551
31.8 Swarm Intelligence 552
31.9 DNA and Cryptography Systems 553
31.10 Monstrous Memory Capacity 554
31.11 Low Power Dissipation 555
31.12 Summary 556
Index 599
What is included with this book?
The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.
The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.
Please wait while the item is added to your bag...
