Priority selection circuit

Details Priority selection circuit Priority selection circuit

1999-03-19

2002-07-16

Jeanpierre, Peguy (Department: 2819)

Coded data generation or conversion

Analog to or from digital conversion

Analog to digital conversion

C711S158000

Reexamination Certificate

active

06420990

ABSTRACT:

TECHNICAL FIELD
The present invention relates generally to priority selection circuits and more particularly to combinational encoder circuits that can be utilized with address encoders to generate priority selection addresses.
BACKGROUND OF THE INVENTION
Priority selection circuits typically receive a number of input signals that can have active and inactive levels. When multiple active input signals are received, the priority selection circuit selects one of the active input signals according to predetermined criteria. For example, input signals may have a particular order, and a priority selection circuit can always select the lowest active input signal in the particular order.
One particular application for priority selection circuits is in content addressable memories (CAMs). A CAM can include an array of CAM cells that compare stored values to an applied comparand value, and in the event there is a match, activate a match indication. A priority selection circuit will select among the multiple match indications to generate single match indication. In CAM applications, priority among multiple match indications can be established according to the physical location of the CAM cells. As just one example, priority can be given to the match indication corresponding to a lowest physical address for the CAM cell array.
In addition to a priority selection circuit, many CAMs will also include an address encoder. An address encoder receives a match signal having priority, and generates an address value from the match signal. The address signal can then be used to access data that corresponds to the match indication. In this way, a CAM will receive a comparand value and generate match signals. The CAM will then determine priority from the match signals, generate an address from a priority match signals, and finally provide output data according to the address.
To better understand the structure and operation of priority encoder circuits and address encoder circuits, a number of conventional circuits will be described.
Referring now to
FIG. 8
, a conventional priority selection circuit is set forth in a schematic diagram. The conventional priority selection circuit is designated by the general reference character
800
, and is shown to include a number of input inverters
802
,
804
,
806
, and
808
. Each input inverter (
802
-
808
) receives a corresponding input signal, shown as MATCH_IN0-MATCH_IN3. The input signals (MATCH_IN0-MATCH_IN3) of
FIG. 8
are active when at a logic low, and inactive when at a logic high. The output of inverter
802
is applied as an input to another inverter
810
.
The various input signals are also applied to disable gates, shown as items
812
,
814
and
816
. The disable gates (
812
,
814
and
816
) will provide a disabling output, which results in an inactive output signal, or alternatively, provide an enabling output which can result in an active output signal. Each disable gate (
812
,
814
and
816
) receives a corresponding input signal by way of an input inverter. In addition, each disable gate (
812
,
814
and
816
) also receives all previous inputs in non-inverted form. Thus, disable gate
812
receives input signal MATCH_IN1 by way of inverter
804
as well as previous input signal MATCH_IN0. Similarly, disable gate
816
receives input signal MATCH_IN3 by way of inverter
808
as well as previous input signals MATCH_IN0, MATCH_IN1 and MATCH
—IN
2. The disable gate arrangement of
FIG. 8
results in the priority selection of input signals (MATCH_IN0-MATCH_IN3) according to order of the signals. If MATCH_IN0 is active (low), the output of disable gates
812
,
814
, and
816
will all be high, regardless of whether the remaining input signals (MATCH_IN1-MATCH_IN3) are high or low. Similarly, provided MATCH_IN0 is inactive (high), if MATCH_IN1 is active (low), the output of disable gates
814
and
816
will be high, regardless of whether or not the input signals MATCH_IN2 or MATCH_IN3 are high or low. Finally, provided MATCH_IN0 and MATCH_IN1 are inactive (high), if MATCH_IN2 is active (low), the output of disable gate
816
will be high, regardless of whether or not the input signal MATCH 3 is high or low.
The priority selection circuit
800
also includes output gates
818
,
820
,
822
, and
824
. The output gates (
818
-
824
) each provide a corresponding output signal, shown as MATCH_OUT0-MATCH_OUT3. The outputs gates (
818
-
824
) can each receive a “prior hit” signal (PRIOR_HIT). The PRIOR_HIT signal indicates whether or not an input signal (not shown) having an even higher priority is active. Thus, when the PRIOR_HIT signal is active (high) the outputs of the output gates (
818
-
824
) will be low, regardless of the logic of the input signals (MATCH_IN0-MATCH_IN3).
Also set forth in
FIG. 8
is a local hit indicator circuit
826
. The prior hit generator
826
generates a local hit signal (LOCAL_HIT). The LOCAL_HIT signal can be used to generate a prior hit signal for subsequent priority selection circuits. The LOCAL_HIT signal will be active whenever one of the input signals (MATCH_IN0-MATCH_IN3) is active. In the particular arrangement of
FIG. 8
, the LOCAL_HIT signal is active when low, and the local hit indicator circuit
826
includes a NAND gate
828
and an inverter
830
. The NAND gate
828
receives each input signal (MATCH_IN0-MATCH_IN3) as an input. The output of NAND gate
828
is inverted by inverter
830
to generate the LOCAL_HIT signal.
While the conventional priority selection circuit of
FIG. 8
provides one way of selecting from among four input signals, such an approach may not be desirable due to the number of transistors required to implement the device. This may be particularly true for devices that must establish priority from among a large number of input signals. As just one example, the circuit of
FIG. 8
would have to be repeated 32 times for 128 input signals.
Circuit implementations that require a large numbers of transistors can be undesirable as a larger number of transistors can require more area on an integrated circuit. Additional area can translate directly into increased cost for each integrated circuit. Further, the number of interconnections required in a circuit can also impact area, as certain interconnections can require the formation of a contact within the integrated circuit. Accordingly, it is almost always desirable to provide a given functionality with as low a number of transistors as possible.
Referring now to
FIG. 9
, another conventional priority selection circuit is set forth in a schematic diagram. The priority selection has the same functionality as that set forth in
FIG. 8
, but reduces transistor count by essentially merging the logic functions of the inverters and disable gates. The circuit of
FIG. 9
is described in “Fully Parallel Integrated CAM/RAM Using Preclassification to Enable Large Capacities,”
IEEE Journal of Solid-State Circuits
, Vol. 31, No. 5, May 1996, by Schultz and Gulak. Like the example of
FIG. 8
, the circuits of
FIG. 9
can be considered to operate like a carry-look-ahead adder circuit, the LOCAL_HIT signal providing the carry signal. The circuit of
FIG. 9
is implemented with complementary metal-oxide-semiconductor (CMOS) gates, and so includes 38 transistors.
To better understand the operation of the conventional priority selection circuits of FIGS.
8
. and
9
, a truth table is set forth in FIG.
10
. Included in
FIG. 10
are the various combinations of input values MATCH_IN3-MATCH_IN0 and the resulting output values MATCH_OUT3-MATCH_OUT0. As shown by
FIG. 10
, for each of the various input signal combinations (MATCH_IN3-MATCH_IN0) only one output signal (MATCH_OUT3-MATCH_OUT0) will be active. The. one active output signal (MATCH_OUT3-MATCH_OUT0) will correspond to the lowest order input signal. For example, when the MATCH_IN3-MATCH_IN0 signal equals “0000,” the output signals MATCH_OUT3-MATCH_OUT0 are 0001, reflecting that the lowest active input signal is the MATCH_IN0 signal. When the MATCH_IN3-MATCH_IN0 signal equals “1001,” the

Affiliated with

Also associated with

Rating

Priority selection circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Priority selection circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Priority selection circuit will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2827998