Method and circuitry for digital system multiplication

Claim 1

A method for optimizing a speed of a subsequent multiplication in a digital system of a first number by a second number, wherein the second number has bit positions including (1) a bit position of order X, which is a least significant bit position of the second number, (2) a bit position of order Y, and (3) a bit position of order Z, wherein X is less than Y, and Y is less than Z, comprising the steps of: (a) detecting whether a string of consecutive zeroes occupies the bit positions of the second number beginning with the bit position X and increasing towards higher order bit positions; (b) if no such string of consecutive zeroes exists, then using bit position X as a starting point for the second number for multiplication; (c) if both (i) the string of consecutive zeroes exists and (ii) the string of consecutive zeroes has its highest order zero in a bit position having an order less than Y minus one, then using bit position X as a starting point for the second number for multiplication; (d) if both (i) the string of consecutive zeroes exists and (ii) the string of consecutive zeroes has its highest order zero in a bit position having an order less than Z minus one but greater than or equal to Y minus one, then using bit position Y as a starting point for the second number for multiplication; (e) if both (i) the string of consecutive zeroes exists (ii) the string of consecutive zeroes has its highest order zero in a bit position having an order greater than or equal to Z minus one, then using bit position Z as a starting point for the second number for multiplication.

Claim 2

A method for optimizing a speed of a subsequent multiplication in a digital system of a first number by a second number, wherein the second number has bit positions including (1) a bit position of order X, which is a least significant bit position of the second number, (2) a bit position of order Y, and (3) a bit position of order Z, wherein X is less than Y, and Y is less than Z, comprising the steps of: (a) detecting whether a string of consecutive zeroes occupies the bit positions of the second number beginning with the bit position X and increasing towards higher order bit positions; (b) if no such string of consecutive zeroes exists, then using bit position X as a starting point for the second number for multiplication; (c) if both (i) the string of consecutive zeroes exists and (ii) the string of consecutive zeroes has its highest order zero in a bit position having an order less than Y minus one, then using bit position X as a starting point for the second number for multiplication; (d) if both (i) the string of consecutive zeroes exists and (ii) the string of consecutive zeroes has its highest order zero in a bit position having an order less than Z minus one but greater than or equal to Y minus one, then using bit position Y as a starting point for the second number for multiplication; (e) if both (i) the string of consecutive zeroes exists (ii) the string of consecutive zeroes has its highest order zero in a bit position having an order greater than or equal to Z minus one, then using bit position Z as a starting point for the second number for multiplication.

Claim 7

A method for optimizing multiplication clock cycles in a digital system, comprising the steps of: (a) prior to multiplying a first number by a second number comprised of N bits using B 2-bit Booth algorithm pairs of bits of the second number per clock cycle, wherein B is a positive integer and N is a positive integer, padding the second number with a zero in each of two bit positions to the left of the most significant bit position of the second number; and (b) prior to multiplying the first number by the second number using B 2-bit Booth algorithm pairs of bits of the second number per clock cycle, padding the second number with a zero in each of C bit positions to the right of the least significant bit position of the second number, wherein C equals D-(N+2), wherein D is a smallest positive integer that is a multiple of B times 2 that will also yield a C that is either zero or a positive integer.

Claim 8

A method for optimizing multiplication clock cycles in a digital system, comprising the steps of: (a) prior to multiplying a first number by a second number comprised of N bits using B 2-bit Booth algorithm pairs of bits of the second number per clock cycle, wherein B is a positive integer and N is a positive integer, padding the second number with a zero in each of two bit positions to the left of the most significant bit position of the second number; and (b) prior to multiplying the first number by the second number using B 2-bit Booth algorithm pairs of bits of the second number per clock cycle, padding the second number with a zero in each of C bit positions to the right of the least significant bit position of the second number, wherein C equals D-(N+2), wherein D is a smallest positive integer that is a multiple of B times 2 that will also yield a C that is either zero or a positive integer.

Claim 13

A method for multiplication in a digital system, comprising the steps of: (a) having a partial product generator generate a first multibit output and a first carry-in output; (b) having a carry-save adder add: (1) the first multibit output from the partial product generator, (2) a sum applied as a sum input into the carry-save adder, and (3) a carry applied as a carry input into the carry-save adder; (c) latching a sum output of the carry-save adder into a sum latch; (d) latching a carry output of the carry-save adder into a sequence of bit positions of the carry latch, wherein the first position of the sequence of bit positions is of a next highest order from a least significant bit position; (e) latching the first carry-in output of the partial product generator into the least significant bit position of the carry latch; (f) adding (1) the least significant T bits of the sum from the sum latch, (2) The least significant T bits of the carry from the carry latch, and (3) a final stage carry-in bit, wherein T is a positive integer; (g) storing the most significant carry bit from the addition of the least significant T sum bits from the sum latch and the least significant T carry bits from the carry latch; (h) truncating the least significant T sum bits from the sum latch and storing the result; (i) truncating the least significant T carry bits from the carry latch and storing the result; (j) repeating steps (a) through (i), the first multibit output of the partial product generator becoming a second multibit output of the partial product generator, the first carry-in output of the partial product generator becoming a second carry-in output of the partial product generator, the truncated sum becoming a sum applied as a sum input to the carry-save adder, the truncated carry becoming a carry applied as a carry input to the carry-save adder, and the stored most significant carry bit from the addition of the least significant T sum bits and T carry bits becoming the final stage carry-in bit.

Claim 14

A method for multiplication in a digital system, comprising the steps of: (a) having a partial product generator generate a first multibit output and a first carry-in output; (b) having a carry-save adder add: (1) the first multibit output from the partial product generator, (2) a sum applied as a sum input into the carry-save adder, and (3) a carry applied as a carry input into the carry-save adder; (c) latching a sum output of the carry-save adder into a sum latch; (d) latching a carry output of the carry-save adder into a sequence of bit positions of the carry latch, wherein the first position of the sequence of bit positions is of a next highest order from a least significant bit position; (e) latching the first carry-in output of the partial product generator into the least significant bit position of the carry latch; (f) adding (1) the least significant T bits of the sum from the sum latch, (2) The least significant T bits of the carry from the carry latch, and (3) a final stage carry-in bit, wherein T is a positive integer; (g) storing the most significant carry bit from the addition of the least significant T sum bits from the sum latch and the least significant T carry bits from the carry latch; (h) truncating the least significant T sum bits from the sum latch and storing the result; (i) truncating the least significant T carry bits from the carry latch and storing the result; (j) repeating steps (a) through (i), the first multibit output of the partial product generator becoming a second multibit output of the partial product generator, the first carry-in output of the partial product generator becoming a second carry-in output of the partial product generator, the truncated sum becoming a sum applied as a sum input to the carry-save adder, the truncated carry becoming a carry applied as a carry input to the carry-save adder, and the stored most significant carry bit from the addition of the least significant T sum bits and T carry bits becoming the final stage carry-in bit.