Electronic digital logic circuitry – Multifunctional or programmable
Reexamination Certificate
2000-04-04
2001-11-27
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
C326S039000
Reexamination Certificate
active
06323677
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to programmable logic array integrated circuit devices, and more particularly to improving the speed and/or efficiency with which such devices can perform multiplication.
A typical programmable logic device (see, for example, Cliff et al. U.S. Pat. No. 5,909,126, and Cliff et al. U.S. Pat. No. 5,999,015, both of which are hereby incorporated by reference herein) includes a large number of relatively small “modules” of programmable logic and various types of programmably controlled interconnection conductors and other circuit elements for selectively conveying signals to, from, and between the logic modules. Each logic module is programmable to perform any of several relatively small logic tasks. But extremely complex logic can be performed by the device as a whole by interconnecting the logic modules to one another via the interconnection conductors and related circuitry.
In many known programmable logic devices, each logic module can be programmed to perform one place of binary addition on two addend signals and a carry in signal in order to produce a sum out signal and a carry out signal. This is true, for example, of the representative logic module shown in FIG. 2 of above-mentioned U.S. Pat. No. 5,999,015. A frequently occurring elemental operation in binary multiplications, however, involves Adding a multiplicand bit and a multiplier bit to produce one of two addends that are to be added together with a carry in bit to produce a sum out bit and a carry out bit. Because a logic module as described above cannot perform both an AND operation and one place of binary addition, two logic modules are required to perform one elemental multiplication operation of the type mentioned in the immediately preceding sentence.
Some elemental operations in a multiplication are even more complex than those mentioned above. These operations require two separate AND operations on two sets of two multiplicand/multiplier bits. The outputs of the two AND operations are two addend bits that must be added together with a carry in bit to produce sum out and carry out bits. Again, because logic modules of the type described above cannot perform more than one two-input AND or one place of binary addition, three logic modules are required to perform an elemental multiplication operation of the type mentioned in the three immediately preceding sentences.
It will be seen from the foregoing that multiplications tend to require large numbers of logic modules on a programmable logic device. And because many of the elemental multiplication operations involved require two or even three logic modules which must be interconnected via interconnection conductors and related circuitry, multiplications tend to be slowed down by the need to pass signals through the interconnection conductors as part of most of the elemental operations, as well as between elemental operations.
In view of the foregoing, it is an object of this invention to provide improved programmable logic device circuitry for performing multiplication.
It is a more particular object of this invention to reduce the number of logic modules on a programmable logic device that are required to perform multiplication.
It is another more particular object of this invention to provide programmable logic circuitry which can perform multiplication more rapidly.
SUMMARY OF THE INVENTION
These and other objects of the invention are accomplished in accordance with the principles of the invention by providing programmable logic device logic modules which are modified or augmented with additional circuitry which makes it possible to perform more of the elemental operations that are required in multiplication in a single logic module. For example, an AND gate and associated programmable logic connector (“PLC”) circuitry may be provided in an input stage to each logic module. When a logic module is to be used in a multiplication, this circuitry can be programmed to allow two inputs to the logic module to be preliminarily added to thereby form the product of those two inputs. The output of the AND gate is then applied to the remainder of the logic module, which is programmed as a full adder to add the AND gate output, another input to the logic module, and a carry in input to the logic module in order to produce sum out and carry out output signals of the logic module. A single augmented logic module is thus able to both multiply two multiplicand/multiplier bits and perform an associated full adder operation. Accordingly, each such logic module can perform an elemental multiplication operation that would have required two conventional logic modules to perform. In addition to conserving logic modules, multiplication speed is increased to the extent that the interconnection conductor resources of the programmable logic device do not have to be used to connect two logic modules that are performing parts of one elemental multiplication operation.
In some embodiments two parallel AND gates may be provided in an input stage to each logic module so that the logic module can perform two preliminary multiplications followed by full addition of the resulting product signals (with carry in, sum out, and carry out being employed or produced as in the preceding paragraph).
The several logic modules in a group of logic modules may receive an input signal in parallel, which can be one input to the above-mentioned AND gate in each logic module. This input signal can be a multiplier bit which is needed in common by several logic modules. If each logic module has two AND gates, then two different multiplier bit signals can be supplied in parallel to all of the logic modules. One of these signals is applied to one input terminal of one of the AND gates in each logic module, and the other of these signals is applied to one input terminal of the other AND in each logic module.
Each logic module may include a flip-flop for enabling the logic module to perform as one stage of a multiplier-accumulator. Several such multiplier-accumulator stages can be interconnected to perform multi-bit multiplication over several successive cycles of a periodic signal which is used to clock the flip-flops. Multiplications can be performed in very small numbers of logic modules by using such multiplier-accumulator arrangements.
Further features of the invention, its nature and various advantages will be more apparent from the accompanying drawings and the following detailed description of the preferred embodiments.
REFERENCES:
patent: 5396127 (1995-03-01), Chan et al.
patent: 5455525 (1995-10-01), Ho et al.
patent: 5550782 (1996-08-01), Cliff et al.
patent: 5570039 (1996-10-01), Oswald et al.
patent: 5859542 (1999-01-01), Pedersen
patent: 5909126 (1999-06-01), Cliff et al.
patent: 5999015 (1999-12-01), Cliff et al.
“Implementing Multipliers with Actel FPGAs”, Application Note, pp. 4-73 through 4-80, Actel Corporation, Apr. 1996.
“Multipliers in ORCA OR2CxxA/OR2TxxA FPGAs”, Microelectronics Application Note, pp. 1-8, Lucent Technologies Inc., May 1996.
“Implementing and Optimizing Multipliers in ORCA FPGAs”, Microelectronics Group Application Note, pp. 1-12, Lucent Technologies Inc., Feb. 1997.
Cliff Richard G.
Lane Christopher F.
Pedersen Bruce B.
Reddy Srinivas T.
Veenstra Kerry
Altera Corporation
Cho James H.
Fish & Neave
Jackson Robert R.
Park Joo-Youn
LandOfFree
Programmable logic device circuitry for improving multiplier... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Programmable logic device circuitry for improving multiplier..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable logic device circuitry for improving multiplier... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2579028