计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (25): 33-36.

• 学术探讨 • 上一篇    下一篇

用线性码构造DNA计算编码的海明距离

朱翔鸥,刘文斌,陈丽春,王向红   

  1. 温州大学 计算机科学与工程学院,浙江 温州 325035
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-09-01 发布日期:2007-09-01
  • 通讯作者: 朱翔鸥

Calculating Hamming distance of DNA codes with linear constructions

ZHU Xiang-ou,LIU Wen-bin,CHEN Li-chun,WANG Xiang-hong   

  1. College of Computer Science and Engineering,Wenzhou University,Wenzhou,Zhejiang 325035,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-09-01 Published:2007-09-01
  • Contact: ZHU Xiang-ou

摘要: 最小海明距离是DNA计算编码性能的重要评价标准。利用线性码来构造DNA计算编码的最小海明距离是一种有效的方法,关键在于构造相应的监督矩阵。为了寻找监督矩阵,提出了监督矩阵的搜索算法和优化方法,及两个必要性定理;作为介于最小海明距离上限与下限之间的编码存在性的判断依据,给出了两个关于线性码存在性定理;最后给出了三字母表DNA计算编码相关的监督矩阵搜索算法结果,以及当最小海明距离一定时,接近编码数量上限的部分线性码的存在性结果。根据这些结果和存在性定理,可以推断常用DNA计算编码最小海明距离的存在性。

关键词: DNA计算, 海明距离, 线性码, 监督矩阵

Abstract: The encoding problem is a most fundamental issue in DNA computing,the minimal Hamming distance is an important evaluation criterion for measuring coding performance for DNA computation.It is effective method used to construct minimal Hamming distance with linear codes,its key is forming a relevant check matrix for codewords.It presents a search algorithm,optimized means and 2 interrelated necessity theorems for check matrix;It also advances judgment of existence between upper limit and lower limit for minimal Hamming distance,and 2 existence theorems of linear codes;Finally,it gives result of search algorithm for checking matrix over three-alphabet in DNA-based computing,and part of existence result that approach upper limit of codeword amount on GF(3) for DNA computation coding when minimal Hamming distance is definite.In accordance to these results and
existence theorems,it can deduce existence for minimal Hamming distance of typical DNA computation coding without computation on algorithm.

Key words: DNA computation, Hamming distance, linear codes, check matrix