Arithmetic cell for field programmable devices

• US 5,805,477 A
• Filed: 09/26/1996
• Issued: 09/08/1998
• Est. Priority Date: 09/26/1996
• Status: Expired due to Fees

• Current Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Perner, Frederick A.
• Primary Examiner(s): NGO, CHUONG D
• Application Number:
  US08/718,849
• Time in Patent Office: 712 Days
• Field of Search: 364/716.01, 364/716.02, 364/716.03, 364/716.04, 364/716.05, 364/716.06, 364/716.07, 364/754.01, 364/757, 364/758, 364/759, 326/37, 326/38, 326/39
• US Class Current: 708/232
• CPC Class Codes: G06F 15/7867 with reconfigurable architecture
• CPC Class Codes: G06F 2207/3884 Pipelining
• 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: G06F 7/5443 Sum of products for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00
• CPC Class Codes: H03K 19/17704 the logic functions being realised by the interconnection of rows and columns
• CPC Class Codes: H03K 19/17728 Reconfigurable logic blocks, e.g. lookup tables

Abstract

An arithmetic cell to be used in field programmable devices is defined in this invention. This cell will allow efficient implementations of multipliers, multipliers/accumulators and adders (addition, compare, and subtraction) in one compact cell that is a collection of circuits common to field programmable devices. This cell may be used in a flexible manner that allows full multipliers of any dimension (n*m products), adders of any length (n+m sums, compare, differences), accumulators, and registers (to hold complete results or partial products). Key elements in this invention are an application controlled multiplexer, signal routing to provide a shift function for multiplication, and a minimum collection of configuration bits and circuit elements to perform the basic arithmetic functions.

Claims

1. An arithmetic cell for a programmable device, the cell comprising:

an adder;

a first multiplexer;

a second multiplexer; and

a steering logic configurable to perform a multiplication operation,

wherein the first and second multiplexers cooperate to perform a test on an active bit of a multiplier input to the adder, and if the active bit of the multiplier is a "1", a multiplicand input to the adder is added to a partial product and the resultant partial product is then shifted,

however, if the active bit of the multiplier is a "0", the resultant partial product is shifted without adding.

2. The arithmetic cell as set forth in claim 1, wherein the adder is a look-up table configured as an adder.

3. The arithmetic cell as set forth in claim 1, further comprising a flip-flop configurable to latch the result from the adder and thereby perform a multiply-accumulate operation.

4. The arithmetic cell as set forth in claim 3, wherein the steering logic can be configured to perform accumulation in the flip-flop without multiplication.

5. The arithmetic cell as set forth in claim 3, wherein the steering logic and the adder can be configured to perform latching in the flip-flop without multiplication and without accumulation.

6. The arithmetic cell as set forth in claim 1, wherein the steering logic and the adder can be configured to perform addition.

7. The arithmetic cell as set forth in claim 1, wherein the steering logic and the adder can be configured to perform comparison.

8. The arithmetic cell as set forth in claim 1, wherein the steering logic can be configured to perform subtraction.

9. A method of performing multiplication within an arithmetic cell for a programmable device, the arithmetic cell including an adder, first and second multiplexers and a configurable steering logic, the method comprising the steps of:

configuring the steering logic to perform the multiplication operation; and

using the first and second multiplexers to cooperatively perform a test on an active bit of a multiplier input to the adder;

if the active bit of the multiplier is a "1", a multiplicand input to the adder is added to a partial product and the resultant partial product is then shifted;

however, if the active bit of the multiplier is a "0", the resultant partial product is shifted without adding.

10. The method of performing multiplication within an arithmetic cell for a programmable device as set forth in claim 9, wherein the adder is a look-up table configured as an adder.

11. The method of performing multiplication within an arithmetic cell for a programmable device as set forth in claim 9, wherein the arithmetic cell further includes a flip-flop, and the method further comprises the steps of:

configuring the steering logic to perform an accumulation operation with the multiplication operation; and

using the flip-flop to latch the result from the adder and thereby perform the accumulate operation.

12. A programmable device, the programmable device comprising an array of cells wherein at least one of the cells is an arithmetic cell having:

an adder;

a first multiplexer;

a second multiplexer; and

a steering logic configurable to perform a multiplication operation,

wherein the first and second multiplexers cooperate to perform a test on an active bit of a multiplier input to the adder, and if the active bit of the multiplier is a "1", a multiplicand input to the adder is added to a partial product and the resultant partial product is then shifted,

however, if the active bit of the multiplier is a "0", the resultant partial product is shifted without adding.

13. The programmable device as set forth in claim 12, wherein the adder is a look-up table configured a an adder.

14. The programmable device as set forth in claim 12, wherein the arithmetic cell further comprises a flip-flop configurable to latch the result from the adder and thereby perform a multiply-acumulate operation.

15. The programmable device as set forth in claim 14, wherein the steering logic can be configured to perform accumulation in the flip-flop without multiplication.

16. The programmable device as set forth in claim 14, wherein the steering logic can be configured to perform latching in the flip-flop without multiplication and without accumulation.

17. The programmable device as set forth in claim 12, wherein the steering logic and the adder can be configured to perform addition.

18. The programmable device as set forth in claim 12, wherein the steering logic and the adder can be configured to perform comparison.

19. The programmable device as set forth in claim 12, wherein the steering logic and the adder can be configured to perform subtraction.