Apparatus and method for serial-parallel binary multiplication

Claim 2

A serial-parallel binary multiplier comprising: a parallel adder arranged to receive at one set of inputs the successive products, in ascending order of significance, of a multiplier and one bit of a multiplicand and to receive at a second set of inputs the delayed next more significant sum bit produced by said adder, delayed by a single bit interval of the multiplicand bit delivery sequence by operation of delay means, the carry output of said adder being regarded as the most significant sum bit produced by said adder; a parallel input series output shift register with input loading gate means adapted to be enabled during a loading pulse, said shift register being arranged to have its cells loaded by the respective sum bits (including said carry output but not necessarily including the least significant sum bit) of said adder, with said sum bits being loaded so that the order of significance of said sum bits corresponds to the order of serial output delay of the cells into which said bits are loaded, and control means, including timing means, for providing said loading pulse just prior to end of the bit interval of the highest significance bit of said multiplicand, for clearing said delay means just after the end of said bit interval and for providing further sequential operations of said adder and said shift register thereafter, regardless of whether another multiplicand is immediately thereafter presented to said adder.

Claim 3

A serial-parallel binary multiplier comprising: parallel adder means having a first (Ei) and a second (Fi) set of data inputs, a set of outputs ( Sigma i), and a carry output (Ck); gate means (1, 2 . . . k) arranged to supply, to said first set (Ei) of inputs of said adder means, the product of a multiplier and one bit of a multiplicand; means for supplying the bits of said multiplier in parallel and the bits of said multiplicand sequentially in ascending order of significance to said gate means; timing means for timing the sequential supplying of said multiplicand bits and timing successive operations of said adder means and components connected thereto as herein specified at a rate no greater than the maximum operating rate of said adder means; a set of flipflops (61, 62 . . . 68, 69) arranged to provide a one bit delay between an input and an output of each flipflop, one of said flipflops (69) having its said input connected to said carry output (Ck) of said adder means and its said output connected to the highest significance input (Fk) of said second set of inputs (Fi) of said adder means, and the remaining flipflops of said set (68 . . . 62, 61) having their said outputs connected to an input of said second set of inputs (Fi) of said adder means of one order of significance less than that of the product output connected to the input of the same flipflop, said flipflops also having an input for restoring a predetermined initial condition upon receipt of a clearing pulse; and control means associated with said timing means for applying said clearing pulse promptly after the close of the bit interval from which the most significant bit of said multiplicand is supplied to said gate means, whereby a sequential product output is available at the sum output related to the least significant bit inputs and a parallel output limited to k + 1 bits is available during the aforesaid bit interval at the outputs of said adder means ( Sigma i and Ck).

Claim 4

A serial-parallel binary multiplier comprising: parallel adder means having a first (Ei) and a second (Fi) set of data inputs, a set of outputs ( Sigma i), and a carry output (Ck); gate means (1, 2 . . . k) arranged to supply, to said first set (Ei) of inputs of said adder means, the product of a multiplier and one bit of a multiplicand; means for supplying the bits of said multiplier in parallel and the bits of said multiplicand sequentially in ascending order of significance to said gate means; timing means for timing the sequential supplying of said multiplicand bits and timing successive operations of said adder means and components connected thereto as herein specified at a rate no greater than the maximum operating rate of said adder means; a set of flipflops (61, 62 . . . 68, 69) arranged to provide a one bit delay between an input and an output of each flipflop, one of said flipflops (69) having its said input connected to said carry output (Ck) of said adder means and its said output connected to the highest significance input (Fk) of said second set of inputs (Fi) of said adder means, and the remaining flipflops of said set (68 . . . 62, 61) having their said outputs connected to an input of said second set of inputs (Fi) of said adder means of one order of significance less than that of the product output connected to the input of the same flipflop, said flipflops also having an input for restoring a predetermined initial condition upon receipt of a clearing pulse; and control means associated with said timing means for applying said clearing pulse promptly after the close of the bit interval from which the most significant bit of said multiplicand is supplied to said gate means, whereby a sequential product output is available at the sum output related to the least significant bit inputs and a parallel output limited to k + 1 bits is available during the aforesaid bit interval at the outputs of said adder means ( Sigma i and Ck).

Claim 5

A serial-parallel binary multiplier as defined in claim 2 in which said controL means is arranged to supply a rounding signal to a carry input of said adder means adapted to add effectively half of the value of the least significant bit position of a parallel output provided by said adder means.

Claim 6

A serial-parallel binary multiplier comprising: parallel adder means having a first (Ei) and a second (Fi) set of data inputs, a set of outputs ( Sigma i), and a carry output (Ck); first gate means (1, 2 . . . k) arranged to supply, to said first set (Ei) of inputs of said adder means, the product of a multiplier and one bit of a multiplicand; means for supplying the bits of said multiplier in parallel and the bits of said multiplicand sequentially in ascending order of significance to said gate means; timing means for timing the sequential supplying of said multiplicand bits and timing operations of said adder means and components connected thereto as herein specified at a rate no greater than the maximum operating rate of said adder means; a set of flipflops (61, 62 . . . 68, 69) arranged to provide a one bit delay between an input and an output of each flipflop, one of said flipflops (69) having its said input connected to said carry output (Ck) of said adder and its said output connected to the highest significance input (Fk) of said second set of inputs (Fi) of said adder means, and the remaining flipflops of said set (68 . . . 62, 61) having their said respective inputs connected to an output other than the least significant output of said set of outputs (Ei) of said adder and their said respective outputs connected to an input of said second set of inputs (Fi) of said adder means of one order of significance less than that of the product output connected to the input of the same flipflop, said flipflops also having an input for restoring a predetermined initial condition upon receipt of clearing pulse; a parallel in series out shift register provided with a second gate means (92, 93 . . . 99, 100) for its parallel inputs adapted to be enabled during application of a loading pulse, said parallel inputs being connected through said gate means so that the cell (Gk) of said shift register the parallel loaded content of which is last to be discharged through the serial output is connected to said carry output (Ck) of said adder means and the remainder, in descending order of output delay, are connected respectively to the set of outputs ( Sigma i), not necessarily including the least significant, of said adder means in descending order of significance; and control means for applying said loading pulse to said second gate means after the most significant bit of said multiplicand has been effectively entered into said first gate means and prior to the next step of said timing means and for applying said clearing pulse to said flipflops promptly after said last mentioned step of said timing means and leaving time for said flipflops to be operated by said adder means prior to the next subsequent step of said timing means.

Claim 7

A serial-parallel binary multiplier comprising: parallel adder means having a first (Ei) and a second (Fi) set of data inputs, a set of outputs ( Sigma i), and a carry output (Ck); first gate means (1, 2 . . . k) arranged to supply, to said first set (Ei) of inputs of said adder means, the product of a multiplier and one bit of a multiplicand; means for supplying the bits of said multiplier in parallel and the bits of said multiplicand sequentially in ascending order of significance to said gate means; timing means for timing the sequential supplying of said multiplicand bits and timing operations of said adder means and components connected thereto as herein specified at a rate no greater than the maximum operating rate of said adder means; a set of flipflops (61, 62 . . . 68, 69) arranged to provide a one bit delay between an input and an output of each flipflop, one of said flipflops (69) having its said input connected to said carry output (Ck) of said adder and its said output connected to the highest significance input (Fk) of said second set of inputs (Fi) of said adder means, and the remaining flipflops of said set (68 . . . 62, 61) having their said respective inputs connected to an output other than the least significant output of said set of outputs (Ei) of said adder and their said respective outputs connected to an input of said second set of inputs (Fi) of said adder means of one order of significance less than that of the product output connected to the input of the same flipflop, said flipflops also having an input for restoring a predetermined initial condition upon receipt of clearing pulse; a parallel in series out shift register provided with a second gate means (92, 93 . . . 99, 100) for its parallel inputs adapted to be enabled during application of a loading pulse, said parallel inputs being connected through said gate means so that the cell (Gk) of said shift register the parallel loaded content of which is last to be discharged through the serial output is connected to said carry output (Ck) of said adder means and the remainder, in descending order of output delay, are connected respectively to the set of outputs ( Sigma i), not necessarily including the least significant, of said adder means in descending order of significance; and control means for applying said loading pulse to said second gate means after the most significant bit of said multiplicand has been effectively entered into said first gate means and prior to the next step of said timing means and for applying said clearing pulse to said flipflops promptly after said last mentioned step of said timing means and leaving time for said flipflops to be operated by said adder means prior to the next subsequent step of said timing means.

Claim 8

A serial-parallel binary multiplier as defined in claim 4 in which the least significant output of said set of outputs ( Sigma i) of said adder means is not connected to said second gate means and in which means are provided for obtaining output pulses selected from said least significant output and from the series output of said shift register.

Claim 9

A serial-parallel binary multiplier as defined in claim 5 in which means are provided for obtaining output pulses selectively from said least significant output of said adder means and from said series output of said shift register under control of said control means so arranged as to take output from said least significant output of said adder means after the supplying to said first gate means of a number of bits of said multiplicand equal to the number of bits in said multiplier until the end of the bit interval in which the most signIficant bit of said multiplicand is supplied to said first gate means, and then taking output from said serial output of said shift register during the serial unloading of said shift register.

Claim 10

A serial-parallel binary multiplier as defined in claim 6 in which said control means is arranged so as to supply a pulse to a carry input of said adder means during the bit interval immediately preceding the first bit interval from which output is taken from said least significant output of said adder means as aforesaid, whereby a rounded product rather than a truncated product may be formed by the output pulses.

Claim 11

A serial-parallel binary multiplier as defined in claim 7 having read only memory means for supplying bits of said multiplier in parallel to said first gate means.

Claim 12

A serial-parallel binary multiplier as defined in claim 7 in which means are provided for successively supplying a succession of multiplicand bit sequences to said first gate means and in which said control means is adapted and arranged to reset itself immediately after the bit interval of the most significant of each bit multiplicand.

Claim 15

A method as defined in claim 10 in which a rounding pulse is added through a carry input of the least significant stage of said adder during the last bit interval before product pulses are taken from said least significant stage of said adder.