Programmable Parallel Arithmetic in Cellular Automata Using a Particle Model.
Richard K. Squier, Kenneth Steiglitz · 1994
In this paper we show how to embed practical computation in onedimensional cellular automata using a model of computation based on collisions of moving particles. The cellular automata have small neighborhoods, and state spaces which are binary occupancy vectors. They can be fabricated in VLSI, and perhaps also in bulk media which support appropriate particle propagation and collisions. The model uses injected particles to represent both data and processors. Consequently, realizations are highly programmable, and do not have applicationspecific topology, in contrast with systolic arrays. We describe several practical calculations which can be carried out in a highly parallel way in a single cellular automaton, including addition, subtraction, multiplication, arbitrarily nested combinations of these operations, and finite-impulse-response digital filtering of a signal arriving in a continuous stream. These are all accomplished in time linear in the number of input bits, and with fixed-p...