資源描述：
《基于FPGA的DNA算法設(shè)計與仿真實現(xiàn).pdf》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、基于FPGA的DNA算法設(shè)計與仿真實現(xiàn)楊震2015年1月中圖分類號：TQ028.1UDC分類號：540基于FPGA的DNA算法設(shè)計與仿真實現(xiàn)作者姓名楊震學(xué)院名稱機(jī)電學(xué)院指導(dǎo)教師馬天寶副教授答辯委員會主席秦太驗教授申請學(xué)位工學(xué)碩士學(xué)科專業(yè)工學(xué)力學(xué)學(xué)位授予單位北京理工大學(xué)論文答辯日期2015年1月DNAalgorithmbasedonFPGAdesignandsimulationimplementationCandidateName：YangZhenSchoolorDepartment:electrical
2、andmechanicalFacultyMentor:AssociateProf.Tianbao-MaChair,ThesisCommittee：Prof.Tianyan-QinDegreeApplied:MasterofPhilosophyMajor：EngineeringMechanicsDegreeby:BeijingInstituteofTechnologyTheDateofDefence：January，2015研究成果聲明本人鄭重聲明：所提交的學(xué)位論文是我本人在指導(dǎo)教師的指導(dǎo)下進(jìn)行的研究工作
3、獲得的研究成果。盡我所知，文中除特別標(biāo)注和致謝的地方外，學(xué)位論文中不包含其他人已經(jīng)發(fā)表或撰寫過的研究成果，也不包含為獲得北京理工大學(xué)或其它教育機(jī)構(gòu)的學(xué)位或證書所使用過的材料。與我一同工作的合作者對此研究工作所做的任何貢獻(xiàn)均已在學(xué)位論文中作了明確的說明并表示了謝意。特此申明。簽名：日期：北京理工大學(xué)碩士學(xué)位論文摘要分子計算又稱DNA計算，具有高度并行性、巨大存儲容量和極低的能耗，理論上能快速求解NPC（Non-deterministicPolynomialcompleteproblem）問題，是一種全新的
4、多值編碼和并行計算方法，它突破了圖靈機(jī)和馮諾曼體系限制，有指數(shù)的加速比、空間交換時間、指數(shù)的并行度和獲得全體解集等特點(diǎn)。本文研究了一個新的并行系統(tǒng)，即廣義分子計算模型，該模型運(yùn)用了sopc（片上系統(tǒng)）技術(shù)和分子計算思想結(jié)合的方法，是一種電子DNA模型，該模型實現(xiàn)了以空間換時間的目的，能夠在多項式時間內(nèi)解決完全NP問題。論文主要研究工作如下：（1）討論了基于分子計算的電子方式的并行處理機(jī)模型的結(jié)構(gòu)和特征，系統(tǒng)地對分子計算方法、原理、主要實現(xiàn)方式和優(yōu)缺點(diǎn)等方面進(jìn)行了比對和總結(jié)；（2）論文提出了一種基于大規(guī)模
5、集成電路設(shè)計的DNA計算實現(xiàn)方式，構(gòu)建了一個完整的計算機(jī)系統(tǒng)，該系統(tǒng)相對于傳統(tǒng)的計算機(jī)具有自己獨(dú)特的優(yōu)勢，它克服了傳統(tǒng)計算機(jī)解決NPC問題的時間并行性，使得它能夠同時搜索獲得所有的結(jié)論；（3）運(yùn)用VHDL編寫硬件語言，解決了具有可擴(kuò)展性的解決SAT問題的算法，并用實例問題對算法的正確性進(jìn)行了驗證；（4）運(yùn)用廣義分子計算模型，探討了0-1背包問題，并在FPGA上實現(xiàn)，驗證了算法的正確性。關(guān)鍵詞：分子計算；FPGA；SAT問題；0-1背包問題I北京理工大學(xué)碩士學(xué)位論文AbstractMolecularcom
6、puting,alsoknownasDNAcomputing,withhighparallelismandhugestoragecapacityandlowenergyconsumption,intheory,canquicklysolvetheNPC(Non-deterministicPolynomialcompleteproblem),isakindofbrand-newmulti-valuecodingandparallelcomputingmethod,itbrokethroughtheTuri
7、ngandvonNormansystemrestriction,haveindexspeedup,exchangeofspacetime,indexofparallelismandgetallthesolutionset,etc.Thispaperstudiesanewparallelsystem,namelygeneralizedmolecularcomputingmodel,themodelusingthesopc(systemonachip)technologyandthemethodofcomb
8、iningmolecularcomputingthought,isakindofelectronicmodelofDNA,themodelachievedwiththepurposeoftradingspacefortime,abletosolvetheproblemoffullNPinpolynomialtime.Papermainresearchworkisasfollows:(1)Thestructureandthecharacter
