DNA编码技术探讨

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

DNA Golay码的设计与分析

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

二元DNA Hamming码的设计及分析

DNA计算作为一种新的计算模式,有着强大的计算能力。实验表明,有效的编码可以提高DNA计算的可靠性,从而保证DNA计算的成功率。二元Hamming码是一类达到Hamming界的好码,也是仅有的两类完全码中的一类。文中基于纠错码编码理论给出了二元DNA Hamming码的设计过程,并进一步分析了所设计的二元DNA Hamming码的性质及其优点。     

基于遗传算法的测量船工况优选方法

根据传统工况设计方法中存在的约束条件多、计算量大、主观因素影响大等特点,采用过滤函数、适应度评估、位串编码、轮盘选择等方法,提出了一种基于遗传算法的测量船工况优选方法,并分析了收敛速度、终止条件、基因突变等影响因素.实验表明,此方法有效提高了测量船工况设计客观性和设计效率,优选了设计结果.     

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

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

DNA密码中的DNA编码技术

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

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

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

DNA计算的研究进展与展望

DNA计算是一种模拟生物分子DNA的结构并借助于分子生物技术进行计算的新方法,它开创了以化学反应作为计算工具的先例,为NP-完全问题的解决提供了一种全新的途径,具有广阔的应用前景.DNA计算的两个主要特点是计算的高度并行性和巨大的信息存储容量.本文首先介绍了DNA计算的基本思想;然后综述了DNA算例及其模型;分析了DNA计算的特点及其与遗传算法的类比关系;指出了DNA计算目前存在的问题;最后对DNA计算的发展前景进行展望.     

一种优化DNA计算模板性能的新方法

编码问题是目前DNA计算中的重点和难点之一,该文介绍了影响编码的各种因素及模板编码的基本思想.在此基础上分析了移位杂交出现的原因,提出了提高模板结合移位距离的一种新算法.该算法一方面降低了搜索空间,另一方面筛选了那些自身移位距离性质差的序列因而提高了算法的效率.计算结果表明模板集合的性能明显提高.此外,在保持01含量基本不变的情况下,适当扩展模板集合的搜索范围可以增加模板的数量.     

图的顶点着色问题的DNA算法

图的顶点着色问题是指无向图中任意两个相邻顶点都分配到不同的颜色,这个问题是著名的NP-完全问题,没有非常有效的算法.但在1994年Adleman^[1]首次提出用DNA计算解决NP-完全问题,设计出一种全新的计算模式—模拟生物分子DNA的结构并借助于分子生物技术进行计算,使得NP-完全问题的求解可能得到解决.本文首先提出了基于分子生物技术的图的顶点着色问题的DNA算法,算法的关键是对图中的顶点和顶点的颜色进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离,依据分子生物学的实验方法,本文提出的算法是有效和可行的;其次指出了该算法的优点、存在的问题及将来进一步的研究方向.     

Linear Time Encoding of LDPC Codes

In this paper, we propose a linear complexity encoding method for arbitrary LDPC codes. We start from a simple graph-based encoding method ?label-and-decide.? We prove that the ?label-and-decide? method is applicable to Tanner graphs with a hierarchical structure-pseudo-trees-and that the resulting encoding complexity is linear with the code block length. Next, we define a second type of Tanner graphs-the encoding stopping set. The encoding stopping set is encoded in linear complexity by a revised label-and-decide algorithm-the ?label-decide-recompute.? Finally, we prove that any Tanner graph can be partitioned into encoding stopping sets and pseudo-trees. By encoding each encoding stopping set or pseudo-tree sequentially, we develop a linear complexity encoding method for general low-density parity-check (LDPC) codes where the encoding complexity is proved to be less than 4 ·M ·((k?- 1), where M is the number of independent rows in the parity-check matrix and k? represents the mean row weight of the parity-check matrix.     

在FPGA中状态机的编码方式

在FPGA(现场可编程门阵列)器件设计中,状态机的设计方法是最常用的设计方法之一,而通过怎样的编码形式才能达到最好的设计要求,成为设计所要解决的一个很重要的问题.在状态机的编码方式中,最常用的是顺序编码和One-hot编码方式.文中通过对这两种状态机编码方式的优缺点比较,说明应该如何选择编码方式,以及如何避免在此过程中可能出现的一些错误.     

Efficient encoding of low-density parity-check codes

Low-density parity-check (LDPC) codes can be considered serious competitors to turbo codes in terms of performance and complexity and they are based on a similar philosophy: constrained random code ensembles and iterative decoding algorithms. We consider the encoding problem for LDPC codes. More generally we consider the encoding problem for codes specified by sparse parity-check matrices. We show how to exploit the sparseness of the parity-check matrix to obtain efficient encoders. For the (3,6)-regular LDPC code, for example, the complexity of encoding is essentially quadratic in the block length. However, we show that the associated coefficient can be made quite small, so that encoding codes even of length n≃100000 is still quite practical. More importantly, we show that “optimized” codes actually admit linear time encoding     

高精度多种进制圆光栅制造方法的研究

本文提出了一种用于ＣＡＭ系统的最小公倍数法，以及用该方法研制的多种进制增量式圆光栅ＣＡＭ刻划系统．应用该方法有效地解决了多种进制增量式圆光栅和多种进制指示光栅的刻划难题，实现了在一种进制的光电图刻线机上刻划多种进制圆光栅。另外，详细介绍了其实现方法，以及用于该ＣＡＭ系统的硬件和软件．     

On the performance of iterative noncoherent detection of codedM-PSK signals

Differential encoding is often used in conjunction with noncoherent demodulation to overcome carrier phase synchronization problems in communication systems employing M-ary phase-shift keying (M-PSK). It is generally acknowledged that differential encoding leads to a degradation in performance over absolutely encoded M-PSK systems with perfect carrier synchronization. In this paper, we show that when differential encoding is combined with convolutional encoding and interleaving, this degradation does not necessarily occur. We propose a novel noncoherent receiver for differentially encoded M-PSK signals that is capable of significantly outperforming optimal coherent receivers for absolutely encoded M-PSK using the same convolutional code. This receiver uses an iterative decoding technique and is based on a multiple differential detector structure to overcome the effect of the carrier phase error. In addition, to better illustrate the benefits of the powerful combination of convolutional encoding, interleaving, and differential encoding, we also present an iterative coherent receiver for differentially encoded M-PSK     

The encoding complexity of network coding

In the multicast network coding problem, a source s needs to deliver h packets to a set of k terminals over an underlying communication network G. The nodes of the multicast network can be broadly categorized into two groups. The first group includes encoding nodes, i.e., nodes that generate new packets by combining data received from two or more incoming links. The second group includes forwarding nodes that can only duplicate and forward the incoming packets. Encoding nodes are, in general, more expensive due to the need to equip them with encoding capabilities. In addition, encoding nodes incur delay and increase the overall complexity of the network. Accordingly, in this paper, we study the design of multicast coding networks with a limited number of encoding nodes. We prove that in a directed acyclic coding network, the number of encoding nodes required to achieve the capacity of the network is bounded by h/sup 3/k/sup 2/. Namely, we present (efficiently constructible) network codes that achieve capacity in which the total number of encoding nodes is independent of the size of the network and is bounded by h/sup 3/k/sup 2/. We show that the number of encoding nodes may depend both on h and k by presenting acyclic coding networks that require /spl Omega/(h/sup 2/k) encoding nodes. In the general case of coding networks with cycles, we show that the number of encoding nodes is limited by the size of the minimum feedback link set, i.e., the minimum number of links that must be removed from the network in order to eliminate cycles. We prove that the number of encoding nodes is bounded by (2B+1)h/sup 3/k/sup 2/, where B is the minimum size of a feedback link set. Finally, we observe that determining or even crudely approximating the minimum number of required encoding nodes is an /spl Nscr/P-hard problem.     

基于一种新的时空编码技术的片上总线的低延迟低能耗设计

在深亚微米设计中,降低能耗和传播延迟是片上全局总线所面对的两个最主要设计目标.本文提出了一种用于片上全局总线的时空编码方案,它既提高了性能又降低了峰值能耗和平均能耗.该编码方案利用空间总线倒相编码和时间编码电路技术的优点,在消除相邻连线上反相翻转的同时,减少了自翻转数和耦合翻转数.在应用该总线编码技术降低总线延时和能耗的设计中,给出了一种总线上插入中继驱动器的设计方法,以确定它们合适的尺寸和插入位置,使得在满足目标延时和翻转斜率要求的同时总线总的能耗最小.该方法可用来为各种编码技术获得翻转斜率约束下的总线能耗与延时的优化折中.     

基于一种新的时空编码技术的片上总线的低延迟低能耗设计

在深亚微米设计中,降低能耗和传播延迟是片上全局总线所面对的两个最主要设计目标.本文提出了一种用于片上全局总线的时空编码方案,它既提高了性能又降低了峰值能耗和平均能耗.该编码方案利用空间总线倒相编码和时间编码电路技术的优点,在消除相邻连线上反相翻转的同时,减少了自翻转数和耦合翻转数.在应用该总线编码技术降低总线延时和能耗的设计中,给出了一种总线上插入中继驱动器的设计方法,以确定它们合适的尺寸和插入位置,使得在满足目标延时和翻转斜率要求的同时总线总的能耗最小.该方法可用来为各种编码技术获得翻转斜率约束下的总线能耗与延时的优化折中.     

Fixed-Rate Maximum-Runlength-Limited Codes From Variable-Rate Bit Stuffing

We introduce the fixed-rate bit stuff (FRB) algorithm for efficiently encoding and decoding maximum-runlength-limited (MRL) sequences. Our approach is based on a simple, variable-rate technique called bit stuffing. Bit stuffing produces near-capacity achieving codes for a wide range of constraints, but encoding is variable-rate, which is unacceptable in most applications. In this work, we design near-capacity fixed-rate codes using a three-step procedure. The fixed-length input data block first undergoes iterative preprocessing, followed by variable-rate bit stuffing, and finally dummy-bit padding to a fixed output length. The iterative preprocessing is key to achieving high encoding rates. We discuss rate computation for the proposed FRB algorithm and show that the asymptotic (in input block length) encoding rate is close to the average rate of the variable-rate bit stuff code. Then, we proceed to explore the effect of decreasing/increasing the number of preprocessing iterations. Finally, we derive a lower bound on the encoding rate with finite-length input blocks and tabulate the parameters required to design FRB codes with rate close to 100/101 and 200/201.