Coded data generation or conversion – Digital code to digital code converters
Reexamination Certificate
2000-02-01
2001-07-31
Williams, Howard L. (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Reexamination Certificate
active
06268807
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to encoder circuits, and more particularly to circuits that may be used in content addressable memories (CAMs) to prioritize and encode match indications.
BACKGROUND OF THE INVENTION
Priority encoder circuits typically receive a number of input signals that can have active and inactive levels. When multiple active input signals are received, a priority encoder can select one of the active input signals according to predetermined criteria. For example, input signals may have a particular order, and a priority encoder 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 encoder circuit can then select among the multiple match indications to generate single prioritized 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 value can be used to access data associated with a particular match signal. In some applications the address encoder is essentially a read only memory (ROM) that can provide addresses as output values. In this way, a CAM will receive a comparand value and generate match signals. The CAM will then determine priority from the match signals, and generate an address value. The address value may then be used to access associated data.
To better understand the structure and operation of priority encoder circuits and address encoder circuits, a conventional approach to prioritizing and encoding signals will be described.
Referring now to
FIG. 7
, a conventional priority encoder circuit is set forth in a schematic diagram. The conventional priority selection circuit is designated by the general reference character
700
, and is shown to receive eight input signals BM_
0
to BM_
7
, that are active when low, and provide eight output signals M_
0
to M_
7
, that are active when high. In the particular arrangement of
FIG. 7
, priority is provided according to position, top to bottom in the view presented.
The conventional priority encoder
700
includes an inverter
702
, seven two-input NOR gates
704
-
1
to
704
-
7
, seven n-channel metal-oxide-semiconductor (NMOS) transistors, and a number of p-channel MOS (PMOS) transistors. The PMOS transistors can be conceptualized as being arranged into rows
706
-
0
to
706
-
7
. Rows
706
-
0
to
706
-
7
can be conceptualized as being associated with input signals BM_
0
to BM_
7
, respectively. Further, the inverter
702
can be conceptualized as being associated with input BM_
0
, while NOR gates
704
-
1
to
704
-
7
can be conceptualized as being associated with inputs BM_
1
to BM_
7
, respectively.
In general, the circuit of
FIG. 7
operates by first precharging all input signals (BM_
0
to BM_
7
) to a high level. The n-channel MOS transistors, can turn on, driving one input of each NOR gate to a low level.
Subsequently, one or more of the input signals (M_
0
to M_
7
) is driven low. The p-channel MOS transistors are arranged to force the outputs of those NOR gates associated with lower priority input signals to a high level. For example, in the event the BM_
0
signal is low, the PMOS transistors of row
706
-
0
will turn on, resulting in a high input to NOR gates
704
-
1
to
704
-
7
. Consequently, associated outputs M_
1
to M_
7
are inactive (driven low).
If it is assumed that the inverter
702
and NOR gates
704
-
1
to
704
-
7
are complementary MOS (CMOS) circuits, the total transistor count for the priority encoder of
FIG. 7
is 65.
Referring now to
FIG. 8
, an address encoder is set forth in a schematic diagram. The address encoder is ROM, and is designated by the general reference character
800
. The ROM
800
receives prioritized output signals M_
0
to M_
7
from a priority encoder, and encodes a single active signal (M_
0
to M_
7
) into a three bit binary value X
2
, X
1
, X
0
.
The particular ROM
800
of
FIG. 8
includes PMOS pull-up transistors
802
-
0
to
802
-
2
coupled to output lines
804
-
0
to
804
-
2
. Provided signals M_
0
to M_
6
are inactive (low), pull-up transistors (
802
-
0
to
802
-
2
) maintain the output lines (
804
-
0
to
804
-
2
) high. However, when one of the signals M_
0
to M_
6
is active, one or more of the output lines (
804
-
0
to
804
-
2
) is driven low by a pull-down NMOS transistors (
806
-
00
to
806
-
23
) to generate a corresponding binary output value (X
2
-X
0
).
It is noted that the total transistor count for the ROM
800
of
FIG. 8
is fifteen. Further, because the NMOS transistors (
806
-
00
to
806
-
23
) must “overpower” the PMOS pull-up transistors (
802
-
0
to
802
-
2
), each NMOS transistor can be a relatively large device. As a result, a priority encoder/ROM combination of
FIGS. 7 and 8
includes eighty transistors total, including ROM NMOS transistors of relatively large size.
A concern with nearly all integrated circuits is the overall size of the device. Smaller integrated circuit (IC) sizes can translate into reduced manufacturing costs. Smaller IC sizes can also be desirable as they can present smaller “footprints” on a circuit board and thus contribute to smaller overall electronic device size. Further, reducing one circuit section of an IC can allow more room for other circuit sections.
In light of the desirability of smaller circuit sizes, it would be desirable to arrive at some way of providing priority encoder and address encoding functions with a smaller circuit than the conventional approach.
SUMMARY OF THE INVENTION
According to the disclosed embodiments, a circuit is provided that can prioritize input signals and encode the signal having the highest priority. The encoded value can be provided on a number of output lines. Particular output lines can be driven by detect circuits when a particular input signal is activated. When more than one input signal is active, those input signals having a lower priority are prevented from propagating to, and activating, corresponding detect circuits.
According to one aspect of the embodiments, the circuit can include detect circuits and passgate circuits arranged into columns, each column corresponding to a particular output line. When a detect circuit of a column is activated, the passgate circuits of the same column are disabled, preventing lower priority input signals from further propagating to lower priority detect circuits.
According to another aspect of the embodiments, each detect circuit includes one transistor and each passgate circuit has two transistors, resulting in a compact circuit.
REFERENCES:
patent: 4348741 (1982-09-01), McAlister et al.
patent: 4566064 (1986-01-01), Whitaker
patent: 4831573 (1989-05-01), Norman
patent: 4887084 (1989-12-01), Yamaguchi
patent: 5123105 (1992-06-01), Wyland et al.
patent: 5160923 (1992-11-01), Sugawara et al.
patent: 5230054 (1993-07-01), Tamura
patent: 5265258 (1993-11-01), Fiene et al.
patent: 5355013 (1994-10-01), Parker
patent: 5508641 (1996-04-01), Appenzeller et al.
patent: 5511222 (1996-04-01), Shiba et al.
patent: 5555397 (1996-09-01), Sasama et al.
patent: 5602545 (1997-02-01), Ishii et al.
Miller Michael H.
Voelkel Eric H.
Lara Technology, Inc.
Sako Bradley T.
Williams Howard L.
LandOfFree
Priority encoder/read only memory (ROM) combination 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 encoder/read only memory (ROM) combination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Priority encoder/read only memory (ROM) combination will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2505539