基于DNA计算的分子下推自动机

DNA分子计算的工作原理是对生物系统进行编码,以生物化学反应为基础,利用生物技术实现生物系统的状态转移来推进计算过程．2001年以色列的Yaakov Benenson等人在基于DNA计算的发卡模型实现了具有状态转移功能的分子有限状态自动机,国内则有利用DNA计算的方法构造可编程分子下推存储器的相关研究．该存储器基于分子自动机的原理,能按一定逻辑进行自组装,是一种纳米尺度的生物存储机构．文中首先通过在分子有限自动机上扩展一个分子下推存储器从而获得了一种简单的分子下推自动机,并基于该下推自动机提出了一类语言的分子自动机解法．接着提出了两种改进的分子下推自动机的模型,通过增加模型复杂度,分别解决了基本型分子下推自动机存在输人字符串限制和输入分子形式不统一的问题．计算理论表明,该种下推自动机的计算能力超过了已有的有限自动机．     

基于DNA自动机的串行二进制进位加法的实现

提出了一种基于DNA自动机的串行二进制进位加法的实现方法。对于一位二进制的进位加法,通过预先设计的DNA自动机模型在一个试管中以自动机的方式完成。对于”位二进制的进位加法,通过将n个类似的试管按照从低位到高位的顺序组成串行网络;将低位加法操作产生的进位转移到高位试管,组成高位自动机的输入符号串,完成高位的加法操作。这种运算方式类似于电子计算机中加法运算系统,为DNA计算机实现算术运算提供了一种新颖的方法。     

一个基于下推自动机的Web测试自动执行器

随着Web应用系统的广泛应用，对其质量要求也越来越高。如何进行有效的测试以保证Web应用系统的质量是值得关注的研究问题。支持测试用例自动执行的测试执行器（Test runner）是其中的一个热点和难点。文章研究并提出了基于下推自动机的Web测试自动执行器，并实现了其原型系统。谊执行器支持测试用例的自动执行并给出测试结果报告，并通过Web应用测试实例验证了其有效性。     

下推自动机的状态转换图与下推自动机的化简

参照有限状态自动机图形表示方式的思想方法,研究了标准下推自动机的图形表示——PAD 状态转换图,证明了下推自动机与标准下推自动机的等价性。给出了对标准下推自动机进行化简的原则,并给出了化简算法,实现了下推自动机的化简。     

人工免疫系统中淋巴细胞的下推自动机模型

有些淋巴细胞的构造模型,如r-邻域位线性构造模型,识别能力不够强,尤其对正则表达式缺乏识别能力。该文以下推自动机模型为原理,提出了一种自动机模型的淋巴细胞,这种淋巴细胞具有比有限自动机更强的识别能力,同时利用相近的入侵具有相似性这一点,引进了一个经验队列,配合HMM中状态转移概率的概念,对状态转移进行评判。最后给出了模型具体的设计方案。     

基于下推自动机的细粒度锁自动重构方法

针对粗粒度锁会严重影响并发程序的可伸缩性问题,提出一种面向细粒度锁的自动重构方法.该方法借助访问者模式分析、别名分析、负面效应分析等多种程序分析技术获取临界区代码的读写模式,然后使用下推自动机构建不同锁模式的识别方法,根据识别结果进行代码重构.与以往锁重构方法的不同之处在于,该方法考虑了锁降级模式,使重构适用性更广.基于此方法,在Eclipse JDT框架下,以插件的形式实现了自动重构工具FLock.在实验中,从重构个数、改变的代码行数、重构时间、准确性和重构后程序性能等方面对FLock进行了评估,并与已有的重构工具Relocker和CLOCK进行了对比.对HSQLDB,Jenkins和Cassandra等11个大型实际应用程序的重构结果表明：FLock共重构了1 757个内置监视器对象,每个程序重构平均用时17.5s.该重构工具可以有效地实现粗粒度锁到细粒度锁的转换,与手动重构相比,有效提升了细粒度锁的重构效率.     

基于下推自动机的XML数据流递归查询研究

针对具有子孙轴(//)和谓词([])结构特征的XPath对具有不同递归深度的XML数据流进行递归查询处理问题,提出了基于下推自动机技术的处理方法,通过将XPath各类置步转化成相对应的处理模块,由算法将各类处理模块组合起来,建立了自上而下的树状查询模型.由于查询过程中将会发生多重匹配,从而会产生大量的匹配模式,该模型通过有效的匹配策略和缓存操作,对匹配模式进行保存及检验,成功地实现XML数据流递归查询.实验结果表明,该算法在性能上要优于传统方法.     

基于量子逻辑的下推自动机的代数刻画

首先,本文提出量子下推自动机（简记为L-VPDA）的概念,从代数角度出发详细研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用量子状态构造证明了任意L-VPDA与状态转移为经典函数且具有量子终状态的L-VPDA间的相互等价性;其次详细研究了量子上下文无关语言的代数刻画以及对于正则运算的封闭性。     

基于量子逻辑的下推自动机与上下文无关文法

给出基于量子逻辑的下推自动机(e-VPDA)的概念,提出广义的子集构造方法,进而证明了一般的e-VPDA与状态转移为分明函数且具有量子终态的e-VPDA的等价性.利用此等价性,给出了量子上下文无关语言的代数刻画与层次刻画,并籍此证明了量子上下文无关语言关于正则运算的封闭性.最后,说明了量子下推自动机和量子上下文无关文法(e-VCFG)的等价性.     

一种基于优先级扩展的时间自动机模型中DBM减法算法的改进

本文介绍一种具有优先级扩展的时间自动机模型,并对一种计算DBM减法算法进行改进。这种减法是DBM上操作中的一种,它会产生需要用DBM集来表示的非凸集合。DBM的数量影响符号模型检测的性能,我们的减法算法是有效的,因为它产生的DBM的数量相对于最初算法具有较大程度的约减。DBM减法操作扩展了具有优先级的时间自动机理论,它对对于具有紧急行为的变换描述、死锁检测、时间博弈等问题具有非常重要的作用。     

基于N进制的DNA并行加法与乘法模型

现有DNA数值计算模型大多在二进制基础上进行计算,通用性不强。针对该问题,设计基于N进制的DNA自装配并行加法与乘法模型。在Labean模型的基础上,加法模型通过改进库分子的编码方式将DNA算法的时间复杂度降为O(1),空间复杂度降为O(n);乘法模型在解决一位数连加问题后,转换为相应的加法模型进行计算。实验结果表明,该并行模型编码简单,具有较低的时间复杂度和空间复杂度。     

二元有限域正规基乘法矩阵快速算法研究与实现

通过对二元有限域上一般正规基乘法矩阵的计算：亨法进行深入分析,利用二元域的特性设计了一种便于计算机实现的快速计算二元有限域上一般正规基乘法矩阵的算法,并且针对该算法的时间及空间复杂度进行了分析。     

椭圆曲线窗口标量乘法的研究与Delphi实现

椭圆曲线加密算法是一种非常流行的方法,影响椭圆曲线算法执行效率的因素有很多,标量乘法就是一个重要因素,椭圆曲线标量乘法的方法很多,文中主要研究了NAF和NAFw的基本原理和算法,最后在VB环境下实现了椭圆曲线窗口标量乘法。     

基于改进谱减方法的语音增强研究

由于噪声的影响导致语音信号的质量降低,因此需要对语音信号进行语音增强。语音增强是语音信号处理的前沿领域,其主要目标足从带噪语音中提取纯净的原始语音信号。介绍了实现语音增强方法的原理,利用实验仿真了传统谱减法和改进谱减方法,改进法通过对带噪信号进行参数调整,然后进行频域谱减,实验结果表明改进方法对语音增强效果明显好于传统方法。此外,对传统谱减法和改进谱减法的信噪比分别进行了计算,结果表明改进谱减方法的信噪比相对传统谱减方法有很大提高。     

Design of Montgomery Multiplication Architecture Based on Programmable Cellular Automata

This study presents a Montgomery multiplication architecture that uses an irreducible all one polynomial (AOP) in GF(2 ^m ) based on a programmable cellular automata (PCA). The proposed architecture has the advantage of high regularity and a reduced latency based on combining the characteristics of the irreducible AOP and PCA. The proposed architecture can be used to implement modular exponentiation, division, and inversion architectures.     

GPU 上的矩阵乘法的设计与实现

矩阵乘法是科学计算中最基本的操作,高效实现矩阵乘法可以加速许多应用。本文使用NVIDIA的CUDA在GPU上实现了一个高效的矩阵乘法。测试结果表明,在Geforce GTX260上,本文提出的矩阵乘法的速度是理论峰值的97％,跟CUBLAS库中的矩阵乘法相当。     

基于双基数的快速标量乘算法

标量乘法是整个椭圆曲线密码体制实现的瓶颈,本文在有效表示标量k方面,引用一个新的数域系统--双基数系统,将标量的双基数链长度限制在O(log k/log log k)范围内,减少标量乘法中的上层运算.在底层域快速算法研究方面,推导出直接计算3kP快速算法.最后结合直接计算2kP,2P±Q,3P±Q及3kP快速算法.给出基于双基数的快速标量乘新算法,新算法的效率优于Dimitrov算法及传统标量乘算法.     

基于进位预估快速模乘方法

研究基于进位预估的大整数模乘运算快速实现方法并应用于FastMM模乘算法的加速。与原算法相比,采用交叉乘和进位预估加速结合方式,理论上最多可以节省33％的字乘操作;在实际应用中,192位椭圆曲线公钥密码系统速度性能与改进前相比提高15％～18％。进位预估方法还可以应用与其它需要截断中间乘积的场合,可以高效实现流行的公钥密码系统。     

基于FPGA自主控制浮点加减乘除控制器设计

为实现一种多浮点操作数乘法运算的自主运算控制器,提出了一种基于FPGA并行操作的硬连接电路的多浮点数乘法运算控制器及其时序控制的方法,该控制器对一条多浮点操作数乘法运算指令的命令字和多浮点操作数连续写入并存储,在内部时序脉冲作用下,可以自主完成读出浮点操作数执行乘法运算,写入存储多浮点操作数过程与执行乘法运算命令的过程能够并行进行;在控制器执行乘法运算命令过程中,系统可以读出执行命令过程中的中间结果和最终运算结果;论述了该控制器的电路构成和基本原理,分析命令字与多操作数在内部时序脉冲作用下的执行过程,应用Verilog HDL语言实现相关硬件的构建和连接;设计完成后通过仿真测试可知,该控制器运行的最高频率为250MHz,从输入到输出端口最小延时是3.185ns,最大延时是15.336ns,且能够自主完成浮点数乘法运算。