Embedding simple reversed-twin elements into self-timed reversible cellular automata

作者：Lee Jia; Huang Xin^*; Zhu Qing sheng

来源：Journal of Convergence Information Technology, 2011, 6(1): 49-54.

DOI：10.4156/jcit.vol6.issue1.6

• Asynchronous modes
• Asynchronous transition
• Asynchrony
• Cellular space
• Computing scheme
• Reversible cellular automata
• Reversible Computing
• Reversible elements
• Reversible transitions
• Self-timed

Both reversibility and asynchrony promise computing schemes with increasing energy efficiency. A pair of reversible elements (Lee, et al. 2008) with mutually reversed functionalities has been proposed, and their universality for logic circuits has been explored. In particular, they can be used to construct a reversible Turing machine in which only a single signal will run around at any time. Thus, it turns out to be able to remove the central clock from the entire circuit, i.e., these elements can work in fully asynchronous mode. The asynchrony of operations allows the elements to be efficiently implemented in a self-timed cellular automaton (STCA), a special type of asynchronous cellular automata. The previous STCA, however, is lack of local reversibility. In this paper, we propose a new STCA model that is able to construct the mutually reversal elements, based on locally reversible transition rules. As a result, the global evolution of our STCA can retain backward deterministic when embedding a reversible computer into its cellular space.

• 出版日期2011