Reversible and DNA Computing

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

About the Author :
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.