Increasing priority encoder speed using the most significant...

Details Increasing priority encoder speed using the most significant... Increasing priority encoder speed using the most significant...

1999-11-12

2003-01-07

Nguyen, Than (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S158000, C711S167000, C711S217000, C711S220000, C365S049130, C365S050000

Reexamination Certificate

active

06505271

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a priority encoder. More specifically, the present invention relates to a priority encoder having increased processing speed for the least significant address bits.
DISCUSSION OF RELATED ART
CAM cells are defined as memory cells that are addressed in response to their content, rather than by a physical address within an array. Rows of CAM cells within an array assert or de-assert associated match signals indicating whether or not each CAM cell row matches the data values applied to the CAM cell array. These match signals are provided to a priority encoder that in turn provides the address of the row of matching CAM cells having the highest priority.
FIG. 1
is a block diagram of a conventional 8n-row by 5-column CAM cell memory array
100
and a 3-bit priority encoder
101
. The CAM cells are labeled M
X, Y
, where X is the row of the array, and Y is the column of the array. Thus, the array includes CAM cells M
0, 0
to M
7, 4
. The required number of address signals provided by priority encoder
101
is defined as the base
2
logarithm of the number of rows in CAM cell memory array
100
, rounded up.
Each of the CAM cells in array
100
is programmed to store a data value. In the described example, the data value stored in each CAM cell is indicated by either a “0” or a “1” in brackets. For example, CAM cells M
0, 0
, M
0, 1
, M
0, 2
, M
0, 3
, and M
0, 4
store data values of 1, 1, 1, 1, and 1, respectively. Each row of CAM cells is coupled to a common match line to provide a match signal for the row. For example, CAM cells M
0, 0
, M
0, 1
, M
0, 2
, M
0, 3
, and M
0, 4
are coupled to the common match line that provides the MATCH
0
signal.
The array of CAM cells is addressed by providing a data value to each column of CAM cells. Thus, data values D
0
, D
1
, D
2
, D
3
, and D
4
are provided to columns
0
,
1
,
2
,
3
, and
4
, respectively. Note that complimentary data values D
0
#, D
1
#, D
2
#, D
3
#, and D
4
# are also provided to columns
0
,
1
,
2
,
3
, and
4
, respectively. If the data values stored in a row of the CAM cells match the applied data values D
0
, D
1
, D
2
, D
3
, and D
4
, then a match condition occurs. For example, if the data values D
0
, D
1
, D
2
, D
3
, and D
4
are 0, 1, 0, 0, and 0, respectively, then the data values stored in the CAM cells of row
1
match the applied data values. Under these conditions, the MATCH
1
signal is high. The high state of the MATCH
1
signal is shown by the value “1” in brackets. Because the applied data values D
0
, D
1
, D
2
, D
3
, and D
4
also match the data values stored in the CAM cells of rows
3
and
7
, the MATCH
3
and MATCH
7
signals also are high. Because the applied data values D
0
, D
1
, D
2
, D
3
, and D
4
do not match the data values stored in the CAM cells of rows
0
,
2
, or
4
-
6
, the MATCH
0
, MATCH
2
, and MATCH
4
-MATCH
6
signals are pulled low.
Priority encoder
101
receives the MATCH
0
-MATCH
7
signals. Priority encoder
101
is a 3-bit priority encoder because three address signals are required to identify the MATCH
0
-MATCH
7
signals. Each of the MATCH
0
-MATCH
7
signals is received at an address, which is noted beside each match signal. For example, the MATCH
1
signal is received at address “001”. Priority encoder
101
provides the address of the asserted match signal with the highest priority (lowest address) as the priority address A
2
-A
0
. Of the asserted match signals MATCH
1
, MATCH
3
, and MATCH
7
, the MATCH
1
signal has the highest priority. Therefore, the address of the MATCH
1
signal (i.e., “001”) is provided as the priority address A
2
-A
0
. Thus, the logic value of priority address bit A
2
is “0”, of priority address bit A
1
is “0”, and of priority address bit A
0
is “1”. Priority encoder
101
asserts the HIT# signal low when at least one of the match signals has a logic high value. This logic low value of the HIT# signal is denoted by a “0” in brackets. A logic low value of the HIT# signal means that the priority address A
2
-A
0
is valid.
Conventionally, the bits of the priority address A
2
-A
0
are generated in parallel in response to the MATCH
0
-MATCH
7
signals. Thus, each of the priority address bits A
2
-A
0
is independently generated. As a result, the time taken to provide a valid address from the priority encoder is equal to the maximum time taken to calculate any one of the priority address bits A
2
-A
0
.
FIG. 2
is a truth table for 3-bit priority encoder
101
of FIG.
1
. Each row is labeled with one of the MATCH
0
-MATCH
7
signals and each column is labeled with one of the priority address bits A
2
-A
0
. The table of
FIG. 2
shows the priority address associated with each match line. Thus, the priority address of the MATCH
3
signal is “100”, with the priority address bit A
2
equal to “0”, the priority address bit A
1
equal to “1”, and the priority address bit A
0
equal to “1”. The match signal with the highest priority in this scheme is the match signal with the lowest priority address. Thus, if all of the MATCH
0
-MATCH
7
signals are asserted high, the MATCH
0
signal (i.e., the signal at address “000”) has priority over the MATCH
1
-MATCH
7
signals (i.e., the signals at addresses “001”-“111”). In the above example, the MATCH
1
signal has the highest priority of the asserted MATCH
1
, MATCH
3
, and MATCH
7
signals.
FIG. 3
is a schematic diagram of a conventional A
0
generator
300
. A
0
generator
300
includes inverters
301
-
306
, n-channel transistors
307
-
316
and p-channel transistor
317
. A
0
generator
300
is used to generate the least significant bit (LSB) (i.e., the A
0
signal) of the priority address. A
0
generator
300
typically exhibits the largest delay in the generation of priority address bits A
2
-A
0
. Each pass transistor
311
-
316
contributes a resistance (i.e., delay) to the determination of the least significant priority address bit A
0
. Thus, if the only matching signal is the lowest priority match signal (i.e., the MATCH
7
signal), then the total (and worst case) delay in determining the least significant priority address bit A
0
is the sum of the delays caused by pass transistors
311
-
316
. If each pass transistor has the same resistance, the total delay for A
0
generator
300
is equal to 6 times the delay attributable to one pass transistor, or 6 pass transistor delays.
FIG. 4
is a schematic diagram of another conventional A
0
generator
400
. A
0
generator
400
includes inverters
401
-
407
and n-channel transistors
408
-
421
. A
0
generator
400
also is used to generate the least significant priority address bit A
0
. Each of pass transistors
415
-
420
contributes resistance during the determination of priority address bit A
0
that results in the worst case delay. If each of pass transistors
415
-
420
has the same resistance, the worst case delay for A
0
generator
400
is equal to 6 times the delay attributable to one pass transistor, or 6 pass transistor delays.
It would therefore be desirable to have a priority encoder that generates the least significant priority address bit A
0
more quickly than A
0
generators
300
and
400
.
SUMMARY
Accordingly, the present invention provides an improved method of generating a priority address that includes the steps of: (1) providing a plurality of match signals from a CAM cell array to a priority encoder, (2) generating a most significant address bit of the priority address in response to a first set of the match signals, and (3) generating a least significant address bit of the priority address in response to the most significant address bit and a second set of the match signals.
In one embodiment, the step of generating the least significant address bit is implemented by splitting the determination of the least significant address bit into two separate determinations, and the using the most significant address bit to select the result of one of these two separate determinations.
Using the most significant address bit to

Affiliated with

Also associated with

Rating

Increasing priority encoder speed using the most significant... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Increasing priority encoder speed using the most significant..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Increasing priority encoder speed using the most significant... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3011132