基于IC的DNA计算模型的设计

论文摘要

近年来DNA计算得到了飞速发展，它具有高度并行性，运算速度快，作为信息载体其贮存容量大，能量消耗低，资源丰富等优点。目前DNA计算在实现上受限于化学条件及自身特点，实现步骤复杂，错误率高。而电子电路具有运算速度快，计算准确，可以复用等优点。本文进行了IC技术和DNA计算思想相结合的尝试，设计出了电子DNA计算模型。该模型具有电子电路和DNA计算共同的优点。本文的主要研究内容如下：1．分析了传统的并行电子计算系统的结构和特征，探讨了DNA计算的方法和思想。2．讨论了使用电路技术实现DNA计算的可行性。提出了电子DNA计算的机器模型的设计方案。3．针对SAT问题，本文参考了DNA计算的解题模型，改造和完善了电子DNA计算的机器模型，使该模型具有最基本的并行存储能力。在FPGA上实现了该机器模型。针对具体SAT问题进行了功能仿真。4．编写了单片机控制程序。电子DNA计算模型通过单片机的控制，实现了全自动的SAT解题过程。5．针对整数均分问题，改造和完善了电子DNA计算机器模型，使电子DNA计算模型具有了并行的算术和逻辑运算能力。在FPGA上实现了该机器模型，通过功能仿真成功解出了1-7的整数均分问题。电子DNA计算的机器模型的设计方案，具有电子电路和DNA计算共同的优点，是利用IC技术模拟DNA计算的一种探索。该模型实现了以空间换时间的目的，是在多项式时间内解决NP完全问题的一种尝试。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 电子并行计算介绍
• 1.2.1 对称多处理机系统
• 1.2.2 分布共享存储处理机系统
• 1.2.3 大规模并行计算机系统
• 1.2.4 机群系统
• 1.3 DNA计算介绍
• 1.3.1 DNA计算的基本思想
• 1.3.2 DNA计算研究现状
• 1.3.3 DNA计算的实现方式
• 1.3.4 DNA计算研究内容及前景
• 1.3.5 DNA计算优点及目前存在的问题
• 第二章 基于IC的DNA计算模型的设计
• 2.1 基于IC的DNA计算模型的设计的可行性
• 2.2 电子DNA模型设计
• 2.3 电子DNA计算模型实现工具
• 2.3.1 FPGA简介
• 2.3.2 VHDL语言介绍
• 2.3.3 ISE8.1ⅰ介绍
• 2.3.4 单片机开发板介绍
• 第三章 基于电子DNA计算模型的SAT问题解决方案
• 3.1 可满足性（SAT）问题概念
• 3.2 DNA计算解决SAT的主要方法
• 3.3 SAT问题解题算法设计
• 3.4 SAT问题解题模型的设计
• 3.4.1 SAT问题解题模型整体结构设计
• 3.4.2 转换器的设计
• 3.4.3 存储运算单元的设计
• 3.4.4 串行接收器的设计
• 3.4.5 结果汇集器的设计
• 3.4.6 控制器的设计
• 3.4.7 单片机程序的设计
• 3.5 系统仿真及硬件实现
• 3.6 可满足性问题实现的规模
• 第四章 基于电子DNA计算模型的均分问题解决方案设计
• 4.1 均分问题简介
• 4.2 均分问题解题模型设计
• 4.3 电子DNA运算单元设计
• 4.4 读出解的方案设计
• 4.5 均分问题解题算法
• 4.6 均分问题的功能仿真
• 第五章 总结展望
• 5.1 结论
• 5.2 进一步工作
• 参考文献
• 致谢