Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2000-04-17
2002-07-30
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S038000, C326S039000
Reexamination Certificate
active
06426648
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to programmable logic arrays, and in particular, to structures and techniques for improving carry propagation in programmable logic arrays.
2. Description of the Related Art
Techniques for implementing carry propagation in commercially prevalent programmable logic devices (PLDs) or arrays (PLAs) aim at fast carry propagation.
FIG. 1
illustrates a configurable logic block (CLB) of a conventional PLD or PLA made by Xilinx, Inc. This CLB is described in more detail in U.S. Pat. No. 5,546,018. As shown, the Xilinx CLB includes four four-input function generator F, G, H, J each comprising lookup tables for implementing one bit of an arithmetic function of two variables which are received on the input terminals
0
,
1
,
2
,
3
of each function generator. Associated with each function generator is a fast carry mux C
1
, C
2
, C
3
, C
4
. The purpose of these muxes is to propagate carry based on the logical input CIN and the result of the arithmetic function between input variables A and B so as to provide a cumulative carry output signal COUT.
In the conventional PLD described above, for multibit operations of two variables greater than four bits, the carry output signal of one CLB is provided to the carry input of a higher-order CLB in a chain of CLBs depending on the number of bits desired. It should be noted that in the CLB illustrated in
FIG. 1
, a sum output stage is provided in another CLB for finalizing the sum values using the outputs of the CLB in FIG.
1
.
FIG. 2
illustrates a logic array block (LAB) of a conventional PLD made by Altera, Inc. This LAB is described in more detail in U.S. Pat. No. 5,761,099. In this device, each logic element
12
(typically eight or ten per LAB) can be configured to perform one bit of an arithmetic operation of two input variables. Each logic element
12
further includes logic
13
for providing a carry output signal based on a carry input and the arithmetic operation of two variables. As shown in
FIG. 2
, carry is propagated between logic elements along lines
70
a
in ripple fashion as in the Xilinx device. Lines
70
b
provide for multibit operations of two variables greater than the number of bits capable of being processed by a single LAB. In such circumstances, the “direct carry out” signal of one LAB is provided to the “direct carry in” signal of a higher-order LAB in a chain of LABs depending on the number of bits desired.
The conventional ripple carry propagation technique described above is slow because the highest order output is not valid until a carry has rippled through all the lower order bits.
Carry lookahead techniques offer the promise of much faster carry propagation than can be achieved with ripple carry techniques. Such techniques have been implemented in digital arithmetic structures for decades (e.g. the 74182 look-ahead carry generator). See, for example, Joseph D. Greenfield,
Practical Digital Design Using ICs
, §14.11 (1983). Some theoretical discussions have addressed considerations for extending such techniques to programmable gate arrays. See, for example, Charle R. Rupp, “Fast Algorithms for Regular Functions in Field Programmable Gate Arrays,” Proceedings of the Third Annual PLD Conference (1993). However, prior art structures for performing carry lookahead features require a prohibitive number of elements and complex interconnections therebetween that are not suitable for implementation in a PLD or PLA. Accordingly, carry lookahead techniques have not been seriously considered for use in conventional programmable logic devices.
What is needed in the art, therefore, is an improved carry propagation technique that is suitable for implementation in a programmable logic device. The present invention fulfills this need, among others.
SUMMARY OF THE INVENTION
Accordingly, it is an object of the present invention to overcome the above-described problems in the prior art.
Another object of the invention is to improve the speed of operations in a programmable logic device.
Another object of the invention is to improve the speed of operations that require carry propagation in a programmable logic device.
Another object of the invention is to provide improved performance in a programmable logic device with minimal additional structure.
Another object of the invention is to minimize the number of interconnections required to implement carry propagation techniques in a programmable logic device.
Another object of the invention is to provide a carry lookahead technique that is suitable for implementation in a programmable logic device.
These and other objects are fulfilled by the present invention, in which carry lookahead techniques are adapted for use in a programmable logic device. In one example of the invention, a carry result is computed for a block of function cells, each function cell representing one bit in a multibit operation that uses carry. This carry result is combined with the carry input from a function cell block representing less significant bits in the operation and a carry output is provided to a function cell block representing more significant bits in the operation. The received carry can also be supplied to adjust provisional carry results for each bit associated with the function cells in the block. Accordingly, the received carry input need not be rippled through all the function cells in the block, thus reducing carry propagation delays. This technique is suitable for use in programmable logic devices because only minimal additional logic need be included in each block of function cells (such as the CLBs and LABs in the prior art), and because few, in any, new interconnections between blocks need be introduced.
REFERENCES:
patent: 5260611 (1993-11-01), Cliff et al.
patent: 5274581 (1993-12-01), Cliff et al.
patent: 5349250 (1994-09-01), New
patent: 5546018 (1996-08-01), New et al.
patent: 5629886 (1997-05-01), New
patent: 5631576 (1997-05-01), Lee et al.
patent: 5672985 (1997-09-01), Lee
patent: 5675262 (1997-10-01), Duong et al.
patent: 5889411 (1999-03-01), Chaudhary
patent: 5898319 (1999-04-01), New
patent: 5926036 (1999-07-01), Cliff et al.
patent: 5977793 (1999-11-01), Reddy et al.
patent: 5982195 (1999-11-01), Cliff et al.
patent: 6140839 (2000-10-01), Kaviani et al.
patent: 6154053 (2000-11-01), New
patent: WO 98/51013 (1998-11-01), None
Rupp, Charles, “Fast Algorithms for Regular Functions in Field Programmable Gate Arrays,” PLD93 Conference Paper, (1993) pp. 1-6.
Hauck, S. et al., “High-Peformance Carry Chains for FPGAs,” ACM 6thConf. (Feb. 22-24, 1998) pp. 223-233.
Anonymous: “Binary Adder,” IBM Tech. Disclosure Bulletin, vol. 6, No. 4, (Sep. 1, 1963), pp. 39-40.
Cooley & Godward LLP
Tran Anh
LandOfFree
Carry lookahead for programmable logic array does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Carry lookahead for programmable logic array, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Carry lookahead for programmable logic array will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2830772