基于FPGA的DNA算法設(shè)計與仿真實現(xiàn)
發(fā)布時間：2018-12-22 08:21
【摘要】：分子計算又稱DNA計算，具有高度并行性、巨大存儲容量和極低的能耗，理論上能快速求解NPC（Non-deterministic Polynomial complete problem）問題，是一種全新的多值編碼和并行計算方法，它突破了圖靈機和馮諾曼體系限制，有指數(shù)的加速比、空間交換時間、指數(shù)的并行度和獲得全體解集等特點。本文研究了一個新的并行系統(tǒng)，即廣義分子計算模型，該模型運用了sopc（片上系統(tǒng)）技術(shù)和分子計算思想結(jié)合的方法，是一種電子DNA模型，該模型實現(xiàn)了以空間換時間的目的，能夠在多項式時間內(nèi)解決完全NP問題。 論文主要研究工作如下： （1）討論了基于分子計算的電子方式的并行處理機模型的結(jié)構(gòu)和特征，系統(tǒng)地對分子計算方法、原理、主要實現(xiàn)方式和優(yōu)缺點等方面進行了比對和總結(jié)； （2）論文提出了一種基于大規(guī)模集成電路設(shè)計的DNA計算實現(xiàn)方式，構(gòu)建了一個完整的計算機系統(tǒng)，該系統(tǒng)相對于傳統(tǒng)的計算機具有自己獨特的優(yōu)勢，它克服了傳統(tǒng)計算機解決NPC問題的時間并行性，使得它能夠同時搜索獲得所有的結(jié)論； （3）運用VHDL編寫硬件語言，解決了具有可擴展性的解決SAT問題的算法，并用實例問題對算法的正確性進行了驗證； （4）運用廣義分子計算模型，探討了0-1背包問題，并在FPGA上實現(xiàn)，，驗證了算法的正確性。
[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
本文編號：2389560
[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
【參考文獻】
相關(guān)期刊論文 前10條
1 高琳,許進,張軍英;DNA計算的研究進展與展望[J];電子學報;2001年07期
2 殷志祥,張鳳月,許進;0-1規(guī)劃問題的DNA計算[J];電子與信息學報;2003年01期
3 張慶友,許祿;DNA編碼序列的圖形表示及相似度計算[J];高等學校化學學報;2002年07期
4 周康;殷燕芳;李玉華;覃磊;;DNA編碼的模型分析[J];華中科技大學學報(自然科學版);2007年07期
5 王子成;周康;羅亮;強小利;;DNA計算中編碼序列的過濾函數(shù)研究[J];計算機工程與應(yīng)用;2008年32期
6 李人厚,余文;關(guān)于DNA計算的基本原理與探討[J];計算機學報;2001年09期
7 許進,張雷;DNA計算機原理、進展及難點(Ⅰ):生物計算系統(tǒng)及其在圖論中的應(yīng)用[J];計算機學報;2003年01期
8 許進,李三平,董亞非,魏小鵬;粘貼DNA計算機模型(Ⅱ):應(yīng)用[J];科學通報;2004年04期
9 李源,方辰,歐陽頎;最大集團問題的DNA計算機進化算法[J];科學通報;2004年05期
10 李艷梅;余文;寧建國;;一種廣義分子計算模型及其在NP問題中的應(yīng)用[J];計算機應(yīng)用研究;2014年11期
本文編號：2389560
本文鏈接：http://www.wukwdryxk.cn/kejilunwen/dianzigongchenglunwen/2389560.html
最近更新
教材專著
