Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-08-31
2003-02-04
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
Reexamination Certificate
active
06516335
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention relates to an incrementer/decrementer and, more particularly, to an incrementer/decrementer having a reduced internal block fanout architecture that reduces propagation delays and which can be implemented without realizing area penalties.
BACKGROUND OF THE INVENTION
One known type of incrementer/decrementer architecture is characterized by an internal block fanout of (incrementer/decrementer width)/2 and a routing complexity of a single propagate signal. One disadvantage of this type of architecture is that performance limitations result from the excessive internal block fanout of the incrementer/decrementer.
FIG. 1
illustrates this type of architecture. Each of the “Os” in
FIG. 1
represent a logic circuit, each of which is comprised of one or more logic gates. Bit
0
and bits
9
through
15
each have an internal block fanout of 1, bits
1
,
2
and
4
through
7
each have an internal block fanout of 2, bit
3
has an internal block fanout of 5, and bit
8
has an internal block fanout of 8.
Therefore, the maximum internal block fanout for the incrementer/decrementer illustrated in
FIG. 1
is
8
, which is extremely large. The propagation delays resulting from the large internal block fanout greatly limit its performance. However, the routing complexity is relatively simple, which is an advantage of this type of architecture in terms of silicon area required to realize the incrementer/decrementer.
A second known type of incrementer/decrementer architecture, which is not shown, is characterized by an internal block fanout of 1 and a routing complexity of (incrementer/decrementer width)/2. One disadvantage of this second type of architecture is that the routing complexity results in unrealistic silicon area penalties, although the single internal block fanout reduces propagation delays. If the routing complexity is simplified, the internal block fanout increases dramatically, thereby resulting in performance limitations in terms of large propagation delays.
Accordingly, a need exists for an incrementer/decrementer architecture that eliminates performance limitation problems caused by excessive internal block fanout and which is efficient in terms of the silicon area required in order to accommodate the routing complexity of the incrementer/decrementer.
SUMMARY OF THE INVENTION
The present invention provides an incrementer/decrementer having a reduced internal block fanout that is achieved efficiently in terms of the silicon area needed to implement the incrementer/decrementer. The incrementer/decrementer of the present invention is characterized by a modified “binary tree” structure and having redundant overlapping carry generate/propagate signal operators located in such a manner that the maximum internal block fanout is equal to (incrementer/decrementer width)/8 for incrementer/decrementers having a width of at least 16 bits. For incrementer/decrementers having a width of less than 16 bits, the internal block fanout is 2.
As a result of the redundant overlapping operators, the internal block fanout is reduced without realizing area penalties. Since increases in routing complexity are accomplished by redundantly overlapping the operators, no increases in area are required for implementing the incrementer/decrementer of the present invention.
In accordance with the present invention, any increases in routing complexity can be accomplished within the minimum X-by-Y area of each stage of the incrementer/decrementer. For each stage of a incrementer/decrementer, the minimum X dimension of the stage is defined by the number of bits being added together by the incrementer/decrementer. The minimum Y dimension of each stage is defined by the logic circuits, also referred to herein as the operators, implemented in the stage for performing the logical operations. Therefore, the minimum area of each stage is defined by the minimum X dimension times the minimum Y dimension, hereinafter referred to as the minimum X-by-Y area.
With existing architectures, when attempts have been made to decrease the internal block fanout of the incrementer/decrementer by increasing the routing complexity, this was not accomplished within the minimum X-by-Y area. Rather, the overall area of the incrementer/decrementer was increased due to increases in the area of one or more stages of the incrementer/decrementer needed to accommodate the additional routing.. In accordance with the present invention, all routing for each stage can be, but does not have to be, accomplished within the minimum X-by-Y area for the stage. Therefore, the overall performance of the incrementer/decrementer of the present invention can be optimized while meeting minimum area requirements.
Other features and advantages of the present invention will become apparent from the following description, drawings and claims.
REFERENCES:
patent: 4153939 (1979-05-01), Kudou
patent: 4486851 (1984-12-01), Christopher et al.
patent: 4685078 (1987-08-01), Torres
patent: 5018094 (1991-05-01), Fischer et al.
patent: 5027310 (1991-06-01), Dairymple
patent: 5635858 (1997-06-01), Chang et al.
patent: 5636156 (1997-06-01), Mikan et al.
patent: 5877972 (1999-03-01), Aoki et al.
Simon Knowles, A Family of Adders, Proceedings of the Symposium on Computer Arithmetic, Apr. 14, 1999.
Dix Gregory S.
Lin Linda L.
Martin Robert J
Agilent Technologie,s Inc.
Malzahn David H.
Neudeck Alex J.
LandOfFree
Incrementer/decrementer having a reduced fanout architecture does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Incrementer/decrementer having a reduced fanout architecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incrementer/decrementer having a reduced fanout architecture will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3166266