Optimization of comparator architecture

Details Optimization of comparator architecture Optimization of comparator architecture

2001-12-12

2004-02-10

Garbowski, Leigh M. (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

Reexamination Certificate

active

06691283

ABSTRACT:

FIELD OF THE INVENTION
This invention relates to digital comparators, and particularly to comparators for use in very large scale integrated circuits (VLSI circuits).
BACKGROUND OF THE INVENTION
Comparators are widely used in VLSI circuits, and are one of the most commonly used datapath modules in application specific integrated circuits (ASICs). The performance of the implemented comparator highly affects the quality of the VLSI circuit, and its timing closure.
Prior digital comparators have employed an architecture based on AND and OR elements. One such circuit, known as a dichotomizing circuit, achieves a circuit depth of 2 log
—
2n+O(1) and a complexity of 3n−O(log
—
2n), where n is the number of bits of the comparator. While the complexity of such comparators is minimally acceptable, the depth, and hence the time delay, is large.
The present invention is directed to a comparator architecture based on a Fibonacci series that provides an approach to the design of comparators based on the global analysis of their Boolean identities. The resulting comparators have smaller depth and time delay. In some cases, circuit area is reduced.
SUMMARY OF THE INVENTION
In accordance with the present invention a comparator is embodied in an integrated circuit and is characterized by an architecture having output functions h_n and v_n that depend from input functions U[i]=AND(NOT(A[i]), B[i]) and V[i]=OR(NOT(A[i]), B[i]), where A[i] and B[i] are inputs to the comparator, and functions h_n, v_n are defined as
h_n
=
 
⁢
h_n
⁢
 
⁢
(
U
⁡
[
0
]
,
U
⁡
[
1
]
,
V
⁡
[
1
]
,
…
⁢
 
,
U
⁡
[
n
-
1
]
,
V
⁡
[
n
-
1
]
)
=
 
⁢
OR
⁢
 
⁢
(
U
⁡
[
n
-
1
]
,
AND
⁢
 
⁢
(
V
⁡
[
n
-
1
]
,
U
⁡
[
n
-
2
]
)
,
…
⁢
 
,
AND
 
⁢
(
V
⁡
[
n
-
1
]
,
…
⁢
 
,
V
⁡
[
1
]
,
U
⁡
[
0
]
)
)
,
and
v_n
=
 
⁢
v_n
⁢
 
⁢
(
V
⁡
[
0
]
,
…
⁢
 
,
V
⁡
[
n
-
1
]
)
=
 
⁢
AND
⁢
 
⁢
(
V
⁡
[
0
]
,
…
⁢
 
,
V
⁡
[
n
-
1
]
)
.
The comparator is further characterized by a minimal depth defined by a recursive expansion of functions h_n=OR(h_k, AND(v_k, h_{n−k})) and v_n=AND(v_k, v{n−k}), where k=F_l and n−k=F_{l−1}, l satisfies F_l<n=F_{l+1}, where {F_l} is a Fibonacci series and n is the number of bits of an input to the comparator.
In some embodiments, a distribution of negations of modules of the comparator is optimized. A set of delay vectors is identified and recursively compared to derive a set of minimum vectors. A vector having a minimum norm is selected from the set of minimum vectors.
The comparator is characterized by the use of logic elements having a function OR(NOT(a),b) instead of EXCLUSIVE OR functions. In some embodiments, the comparator is further characterized by the inclusion of OR logical functions in place of NOR functions and AND logical functions in place of NAND functions.
In some embodiments, a LEQ flag is input to the comparator to signify strict or non-strict comparison of the input numbers.
In some embodiments, the comparator is constructed using 2-input elements mapped from 3-input elements in a library. In other embodiments, the comparator is constructed using 4-input elements constructed from 2-input elements. In other embodiments, the comparator is constructed having six outputs.
In other embodiments, the invention is manifest in a computer readable program containing code that, when executed by a computer, causes the computer to perform the process steps to design a comparator for an integrated circuit based on a Fibonacci series and employing 2-input elements of minimal depth.


REFERENCES:
patent: 4187500 (1980-02-01), Stakhov et al.

Affiliated with

Also associated with

Rating

Optimization of comparator 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 Optimization of comparator architecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimization of comparator architecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3313174