最优指派问题DNA算法

对求最小值的最优指派数学模型,设计并实现了DNA计算算法。首先经过特殊的DNA编码将二维的决策变量和二维的效益值编入DNA序列中;然后通过杂交实验和分离实验得到指派问题的全部可行解;最后通过电泳实验和检测实验获得最优指派问题的最优解。证明了算法的复杂性并举例说明了算法的可行性。分别给出了求最大值的最优指派问题和人数与工作数不等的最优指派问题的处理方法。     

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

在DNA算术运算中引入4模数集剩余数制,以减少运算中的进位影响,实现并行运算,降低算法的复杂度,同时有利于简化DNA编码。首先分析剩余数制的基本原理以及计算模型,然后给出整数模表示的DNA编码方案与并行DNA算术运算的算法,最后讨论DNA剩余算术运算的算法与编码复杂度。     

最短路问题的闭环DNA算法

提出了不等长闭环DNA分子的概念,由此推广了闭环DNA计算模型。给出了固定端点的最短路问题闭环DNA算法,该算法首先对每条弧进行了三组DNA编码,再用有目的的终止技术合成固定端点的所有链,然后通过接入实验和电泳实验得到最短路,并通过检测实验输出所有最短路径。得出了算法的复杂性,为说明算法的有效性给出了一个算例。最后讨论了最短路问题闭环DNA算法在变权网络、自由终点或固定中间点的最短路问题中的应用,并给出了相应的解决方法。由此说明该算法具有广泛的适应性。     

有向最短哈密尔顿路问题的DNA算法

首次提出了基于分子生物技术的有向最短哈密尔顿路问题的DNA (deoxyribonucleicacid)算法 ,将顶点、权值用DNA片段编码 ,边的方向通过顶点的编码获得。将这些DNA片段放入溶液中进行生化反应 ,通过基本的生物操作及生物酶完成解的产生及最终解的分离。该算法的创新之处在于权值的设计 ,合理有效地用DNA序列表示权值的大小 ,以便于使用常规的生物分离方法进行最优路径的选择。依据分子生物学的实验方法 ,说明了所提算法是有效和可行的。     

基于自组装DNA计算的RSA密码系统破译方案

自组装DNA计算在解决NP问题,尤其是破译密码系统方面,具有传统计算机无法比拟的优势。采用DNA分子瓦编码信息,借助于分子瓦之间的粘性末端进行自组装,给出了乘法运算的实现方案。在此基础上,通过引入非确定性的指派分子瓦,提出了一种用自组装DNA计算破译RSA公钥密码系统的非确定性算法。通过创建数以亿计的参与计算的DNA分子瓦,在DNA计算能力允许的范围内,该算法可以并行地测试每个可能的因子,以高概率地分解整数。该方法最大的优点是充分利用了DNA分子瓦具有的海量存储能力、生化反应的巨大并行性以及组装的自发有序性。     

0-1规划问题的闭环DNA算法

提出了闭环DNA分子的结构灵活性的两个方面,即DNA分子链长的可控性和DNA分子之间的相互转化。针对非负整数系数的0-1规划问题,提出了闭环DNA算法。该算法首先对0-1变量按照0和1的取值、对应的各项系数和检测标记进行五组DNA编码并形成所有可能解;再利用接入实验、电泳实验和删除实验筛选出可行解,进而得到所有最优解;最后通过检测实验输出实验结果。给出了算法的正确性的证明并讨论了算法复杂性,给出一个算例说明了算法的有效性。对算法进行了改进,改进后的算法适用于可以含有负数的实数系数0-1规划问题。     

DNA计算与软计算

最近,DNA计算引起了人们的广泛兴趣,尤其是DNA计算与软计算的集成.本文较系统地介绍了与DNA计算相关的生物学知识、主要生物操作,给出了DNA计算模型及其算法实现,探讨了DNA计算与进化计算、模糊控制、神经网络和人工免疫系统进行集成的概念与方法.     

背包问题的闭环DNA算法

提出了闭环DNA分子的结构多样性,即闭环DNA分子在同一个位置上具有不同的DNA序列.提出了双约束的整数规划背包问题闭环DNA算法,即对变量取值进行DNA编码并形成所有可能解;用批接入实验、电泳实验和批删除实验筛选出可行解,用批接入实验、电泳实验得到最优解;通过检测实验输出所有最优解.由一个算例说明算法的有效性.针对减少DNA编码和内切酶数量的问题改进了算法;对有特殊要求的背包问题提出了解决方法.     

TSP的DNA计算算法

提出了TSP的DNA算法,共有六个步骤:首先将TSP转化为有向图的经过所有点最短闭链问题并进行编码;其次从某点开始用有目的的终止技术——芯片技术、保护基技术以及杂交实验——得到起点和终点相同的DNA链;再用分离实验产生经过所有顶点的DNA链;然后用电泳实验取出链长最短的DNA链;最后用标记实验解读最优解集。讨论了算法的复杂性并用实例说明了算法的有效性。还讨论了推广的TSP——推销员在城市有停留时间——的算法的变化——只需改变编码方式,以及实验的简化问题。最后说明了本算法提出的一种新的合成技术——有目的的终止技术的优势和前景。     

最小顶点覆盖问题的DNA分子算法

最小顶点覆盖问题是找给定图G中覆盖每条边的最小顶点子集,这个问题即是一个著名的NP 完全问题。给出了基于分子生物技术的图的顶点覆盖问题的DNA算法。算法的关键是数学问题到DNA链的映射,对图中的顶点进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离。依据分子生物学的实验方法,提出的算法是有效和可行的。最后指出了该算法的优点、存在问题及下一步的研究方向。     

DNA计算在组合优化中的应用及其复杂性

在过去几年里,一些富有卓见的研究人员已经衔接了生物计算和实际的DNA计算之间的间隙。他们使用机灵的编码技术和聪明的分子生物学操作,找到了计算复杂问题的简单方案,并且解决了许多组合优化中的NP-完全问题。然而,计算的执行期间(生物反应过程中),技术的问题已经揭示了对于解决实际问题来说,DNA计算机作为硅计算机的竞争对手目前仍将是不可能的。主要介绍了目前利用DNA计算已经解决的组合优化中的NP-完全问题,并简单地分析了它们的复杂性。     

非线性多目标决策的一个交互式算法

给出了一个求解多目标决策问题的新交互式算法。该算法适用于线性和非线性的情形,能保证解的非劣性,具有计算量小,交互过程简单明确且易于在计算机上实现等特点,有良好的实施前景.     

非规则RA码无码率特性分析

介绍了非规则重复累积(repeat accumulate, RA)码的构成原理,引入了编码线图进行RA码的图模型表示。详细分析了编码中的两种交织策略,并证明了其等价性。通过分析非规则RA码的奇偶校验位的生成过程,证明了非规则RA码的无码率特性。给出了不同码率情况下的系统非规则RA码在二元删除信道性能曲线。通过与LT码的比较,表明非规则RA码是逼近容量限的错误平层性能较低的无码率码。对系统非规则RA码的错误平层进行分析,并给出了降低错误平层的编码修正方法。     

Construction of protograph LDPC codes with circular generator matrices

The application of protograph low density parity check(LDPC) codes involves the encoding complexity problem.Since the generator matrices are dense,and if the positions of "1" s are irregularity,the encoder needs to store every "1" of the generator matrices by using huge chip area.In order to solve this problem,we need to design the protograph LDPC codes with circular generator matrices.A theorem concerning the circulating property of generator matrices of nonsingular protograph LDPC codes is proposed.The circulating property of generator matrix of nonsingular protograph LDPC codes can be obtained from the corresponding quasi-cyclic parity check matrix.This paper gives a scheme of constructing protograph LDPC codes with circulating generator matrices,and it reveals that the fast encoding algorithm of protograph LDPC codes has lower encoding complexity under the condition of the proposed theorem.Simulation results in additive white Gaussian noise(AWGN) channels show that the bit error rate(BER) performance of the designed codes based on the proposed theorem is much better than that of GB20600 LDPC codes and Tanner LDPC codes.     

Construction of time-frequency codes based on protograph LDPC codes in OFDM communication systems

This paper proposes a scheme to construct timefrequency codes based on protograph low density parity check (LDPC) codes in orthogonal frequency division multiplexing (OFDM) communication systems.This approach synthesizes two techniques:protograph LDPC codes and OFDM.One symbol of encoded information by protograph LDPC codes corresponds to one subcarrier,namely the length of encoded information equals to the number of subcarriers.The design of good protograph LDPC codes with short lengths is given,and the proposed protograph LDPC codes can be of fast encoding,which can reduce the encoding complexity and simplify encoder hardware implementation.The proposed approach provides a higher coding gain in the Rayleigh fading channel.The simulation results in the Rayleigh fading channel show that the bit error rate(BER) performance of the proposed time-frequency codes is as good as random LDPC-OFDM codes and is better than Tanner LDPC-OFDM codes under the condition of different fading coefficients.     

基于有限域构造的QC LDPC码编码器设计

为了降低准循环低密度奇偶校验（quasi-cyclic low-density parity-check, QC LDPC）码编码的复杂度,提出了一种利用近似满秩（approximate full rank, AFR）矩阵实现QC LDPC码的高效编码方案。基于有限域GF(q)乘群、加群构造出AFR校验矩阵,利用AFR矩阵可以快速得到其系统循环形式的生成矩阵。此方案不但可以实现线性化编码,而且编出的码都为系统码。仿真表明,该编码方案对于列重较小的QC LDPC码具有较好的通用性和实用价值。     

ON THE CONSTRUCTION OF ALGEBRAIC-GEOMETRIC CODES

1,Illtroduction'SincetheearlypapersbyG0ppa[1-31,algebralc-ge0metriccodeshavebeeninthespotlight0fcodingthe0reticresearchf0rab0uttwodecades.NumerousexcitingresultshavebeenachievedusingGoppa'sconstructi0noflinearcodesfromalgebralccurvesoverfinitefields,bothbyalgebraicge0metorsandcodingtheorists.Becauseofthedifficultyofthesubject,severalexplanatorypaPersandtextbookshaveappeared,seeforinstance[4-8].Inthispaperwepresentaquitedtherentpointofviewconcerningalgebraic-geometriccodes.Itiswellknownthataq…     

基于叠加度的有限长系统LT码编码方案

提出了一种基于叠加度的系统卢比变换(Luby transform, LT)码编码方案。与需要预编码的系统Raptor码或交织编码的准系统掺杂LT码方案不同,由掺杂度分量与弱鲁棒孤波分布进行叠加的叠加度分布,使得系统LT码的中间节点能以LT编码方式构造输出节点。理论分析了优化掺杂度分量叠加比例的系统LT码具有译码渐近性能,对给定码长k和冗余开销ε的编译码复杂度为O(k·ln(1/ε))。仿真验证了优化后的有限长系统LT码克服了系统Raptor码在信道删除概率大于0.01即出现误码平台的问题,在译码失败概率10e-4时相对于准系统掺杂LT码的所需译码冗余开销可降低12%~20%。     

Cipher quasi-chaotic code for frequency hopping communications

The chaotic frequency hopping (FH) communication systems have been presented so far. The chaotic sequences possesses good randomness and sensitive dependence on initial conditions, which is quite advantageous to run the FH codes in code-division multiple access (CDMA) systems. But the finite precision of computation and the fact of the low-dimensional chaos predicted easily cause difficulty in chaotic application. In this paper, some disadvantages associated with the conventional FH codes and the chaotic code scrambled by m-sequences are reviewed briefly. In order to overcome these drawbacks to some extents, a new higher performance FH code called cipher quasi-chaotic (CQC) code is proposed, which is generated by combining the clock-controlled stream cipher technique and chaotic dynamics. Performance analysis applying in FH communication systems of this kind of code is given. The privacy of the CQC sequence is also analyzed.