+353-1-416-8900REST OF WORLD
+44-20-3973-8888REST OF WORLD
1-917-300-0470EAST COAST U.S
1-800-526-8630U.S. (TOLL FREE)

Reversible and DNA Computing. Edition No. 1

  • Book

  • 432 Pages
  • September 2020
  • John Wiley and Sons Ltd
  • ID: 5836783

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

Authors

Hafiz M. H. Babu