Electronic digital logic circuitry – Multifunctional or programmable
Reexamination Certificate
1997-09-16
2002-03-19
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
C326S039000, C326S040000, C326S041000, C326S113000
Reexamination Certificate
active
06359466
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a circuit for providing a carry for a circuit performing an addition or subtraction operation. More particularly, the present invention relates to a circuit for performing a carry in a system utilizing look up tables.
2. Description of the Related Art
Circuitry for providing a carry operation when look up tables are used to perform an addition or subtraction operation has typically taken one of two forms. In a first form, the look up tables are programmed to determine a carry out based at least on two data inputs and a carry input. In a second form, to increase operation speed over performing an entire operation using look up tables, dedicated logic is utilized to determine the carry instead of a look up table.
To illustrate programming of look up tables to determine a carry, reference is made to FIG.
1
and FIG.
2
.
FIG. 1
shows a block diagram of components for a 3-input lookup table. The look up table of
FIG. 1
includes a three input decoder, 8 memory cells and a multiplexer. The three input decoder decodes a signal provided to the look up table inputs to control the multiplexer so that only one of the memory cells provide a signal to the output. The memory cells can be programmed in any arbitrary manner to provide a desired look up table output based on inputs to the look up table.
FIG. 2
is a table illustrating programming of the memory cells in the look up table of
FIG. 1
to determine a carry in an addition operation. In Table 2, it is assumed that A and B are binary numbers being added, and C is a carry in from a previous operation. The output then provides an indication of the carry out of the binary addition of A and B with the carry in C.
FIG. 3
illustrates typical dedicated carry logic utilized in conjunction with look up tables to free up the look up tables for purposes other than determining carries, and potentially speed up the carry operations. The logic includes an exclusive OR (XOR) gate
2
and a multiplexer
4
. The XOR gate
2
receives signals representing two numbers to be added, A
i
and B
i
. The multiplexer
4
has a select input connected to the XOR gate
2
output, a first input receiving the A
i
signal which is provided as the output of multiplexer
4
when select is 0, and a second input receiving a carry in C
i
signal which is provided as the output of multiplexer
4
when select is 1. The output of the multiplexer
4
then provides a carry out C
i+1
of the operation A
i
+B
i
+C
i
.
FIG. 4
provides a table illustrating operation of the XOR gate
2
and multiplexer
4
of FIG.
3
. In
FIG. 4
, A
i
and B
i
inputs with the carry in, C
i
, are followed by a carry out, C
i+1
, which is the carry of the operation A
i
+B
i
+C
i
. As shown, if A
i
=B
i
, C
i+1
is defined without reference to C
i
, and is equal to either the A
i
or B
i
input. This operation is performed with the logic of
FIG. 3
, with A
i
being selected to provide the output of multiplexer
4
, or C
i+1
, by the XOR gate
2
only when A
i
=B
i
. As further shown in
FIG. 4
, if A
i
≠B
i
, then C
i+1
=C
i
. This operation is performed with the logic of
FIG. 3
, with C
i
being selected as the output of multiplexer
4
, or C
i+1
, when A
i
≠B
i
. In other words, in
FIG. 3
, C
i+1
is created by multiplexing between the A
i
input and C
i
.
In
FIG. 3
, additional signals representing numbers A
i+1
and B
i+1
are added with a carry in provided by the output of multiplexer
4
. The signals representing numbers A
i+1
and B
i+1
are provided to inputs of an additional XOR gate
8
. The output of the XOR gate is provided to the select input of an additional multiplexer
6
, while the output of multiplexer
4
provides one input to the multiplexer
6
, and the signal representing the number A
i+1
provides another input to the multiplexer
6
. The signal A
i+1
is provided as the multiplexer
6
output when select is 0, and the output of multiplexer
4
is provided as the multiplexer
6
output when select is 1. The output of the multiplexer
6
then provides a carry out C
i+2
of the operation A
i+1
+B
i+1
+C
i+1
. Operation of XOR gate
8
with multiplexer
6
is similar to operation of XOR gate
2
with multiplexer
4
as described with reference to FIG.
4
.
In
FIG. 3
, additional multiplexers
10
-
11
are further provided to selectively provide the carries C
i
and C
i+1
to look up tables for subsequent operations. Typical circuitry using look up tables with either dedicated carry logic as shown in
FIG. 3
, or look up tables configured to provide carry operations can be found in field programmable gate arrays (FPGAs).
SUMMARY OF THE INVENTION
The present invention provides a high speed carry operation with minimal circuitry by using look up tables in conjunction with dedicated logic provided after the look up tables.
The present invention configures the dedicated logic provided after the look up tables to be versatile so that in addition to providing a carry, the circuitry can provide the result of an addition or subtraction operation and can enable two 3-input look up tables to be combined to form a 4-input look up table. With such versatility, the circuitry of the present invention can be configured to provide an adder-subtractor, an up/down counter, an accumulator and a pre-loadable counter using 3-input or 4-input look up tables. If the 3-input look up tables are combined to form a 4-input look up table, then the carry logic can be used to implement a wide gate, such as an AND gate, which can AND the output of a large number of 4-input look up tables.
To provide a carry, the present invention includes a first multiplexer having a first input receiving a carry in C, a select input coupled to the output of a first 3-input look up table, and a second input coupled to the output of a second 3-input look up table. The two 3-input look up tables each receive two input signals A and B representing numbers to be added or subtracted and a third input signal ADD/SUB indicating if addition or subtraction is desired. The first look up table is programmed to provide A(+)B, while the second look up table is programmed to provide A*B, where (+) indicates a Boolean exclusive OR, and * indicates a Boolean AND. As configured, with addition selected using the ADD/SUB signal, the first multiplexer output provides the carry out of the operation A+B+C. With subtraction selected using the ADD/SUB signal, a 2's complement is provided with B complemented in the look up tables, so the output of the first multiplexer will provide the carry out of the operation A−B, with the carry in C considered.
To provide a result of an addition or subtraction, the present invention further includes a second multiplexer having a first input receiving the carry in C, a second input receiving the inverse of the carry in C, and a select input coupled to the output of the first look up table. The output of the second multiplexer provides a signal S which is the result of the addition or subtraction of A and B with the carry in C considered.
With addition and subtraction both being provided, a counter can be formed by registering an S output and feeding that back to its corresponding A input. By providing an appropriate B input, an up/down counter or a pre-loadable counter can be formed.
To selectively enable the two 3-input look up tables in a circuit to be combined to form a 4-input look up table, the present invention further includes a third multiplexer having a first input connected to the output of the first look up table, a second input coupled to the output of the second look up table, and an output connected to the select input of the first and second multiplexers. The output of the third multiplexer then provides the 4-input look up table output when the 4-input look up table is desired. The select input to the third multiplexer is pr
Fliersler Dubb Meyer & Lovejoy LLP
Paik Steven S.
Vantis Corporation
LandOfFree
Circuitry to provide fast carry does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Circuitry to provide fast carry, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Circuitry to provide fast carry will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2835868