基于特定模数集的并行DNA算术运算

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (6): 51-54.

基于特定模数集的并行DNA算术运算

郑学东¹,许进¹,徐菲²

1.华中科技大学控制科学与工程系，武汉 430074
2.青岛科技大学数理学院，山东青岛 266061

收稿日期:2007-09-03 修回日期:2007-10-19 出版日期:2008-02-21 发布日期:2008-02-21
通讯作者: 郑学东

Parallel DNA arithmetic computation based on special moduli set

ZHENG Xue-dong¹,XU Jin¹,XU Fei²

1.Department of Control Science and Engineering，Huazhong University of Science and Technology，Wuhan 430074，China
2.Academy of Mathematics and Physics，Qingdao University of Science and Technology，Qingdao，Shandong 266061，China

Received:2007-09-03 Revised:2007-10-19 Online:2008-02-21 Published:2008-02-21
Contact: ZHENG Xue-dong

摘要/Abstract

摘要： 在DNA算术运算的模型中普遍应用二进制，受制于进位的影响，难以实现并行运算。但在剩余数制中，算术运算（加、减、乘）在剩余位之间不存在进位，故可降低运算过程的复杂度，可以充分利用DNA计算巨大并行性的优势，简化实际编码的难度。基于Adleman-Lipton模型，分析了剩余数制的基本原理，基于特定的模数集，改进了整数的DNA链表示，并将其应用于DNA算术运算，给出了特定剩余数制下进行并行DNA算术运算的具体算法。

Abstract: The binary number system is widely implemented in the model of DNA arithmetic computation，but the rippling effect caused by carry-propagation on a sum makes it difficult to realize the arithmetic computation in parallel.In the Residue Number System（RNS），the arithmetic computation（addition，subtraction and multiplication） is carry-free inherently.So the complexity of arithmetic computation can be decreased and the massive parallelism of DNA computing can be exploited and DNA encoding can be simplified in practice.The basic principles of RNS are analyzed and a special moduli set is selected in this paper.Based on the Adleman-Lipton model，an improved DNA representation of number is presented and applied in the arithmetic computation in RNS.And the concrete algorithm is presented for DNA arithmetic computation based on the special moduli set.

郑学东¹,许进¹,徐菲². 基于特定模数集的并行DNA算术运算[J]. 计算机工程与应用, 2008, 44(6): 51-54.

ZHENG Xue-dong¹,XU Jin¹,XU Fei². Parallel DNA arithmetic computation based on special moduli set[J]. Computer Engineering and Applications, 2008, 44(6): 51-54.