基于DNA下推自动机二进制减法和乘法的实现

Implementation of Binary Subtraction and Multiplication Based on DNA Push-Down Automaton

提出了基于DNA下推自动机二进制减法和乘法的实现方法.一位二进制借位减法,是通过预先构造好的DNA下推自动机模型在一个试管中以该模型的运行方式自动完成运算.m位二进制借位减法,是在一位二进制减法的基础上,按照从低位到高位的顺序,将低位产生的借位作为高位试管操作中的输入符号串,从而完成高位的减法运算.两位二进制乘法中包含移位和加法操作,在两个试管中分别设计好DNA下推自动机模型,分别完成被乘数与乘数各位的移位操作,同时结合相应的生物操作,将其作为另一个试管加法操作中的输入符号串,则加法操作中产生的结果即为所求.在此基础上,m位二进制乘法可通过移位操作的并行性和加法操作的串行性来完成运算.这些实现方法为DNA下推自动机实现基本的算术运算提供了比较完整的运算机制.

The implementations of binary borrow bit subtraction and multiplication based on DNA push-down automata are proposed. The one bit binary subtraction can be automatically completed through the operations in one tube using the DNA push-down automata model designed in advance. Based on this model, rn bits subtraction can be obtained by putting the borrow bit from the low bit tube to the high bit tube as the input strings. The two bits binary multiplication based on DNA push-down automata model includes shift operations and addition operations, the shift operations between the string representing of the multiplicand and the strands denoting of each bit of the multiplier can be performed in two tubes synchronously combining biology operation, then the result strings are put into another tube as the input strings in the addition operation, finally the output in this operation is the solution. The m bits binary multiplication can be got by parallel shift operations and serial addition operations. These processes provide relatively complete arithmetic mechanisms for DNA automata.