Vendor
Wiley
Published by
Wiley (2020-11-09)
Current material
Hardback
Original language
English
Themas
Electronics: circuits & components
BACK

Reversible and DNA Computing

by Hafiz M. H. Babu

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

Available rights (32)

Language Territory Type Vendor Status
Afrikaans World All

Wiley
Julie Attrill

Available View on Rightsdesk
Albanian World All

Wiley
Julie Attrill

Available View on Rightsdesk
Arabic World All

Wiley
Julie Attrill

Available View on Rightsdesk
Armenian World All

Wiley
Julie Attrill

Available View on Rightsdesk
Azerbaijani World All

Wiley
Julie Attrill

Available View on Rightsdesk
Find 27 more rights on Rightsdesk.

More like this