Bit-sliced digit-serial multiplier

A parallel-in digit-serial-out register for words of W bits supplied as m successive digits of n-bits each, m and n being positive plural integers, and W being the integer equal to m times n, said parallel-in digit serial-out register comprising:

• an n-bit-wide output port for delivering digit-serial output signals each digit of which has n bits therein;
• a respective pipeline for each bit of said digit-serial output signals preceding said output port, said pipelines identified by consecutive ordinal numbers first through n.sup.th ;
• a plurality W in number of input ports for receiving in parallel the bits of a digit-serial word, said input ports identified by consecutive ordinal numbers first through W.sup.th in order of the significance of the bit respectively applied thereto;
• a plurality W in number of multiplexers consecutively ordinally numbered zeroeth through (W-1).sup.th having respective first input connections to the input port similarly ordinally numbered, having respective second input connections, and having respective output connections, each said multiplexer having between the second input connection and the output connection thereof a respective selective path which is included in the pipeline having the same ordinal number modulo n that that one of said multiplexers has, the multiplexers thus included in each pipeline being arranged in order of ordinal number between the beginning end and the output port end of that pipeline;
• a number W of latches, m latches of which are included in each pipelined with one of the m latches being included at one end of said pipeline and the other of the m latches respectively connecting the output connection of each said multiplexer included in that pipeline to the second input connection of the following said multiplexer included in that pipeline;
• means for clocking in parallel once a clock interval said latches in said number W thereof;
• means for controlling said multiplexers to discontinue the selective paths therewithin only during selected clock intervals separated by at least (m-1) intervening clock intervals, and to provide instead during said selected clock intervals selective paths from the first input connections of said multiplexers to their output connections respectively;
• and
• means for arranging said multiplexers to be in respective iterations of an iterative monolithic integrated-circuit structure, including
• a braiding of said pipelines from latch to latch.

A digit multiplier for multiplying together two digit-serial operands, one a multiplicand W bits in length and the other a multiplier mn bits in length, each digit in said operands being n bits in length, m being a positive integer and n being a positive plural integer that is a submultiple of W, said digital multiplier comprising:

• a plurality n times W in number of multiplying circuits each having respective first and second single-bit-wide input ports and having a respective single-bit-wide output port, said plurality of multiplying circuits being grouped into n groups respectively identified by consecutive ordinal row numbers first through n.sup.th, each of which groups consists of a respective number W of multiplying circuits respectively identified by consecutive ordinal column numbers first through W.sup.th, whereby a respective one of said multiplying circuits is uniquely identified by each pair of row and column numbers;
• a plurality, n in number, of row busses respectively identified by consecutive ordinal row numbers first through n.sup.th, each row bus connecting to the first input ports of those of said multiplying circuits in the one of said n groups identified by the same ordinal row number as that row bus;
• a plurality, W in number, of column busses respectively identified by consecutive ordinal column numbers first through W.sup.th, each column bus connecting to the second input ports of those of said multiplying circuits identified by the same ordinal column number as that column bus;
• a plurality, n times W in number, of adders being grouped into n groups, respectively identified by consecutive ordinal row numbers first through n.sup.th, each of which groups consists of a respective number W of adders respectively identified by consecutive ordinal column numbers first through W.sup.th, whereby a respective one of said adders is uniquely identified by each pair of row and column numbers, each said adder having a respective first input port to which connects the output port of said multiplying circuit identified by the same pair of row and column numbers, each said adder having a respective second input port, each said adder except each identified by first column number having a respective third input port, each said adder having first and second output ports for supplying a carry bit portion and a sum bit portion respectively of a two-bit full sum of bits received at its input ports, the first output port of each said adder identified by a row number other than n.sup.th connecting to the second input port of said adder identified by the same column number and a row number one higher, the second output port of each said adder identified both by a row number other than n.sup.th and by a column number other than W.sup.th connecting to the third input of said adder identified by the next higher row and column numbers;
• means for providing a minor product output signal in digit-serial form from the second output ports of said adders identified by W.sup.th column number;
• and
• means for providing a major product output signal in digit-serial form;
• which means includes:
• a first parallel-in/digit-serial-out register having W successive stages loaded in parallel during the last of said second series of clock intervals with carry bits from the first output ports of said adders identified by said n.sup.th row number and by each of said column numbers;
• means for shifting the contents of said first parallel-in/digit-serial-out register one stage towards an output port thereof during each succeeding clock interval of a third series of clock intervals following said second series of clock intervals;
• a second parallel-in/digit-serial-out register having n successive stages loaded in parallel during the last of said second series of clock intervals with sum bits from the second output ports of said adders identified by said n.sup.th row number and by each of said column numbers;
• means for shifting the contents of said second parallel-in/digit-serial-out register one stage towards an output port thereof during each succeeding clock interval of said third series of clock intervals;
• means for delaying the shifted carry portions one clock interval respective to the shifted sum portions;
• and
• a digit-serial adder for adding the delayed shifted carry bits to the shifted sum bits to generate said major product output signal in digit-serial form.

A method of performing digit-serial multiplication of a multiplicand signal by a multiplier signal, by iteratively using a combinational array multiplier composed of (1) a plurality of multiplier cells connected in an n successive row by W successive columns array, for generating a minor product n bits at a time from the column of said array receiving the least significant bit of said multiplicand signal, and for generating W uncombined sum bits and W uncombined carry bits of different weights defining a major product which are supplied from the row of said array receiving the most significant bit of said multiplier signal, each multiplier cell including a respective digital multiplier and subsequent adder, and (2) means for generating a major product by combining the uncombined sum and carry bits of different weights defining it, as supplied from the row of said array receiving the most significant bit of said multiplier signal, n being a plural positive integer and W being a positive multiple thereof, said method comprising the steps of:

• applying the W bits of a multiplicand signal in parallel to respective ones of said columns of multiplier cells in said combinational array multiplier, thereby to supply multiplicand bits to the digital multipliers in said multiplier cells;
• applying the mn bits of a multiplier signal, in m successive digits of n bits applied in parallel to respective ones of said rows of multiplier cells in said combinational multiplier, thereby to supply multiplier bits to the digital multipliers in said multiplier cells, m being a positive plural integer;
• applying during the first (m-1) digits of said multiplier signal the uncombined bits of said major product with appropriate bit place shifts as carries to said adders in the row of said array receiving the least significant bit of said multiplier signal, thereby continuing multiplication to extend said minor product to m digits of n bits width;
• and
• after the m.sup.th digit of said multiplier signal, generating said major product by combining the uncombined sum and carry bits of different weights defining it, as supplied from the row of said array receiving the most significant bit of said multiplier signal.