JP2001256787A - Priority encoder - Google Patents

Abstract

(57) [Summary] [Problem] To reduce the number of elements in a large-capacity content addressable memory,
A priority encoder capable of prioritizing coincidence output signals with a small layout area. A priority circuit divides m input signals into m / n groups of n signals, assigns priorities among the grouped groups, and uses an encoding circuit to assign the highest priority group. The above-mentioned problem is solved by separately encoding and outputting the memory address corresponding to, and the memory address corresponding to the highest-priority input signal included in the highest-priority group.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a priority encoder for sequentially outputting memory addresses corresponding to a plurality of coincidence output signals in which coincidence is detected in a large-capacity associative memory (hereinafter referred to as CAM) in accordance with a priority order. Things.

[0002]

2. Description of the Related Art The above-mentioned CAM has a function of comparing stored data stored therein with search data inputted from the outside, and outputting a memory address at which the matched stored data is stored. is there. At this time, if there are a plurality of coincidence output signals for which coincidence is detected, the memory addresses corresponding to all the coincidence output signals cannot be output at the same time. Then, the corresponding memory addresses are output in order from the one with the highest priority.

A conventional priority encoder and its problems will be described below with reference to FIGS. 7 to 10 by taking as an example a case where 4K (= 4096) priorities are assigned as coincidence output signals.

The priority encoder 6 shown in FIG.
0 is a priority disclosed in Japanese Patent Application Laid-Open No. Hei 5-189799, which assigns priorities to a plurality of coincidence output signals for which coincidence is detected, according to a preset priority. Circuit 62
And an encoding circuit 64 for encoding and outputting a memory address corresponding to the highest priority coincidence output signal selectively output by the priority circuit.

First, in the illustrated example, the priority circuit 62 includes a plurality of priority blocks hierarchized into three layers, a first layer (256), a second layer (16), and a third layer (one). 66 are provided. In the example shown in FIG. 8, the priority block 66 assigns priorities to 16 input signals, and includes four OR gates 68, an OR gate 70, and an input signal priority circuit 72. I have.

The input signal is ORed by four OR gates 68 each, and the OR gate 70 ORs the output signals from the four OR gates 68, ie, 16 OR gates. The logical sum of the input signals is obtained and output as an OR signal. In other words, if this OR signal is at a high level, it is understood that among the 16 input signals input to the priority block 66, there is a signal at which a match is detected, that is, a signal for which a match is detected.

The input signal priority circuit 72 is shown in FIG.
As shown in the figure, 16 priority units 74
An N-type MOS transistor for discharging (hereinafter referred to as NMOS) 76; and a P-type M for precharging.
An OS transistor (hereinafter, referred to as a PMOS) 78 is provided. Also, each priority unit 74
Represents an inverter 80, a NOR gate 82, an AND gate 84, two PMOSs 86 and 88, and an NMOS 9
0.

In the input signal priority circuit 72, first, the control line is set to low level. At this time, the PMOS 86 and the precharge PMOS 78 of each priority unit 74 are turned on, and both ends (source and drain) of the NMOS 90 connected in series between the priority units 74 are precharged to a high level. Also, the input signal priority circuit 72 includes:
Sixteen input signals are input corresponding to each priority unit 74.

Here, it is assumed that, for example, 16 input signals are LHHL... L from the upper side in the figure. Note that L indicates a low level and H indicates a high level. It is also assumed that the uppermost input signal has the highest priority, the lower priority sequentially decreases, and the lowermost input signal has the lowest priority. The input signal is sent to each priority unit 7
4, the output is inverted by the inverter 80, and the inverted output is input to the gates of the NMOS 90 and the PMOS 88.

After a match search is performed and the level of the input signal is determined, the control line is set to the high level. This allows
The PMOS 86 and the precharge PMOS 78 of each priority unit 74 are turned off, and the discharge NMOS 76 is turned on. Accordingly, a node between the NMOS 90 of the uppermost priority unit 74 and the NMOS 76 for discharging is discharged to a low level via the NMOS 76 for discharging.

First, since the uppermost input signal in the figure is at a low level, the inverted output of the inverter 80 is at a high level, and the NMOS 90 is turned on and the PMOS 88 is turned off.
Therefore, the NMOS 90 of the uppermost priority unit 74 and the second priority unit 7
The node between the fourth NMOS 90 and the NMOS 90 of the uppermost priority unit 74 and the NMOS 76 for discharging are discharged to a low level.

Subsequently, since the second input signal from the top is at the high level, the inverted output of the inverter 80 is at the low level, the NMOS 90 is turned off, and the PMOS 88 is turned on. Therefore, the NMOS 90 of the second priority unit 74 and the NMOS 90 of the third priority unit 74
The node between the second priority unit 74 and the NMOS 90 is charged up through the PMOS 88 of the second priority unit 74, and maintains the high level precharged through the PMOS 86.

At this stage, since the NMOS 90 of the second priority unit 74 is turned off, all the subsequent nodes between the NMOSs 90 are maintained at the high level. Therefore, the output signal from the NOR gate 82 becomes LHLL... L in order from the upper side in the figure, and only the output of the second NOR gate 82 becomes high level. If the enable signal from the higher-order priority block 72 is at a high level, the second AND gate 84 also outputs a high level.

That is, in each priority block 72, the logical sum of the input 16 input signals is calculated, and this is used as an OR signal, and the priority level of the higher hierarchical level is determined.
Output as an input signal to the block 72, prioritize these 16 input signals, and set only the output signal corresponding to the highest priority input signal among the input signals for which coincidence is detected to the high level. , To the encoding circuit 64.

In the priority circuit 62 shown in FIG.
Sixteen coincidence output signals are input to the first hierarchy priority blocks 66, respectively, and the OR1 signals output from the sixteen first hierarchy priority blocks 66 are respectively assigned to the corresponding second hierarchy priority blocks. The OR2 signal input as the input signal of the second hierarchy 66 and output from the 16 priority blocks 66 of the second hierarchy is input as the input signal of the priority block 66 of the third hierarchy.

The enable signal of the third-level priority block 66 is at a high level (power supply potential). An output signal from the third-level priority block 66 is input as an enable signal of the corresponding second-level priority block 66, and an output signal from the second-level priority block 66 corresponds to the corresponding output signal. As an enable signal to the priority block 66 of the first hierarchy.

In the priority circuit 62, first, the first
In each of the 256 priority blocks 66 of the hierarchy, OR1 which is the logical sum of 16 coincidence output signals
A signal is output. These 256 OR signals are 1
Each of the six signals is input to a corresponding one of the priority blocks 66 of the second hierarchy. In each of the sixteen priority blocks 66 of the second hierarchy, an OR2 signal, which is a logical sum of the sixteen OR1 signals, is output. .

The third-level priority block 66
Since the enable signal is always at the high level, the 16 priority blocks 66 in the second hierarchy
Are prioritized for the OR2 signal output from the.
The output signal from the third hierarchy priority block 66 is the 16th priority block 6 of the second hierarchy.
6, the highest priority O2 signal among the OR2 signals from
Only the output signal corresponding to the R2 signal becomes high level.

The third-level priority block 66
Is fed back as an enable signal to the corresponding second-level priority block 66. At this time, only the priority block 66 of the second hierarchy in which the enable signal is at the high level is enabled, and the highest priority of the OR1 signals from the corresponding 16 priority blocks 66 of the first hierarchy at the high level Only the output signal corresponding to the OR1 signal is at the high level.

Subsequently, the output signal from the second hierarchy priority block 66 is fed back as an enable signal to the corresponding first hierarchy priority block 66. Similarly, only the first-level priority block 66 in which the enable signal is at the high level is enabled, and the output signal corresponding to the high-priority coincidence output signal among the 16 coincidence output signals to be inputted is the highest level. Only the high level.

As described above, the three priority blocks 66 of the first, second and third layers corresponding to the high-priority coincidence output signal among the coincidence output signals for which coincidence has been detected. Only the enabled state is set, and only the output signal corresponding to the high-level highest priority coincidence output signal is at the high level. And these first,
Each priority block 66 of the second and third layers
Is input to an encoding circuit 64 described below.

The encoding circuit 64 includes an encoder 92 and an output circuit 94 as shown in FIG.
Although not shown, in the encoding circuit 64, one encoder 92 is provided corresponding to each priority block 66. Of the plurality of priority blocks 66, as described above,
Encoders 92 corresponding to the three priority blocks 66 of the enabled first, second and third layers
Only works.

First, the encoder 92 encodes a memory address corresponding to 16 output signals input from the priority block 66, and is provided with four NMOSs 96 for one output signal.
The output circuit 94 inverts the amplified output of the encoder 92 and outputs the inverted output.
98, an inverter 100, and a PMOS 102.

In the encoding circuit 64, first, the control line is set to low level. At this time, as can be seen from FIG. 9, the 16 output signals from the priority block 66 are all low level, and the two PMOSs 98, 1
02, the signal line 104 is precharged to a high level. Thereafter, as described above, the 16 output signals from the first, second, and third hierarchy priority blocks 66 corresponding to the highest priority matching output signal are input to the corresponding encoders 92, respectively.

In the encoder 92, the signal line 104 corresponding to the high-level output signal is pulled down to the low level in accordance with the memory address, and is inverted and output by the inverter 100 of the output circuit 94. 1st to 15th from the top in the figure
The fourth four NMOSs 96 each have a memory address 1
15 are connected to the signal line 104. In the case of the memory address 0, the signal line 104 is held at the high level, and this is inverted and output by the output circuit 94, and all 0s are output as the memory address.

In the conventional CAM, the memory array is divided into blocks, and the priority encoder 60 is shared by a plurality of blocks, so that the priority
The number of coincidence output signals input to the encoder 60 has been reduced to, for example, about 128 to 256. But C
As the memory capacity of the AM increases, the number of words per block also increases.
There is a need to prioritize the 096 coincidence output signals.

The priority encoder 60 disclosed in the above-mentioned Japanese Patent Application Laid-Open No. Hei 5-18979 is based on the premise that priority is given to about 128 to 256 coincidence output signals as described above. When the priority encoder 60 that prioritizes 4096 coincidence output signals is configured by applying the technology disclosed in the publication, the number of elements per word of the input signal priority circuit 72 is large. There was a problem of becoming large.

In the CAM, a plurality of words, for example, the same 16 words as those in the above example, are arranged in one horizontal row for the purpose of reducing the layout area instead of arranging 4096 words of memory cells in a vertical line. Have been placed. In this case, since the priority encoder 60 must be laid out in a region of the memory cell at a short vertical interval, the layout becomes long, the number of wirings in the horizontal direction increases, and the layout area becomes very large. There was a point.

[0029]

SUMMARY OF THE INVENTION An object of the present invention is to solve the above-mentioned problems of the prior art and to prioritize coincidence output signals with a small number of elements and a small layout area in a large-capacity content addressable memory. It is to provide a priority encoder which can be used.

[0030]

In order to achieve the above object, the present invention divides m input signals into m / n groups of n signals each, and assigns a priority order among the grouped groups. The priority circuit to be assigned, the memory address corresponding to the highest priority group selected by the priority circuit, and the memory address corresponding to the highest priority input signal included in the highest priority group. An encoder circuit for encoding and outputting the encoded data is provided.

Here, the priority circuit includes at least one priority block. The priority block includes a plurality of first means for calculating a logical sum of n input signals, and the plurality of first means. It is preferable to include second means for calculating the logical sum of the output signals from the first and second means, and third means for prioritizing the output signals from the first means.

Further, the priority circuit includes a plurality of priority circuits of a lower hierarchy to which the input signal is inputted.
Blocks and the priority /
Each of the logical sums output from the second means of the block is hierarchically constituted by a higher-order priority block to which the logical sum is input, and the lower-order priority block is assigned to the lower-order priority block according to a result of the prioritization by the higher-order priority block. Preferably, one of the priority blocks of the hierarchy is enabled, and prioritization is preferably performed only in the enabled lower priority block.

[0033] Further, it is preferable that the priority encoder of the upper layer is further hierarchically composed of a plurality of priority blocks.

[0034]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Hereinafter, a priority encoder according to the present invention will be described in detail based on a preferred embodiment shown in the accompanying drawings.

FIG. 1 is a conceptual diagram showing the configuration of an embodiment of a priority encoder according to the present invention. The priority encoder 10 shown in FIG. 1 uses a memory address corresponding to a plurality of match output signals in which a match is detected when a match is detected in a plurality of words as a result of a match search in a large-capacity associative memory. , And sequentially outputs according to a preset priority. The priority circuit 12 and the encoding circuit 14 are provided.

First, the priority circuit 12 outputs m matching output signals to be prioritized by m / n
(N is an integer of n <m) into groups.
Priorities are assigned to these m / n groups according to preset priorities. The priority circuit 12 may be hierarchized into two or more hierarchies, or may not be hierarchized. In the illustrated example, the priority circuit 12 has a plurality of priority blocks 16 hierarchized into three hierarchies.
It has.

In the case of this embodiment, the priority block 16 divides the 16 coincidence output signals into four groups A, B, C, and D of four, and the four groups A,
For prioritizing B, C, and D, for example, when prioritizing 4K (= 4096) signals as a coincidence output signal, 256 priority blocks 16 of the first hierarchy, 256 The number of priority blocks 16 in the second hierarchy is 16, and the number of priority blocks 16 in the third hierarchy is one.

FIG. 2 is a conceptual diagram showing the configuration of an embodiment of the priority block. As shown in the figure, the priority block 16 includes groups A, B, C,
As for D, an OR gate 18 that takes a logical sum of four input signals, and an OR gate 20 that takes a logical sum of output signals from the OR gates 18 of these four groups A, B, C, and D
And a group priority circuit 22 for prioritizing the four groups A, B, C, and D.

The OR gates 18 of each of the groups A, B, C, and D receive four input signals, each of which is divided into groups.
Signals A, B, C, D output from the OR gates 18
Is entered. The group priority circuit 22 also receives signals A, B, C, and D from the OR gates 18 of the groups A, B, C, and D, and 16 inputs to the priority block 16. Signal is input.

FIG. 3 is a circuit diagram showing the configuration of an embodiment of the group priority circuit. The group priority circuit 22 shown in FIG.
4, 26, 28. In FIG. 3,
The illustration of the 16 input signals input to the group priority circuit 22 shown in FIG. 2 and the 16 output signals output from the group priority circuit 22 corresponding to the input signals is omitted. I have.

Here, the signal A is output as it is as a signal (A), and the enable signals from the priority blocks of the upper hierarchy are commonly input to the AND gates 24, 26, and 28. And the AND gate 24
, The signals A and B are input to the inverted input of the AND gate 26, the signals A, B and C are input to the inverted input of the AND gate 28, and the AND gates 24 and 2
From signals 6 and 28, signals (B), (C) and (D)
Is output.

In the group priority circuit 22 'shown in FIG. 2B, the enable signal is removed from the inputs of the AND gates 24, 26 and 28 in the group priority circuit 22, and the inverter 25 and the AND Using the gates 27 and 29,
Three AND gates 49, 51, and 53 for taking the logical product of each of these output signals and the enable signal are added, and which of the group priority circuits 22, 2 is used.
2 ′ may be used.

In this embodiment, the coincidence output signal indicates that a coincidence has been detected when it is at a high level, and indicates that there is no coincidence when it is at a low level. Group A (signal A) has the highest priority and group B (signal A)
It is assumed that the priority order becomes lower in the order of (signal B) and group C (signal C), and the priority order of group D (signal D) is the lowest.

In each of groups A, B, C and D, OR
The gate 18 takes the logical sum of the four input signals that are input, and detects the presence or absence of a match among the four input signals that are input to each of the groups A, B, C, and D. .
In other words, if at least one of the four input signals contains a high level, that is, a coincidence output signal in which coincidence is detected, the signals A, B, and
C and D become high level.

The signals A, B, C, and D output from the OR gate 18 are ORed by the OR gate 20, and there is a match between the 16 input signals input to the priority block 16. Is detected. In other words, if at least one of the 16 input signals includes a high level, the OR signal output from the OR gate 20 is at a high level. The signals A, B, C, and D output from the OR gate 18 are also input to the group priority circuit 22 (22 ').

The group priority circuit 22 (2
In 2 ′), the signal (A) unconditionally goes high if the signal A is high. Hereinafter, as described above, in the present embodiment, since the priority is higher in the order of signal A> signal B> signal C> signal D, the signal (B) is low at the signal A, and the signal (C) is the signal A, B is at the low level, and the signal (D) is at the high level only when the signals A, B, and C are at the low level and the enable signal from the upper hierarchy is at the high level.

In other words, when the signal A is at a high level by the group priority circuit 22 (22 '),
That is, when there is a high-level input signal in the group A, the signal (A) becomes high level. Signal (B),
(C) and (D) show that there are no high-level input signals in the groups A, A and B, and the groups A, B and C, respectively, and the high-level signals in the groups B, C and D respectively. High level only when there is an input signal.

As described above, in the priority block 16, the logical sum of the 16 input signals is calculated, and this is
The signal is output as an R signal as an input signal to the priority block of the upper layer, and the four groups A, B, C, and D are prioritized, and among the high-level signals A, B, C, and D, , And only the signals (A), (B), (C), and (D) corresponding to the highest-priority signals are set to the high level and output to the encoding circuit 14.

The group priority circuit 22
Of the 16 output signals output from (22 '), only the four output signals corresponding to the highest-priority signal in the four groups A, B, C, and D are enabled. Four input signals corresponding to the four output signals are output as they are. This output signal is used as an enable signal of the lower priority block, and is also output to the encoding circuit 14.

In the priority circuit 12 shown in FIG. 1, the 256 priority blocks 1
The OR1 signals output from 6 are input as input signals to the corresponding second-level priority blocks 16 by 16 lines. Similarly, 1 of the second hierarchy
O output from the six priority blocks 16
The R2 signal is transmitted to the priority block 16 of the third hierarchy.
Is input as an input signal for.

As shown in FIG. 1, a high level (power supply potential) is applied to the priority block 16 of the third hierarchy as an enable signal. As a result, the third
The group priority circuit 22 (22 ') of the hierarchy priority block 16 is always enabled. The 16 output signals output from the third-level priority block 16 are input as enable signals for the corresponding second-level priority block 16.

Similarly, 16 output signals output from each of the 16 priority blocks 16 of the second hierarchy are input as enable signals of the corresponding priority block 16 of the first hierarchy. Although not shown, the signals (A), (B), (C), (D), and (B) output from all the priority blocks 16 in the first, second, and third layers , And 16 output signals are also input to an encoding circuit 14 described later.

In the priority circuit 12, first, the first
In each of the 256 priority blocks 16 of the hierarchy, the OR of the input 16 coincidence output signals is ORed, and the OR1 signal is output. These 256 O
The R1 signals are input to the corresponding second-level priority blocks 16 by 16 signals, respectively.
In each of the priority blocks 16
The OR of the six OR1 signals is obtained, and the OR2 signal is output.

Third-level priority block 16
Since the enable signal is always at the high level, the 16 priority blocks 16
Priority is assigned among four groups A, B, C, and D obtained by grouping a total of 16 OR2 signals input from the group A into four, and among the signals A, B, C, and D, a high level signal is assigned. Signals (A), (B) corresponding to the highest priority signals,
Only (C) and (D) are at the high level.

From the priority block 16 of the third hierarchy, the priority block 1 of the second hierarchy
6 corresponding to the 16 OR2 signals input from
Six output signals are output. Of these 16 output signals, only four output signals corresponding to the highest-level signals A, B, C, and D at the high level are enabled,
The corresponding four OR2 signals are output as they are,
The other twelve output signals are at low level.

Third-level priority block 16
Are fed back as enable signals to the corresponding second-level priority blocks 16 respectively. At this time, only the second-level priority block 16 in which the enable signal is at the high level is enabled. Then, priority is assigned to four groups A, B, C, and D obtained by dividing the total of 16 OR1 signals input from the corresponding 16 priority blocks 16 of the first hierarchy into four groups. ,
Only the signals (A), (B), (C) and (D) corresponding to the highest priority signal among the signals A, B, C and D are at the high level.

From the priority block 16 of the second hierarchy, the priority block 1 of the first hierarchy
6 corresponding to the 16 OR1 signals input from
Six output signals are output. Of these 16 output signals, only four output signals corresponding to the highest-level signals A, B, C, and D at the high level are enabled,
Four corresponding OR1 signals are output as they are,
The other twelve output signals are at low level.

Subsequently, the output signal from the second-level priority block 16 is fed back as an enable signal to the corresponding first-level priority block 16. Similarly, only the priority block of the first hierarchy in which the enable signal is at the high level is enabled, and four groups A, B, C, which are obtained by grouping 16 coincidence output signals into groups of four.
D is prioritized, and only the signals (A), (B), (C), and (D) corresponding to the highest priority signal among the signals A, B, C, and D are set. High level.

From the priority block 16 of the first hierarchy, 16 output signals corresponding to the 16 coincidence output signals input to the priority block 16 of the first hierarchy are output. Of these 16 output signals, the highest-level signals A, B, C,
Only the four output signals corresponding to D are enabled, the four corresponding output signals corresponding thereto are output as they are, and the other twelve output signals are at low level.

The signal (A) output from the priority block 16 which is not in the enabled state,
(B), (C), (D), and all 16 output signals are at low level.

As described above, only the first, second and third hierarchy priority blocks corresponding to the high-level highest-priority group are enabled,
A signal (A) corresponding to this highest priority group,
Only one of (B), (C), and (D) is at the high level, and only four of the 16 output signals are in the enabled state. The signals (A), (B) from the priority blocks 16 of the first, second and third layers,
(C), (D) and the 16 output signals are input to the encoding circuit 14 described below.

The encoding circuit 14 includes a memory address corresponding to the highest priority group selected by the priority circuit 12 among the m / n groups divided into groups, and includes the memory address in the highest priority group. The memory address corresponding to the highest priority match output signal among the n match output signals is separately encoded and output. When these groups and the memory address of the coincidence output signal are combined, the final memory address is obtained.

FIG. 4 is a structural circuit diagram of one embodiment of the encoding circuit. As shown in FIG.
Includes a signal detection circuit 30, an output circuit 32, and an encoder 34. Although not shown, the signal detection circuit 30 is provided for each of the priority blocks 1
6 are provided one by one. Of the plurality of priority blocks 16, the first, second, and third hierarchy priority blocks 1 in the enabled state are set.
Only the signal detection circuit 30 corresponding to No. 6 operates.

In the encoding circuit 14, first, the signal detecting circuit 30 detects a state of the signals (A), (B), (C), and (D) outputted from the priority block (FIG. 1). (A middle right side) 30a, and a second detection circuit (the left side) 30b for detecting states of four output signals corresponding to the highest-level signals A, B, C, and D.

The first detection circuit 30a outputs the signal (B),
Regarding (C) and (D), three discharge circuits 38 including two NMOSs connected in series between the signal line 36 and the ground are provided. Signals (B), (C), and (D) are input to the upper gates of the NMOSs in the figure of the respective discharge circuits 38, and the lower N
A control line 39 output from each priority block 16 is commonly input to the gate of the MOS.

The second detection circuit 30b provides two N series connected in series between the signal line 40 and the ground for each of the signals (A), (B), (C), and (D).
It has four discharge circuits 42 composed of MOS. The upper NM of each discharge circuit 42 in the drawing
The four output signals output from the priority block 16 are input to the gate of the OS, and the lower NMOS
, A control line 39 supplied from each priority block 16 is commonly input.

The output circuit 32 inverts and amplifies and outputs the signals (A), (B), (C), (D) detected by the signal detection circuit 30 and the four output signals in the enable state. It has two PMOSs for charging and an inverter. The encoder 34 amplifies and outputs signals (A), (B), (C),
(D) and separately encode and output the memory addresses corresponding to the four output signals in the enabled state.

FIG. 5 is a circuit diagram showing the configuration of an embodiment of the encoder. The encoder 34 shown in the figure assigns priority to four enabled output signals included in the selected group and encodes and outputs a memory address corresponding to the highest priority output signal. And two NOR gates 44, 46, three AND gates 48, 50, 52, and two OR gates 54, 56
It is composed of

The signals A0, A1, and A are supplied to the NOR gate 44.
2, and signals A0 and A1 are input to the NOR gate 46. The AND gate 48 also has a signal A
3 and an output signal from the NOR gate 44,
The AND gate 50 has the signal A1 and the NOR gate 4
6 and the AND gate receives the signal A2 and the output signal from the NOR gate 46. The OR gate 54 has an AND gate 4
The output signals from 8, 50 are input, and the signal AD0 is output from the OR gate 54. The output signals from the AND gates 48 and 52 are input to the OR gate 56,
The signal AD1 is output from the R gate 56.

Assuming that the priorities are higher in the order of the signals A0>A1>A2> A3, the encoder 34 shown in FIG.
As shown in the truth table, when the signal A0 is “1”, the signals AD1 and A1 are output regardless of the state of the signals A1 to A3.
D0 is '0,0'. When the signals A0 and A1 are "0, 1", the signals AD1 and AD0 are "0, 1" regardless of the states of the signals A2 and A3. Signal A0
When A2 is '0, 0, 1', the signals AD1, AD0 are '1, 0' regardless of the state of the signal A3. When the signals A0 to A2 and A3 are '0, 0, 0, 1',
The signals AD1 and AD0 are '1,1'.

As described above, the encoder 34 outputs the memory address corresponding to the signal output from the output circuit 32. Although the illustrated example is configured using static logic, it can also be configured using dynamic logic together. Also, when the signals A0 to A3 are all "0", the signals AD1 and AD0 are "0, 0". The case where the signals A0 to A3 are all “0” means that no coincidence output signal is detected or that the highest address has priority. In addition, conventionally known encoders can be used as the encoders of the group.

In the encoding circuit 14, first, the control line 39 is set to the low level. As a result, all the discharge circuits 38 and 42 are turned off, and all the signal lines 36 and 40 are precharged to a high level by the two PMOSs of the output circuit 32. Subsequently, as described above, the first, second, and third-level priority blocks 16 corresponding to the highest-priority coincidence output signal output the signal (B) to the corresponding signal detection circuit 30 respectively. ,
(C), (D) and four output signals in the enabled state are input.

Thereafter, the control line 39 is set to the high level. Accordingly, the first detection circuit 30a outputs the signal lines 3 corresponding to the high-level signals (B), (C), and (D).
6 is discharged to a low level. When the signal (A) is at the high level, the signal line 36 is not discharged, and retains the precharged high level. Further, by the second detection circuit 30b,
The signal line 40 corresponding to the highest priority output signal is discharged to a low level.

The states of the signal lines 36 and 40 are inverted and amplified by the output circuit 32 and input to the encoder 34. In the encoder 34, the signals (A), (B),
Memory addresses AD2,3 corresponding to (C) and (D)
And the memory addresses AD0, 1 corresponding to the four output signals in the enabled state are separately encoded. Then, the memory addresses of the first, second and third hierarchical priority blocks 16 are matched to obtain a memory address corresponding to the highest priority match output signal in which a match is detected.

The priority encoder 10 of the present invention
In order to prioritize between groups, the priority encoder 60 disclosed in Japanese Patent Application Laid-Open No. HEI 5-18979, which is cited in the description of the prior art, is used in the circuit configuration of this embodiment. As compared with the case of (1), the number of elements required to construct the priority block of the first hierarchy, which is used most frequently, can be reduced to about 1/10, and the layout area of the entire circuit can be reduced to about half. .

In the present invention, a delay due to encoding of the coincidence output signal included in the selected group is newly generated as a circuit operation delay. However, in the present invention, as shown in FIG. 5, the circuit scale of the encoder 34 is very small, there is almost no delay, and the signal detection circuit 3 in the preceding stage of the encoder 34 is used.
Since the load at 0 is approximately half and the operation speed is high, the operation speed is almost equal to that of the priority encoder 60 disclosed in the above publication.

In the embodiment, the input signals to the priority block 16 are set to 16 signals, which are divided into four groups of four signals. However, the present invention is not limited to this, and the priority block 16 is not limited thereto. There is no limitation on the number of input signals, the number of groups, and the number of input signals included in one group for 16. Further, the number of coincidence output signals for which the entire priority encoder of the present invention assigns priorities is not limited at all.

The group priority circuit 22
(22 ') and specific circuits of the signal detection circuit 30, the output circuit 32, and the encoder 34 have been illustrated, but the invention is not limited thereto, and another circuit configuration that realizes the same function may be used. The priority encoder of the present invention is basically as described above. As described above, the priority encoder of the present invention has been described in detail. However, the present invention is not limited to the above embodiment, and various improvements and modifications may be made without departing from the gist of the present invention. is there.

[0079]

As described in detail above, the priority encoder of the present invention divides m input signals into m / n groups of n signals, and sets the priority order among the grouped groups. The memory address corresponding to the highest priority group and the memory address corresponding to the highest priority input signal included in the highest priority group are separately encoded and output. According to the priority encoder of the present invention, the coincidence output signals are divided into groups, prioritization among groups is performed, and coincidence output signals included in the selected group are prioritized. Since the signal prioritization circuit is shared between the lower priority blocks, the priority circuit can be configured with a smaller number of elements. Since the number of elements in the block can be significantly reduced, the layout area of the priority encoder can be significantly reduced.

[Brief description of the drawings]

FIG. 1 is a conceptual diagram illustrating a configuration of an embodiment of a priority encoder according to the present invention.

FIG. 2 is a configuration conceptual diagram of an embodiment of a priority block of the priority circuit shown in FIG. 1;

3 (a) and 3 (b) are circuit diagrams of an embodiment of a group priority circuit of the priority block shown in FIG. 2;

FIG. 4 is a configuration circuit diagram of an embodiment of the encoding circuit shown in FIG. 1;

FIG. 5 is a configuration circuit diagram of one embodiment of an address encoder.

FIG. 6 is a truth table of one embodiment of an address encoder.

FIG. 7 is a conceptual diagram illustrating an example of a configuration of a conventional priority encoder.

8 is a configuration conceptual diagram of an example of an input signal priority block of the priority circuit shown in FIG. 7;

9 is a circuit diagram illustrating an example of an input signal priority circuit of the priority block illustrated in FIG. 8;

FIG. 10 is a configuration circuit diagram of an example of the encoding circuit shown in FIG. 7;

[Explanation of symbols]

10, 60 priority encoder 12, 62 priority circuit 14, 64 encoding circuit 16, 66 priority block 18, 20, 54, 56, 68, 70 OR gate 22, 22 'group priority circuit 24, 26, 27, 28 , 29,48,49,50,5
1, 52, 53, 84 AND gate 25 inverter 30 signal detection circuit 30a first detection circuit 30b second detection circuit 32, 94 output circuit 34, 92 encoder 36, 40, 104 signal line 38, 42 discharge circuit 39 control line 44, 46, 82 NOR gate 72 Input signal priority circuit 74 Priority unit 76, 90, 96 N-type MOS transistor 78, 86, 88, 98, 102 P-type MOS transistor 80, 100 Inverter

Claims (4)

[Claims] 1. A priority circuit that divides m input signals into m / n groups of n signals, and assigns a priority to the grouped groups, and a highest priority circuit selected by the priority circuit. A priority circuit comprising: a memory address corresponding to the priority group; and an encoding circuit for separately encoding and outputting the memory address corresponding to the highest priority input signal included in the highest priority group.・ Encoder. 2. The method according to claim 1, wherein the priority circuit has at least one
A plurality of first means for performing a logical sum of n input signals, and a second means for performing a logical sum of output signals from the plurality of first means. 3. The priority encoder according to claim 1, further comprising: third means for prioritizing output signals from the first means. 3. The priority circuit receives a plurality of priority blocks of a lower hierarchy to which the input signal is input and a logical sum of each of the plurality of lower priority blocks output from the second means. One of the priority blocks of the lower hierarchy is enabled according to the result of the prioritization by the priority blocks of the upper hierarchy, and 3. The priority encoder according to claim 2, wherein prioritization is performed only in the enabled lower priority block. 4. The apparatus according to claim 3, wherein the priority encoder of the upper layer is further hierarchically constituted by a plurality of priority blocks of the layer.
Priority encoder according to 1.