Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2000-07-27
2002-02-12
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S040000, C326S041000
Reexamination Certificate
active
06346824
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to an architecture for a field programmable gate array (FPGA). More specifically, the present invention relates to an FPGA that includes a plurality of configurable logic blocks (CLBs), each having a configurable logic element (CLE) and an associated function block.
2. Related Art
FIG. 1A
is a representation of the binary multiplication of a 4-bit multiplicand number x with a 4-bit multiplier word Y. Multiplicand number X includes bits X
3
, X
2
, X
1
and X
0
(X
3
being the most significant bit and X
0
being the least significant bit). Similarly, multiplier word Y includes bits Y
3
, Y
2
, Y
1
and Y
0
(Y
3
being the most significant bit and Y
0
being the least significant bit). Each bit of multiplicand number x is multiplied by each bit of multiplier word Y as illustrated, thereby creating four partial products
101
-
104
. The first partial product
101
includes each bit of multiplicand number X multiplied by Y
0
. The second partial product
102
includes each bit of multiplier number X multiplied by Y
1
. The second partial product
102
is shifted left one place with respect to the first partial product
101
, thereby providing the appropriate weight to these partial products. The third and fourth partial products
103
and
104
are created and weighted in a similar manner. The aligned columns of partial products
101
-
104
are added to create product bits P
7
-P
0
. Product bits P
7
-P
0
represent the product P of multiplicand number x and multiplier word Y.
FIG. 1B
illustrates the addition of partial products
101
-
104
in more detail. As illustrated in
FIG. 1B
, the first and second partial products
101
and
102
are initially added. The values in each column are added, thereby generating six sum signals (C
4
, PP
2
, PP
1
, PP
0
, P
1
and P
0
) and four carry signals (C
1
-C
4
) as illustrated. The sum and carry signals for each column are generated in response to the three input signals associated with the column. The generation of sum and carry signals in response to three generic input signals A, B and C is summarized below in Table 1.
TABLE 1
A
B
C
SUM
CARRY
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
Carry signal C
1
is the carry result from the addition of X
1
Y
0
, X
0
Y
1
and “0”. Similarly, carry signal C
2
is the carry result from the addition of X
2
Y
0
, X
1
Y
1
and C
1
. Carry signal C
3
is the carry result from the addition of X
3
Y
0
, X
2
Y
1
and C
2
. Finally, carry signal C
4
is the carry result from the addition of X
3
Y
1
, C
3
and “0”.
Six sum signals (C
4
, PP
2
, PP
1
, PP
0
, P
1
and P
0
) result from the addition of partial products
101
and
102
. Sum signal P
0
(which is also product bit P
0
) is equal to X
0
Y
0
. Sum signal P
1
(which is also product bit P
1
) is the sum result of X
1
Y
0
, X
0
Y
1
and “0”. Sum signal PP
0
is the sum result of X
2
Y
0
, X
1
Y
1
and C
1
. Sum signal PP
1
is the sum result of X
3
Y
0
, X
1
Y
1
and C
2
. Sum signal PP
2
is the sum result of X
3
Y
1
and C
3
.
Partial product
103
is added to the six sum signals that result from the addition of partial products
101
and
102
. Seven sum signals (C
8
, PP
5
, PP
4
, PP
3
, P
2
, P
1
and P
0
) and four carry signals (C
5
-C
8
) are generated by this addition operation as illustrated. Partial product
104
is then added to the seven sum signals resulting from the addition of partial products
101
,
102
and
103
. Sum signals (i.e., the product bits P
7
-P
0
) and carry signals C
9
-C
12
are generated during this addition operation as illustrated.
FIG. 2
is a circuit diagram of a conventional 4×4 bit multiplier circuit
200
for implementing the multiplication operation illustrated in
FIGS. 1A and 1B
. Multiplier circuit
200
includes AND gates
201
-
216
and adder circuits
221
-
236
. Each of adder circuits
221
-
236
provides a sum signal and a carry signal in response to three input signals in the manner set forth in Table 1. Each of AND gates
201
-
216
has a first input terminal which is coupled to receive a selected one of the multiplicand bits X
3
-X
0
. Similarly, each of AND gates
201
-
216
has a second input terminal which is coupled to receive a selected one of the multiplier bits Y
3
-Y
0
. AND gates
201
-
216
operate to multiply the X and Y bits. The truth tables for the logical AND of two bits and the arithmetic product of two bits are identical, the result being a logic “1” value only if both bits have logic “1” values, the result being a logic “0” otherwise. As a result, AND gates
201
-
216
provide the terms of partial products
101
,
102
,
103
and
104
. More specifically, AND gates
201
-
204
provide the terms of partial product
101
; AND gates
205
-
208
provide the terms of partial product
102
; AND gates
209
-
212
provide the terms of partial product
103
; and AND gates
213
-
216
provide the terms of partial product
104
. The terms of partial products
101
-
104
are provided to adder circuits
221
-
236
as illustrated. Note that the terms of partial products
101
-
104
are shifted down in successive columns, thereby providing the appropriate weighting to the partial products. Adder circuits
221
-
236
add partial products
101
-
104
in the manner illustrated in
FIG. 1B
, thereby creating product bits P
7
-P
0
. The carry signals C
1
-C
12
and sum signals PP
0
-PP
5
previously described in connection with
FIG. 1B
are illustrated in
FIG. 2
, thereby showing the manner in which multiplier circuit
200
implements the multiplication operation of FIG.
1
B.
FIG. 3
, which includes
FIGS. 3A and 3B
, is a circuit diagram illustrating the implementation of multiplier circuit
200
in an FPGA. The FPGA includes an array of configurable logic blocks (CLBS), which includes CLBs
301
-
316
. Programmable interconnect resources extend between the CLBs, thereby allowing the illustrated connections to be made. The resources present within each CLB can be configured to implement either a pair of adder circuits or a pair of AND gates. For example, CLB
302
is configured to implement AND gates
201
and
202
, and CLB
304
is configured to implement adder circuits
221
and
222
. A total of eight CLBs (i.e., CLBs
301
-
302
,
305
-
306
,
309
-
310
and
313
-
314
) are required to implement AND gates
201
-
216
. A total of eight CLBs (i.e., CLBs
303
-
304
,
307
-
308
,
311
-
312
and
315
-
316
) are required to implement adder circuits
221
-
236
. As a result, at least sixteen CLBs are required to implement multiplier circuit
200
. This typically represents a significant portion of the FPGA resources. As a result, it is fairly inefficient to implement multiplier circuit
200
in an FPGA.
Some FPGAs enable one or more of AND gates
201
-
202
to be implemented in CLB
304
. However, even if both of AND gates
201
-
202
are implemented in CLB
304
, at least eight CLBs are required to implement multiplier circuit
200
. This still represents a significant portion of the FPGA resources. In general, multiplier circuits cannot be implemented efficiently in a conventional FPGA because of the relatively large number of CLBs required to form the multiplier circuit.
It would therefore be desirable to have an FPGA which is capable of efficiently performing multiplication operations.
Furthermore, within an FPGA, each CLB includes logic which is programmed to perform a particular function or functions desired by the user of the FPGA. In particular FPGAs, such as Xilinx's XC4000 family of devices, writable RAM-based look-up tables are included in each CLB. The writable RAM-based look-up tables can be used to create a “user-RAM” array. However, such user-RAM arrays are inefficient because creation of the RAM array detracts from the amount of logic available to perform other operations within the FPGA. That is, when a CLB is used to create user-RAM array, the logic capacity of the CLB is lost.
Moreover, the RAM arrays which can be conveniently created usi
Bever Hoffman & Harms LLP
Tokar Michael
Xilinx , Inc.
LandOfFree
Dedicated function fabric for use in field programmable gate... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dedicated function fabric for use in field programmable gate..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dedicated function fabric for use in field programmable gate... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2948855