Efficient Circuit Construction in Brownian Cellular Automata Based on a New Building-Block for Delay-Insensitive Circuits

摘要

A Brownian cellular automaton (BCA)(Lee & Peper, 2008) is an asynchronous cellular automaton, where configurations represent-ing signals propagate randomly in the cellular space, resembling particles under Brownian motion. Depending on merely three kinds of local tran-sition rules, this BCA model can be used to construct all primitives in an universal set of delay-insensitive circuit elements, such that all well-known logic circuits can be realized in the cellular space. Though Brownian-like movements of signals enable spontaneous searching for so-lutions through the state space of computation, their diffusive behavior may induce substantial overhead in the operation of the circuits. In this paper, we propose a novel kind of primitive element that can be employed as a new building-block for the delay-insensitive circuits. Moreover, con-struction of this new element in the BCA can utilize the spontaneous fluctuations of signals more effectively, while at the same time restricts the Brownian behavior into possibly smaller configurations as compared to the construction of the previous elements, thus will improve the effi-ciency of the realized logic circuits in the BCA.