DNA Golay码的设计与分析

 DNA编码是DNA计算初始数据库中寡核苷酸序列的设计问题.合理的DNA编码可以提高实验的稳定性和正确性,从而确保DNA计算的成功率.本文给出DNA码字重量和DNA码字间Watson-Crick Hamming距离的定义;提出DNA Golay码的设计方法;分析了DNA Golay码的性质和规模;与随机搜索优码方法相比,DNA Golay码求解优码更加简单可行.     

DNA计算编码研究及其算法

编码问题仍是目前DNA计算中的重点和难点之一,实践证明通过有效的编码设计能够提高DNA计算过程中可靠性.本文介绍了约束条件的生物学特性,分析了约束条件与编码数量的关系,并给出编码的计数公式.文中设计了一种基于三字母表{A,T,C}的线性码的编码构造算法,并对运行结果进行了比较分析,同时分析了结果编码的热力学性质.最后指出DNA计算编码存在的问题及下一步的研究方向.     

一类新的能够渐进达到Gilbert-Varshamov界的Alternant子类码

本文基于Maximum Distance Separable(MDS)码的Hamming重量分布提出一类新的二元Alternant子类码.分析表明这类新的子类码包含整个BCH码类,并且可以渐进达到Gilbert-Varshamov(GV)界.     

基于DNA域编码的余三码四位减法器的设计

DNA分子逻辑电路的设计是DNA计算领域的重要研究方向。该文针对当前双轨分子逻辑电路复杂度高、响应时间慢的问题,提出一种基于域编码策略的DNA逻辑电路设计的新方法。该文设计了“多输入1输出”逻辑运算模块,构建了扇出门和放大器,并利用所构建的电路模块搭建了4位平方根分子逻辑电路,与经典的双轨策略下的4位平方根电路相比,反应物的数量由双轨的130种降低为61种,系统响应时间缩减为双轨的1/24,大大简化了电路的复杂度,提高了系统的响应速度,进一步验证了域编码策略在分子逻辑电路设计中的有效性。为了深度解析基于域编码策略的大规模复杂分子逻辑电路的设计思想,该文构造了“余三码四位减法器”,为设计大规模功能性DNA逻辑电路提供了更多的解决方案。     

DNA计算在整数规划问题中的应用

基于生化反应原理的DNA计算由于在解决一类困难问题,特别是NP-完全问题上具有硅计算机无法比拟的优势,因此对DNA计算的研究具有重要意义。利用在基于表面的DNA计算中采用荧光标记的策略,提出了一种基于DNA计算的一类特殊整数规划问题最优解的求解算法,新算法利用荧光猝灭技术,通过观察DNA分子表面的荧光来排除非解。算法分析表明,新提出的基于DNA计算的求解算法具有编码简单和错误率低等特点。     

工程数学

0157.4 2003050008Hamming码和延长Hammiog码的周期分布/王开弘,丁川,谢安国(重庆师范学院)刀曲阜师范大学学报〔自然科学版)一2 003,29(2)一45一48Halnming码是一类特殊的线性码.该文对Ha~ing码和延长Hamming码的周期分布作进一步的分析,首次利用延长Hamming码是第1阶R-M码的对偶码,给出了延长Hamming码的周期分布的表达式.参12(木)太原理工大学学报一2003,34(2)一110一112给出了一个递归构造,并且应用这个递归构造给出了区组长为4,v三2(mod 12)和v三6(mod 12)的SCDB(4,3;v).这相当于上述两类结果存在性的证明.参5(木)0157.4 2003050…     

DNA密码中的DNA编码技术

DNA密码是目前新兴的一个前沿研究方向。文章阐述了DNA计算在密码学中几个方面的应用,探讨了DNA编码问题及限制条件,特别是从用DNA计算解决密码学中的一个组合问题的实验步骤中分析了DNA编码的质量,提出了更好的编码。     

DNA编码技术探讨

文中研究了DNA编码的一般约束条件-编码距离的各种情况,找出了其中的某些等价计算,对任意两个编码序列的编码距离提出了最简化的计算方法,降低了基于汉明距离约束的计算复杂度。同时,文中还分析了Adleman哈密尔顿路径实验中采用的编码性能,提出了全新的性能更好的编码,并设计了生物验证实验进行验证。     

DNA编码的计算机筛选策略研究

1994年,Adleman提出了使用DNA分子进行计算的模型并通过实验得到了验证,昭示了这一新方法在大规模并行计算和数据存储中使用的广阔前景。然而,至今仍有很多影响其投入实际使用的关键问题未能得到很好地解决,DNA编码问题便是其中之一。文中分析了DNA编码中存在的限制条件,提出了使用计算机筛选DNA编码的思路,并使用计算机筛选出的DNA编码开展了分子生物学实验,旨在提供计算机快速有效筛选DNA编码的方法。     

等距码的几点注记

设Q(n,d)为码长为n,任意两个不同码字之间的Hamming距离为d的二元等距码所能达到的最大码字数,本文确定了Q(n,d)的一些精确值,并且给出了最优等距码的一些性质。     

On the generalized Hamming weights of several classes of cycliccods

The generalized Hamming weights of a linear code are fundamental code parameters related to the minimal overlap structures of the subcodes. They were introduced by V.K. Wei (1991) and shown to characterize the performance of the linear code in certain cryptographical applications. Results are presented on the generalized Hamming weights of several classes of binary cyclic codes, including primitive double-error-correcting and triple-error-correcting BCH codes, certain reversible cyclic codes, and some extended binary Goppa codes. In particular, the second generalized Hamming weight of primitive double-error-correcting BCH codes is determined and upper and lower bounds are obtained for the generalized Hamming weights for the codes studied. These bounds are compared to results from other methods     

Optimal binary vector quantization via enumeration of coveringcodes

Binary vector quantization (BVQ) refers to block coding of binary vectors under a fidelity measure. Covering codes were studied as a means of lattice BVQ. But a further source coding problem hidden in the equivalence of covering codes has seemingly eluded attention. Given a d-dimensional hypercube (code space), equivalent covering codes of the same covering radius but of different codewords have different expected BVQ distortions for a general probability mass function. Thus one can minimize, within the code equivalence, the expected distortion over all different covering codes. This leads a two-stage optimization scheme for BVQ design. First we use an optimal covering code to minimize the maximum per-vector distortion at a given rate. Then under the minmax constraint, we minimize the expected quantization distortion. This minmax constrained BVQ method (MCBVQ) controls both the maximum and average distortions, and hence improves subjective quality of compressed binary images, MCBVQ also avoids poor local minima that may trap the generalized Lloyd method. The [7,4] Hamming code and [8,4] extended Hamming code are found to be particularly suitable for MCBVQ on binary images. An efficient and simple algorithm is introduced to enumerate all distinct [7,4] Hamming/[8,4] extended Hamming codes and compute the corresponding expected distortions in optimal MCBVQ design. Furthermore, MCBVQ using linear covering codes has a compact codebook and a fast syndrome-encoding algorithm     

Computerised search for linear binary codes

A computerised search procedure is described for finding new binary codes The method involves the extension of a given known code by annexing a number of parity-check digits to it in such a way that the minimum Hamming distance of the given code is improved. A number of codes found by this procedure have better rates than the best known codes of identical Hamming distance and the same number of information digits; a table of these codes is presented.     

Simple MAP decoding of first-order Reed-Muller and Hamming codes

A maximum a posteriori (MAP) probability decoder of a block code minimizes the probability of error for each transmitted symbol separately. The standard way of implementing MAP decoding of a linear code is the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm, which is based on a trellis representation of the code. The complexity of the BCJR algorithm for the first-order Reed-Muller (RM-1) codes and Hamming codes is proportional to n/sup 2/, where n is the code's length. In this correspondence, we present new MAP decoding algorithms for binary and nonbinary RM-1 and Hamming codes. The proposed algorithms have complexities proportional to q/sup 2/n log/sub q/n, where q is the alphabet size. In particular, for the binary codes this yields complexity of order n log n.     

Estimating the fraction of erasure patterns correctable by linear codes

The conditional probability (fraction) of the successful decoding of erasure patterns of high (greater than the code distance) weights is investigated for linear codes with the partially known or unknown weight spectra of code words. The estimated conditional probabilities and the methods used to calculate them refer to arbitrary binary linear codes and binary Hamming, Panchenko, and Bose–Chaudhuri–Hocquenghem (BCH) codes, including their extended and shortened forms. Error detection probabilities are estimated under erasure-correction conditions. The product-code decoding algorithms involving the correction of high weight erasures by means of component Hamming, Panchenko, and BCH codes are proposed, and the upper estimate of decoding failure probability is presented.     

No binary quadratic residue code of length 8m-1 is quasi-perfect

The class of binary quadratic residue (QR) codes of length n=8m-1 contains two perfect codes. These are the (7,4,3) Hamming code and the (23,12,7) Golay code. However, it is proved in the present paper that there are no quasi-perfect QR codes of length 8m-1. Finally, this result is generalized to all binary self-dual codes of length N>72     

On the Undetected Error Probability for Shortened Hamming Codes

Shortened Hamming codes are widely used for error detection in data communications. In this paper, a method for computing the probability of an undetected error for these codes is presented. This method is then used to evaluate the error-detection performance of the shortened codes obtained from the two distance-4 Hamming codes adopted by CCITT X.25 for error control for packet-switched networks. We show that shortening a code does affect its error-detection performance.     

几种LDPC码的最小汉明距离的计算

本文提出一种计算LDPC码的真实最小汉明距离的方法．该方法能够用来计算多种LDPC码方案的真实最小汉明距离，比如准循环LDPC码、pi-旋转LDPC码等．该方法是通过计算码的环长间接地找到LDPC码最小距离，由于计算环长的计算量要远比直接计算最小汉明距离来得低，因而该算法能够在有限时间内找到LDPC码的真实最小距离．通过仿真表明，用目前主流的个人计算机利用该方法找出一个有最小距离24的码率为1／4的准循环LDPC码最小距离大概需要花77分钟。     

Difference-preserving codes

A code of integers into binary sequences is called a difference-preserving code (DP code) if it has the following two properties: 1) if the absolute value of the difference between two integers is less than or equal to a certain threshold, the Hamming distance between their codewords is equal to this value and 2) if the absolute value of the difference between two integers exceeds the threshold, then the Hamming distance between their codewords also exceeds this threshold. Such codes (or slight modifications thereof) have also been called path codes, circuit codes, or snake-in-the-box codes. This paper discusses the application of DP codes to pattern recognition and classification problems and presents a construction of efficient DP codes whose information content is asymptotically (in the length of codewords) of the order of theoretical upper bounds.     

Euclidean distance for combinations of some Hamming codes and binary CPFSK modulation (Corresp.)

The integration of channel coding and modulation in a communication system to increase the Euclidean distance between modulated signals is analyzed. Systems using binary continuous-phase frequency-shift keying modulation and some block codes, such as Hamming codes and shortened Hamming codes, are considered. It is shown that the minimum Euclidean distance depends on the configuration of the parity-check matrixHof the code. For the examined codes the optimum configurations ofH, which give the maximum values of the minimum Euclidean distance, are determined.