基于FPGA的DNA算法设计与仿真实现

发布时间：2018-12-22 08:21

【摘要】：分子计算又称DNA计算，具有高度并行性、巨大存储容量和极低的能耗，理论上能快速求解NPC（Non-deterministic Polynomial complete problem）问题，是一种全新的多值编码和并行计算方法，它突破了图灵机和冯诺曼体系限制，有指数的加速比、空间交换时间、指数的并行度和获得全体解集等特点。本文研究了一个新的并行系统，即广义分子计算模型，该模型运用了sopc（片上系统）技术和分子计算思想结合的方法，是一种电子DNA模型，该模型实现了以空间换时间的目的，能够在多项式时间内解决完全NP问题。论文主要研究工作如下：（1）讨论了基于分子计算的电子方式的并行处理机模型的结构和特征，系统地对分子计算方法、原理、主要实现方式和优缺点等方面进行了比对和总结；（2）论文提出了一种基于大规模集成电路设计的DNA计算实现方式，构建了一个完整的计算机系统，该系统相对于传统的计算机具有自己独特的优势，它克服了传统计算机解决NPC问题的时间并行性，使得它能够同时搜索获得所有的结论；（3）运用VHDL编写硬件语言，解决了具有可扩展性的解决SAT问题的算法，并用实例问题对算法的正确性进行了验证；（4）运用广义分子计算模型，探讨了0-1背包问题，并在FPGA上实现，，验证了算法的正确性。
[Abstract]:Molecular computing, also known as DNA computing, has high parallelism, huge storage capacity and extremely low energy consumption. It can solve NPC (Non-deterministic Polynomial complete problem) problem quickly in theory, which is a new multi-value coding and parallel computing method. It breaks through the limitation of Turing machine and von Norman system, and has the characteristics of exponential speedup, space exchange time, parallel degree of exponent and obtaining all solution sets. In this paper, a new parallel system, the generalized molecular computing model, is studied. The model combines sopc (system on Chip) technology with the idea of molecular computing. It is an electronic DNA model, which realizes the purpose of exchanging time by space. It can solve the complete NP problem in polynomial time. The main work of this paper is as follows: (1) the structure and characteristics of the parallel processor model based on the electronic method of molecular computing are discussed, and the methods and principles of molecular computing are systematically discussed. The main ways of implementation and advantages and disadvantages are compared and summarized; (2) in this paper, a DNA computing implementation method based on LSI is proposed, and a complete computer system is constructed, which has its own unique advantages compared with the traditional computer. It overcomes the time parallelism of the traditional computer to solve the NPC problem, and makes it possible to simultaneously search and obtain all the conclusions. (3) using VHDL to write hardware language, the extensible algorithm for solving SAT problem is solved, and the correctness of the algorithm is verified by an example problem. (4) the 0-1 knapsack problem is discussed by using the generalized molecular model and implemented on FPGA to verify the correctness of the algorithm.
【学位授予单位】：北京理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP301.6;TN791

【参考文献】