資源描述：
《基于FPGA的DNA算法設(shè)計(jì)與仿真實(shí)現(xiàn).pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、基于FPGA的DNA算法設(shè)計(jì)與仿真實(shí)現(xiàn)楊震2015年1月中圖分類號(hào)：TQ028.1UDC分類號(hào)：540基于FPGA的DNA算法設(shè)計(jì)與仿真實(shí)現(xiàn)作者姓名楊震學(xué)院名稱機(jī)電學(xué)院指導(dǎo)教師馬天寶副教授答辯委員會(huì)主席秦太驗(yàn)教授申請(qǐng)學(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é)位或證書所使用過的材料。與我一同工作的合作者對(duì)此研究工作所做的任何貢獻(xiàn)均已在學(xué)位論文中作了明確的說明并表示了謝意。特此申明。簽名：日期：北京理工大學(xué)碩士學(xué)位論文摘要分子計(jì)算又稱DNA計(jì)算，具有高度并行性、巨大存儲(chǔ)容量和極低的能耗，理論上能快速求解NPC（Non-deterministicPolynomialcompleteproblem）問題，是一種全新的
4、多值編碼和并行計(jì)算方法，它突破了圖靈機(jī)和馮諾曼體系限制，有指數(shù)的加速比、空間交換時(shí)間、指數(shù)的并行度和獲得全體解集等特點(diǎn)。本文研究了一個(gè)新的并行系統(tǒng)，即廣義分子計(jì)算模型，該模型運(yùn)用了sopc（片上系統(tǒng)）技術(shù)和分子計(jì)算思想結(jié)合的方法，是一種電子DNA模型，該模型實(shí)現(xiàn)了以空間換時(shí)間的目的，能夠在多項(xiàng)式時(shí)間內(nèi)解決完全NP問題。論文主要研究工作如下：（1）討論了基于分子計(jì)算的電子方式的并行處理機(jī)模型的結(jié)構(gòu)和特征，系統(tǒng)地對(duì)分子計(jì)算方法、原理、主要實(shí)現(xiàn)方式和優(yōu)缺點(diǎn)等方面進(jìn)行了比對(duì)和總結(jié)；（2）論文提出了一種基于大規(guī)模
5、集成電路設(shè)計(jì)的DNA計(jì)算實(shí)現(xiàn)方式，構(gòu)建了一個(gè)完整的計(jì)算機(jī)系統(tǒng)，該系統(tǒng)相對(duì)于傳統(tǒng)的計(jì)算機(jī)具有自己獨(dú)特的優(yōu)勢(shì)，它克服了傳統(tǒng)計(jì)算機(jī)解決NPC問題的時(shí)間并行性，使得它能夠同時(shí)搜索獲得所有的結(jié)論；（3）運(yùn)用VHDL編寫硬件語言，解決了具有可擴(kuò)展性的解決SAT問題的算法，并用實(shí)例問題對(duì)算法的正確性進(jìn)行了驗(yàn)證；（4）運(yùn)用廣義分子計(jì)算模型，探討了0-1背包問題，并在FPGA上實(shí)現(xiàn)，驗(yàn)證了算法的正確性。關(guān)鍵詞：分子計(jì)算；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
