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

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

基于DNA粘附子模型的并行乘法算法

提出了一种基于DNA计算的粘附子模型的并行乘法算法,该算法首先将两个二进制数相乘转变成根据被乘数对乘数进行一系列的移位相加。将被乘数与乘数编码在同一条存储链上,通过组合、分离、设置、清除等四种运算计算出积的值。由于表示输出的DNA链的结构与表示输入的DNA链的结构相同,因此表示输出的DNA链无需做任何改变,就能在后面的运算中重复使用。该算法不仅能用于整数乘法中,还可以很方便地推广到包含小数的乘法运算及多个因数参与的乘法运算中。该算法的突出优点是充分发挥了DNA计算内在的并行计算性,如果参与乘法运算的因数的个数相等,则计算多组乘法运算与计算一组乘法运算所需的时间相同,并且多组乘法运算能从同一个试管内开始。     

基于DNA计算的分子下推自动机(英文)

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

高速乘法器

乘法是日常生活中经常遇到的一种算术运算。用计算机实现乘法运算的最简单的方法是加和移位算法,除了数据格式是用二进制表示以外,它和普通的笔算非常类似。图1示出了一个8×8乘法的例子。每一位乘数,都产生一个部分积,然后相加。对计算机来说每得一部分积就要进行一次加法和一次移位操作。对n×n位乘法,则需n次加和移位操作。实际上,在通用计算机上用软件实现乘法还要复杂些,速度甚慢。以Intel 8080微处理器为例,调用一次乘法子程序,完成一个8×8乘法运算,约需250～300μs时间。对于许多科学计算和实时数字信号处理,这是远远不能满足要求的。例如在矩阵运算、数字滤波和FFT(快速付     

一种乘同余伪随机序列快速实现的FPGA设计

针对一类乘同余运算,提出了一种快速算法。采用1个32位乘法、2个32位加法、少量移位操作和1个最高位分离操作方法,避免了连续减法和除法运算。采用硬件语言设计了快速算法。在此算法的基础上,设计了基于FPGA的伪随机序列发生器。     

基于量子傅里叶变换算法的量子乘法器

乘法运算是许多量子算法中的基本运算之一。为了实现量子乘法运算并且尽可能少地使用辅助量子比特,提出了一种基于量子傅里叶变换算法的量子乘法器。在量子傅里叶加法电路基础上,设计了量子移位电路,并实现了两个n位二进制无符号数相乘的量子电路,其时间复杂度为O（n³）。使用IBM提供的开源量子计算工具包Qiskit分别验证了两个2位二进制数相乘,以及一个2位二进制数与另一个4位二进制数进行量子乘法运算的正确性。实验结果表明,所设计的量子乘法器使用较少的量子比特数目实现了较高的准确率和较低的计算复杂度。该量子乘法器代码已开源。     

说名词解术语—CPU篇（3）

CPU的工作就是处理存储在存储器中的信息。一般信息是按字节存储的,也就是以8位二进制数或8比特为1个存储单元,这些信息可以是数据或指令。数据是用二进制表示的字符、数字或颜色等等。而指令告诉CPU对数据执行哪些操作,比如完成加法、减法或移位运算。通过下列这些名词、术语,让大家更好地了解CPU各     

基于DNA序列的彩色图像加密算法

结合混沌系统和DNA密码学,提出了一种基于DNA序列的彩色图像加密算法。该算法应用了DNA序列的加法、减法、异或运算,并且把彩色图像分解为位平面进行处理。首先对彩色图像位平面分解、DNA编码;然后对DNA平面置乱、DNA加法运算、DNA异或运算;最后进行DNA解码、位平面合并,得到密文图像。实验结果表明,原始图像加密后的图像类似噪声,加密后的直方图变得更平滑,对密钥有很高的敏感性,密文图像的随机性好,密文图像相邻像素之间相关性低。     

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

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

基于DNA计算自组装模型的Diffie-Hellman算法破译(英文)

DNA自组装计算模型是近年来引人关注的计算模型,已有基于自组装模型的二进制加法、乘法以及有限域中的加法和乘法的讨论．文中利用DNA自组装模型设计的模乘系统,实现了素数P的本原根g连续乘方后模p的数的排列,从而可以在线性时间内求解离散对数,为破译Diffie—Hellman密钥交换算法提供了新的生物方法．该模乘系统使用了Θ（p）种自组装类型,组装的时间复杂度为Θ（p-1）．系统最后组装结果提取出报告链后,经过PCR和凝胶电泳读取离散对数结果．该模型扩展了DNA自组装计算模型的应用,为求取离散对数提供了新思路．     

Integer Representation and Counting in the Bit Probe Model

We examine the problem of integer representation in a nearly minimal number of bits so that the increment and the decrement (and indeed the addition and the subtraction) operations can be performed using few bit inspections and fewer bit changes. The model of computation we considered is the bit probe model, where the complexity measure counts only the bitwise accesses to the data structure. We present several efficient data structures to represent integer that use a logarithmic number of bit inspections and a constant number of bit changes per operation. The most space-efficient data structure uses only one extra bit. We also present an extension to our data structure to support efficient addition and subtraction, where the larger value is replaced by the result, while retaining the same asymptotic bounds for the increment and the decrement operations.     

DNA计算机算术运算的自装配模型（I）—加法

DNA计算是基于DNA分子生化反应,能够在DNA计算机上实现的算法。它具有高度并行性、容量大、速度快等特点。同传统电子计算机一样,它也是以加、减、乘、除等简单算术运算和异或等逻辑运算为基本运算单元。在Labean加法的基础上,设计了通用的N进制的并行加法DNA自装配模型,算法的时间复杂度为O（1）,空间复杂度为O（n）。在此基础上又设计了一位数连加的DNA自装配模型,为今后的并行乘法奠定了基础。算法的主要优点在于编码简单、效率高,且具有通用性。     

Pollard p-1因子分解的DNA计算机算法

如何有效地对大整数进行因子分解是数学上的一个难题.给出了基于分子生物技术的因子分解问题的DNA计算机算法.算法以Pollard p-1算法为基础,利用DNA分子生物操作完成加、减、乘、除运算,实现平方-乘以及欧几里德算法,产生并得到最终解.基于分子生物学的实验表明,该算法是可行和有效的.     

金字塔结构逻辑运用二值脉冲对简单图形处理

本文根据元胞自动机模型划分方法, 将二维图像分解为2×2矩阵单元结构. 提出了几种逻辑运算式, 用以分类由黑白二值点构成的2×2矩阵图形. 通过CNN神经网络的多层结构形式, 分析了金字塔结构逻辑在相似的组合形式下, 对二值图形边缘检测和池化的功能. 通过同步脉冲形式能将灰度图像, 分解为多个时间维度的二值图形, 方便多层金字塔逻辑运算处理. 分析了如何采用延时继电器使金字塔结构逻辑具有记忆的特性. 讨论了3×3输入金字塔模型, 在不规律脉冲情况下, 通过逻辑运算对线性交点检测的可能.     

The Complexity of a Pipelined Algorithm for Remainder Computing in a Given Modulo

A pipelined algorithm for computing the remainder when dividing an arbitrary binary number of a given bit capacity (numerator) by a certain constant value (a constant) is proposed. The algorithm is based on the same types of operations of comparisons and addition–subtraction of partial remainders upon division by this constant. Depending on whether an intermediate result during computation of the remainder is positive or negative, addition with the value of the intermediate result or subtraction from it of the remainder upon division of a given power of two occur. The number of algorithm stages compared with the model is known in advance and depends on the bit capacities of both the dividend and constants. The estimates of the time complexity of the proposed pipelined algorithm are determined by the maximum delay time of operation of the pipeline stage. The estimates of the hardware complexity of the proposed algorithm, as well as the model of the device that implements the algorithm, are determined at the abstract and structural levels.     

利用剩余数制简化DNA算术运算

在DNA算术运算的理论模型中,普遍应用固定基数制,比如二进制、三进制。但是由于受到进位的影响,难以实现并行运算。基于Adleman-Lipton模型,分析了剩余数制的基本原理,改进了整数的DNA链表示,并将其应用于DNA算术运算,给出了剩余数制下进行DNA算术运算的算法模型。由于在剩余数制中,算术运算(加、减、乘)在剩余位之间无须进行进位计算,故可以降低运算过程的复杂度,而且有利于进行各个剩余位上的并行计算。     

DNA计算机算术运算的自装配模型（II）—乘法

DNA计算机与传统电子计算机相比具有高度并行性、容量大、速度快等特点。它也是以加、减、乘、除等简单算术运算和异或等逻辑运算为基本运算单元。在自装配加法的基础上,设计了DNA自装配乘法模型,算法的时间复杂度为[O(1)],空间复杂度为[O(n)],并给出实例验证了算法的有效性。该算法具有编码简单、效率高、通用性强等优点。     

Improved DNA-sticker arithmetic: tube-encoded-carry, Logarithmic Number System and Monte-Carlo methods

The sticker model of computation, implemented using robotic processing of DNA, manipulates in parallel many bitstrings, called strands, that are contained in a limited number of tubes. Prior sticker arithmetic algorithms, patterned on digital-electronics, generate carry bits in the strand, either wasting bits or using a clear operation (with problematic biochemical implementation). The novel addition algorithm here does not need to record the carry. Instead, which tube holds a particular strand implicitly encodes the carry. The speed and number of tubes are half that of prior approaches. Further encoding data in the Logarithmic Number System (LNS) allows such integer operations to perform cost-effective real multiplications, divisions and roots. An example LNS Euclidian norm is more efficient than prior methods, assuming perfect operations. Unfortunately, DNA-stickers are unreliable. This paper uses sticker unreliability as a source of randomness to implement Monte-Carlo (MC) arithmetic (previously fabricated in silicon at the cost of pseudo-random generators). With stickers, the randomness is free. MC engineering mimics natural systems using unreliable but redundant components. Here, MC randomness is only useful in low-order bits. Multiple re-testing of the same bit (“refinement”) trades improved reliability for slower operation using more tubes. Simulations (with different sizes, probabilities and refinement) show that increasing refinement as a function of bit position allows imperfect implementations to achieve suitable MC strand-error distributions, predicting 1000x speed-mass advantage of sticker-MCLNS over conventional supercomputers.     

Partition Algorithm For Parallel Processing Of Array Multiplication In Gf(2m) Fields

The multiplication operations in GF(2m) fields are widely used in cryptosystems. However, the multiplication operations for public-key cryptosystems require very large operands with 512 bits or more, and then existing multipliers are not available for such multiplications. In this paper, we will present a partition algorithm to divide large operands into small operands such as 32 bits or 64 bits, and then existing multipliers can be employed. We also present a parallel version of the partition algorithm by employing an important natural property of the multiplication operations in GF(2m) fields.