Chinese Journal of Computers   Full Text
Title	Implementation of Binary Subtraction and Multiplication Based on DNA Push-Down Automaton
Authors	CHENG Zhen1) HUANG Yu-Fang1) ZHOU Kang2)
Address	1)(Research Institute of Bio-molecular Computing, Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074) 2)(Department of Mathematics and Physics, Wuhan Polytechnic University, Wuhan 430023)
Year	2009
Issue	No.12(2338—2346)
Abstract &   Background	Abstract 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, mbits 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 mbits binary multiplication can be got by parallel shift operations and serial addition operations. These processes provide relatively complete arithmetic mechanisms for DNA automata. Keywords DNA push-down automata; borrow bit subtraction; multiplication; shift operation; DNA-encoding Background This research is supported by the National Natural Science Foundation of China(grant Nos.60373089, 60674106, 60573190 and 60803113), and program for New Century Excellent Talents in University(NCET-05-0612). There are many research results based on this Foundation, such as the coding of DNA computing, the application of DNA automata in cryptography and so on. This paper is concerned to the field which is the arithmetic computation of DNA 　automata in DNA computing. The implementations of binary borrow bit subtraction and multiplication based on DNA push-down automata are proposed. These processes provide relatively complete arithmetic mechanisms for DNA automata.