Hafiz M. H. Babu - Reversible and DNA Computing

Reversible and DNA Computing has three parts with 31 chapters, covering reversible circuits, fault‐tolerant reversible circuits, and DNA computing. This book focuses on state‐of‐the‐art research on reversible computing, reversible fault tolerance, and DNA‐based reversible circuits with their intended application.

In the first part of the book reversible circuits are illustrated and explained in a way that readers will understand, from the basics of reversible circuits to their applications in different types of arithmetic and logical units. In reversible computing, fault tolerance is an important part for the robust operation. Therefore, the second part of the book is designed with the fundamental concepts of fault tolerance and its application in the reversible computing. Various arithmetic and logical circuits are designed with fault‐tolerant support, and it will give the confidence of designing the new reversible circuits for quantum computing. In addition, reversible and DNA computing are the new face of research for information processing and operation. The third part of the book consists of the most recent DNA applications in the circuit level, which supports the reversible computing. As a whole, from the reversible and DNA computing book a core researcher, academician, and student will get the guidelines of reversible and DNA circuits and its applications.

Dhaka, Bangladesh

January, 2020

I would like to express my sincere gratitude and special appreciation to the researchers and my beloved students who are working in the field of reversible and DNA computing. The contents of this book have been compiled from a wide variety of research works, which are listed at the end of this book.

I am grateful to my parents and family members for their endless support. Most of all, I want to thank my wife Mrs. Sitara Roshan, daughter Ms. Fariha Tasnim, and son Md. Tahsin Hasan for their invaluable cooperation in completing this book.

Finally, I am also thankful to all of those who have provided their support and important time to finish this book.

ALUarithmetic logic unitBCDbinary coded decimalBJSBabu‐Jamal‐SaleheenCADcomputer‐aided designCSAcarry skip adderCLAcarry look‐ahead adderCPUcentral processing unitDAGdirected acyclic graphDFSdepth first searchDSPdigital signal processingDNAdeoxyribonucleic acidDRAGDNA‐based reversible AND gateDRNGDNA‐based reversible NOT gateDROGDNA‐based reversible OR gateDXRGDNA‐based reversible Ex‐OR gateDRFADNA‐based reversible full adderDSMdeep sub micronESOPexclusive sum‐of‐productsFPGAfield programmable gate arrayF2GFeynman double gateFGFeynman gateFRGFredkin gateFPUfloating‐point unitFPGAfield programmable gate arrayFTFAfault‐tolerant full adderHLNHasan‐Lafifa‐NazirHPPHamiltonian path problemIRinstruction registerMIGmodified Islam gateMOAmulti‐operand additionNFTnew fault tolerantPCRpolymerase chain reactionPFApartial full adderPGPeres gatePALprogrammable array logicPLAprogrammable logic arrayPIPOparallel‐in parallel‐outPISOparallel‐in serial‐outPPGpartial product generationPROMprogrammable read‐only memoryQCAquantum‐dot cellular automataLDPClow‐density parity‐checkRAMrandom access memoryRFDreversible fault‐tolerant decoderRFTPLAreversible fault‐tolerant programmable logic arrayRGreversible gateSOPsum‐of‐productsSISOserial‐in serial‐outSIPOserial‐in parallel‐outSNFAsingle NFT full adderTBtestable blockTGToffoli gateUPPGuniversal parity‐preserving gate

The limit of energy dissipation during computation is fundamentally based on the apparent thermodynamic paradox of Maxwell's demon. Maxwell described the system as follows:

For we have seen that the molecules in a vessel full of air at uniform temperature are moving with velocities by no means uniform, though the mean velocity of any great number of them, arbitrarily selected, is almost exactly uniform. Now let us suppose that such a vessel is divided into two portions, A and B , by a division in which there is a small hole, and that a being, who can see the individual molecules, opens and closes this hole, so as to allow only the swifter molecules to pass from A to B , and only the slower ones to pass from B to A . He will thus, without expenditure of work, raise the temperature of B and lower than that of A , in contradiction to the second law of thermodynamics.

The demon has been depicted in various ways. Some show the demon inside the chamber with gas, some have it outside. Any analysis must be sure to include the thermodynamic effects within the demon itself in the energy and entropy accounting. Some images give the demon a light source to aid in measurement of the particles speed, indicating the lack taken by some authors to explain the paradox of attributing the entropy increase to dissipation during measurement.

Szilard, nearly 60 years after Maxwell first postulated the demon, attempted to resolve the paradox by arguing that the process of measurement required dissipation. Although he did notice entropy generation of when the demon was reset. But it was not until much later that researchers firmly placed the source of dissipation in the erasure of information. When the demon measures a particle, he must set a bit indicating the speed of the particle. The hole between the portions of the vessel is controlled by the state of this bit. Once a particle has been directed to the correct portion, the demon must reset the bit in preparation for the next measurement value. This resetting is the logically irreversible event that saves the second law. Measurement may be performed reversibly; information destruction, rather than information acquisition, has a thermodynamic cost. In any irreversible process, entropy must increase. The required entropy increase during irreversible bit erasure is a function of the process by which it is done, the time taken for erasure, and the temperature of the system, but the increase must be at least zero. However, the required energy dissipation must be at least , where k is the Boltzmann constant and T is the operating temperature.

This book is divided into three parts, namely (i) Reversible Circuits, (ii) Fault‐Tolerant and Online Testable Circuits, and (iii) DNA Computing. The first part starts with some backgrounds and preliminary studies about reversible logic synthesis and some popular reversible gates. Then many of the reversible gates are included in different chapters. Some approaches of designing different reversible adders and subtractor circuits, signed multiplier, sequential division circuit, low power n ‐bit binary comparator, reversible latches and flip‐flops, n ‐bit synchronous and asynchronous counter, barrel shifter, shift register, field programmable gate array (FPGA), programmable logic array (PLA), random access memory (RAM), programmable read‐only memory (PROM), the arithmetic logic unit (ALU) implementation and finally, the control unit is presented.

The second part is divided into two types of contents; namely reversible fault‐tolerant circuits and reversible online testable circuits. In fault‐tolerant part, some backgrounds and preliminary studies about reversible fault‐tolerant logic gates are included in different chapters. Some approaches of designing different reversible fault‐tolerant adders, multiplier circuit, floating‐point division circuit, decoder, shifter and rotator techniques, programmable logic devices (programmable logic array, programmable array logic and field programmable gate array) and finally, arithmetic logic unit (ALU) with its QCA implementation are described. In addition, online testable part describes the realization of reversible circuits using NAND blocks and designs of some reversible online testable circuits.