Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-10-27
2004-10-19
Mai, Tan V. (Department: 2121)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S706000
Reexamination Certificate
active
06807556
ABSTRACT:
FIELD OF THE INVENTION
The field of invention relates to semiconductor device technology generally and, more specifically, to carry chain structures associated with semiconductor device design.
BACKGROUND
A carry chain is a series of logical structures that together perform an overall function. Each logical structure typically has an output term and a carry out term that are functions of a carry input term from a prior logical structure in the series and an input term.
FIG. 1A
shows a six bit incrementor function
100
implemented as a carry chain
100
having a sequence of six logical structures
101
-
106
. Incrementers are functions that add a value (e.g., “1”) to an input value (e.g., a 000000 input corresponds to an output of 000001). Input terms of the incrementer function are presented on input nodes A
0
through A
5
. The input terms are used to determine the output terms (on output nodes S
0
through S
5
) of the incrementer function.
Logical structures
101
through
106
contain one or more functional units (e.g., functional unit
110
within logical structure
105
) that typically accept one or more input terms and a carry input term to produce another output term or carry term. A functional unit effectively performs a logical operation upon or with its input value(s).
Referring to logical structure
105
as an example, note that the S
4
output term depends upon the carry value
107
produced by a functional unit
108
(executed by the prior logical structure
104
) and the fourth input term A
4
. Similar dependencies repeat themselves through the carry chain.
FIG. 1B
shows a possible logical structure implementation
160
. The logical structure
160
comprises a first look up table
161
(LUT) having three inputs
162
through
164
. The look up table
161
, which corresponds to a functional unit, may be used to effectively implement a logical operation upon or with the values presented at inputs
162
through
164
. Note that an input (e.g., input
164
) may be used as a carry input. The second lookup table
165
also receives inputs
162
through
164
. The first look up table
161
may be used to generate an output term
166
while the second look up table
165
may be used to generate a carry output term
167
.
Note that look up table
161
and
165
may be viewed as functional units within the logical structure
160
. In alternate embodiments, the function provided by the look up tables may be enhanced (or otherwise added to) by other logic components within the logical structure (such as by a multiplexer that drives the carry output
167
or an XOR gate that drives the output
166
). Actual logic may be used instead of look-up tables as well.
Significant amounts of time may be consumed by the carry chain
100
of
FIG. 1A
in order to execute the function. That is, referring to
FIG. 1
a
, in order to fully execute the overall function represented by the carry chain
100
each logical structure
101
-
106
must be executed. Thus the total propagation delay of the carry chain
100
(and thus of the overall function) corresponds to the summed propagation delay over all logical structures
101
-
106
. Because many vendors currently have a limit of one output term per logical structure, a logical structure has to be separately executed for each output term in the function performed by the carry chain. The time consumed as a result may be undesireable in various applications because each output term has to “wait” for all lower order terms to be determined beforehand.
SUMMARY OF THE INVENTION
An apparatus comprising two or more parallel carry chain structures, each of the carry chain structures comprising a series of logical structures, where at least one of the logical structures within each of the carry chain structures has an associated input node, output node and carry node. The input node corresponds to a function input term, the output node corresponds to an output term of the function and the carry node corresponds to a carry value to a following logical structure in the series of logical structures.
REFERENCES:
patent: 4853887 (1989-08-01), Jutand et al.
patent: 4885716 (1989-12-01), Little
patent: 5272662 (1993-12-01), Scriber et al.
patent: 5285406 (1994-02-01), Lynch et al.
patent: 5483478 (1996-01-01), Chiang
patent: 5487025 (1996-01-01), Partovi et al.
patent: 6003059 (1999-12-01), Bechade
Blakely , Sokoloff, Taylor & Zafman LLP
Mai Tan V.
Synplicity, Inc.
LandOfFree
Method and apparatus for parallel carry chains does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for parallel carry chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for parallel carry chains will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3300818