Methods and apparatus for performing fast multiplication operations in bit-serial processors
AssigneeTeraNex, Inc.
InventorsWoodrow Meeker, Andrew P. Abercrombie, Michele D. Van Dyke-Lewis
Life of this patent
Estimating the term…
Abstract
Bit-serial processors quickly multiply multiple-bit operands using significantly fewer clock cycles as compared to conventional bit-serial implementations. Exemplary embodiments process groups of operand bits simultaneously to provide the significant speed increases. Advantageously, however, the exemplary embodiments utilize logic and memory architectures which are fully compatible with, and fully useful for, conventional bit-serial applications, and the embodiments thus provide fast multiple-bit multiplications while at the same time providing all of the advantages typically associated with conventional bit-serial processors.
Claims12
A method of performing an iteration in an iterative method of multiplying a multiplicand by two or more 2-bit portions of a multiplier in a data processing apparatus, wherein each of the 2-bit portions of the multiplier is binary encoded to represent any of the numbers 0, 1, 2 and 3, the method comprising the steps of:
- selecting one of the 2-bit portions of the multiplier in the data processing apparatus;
- performing a first pass operation that comprises the steps of:
- generating a first partial product representing the multiplicand multiplied by a value that is equal to the selected 2-bit portion of the multiplier if the selected 2-bit portion of the multiplier is not equal to 3, and representing the multiplicand multiplied by a value that is equal to minus one if the selected 2-bit portion of the multiplier is equal to 3;
- and
- conditionally setting a flag if the selected 2-bit portion of the multiplier is equal to 3;
- and
- performing a second pass operation that comprises the step of conditionally adding a value of 1 to a next 2-bit portion of the multiplier if the flag is set.
A method of multiplying a multiplicand by a multiplier in a data processing apparatus, wherein the multiplier comprises m or more 2-bit digits, wherein m is an integer greater than one, and each 2-bit digit is binary encoded to represent any of the numbers 0, 1, 2 and 3, the method comprising the steps of:
- performing one or more passes in the data processing apparatus, wherein each pass generates a partial product;
- and
- combining the one or more partial products,
- wherein each pass comprises the steps of:
- a) selecting an m-digit portion of the multiplier;
- b) selecting an m-digit portion of the multiplicand, wherein each of the multiplicand digits comprises 2 bits;
- c) simultaneously pairing each of the selected 2-bit digits of the multiplier with a respective one of the m selected 2-bit digits of the multiplicand and performing a multiply operation between each pair, thereby generating a number, m, of pair results;
- d) combining the m pair results and a previously generated partial product to generate a present partial product, wherein for a first pass, the previously generated partial product is zero;
- and
- e) selecting a next m-digit portion of the multiplicand and repeating steps c), d) and e) at least until each digit of the multiplicand has been paired with each of the m selected 2-bit digits of the multiplier,
- wherein the multiply operation between each pair comprises the steps of:
- generating a pair result representing the one digit of the multiplicand multiplied by a value that is alternatively equal to 0, 1, 2 or -1 as a function of the value of the paired 2-bit digit of the multiplier and of the values of all multiplier digits of lesser significance than the paired 2-bit digit of the multiplier.
An apparatus for performing an iteration in an iterative method of multiplying a multiplicand by two or more 2-bit portions of a multiplier in a data processing apparatus, wherein each of the 2-bit portions of the multiplier is binary encoded to represent any of the numbers 0, 1, 2 and 3, the apparatus comprising:
- means for selecting one of the 2-bit portions of the multiplier;
- means for performing a first pass operation that:
- generates a first partial product representing the multiplicand multiplied by a value that is equal to the selected 2-bit portion of the multiplier if the selected 2-bit portion of the multiplier is not equal to 3, and representing the multiplicand multiplied by a value that is equal to minus one if the selected 2-bit portion of the multiplier is equal to 3;
- and
- conditionally sets a flag if the selected 2-bit portion of the multiplier is equal to 3;
- and
- means for performing a second pass operation that conditionally adds a value of 1 to a next 2-bit portion of the multiplier if the flag is set.
An apparatus for multiplying a multiplicand by a multiplier in a data processing apparatus, wherein the multiplier comprises m or more 2-bit digits, wherein m is an integer greater than one, and each 2-bit digit is binary encoded to represent any of the numbers 0, 1, 2 and 3, the apparatus comprising:
- means for performing one or more passes, wherein each pass generates a partial product;
- and
- means for combining the one or more partial products,
- wherein each pass:
- a) selects an r-digit portion of the multiplier;
- b) selects an m-digit portion of the multiplicand, wherein each of the multiplicand digits comprises 2 bits;
- c) simultaneously pairs each of the 2-bit digits of the multiplier with a respective one of the m selected 2-bit digits of the multiplicand and performs a multiply operation between each pair, thereby generating a number, m, of pair results;
- d) combines the m pair results and a previously generated partial product to generate a present partial product, wherein for a first pass, the partial product is zero;
- and
- e) selects a next m-digit portion of the multiplicand and repeats steps c), d) and e) at least until each digit of the multiplicand has been paired with each of the m selected 2-bit digits of the multiplier,
- wherein the multiply operation between each pair comprises:
- generating a pair result representing the one digit of the multiplicand multiplied by a value that is alternatively equal to 0, 1, 2 or -1 as a function of the value of the 2-bit digit of the multiplier and of the values of all multiplier digits of lesser significance than the paired 2-bit digit of the multiplier.
Dependencies are inferred from the claim text.