Programmable Parallel Arithmetic in Cellular Automata Using a Particle Model

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 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
application-specific 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-point
arithmetic of arbitrary precision, independent of the hardware.

This technical report has been published as

Programmable Parallel Arithmetic in Cellular Automata Using a
Particle Model.
Richard K. Squier and Kenneth Steiglitz, Complex Systems,
8, pp. 311-323, 1994.