Method and apparatus for performing two's complement multiplication

• US 7,818,361 B1
• Filed: 11/07/2005
• Issued: 10/19/2010
• Est. Priority Date: 11/07/2005
• Status: Expired due to Fees

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Tabula Incorporated
• Inventors: Pugh, Daniel J.
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US11/269,858
• Time in Patent Office: 1,807 Days
• Field of Search: 708/232, 708/625
• US Class Current: 708/625
• CPC Class Codes: G06F 7/53 in parallel-parallel fashion, i.e. both operands being entered in parallel G06F7/533 takes precedence
• CPC Class Codes: H03K 19/20 characterised by logic function, e.g. AND, OR, NOR, NOT circuits H03K19/003 - H03K19/01 take precedence

Abstract

Some embodiments provide a novel way of performing a signed multiplication. Each individual bit of a first operand is multiplied by every bit of a second operand to generate partial multiplication results. Each partial result is shiftably added to other partial results except one partial result which is shiftably subtracted. For the partial result that is subtracted, the most significant bit of the second operand is negated and is utilized as carry in of the subtraction operation. The most significant bit of each operand is considered to have a negative sign when generating the partial multiplication results. Also, one of the partial results is appended with the most significant bit of the second operand. Some embodiments utilize a configurable IC that performs subtraction with the same circuitry and at the same cost as addition. The configurable IC also utilizes hybrid interconnect/logic circuits to perform part of the multiplication operation.

Claims

1. An integrated circuit (“

IC”

) for performing a signed multiplication, the IC comprising;

a set of configurable logic circuits, each configurable logic circuit for configurably performing a set of functions on a set of inputs; and

a plurality of input select interconnect circuits for selecting the input set supplied to each configurable logic circuit,

wherein the input select interconnect circuits multiply each individual bit of a first operand by every bit of a second operand to generate partial multiplication results,

wherein the configurable logic circuits shiftably add all partial results except one partial result which is shiftably subtracted,

wherein at least one of the input select interconnect circuits is configured to perform a logical NOT operation on a most significant bit of one of the operands and utilize a result of the NOT operation as a carry-in to perform a subtraction operation.

2. The IC of claim 1, wherein some of said input select interconnect circuits are configured to perform a logical AND operation on an individual bit of the first operand and an inverted individual bit of the second operand.

3. The IC of claim 1 further comprising:

at least one multi-bit subtractor comprising a set of configurable logic circuits and their associated input select interconnect circuits to perform said shiftably subtracting of said one partial result.

4. The IC of claim 3 further comprising:

at least one first-type multi-bit adder comprising a set of configurable logic circuits and their associated input select interconnect circuits to perform said shiftably adding of said partial results.

5. The IC of claim 1 further comprising:

a configurable logic circuit and its associated input select interconnect circuits for generating a least significant bit of a multiplication result,

wherein one of the associated input select interconnect circuits of the logic circuit is a hybrid interconnect/logic circuit implementing an AND operation.

6. An integrated circuit (“

ICD”

) for performing a signed multiplication, the IC comprising;

a set of configurable logic circuits, each configurable logic circuit for configurably performing a set of functions on a set of inputs; and

a plurality of input select interconnect circuits for selecting the input set supplied to each configurable logic circuit,

wherein the input select interconnect circuits multiply each individual bit of a first operand by every bit of a second operand to generate partial multiplication results,

wherein the configurable logic circuits shiftably add all partial results except one partial result which is shiftably subtracted,

wherein each operand has a most significant bit, wherein the most significant bit of the second operand is negated by a hybrid interconnect/logic circuit and is utilized as a carry-in for shiftably subtracting of said one partial result.

7. The IC of claim 6, wherein the most significant bit of each operand is considered to have a negative weight when generating said partial results.

8. The IC of claim 6, wherein the first operand has a least significant bit, wherein one of said partial multiplication results that is generated by multiplying the least significant bit of the first operand to every bit of the second operand is appended to have a most significant bit equal to the most significant bit of the second operand.

9. An integrated circuit (“

ICD”

) for performing a signed multiplication, the IC comprising;

a set of configurable logic circuits, each configurable logic circuit for configurably performing a set of functions on a set of inputs;

a plurality of input select interconnect circuits for selecting the input set supplied to each configurable logic circuit,

wherein the input select interconnect circuits multiply each individual bit of a first operand by every bit of a second operand to generate partial multiplication results,

wherein the configurable logic circuits shiftably add all partial results except one partial result which is shiftably subtracted;

at least one multi-bit subtractor comprising a first group of configurable logic circuits and their associated input select interconnect circuits to perform said shiftably subtracting of said one partial result;

at least one first-type multi-bit adder comprising a second group of configurable logic circuits and their associated input select interconnect circuits to perform said shiftably adding of said partial results; and

at least one second-type multi-bit adder comprising a third group of configurable logic circuits and their associated input select interconnect circuits to add a result of said at least one multi-bit subtractor and said at least one first-type first multi-bit adder.

10. An integrated circuit (“

ICD”

) for performing a signed multiplication, the IC comprising

a set of configurable logic circuits, each configurable logic circuit for configurably performing a set of functions on a set of inputs;

a plurality of input select interconnect circuits for selecting the input set supplied to each configurable logic circuit,

wherein the input select interconnect circuits multiply each individual bit of a first operand by every bit of a second operand to generate partial multiplication results,

wherein the configurable logic circuits shiftably add all partial results except one partial result which is shiftably subtracted;

at least one multi-bit first subtractor comprising a group of configurable logic circuits and their associated input select interconnect circuits to perform said shiftably subtracting of said one partial result; and

a second subtractor to invert a carry-out of said multi-bit first subtractor.

11. An electronics system comprising:

an integrated circuit (“

IC”

) for performing a signed multiplication, the IC comprising;

a set of configurable logic circuits, each configurable logic circuit for configurably performing a set of functions on a set of inputs; and

a plurality of input select interconnect circuits for selecting the input set supplied to each configurable logic circuit,

wherein the input select interconnect circuits multiply each individual bit of a first operand by every bit of a second operand to generate partial multiplication results,

wherein the configurable logic circuits shiftably add all partial results except one partial result which is shiftably subtracted,

wherein each multiplication operand has a most significant bit, wherein at least one of the input select interconnect circuits is configured to perform a logical NOT operation on a most significant bit of one of the operands and utilize a result of the NOT operation as a carry-in to perform a subtraction operation.

12. The electronics system of claim 11, wherein the most significant bit of each operand is considered to have a negative weight when generating said partial results.

13. The electronics system of claim 11, wherein the first operand has a least significant bit, wherein one of said partial multiplication results that is generated by multiplying the least significant bit of the first operand to every bit of the second operand is appended to have a most significant bit equal to the most significant bit of the second operand.

14. The electronic system of claim 11 further comprising a non-volatile memory for storing configuration data and for supplying configuration data to the IC when the IC powers up.