Programmable Parallel Arithmetic in Cellular Automata Using a Particle Model
Richard K. Squier
Computer Science Department, Georgetown University,
Washington, DC 20057, USA
Ken Steiglitz
Computer Science Department, Princeton University,
Princeton, NJ 08544, USA
Abstract
In this paper we show how to embed practical computation in one-dimensional cellular automata using a model of computation based on collisions of moving particles. The cellular automata have small neighborhoods, and state spaces that are binary occupancy vectors. They can be fabricated in VLSI, and perhaps also in bulk media that 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 application-specific topology, in contrast to systolic arrays. We describe several practical calculations that 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-point arithmetic of arbitrary precision, independent of the hardware.