Please use this identifier to cite or link to this item: http://hdl.handle.net/123456789/435
Title: DNA Based Boolean Satisfiable Approach for FPGA Test Generation
Authors: Singh, Sikha
Supervisor: Singh, Amardeep
Keywords: DNA;FPGA test generation;Networks;Networking;Computer science
Issue Date: 8-Oct-2007
Abstract: The potential of DNA computing has been used to solve many computationally hard problems. FPGA Test Generation is a compute intensive problem and involves generating input patterns that give different response for a given fault in a faulty and fault-free circuit. Conventional methods for test generation involve exhaustive, random and deterministic techniques. These methods are not very effective and become very costly and time-consuming as the size of the circuit increases. The complexity of FPGA is rapidly increasing. The need for effective and economical testing has given birth to unconventional methods for it. These include methods such as Boolean Satisfiability approach, Quantum approach, Neural Computing etc. The Boolean Satisfiability approach for test generation was proposed by Larrabee in 1992. It is neither purely structural nor an algebraic one. The approach generates test patterns in two steps: First, it extracts the formula that defines the test patterns that detect the fault. Second, it satisfies the formula using Boolean satisfiability algorithm. In this thesis, we have explored the computational power of DNA molecules to solve the computationally hard problems, the Boolean Satisfiability approach and proposed a DNA computing based approach for FPGA test generation. The DNA based Boolean Satisfiable approach for FPGA Test Generation is efficient, faster and economical for the generation of test patterns for single-stuck-at faults and bridging faults in FPGA. The effectiveness of the approach has been demonstrated by the theoretical comparison of DNA based Boolean Satisfiable approach for FPGA Test Generation (DSTG) results with the exhaustive search. DNA computing, also known as molecular computing, is a new computational paradigm for parallel computation, which uses the parallelism provided by DNA molecules to solve a particular problem. This new field was launched by Leonard M. Adleman in 1994. In his groundbreaking work he showed that how the biological experiments could be used to solve an instance of Hamiltonian Path Problem (HPP), which is a compute intensive problem The encoding of the instance of the HPP was done by DNA strands and the commonly available techniques form the molecular biology were used to manipulate this encoded information After Adleman's experiment, Lipton used the potential of DNA computing to solve another NP - Complete problem: the Satisfiability problem. The proposed DNA based Boolean Satisfiable approach for FPGA Test Generation (DSTG) algorithm exploits the Lipton model.
URI: http://hdl.handle.net/123456789/435
Appears in Collections:Masters Theses@CSED

Files in This Item:
File Description SizeFormat 
m92140.pdf11.02 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.