A One-Dimensional Real-Time Iterative Multiplier

The class of one-dimensional, real-time, iterative, discrete-state automata is described. By example, it is shown that serial multiplication can be carried out by such a sequential switching network. Each of two arbitrarily large integers is represented in binary notation by a time sequence of digits 0 or 1, the lowest order digits first. A design is given for a discrete-state machine that has as input the two time sequences of binary digits and as output a single sequence of binary digits, which is the product of the two input integers, lowest-order digit first. The multiplier is constrained to be a linear array of identical cells. The cells each have a finite number of states and each cell communicates directly only with the adjacent cells, such communications occurring in a synchronous manner. The multiplication is performed in real time; that is, the delay between the receipt of the nth digits of the input and the generation of the nth digit of the output is a fixed number of periods of the synchronizing clock. A design with no time delay is described.