资源描述：
《基于FPGA的DNA算法设计与仿真实现.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、基于FPGA的DNA算法设计与仿真实现杨震2015年1月中图分类号：TQ028.1UDC分类号：540基于FPGA的DNA算法设计与仿真实现作者姓名杨震学院名称机电学院指导教师马天宝副教授答辩委员会主席秦太验教授申请学位工学硕士学科专业工学力学学位授予单位北京理工大学论文答辩日期2015年1月DNAalgorithmbasedonFPGAdesignandsimulationimplementationCandidateName：YangZhenSchoolorDepartment:electrical
2、andmechanicalFacultyMentor:AssociateProf.Tianbao-MaChair,ThesisCommittee：Prof.Tianyan-QinDegreeApplied:MasterofPhilosophyMajor：EngineeringMechanicsDegreeby:BeijingInstituteofTechnologyTheDateofDefence：January，2015研究成果声明本人郑重声明：所提交的学位论文是我本人在指导教师的指导下进行的研究工作
3、获得的研究成果。尽我所知，文中除特别标注和致谢的地方外，学位论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京理工大学或其它教育机构的学位或证书所使用过的材料。与我一同工作的合作者对此研究工作所做的任何贡献均已在学位论文中作了明确的说明并表示了谢意。特此申明。签名：日期：北京理工大学硕士学位论文摘要分子计算又称DNA计算，具有高度并行性、巨大存储容量和极低的能耗，理论上能快速求解NPC（Non-deterministicPolynomialcompleteproblem）问题，是一种全新的
4、多值编码和并行计算方法，它突破了图灵机和冯诺曼体系限制，有指数的加速比、空间交换时间、指数的并行度和获得全体解集等特点。本文研究了一个新的并行系统，即广义分子计算模型，该模型运用了sopc（片上系统）技术和分子计算思想结合的方法，是一种电子DNA模型，该模型实现了以空间换时间的目的，能够在多项式时间内解决完全NP问题。论文主要研究工作如下：（1）讨论了基于分子计算的电子方式的并行处理机模型的结构和特征，系统地对分子计算方法、原理、主要实现方式和优缺点等方面进行了比对和总结；（2）论文提出了一种基于大规模
5、集成电路设计的DNA计算实现方式，构建了一个完整的计算机系统，该系统相对于传统的计算机具有自己独特的优势，它克服了传统计算机解决NPC问题的时间并行性，使得它能够同时搜索获得所有的结论；（3）运用VHDL编写硬件语言，解决了具有可扩展性的解决SAT问题的算法，并用实例问题对算法的正确性进行了验证；（4）运用广义分子计算模型，探讨了0-1背包问题，并在FPGA上实现，验证了算法的正确性。关键词：分子计算；FPGA；SAT问题；0-1背包问题I北京理工大学硕士学位论文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
