An 0(n) Parallel Multiplier with Bit-Sequential Input and Output

Previous proposals for fast multipliers are discussed, along with a summary of the known theoretical limitations of such designs. Then, a new parallel multiplier with a very simple configuration is suggested. This multiplier operates in time 0(n), where n is the maximum of the lengths of the multiplier and multiplicand, both of which are fixed point, expressed in binary notation. It is a logical circuit consisting of 2n modules, each being only slightly more complex than a full adder; instead of three inputs and two outputs, each module has five inputs and three outputs. A logical circuit realization is given for the modules. But perhaps the most significant aspect of this design is the property that the input is required only bit-sequentially and the output is generated bit-sequentially, both at the rate of one bit per time step, least significant bit first. The advantages of such bit-sequential input and output arithmetic units are described.