JPH0855010A - Priority encoder - Google Patents

Abstract

PURPOSE:To provide a high-speed priority encoder (PE) of a small scale hardware amount. CONSTITUTION:An eight-bit input PE is provided with a first PE 1011 for upper four bits, a second PE 1012 for lower four bits and a selection circuit 1013 constituted of a CMOS transfer gate so as to search a first'1' in input binary number data from a most significant bit and output a binary number code for indicating the number of preceding '0.' The first PE 1011 generates a two- bit code relating to the upper four bits, an OR S4 and an OR negation XS4, the second PE 1012 generates the two-bit code relating to the lower four bits and the OR negation XS4 is outputted as the most significant bit of the binary number code as it is. The selection circuit 1013 outputs the generation code of the first PE 1011 at the time of XS4='0' and outputs the generation code of the second PE 1012 at the time of XS4='1' as the lower two bits of the binary number code respectively.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a priority encoder (hereinafter abbreviated as PE) which is preferably used in an arithmetic operation device or the like.

[0002]

2. Description of the Related Art In a normalization process in a floating-point arithmetic operation device, it is necessary to detect the number of leading "0" bits in multi-bit binary number data forming a mantissa operation result. To detect the bit number of this leading "0", PE
Is used. PE is also used in the format conversion between integer format and normalized floating point format. PE may be used for other purposes.

Japanese Unexamined Patent Publication No. 59-121435 discloses 6
A 64-bit input PE composed of eight 8-bit input PEs (first to eighth PEs) so as to output a binary code of bits is disclosed. Each of the eight 8-bit inputs PE is provided if the enable input EI is "1" and there is at least one "1" bit among all the bits forming the given 8-bit data. , The first appearing "1" bit in the given 8-bit data is searched from the most significant bit of the 8-bit data, and the first 3 bits indicating the position of the found first "1" bit 3 which indicates the block position address (7 to 0) unique to each 8-bit input PE while outputting the code
Outputs a second code of bits and enables output E
O is reset to "0". Further, each of the 8-bit inputs PE has a first and a second if the enable input EI is "1" and the values of all the bits forming the given 8-bit data are "0". The code output is set to high impedance (deactivated), and the enable output EO is set to "1". Further, each of the 8-bit inputs PE sets (deactivates) the first and second code outputs to high impedance when the enable input EI is “0”, and
The enable output EO is reset to "0". And
The enable input EI of the first PE assigned with 7 as the block position address is fixed to "1", and
The enable output EO of the PE of the second PE is the enable input E to the second PE assigned with 6 as the block position address.
Supplied as I. Hereinafter, when n = 2 to 7, the enable output EO of the nth PE is the (n + 1) th PE.
Respectively to the enable inputs EI.

64-bit input P having such a configuration
According to E, only the first and second code outputs of one 8-bit input PE receiving the 8-bit data including the bit of "1" that first appears in the given 64-bit data are active. A 6-bit code obtained by merging the activated first and second codes is output as a 6-bit binary code indicating the position of the first "1" bit.

In Japanese Patent Laid-Open No. 5-27946, there are five 4-bit input PEs (first to fifth PEs) and two decode selection circuits so as to output a 4-bit binary code. A 16-bit input PE is disclosed. 5
Each of the four 4-bit inputs PE searches for the first appearing "1" bit in the given 4-bit data from the most significant bit of the 4-bit data, and finds the first "1" bit found. A 2-bit code indicating the position of is generated, and a logical sum of all the bits forming the given 4-bit data is generated. 1st-4th PE
Is supplied as 4-bit data to the fifth PE, and the upper 2 bits of the binary code are output from the fifth PE. Upper 2 of the binary code
The bit indicates which of the first to fourth PEs has received the 4-bit data including the bit of "1" that first appears in the given 16-bit data.
Therefore, the two decode selection circuits select one of the output codes of the first to fourth PEs according to the value of the upper 2 bits of the binary code, and select the selected code from the binary number. It is output as the lower 2 bits of the code.

[0006]

DISCLOSURE OF THE INVENTION Problems to be Solved by the Invention
The 64-bit input PE of Japanese Patent No. 1435 controls the operation of each 8-bit input PE by the enable inputs / outputs EI and EO, so that the "1" bit that appears first in the given 64-bit data is The lower the position,
There is a problem that a large delay occurs in the output of the 6-bit binary code. In particular, the first and second code outputs of the eighth PE are the enable output EO of each of the first to seventh PEs.
Can be activated for the first time after each is sequentially set to "1". At this time, each of the first to seventh PEs has two logic gates (one inverter and one 9-input NOR) between the respective enable inputs EI and EO.
Gate).

The first to fourth PEs among the 64-bit input PEs disclosed in the above-mentioned Japanese Patent Laid-Open No. 59-121435 are 32.
The bit input PE constitutes the 16-bit input PE, and the first and second PEs constitute the 16-bit input PE. Of these, the delay of the 32-bit input PE is the delay of the 16-bit input PE plus the delay of two logic gates (one inverter and one 9-input NOR gate). Also, 64
The delay of the bit input PE is the delay of the 32-bit input PE plus the delays of the six logic gates.

On the other hand, 16 of JP-A-5-27946
Even with the bit input PE, there is a problem that a large delay occurs in the output of the binary code. This 16-bit input PE is the first
A first stage encoder composed of a fourth PE and a fifth stage encoder
Has a hierarchical structure including a second stage encoder composed of PEs. The fifth PE is composed of six logic gates like the first to fourth PEs, and a maximum of three logic gates (one inverter and two two gates) are provided between the input and the output.
It causes a delay in the input NOR gate). Also,
The two decode selection circuits cause an increase in the amount of hardware and are a major cause of output code delay. Each decode selection circuit is composed of as many as 11 logic gates, and a maximum of 4 logic gates (1 inverter, 1
2 2-input NOR gates, 1 2-input NAND gates and 1 4-input NAND gates). After all, the delay of the 16-bit input PE in Japanese Patent Laid-Open No. 5-27946 is the degree of delay in a maximum of 10 logic gates.

An object of the present invention is to determine the output binary code of the N-bit input PE with a constant and small delay regardless of the position of the searched bit.

Another object of the present invention is to provide a 2N bit input PE.
To reduce the difference between the delay of 1 logic gate and the delay of the N-bit input PE to the extent of the delay in one logic gate.

Still another object of the present invention is to provide an N bit input P
E is to reduce the amount of hardware.

[0012]

According to the present invention, in a 2 ^{n + 1-} bit input PE (n is an integer of 2 or more), a given 2
^From only the upper 2 ⁿ bits of ^{n + 1} bit data,
It is noted that the most significant bit of the output binary code of (n + 1) bits can be determined. The positive logic 2 ^{n + 1} bit input PE according to the present invention includes two positive logic 2
It is composed of ^n- bit input PEs (first and second PEs) and a simple selection circuit. The first PE is given 2
The upper 2 ⁿ bits of the ^{n + 1} bit data are encoded, and a 1-bit logical sum negation of the upper 2 ⁿ bits is generated. The second PE is given 2 ^{n + 1}
The lower 2 ⁿ bits of the bit data are encoded. The 1-bit logical sum negation generated by the first PE is
It is output as it is as the most significant bit of the output binary code and is also supplied to the selection circuit. The selection circuit selects either one of the encoding result of the first PE and the encoding result of the second PE according to only the generated 1-bit logical OR negation value, and the selected encoding result Is output as the lower n bits of the output binary code. The selection circuit is composed of two switch circuits each having at least n transfer gates.

The first positive logic 2 ^n- bit input PE is
Two positive logic 2 ^n-1 bit inputs PE (third and fourth P
E), a simple selection circuit, and a simple logic circuit. The second positive logic 2 ⁿ bit input PE is
Two positive logic 2 ^n-1 bit inputs PE (fifth and sixth P
E) and a simple selection circuit. The third, fourth, and fifth PEs have a function of encoding 2 ^n-1 bit data and a function of generating 1-bit logical negation of the 2 ^{n- 1} bit data. The logic circuit is the upper 2 of the given 2 ^{n + 1} bit data.
It is to check whether or not all ⁿ bits are "0" bits, and is composed of at least one 2-input logic gate.

[0014]

The 8-bit input PE according to the present invention is composed of two 4-bit inputs PE which operate in parallel with each other and one selection circuit. The delay of each 4-bit input PE is at most about the degree of delay in three logic gates, as in the first to fifth PEs of Japanese Patent Laid-Open No. 5-27946. That is, the delay of the 8-bit input PE according to the present invention is at most the delay of three logic gates.

The 16-bit input PE according to the present invention includes four 4-bit input PEs which operate in parallel with each other, and three (1 + 2) selection circuits arranged in a two-stage hierarchical structure.
It is composed of one logic circuit. The 16-bit input PE
Is the sum of the delay of the 8-bit input PE according to the present invention and the delay of one logic gate.

A 32-bit input PE according to the present invention includes eight 4-bit input PEs that operate in parallel with each other, seven (1 + 2 + 4) selection circuits arranged in a three-stage hierarchical structure, and two-stage input PEs. It is composed of four (1 + 3) logic circuits arranged in a hierarchical structure. The delay of the 32-bit input PE is the delay of the 16-bit input PE according to the present invention plus the delay of one logic gate.

The 64-bit input PE according to the present invention includes 16 4-bit input PEs that operate in parallel with each other, 15 (1 + 2 + 4 + 8) selection circuits arranged in a 4-stage hierarchical structure, and 3-stage input PEs. 11 (1+) arranged in a hierarchical structure
3 + 7) logic circuits. The delay of the 64-bit input PE is the delay of the 32-bit input PE according to the present invention plus the delay of one logic gate.

[0018]

EXAMPLES Hereinafter, PEs according to examples of the present invention will be described.
This will be described with reference to the drawings.

(Embodiment 1) FIG. 1 is a circuit diagram of an 8-bit input PE according to the first embodiment of the present invention. This circuit does not care the output when all the inputs are "0". 8-bit input P of FIG.
E is configured by combining 4-bit inputs PE 1011 and 1012 and a selection circuit 1013,
The input terminals I7 to I4 of the 8-bit input PE are connected to the input terminals I3 to I0 of the 4-bit input PE 1011 and the input terminals I3 to I0 of the 8-bit input PE are 4-bit input PE1.
012 is connected to the input terminals I3 to I0. The selection circuit 1013 includes two switch circuits 11 and 12 each composed of two pairs of CMOS transfer gates. The output XS4 (logical sum negation) of the 4-bit input PE 1011 is output as it is as the most significant bit P2 of the output code of the 8-bit input PE. Outputs P1 and P0 of 4-bit input PE1011 and 4-bit input PE10
12 outputs P1 and P0 are 4-bit input PE1011
Output XS4 (logical sum negative) and output S4 (logical sum) are selected by the selection circuit 1013, and the lower 2 bits P1 and P0 of the output code of the 8-bit input PE are selected.
Is output as

FIG. 2 shows the 4-bit input PE101 shown in FIG.
FIG. 3 is a circuit diagram of 1,1012. The circuit of FIG. 2 has two inverters 102 so as to realize the operation shown in Table 1.
1, 1026 and three 2-input NOR gates 1022
1023, 1024 and one 4-input NOR gate 10
And 25.

[0021]

[Table 1]

Table 2 shows the operations required for the 8-bit input PE in FIG.

[0023]

[Table 2]

Looking at Table 2, if there is at least one "1" bit among the inputs I7 to I4 including the most significant bit I7, the output P2 becomes "0", and all the inputs I7 to I4 are "0". If it is ", it is understood that the output P2 is" 1 ". Further, when P2 = “0”, the 4-bit input encoding result regarding the inputs I7 to I4 is P2 = “1”.
In the case of, it can be seen that the 4-bit input encoding results for the inputs I3 to I0 are the outputs P1 and P0, respectively.

The 8-bit input PE of FIG. 1 has inputs I7-I.
The logical sum negation XS4 of 4 is the most significant bit P2 of the output code.
And inputs I7 to I4 and inputs I3 to I0 are encoded by 4-bit inputs PE1011 and 1012, respectively, and when XS4 = "0", 4-bit input PE101.
When XS4 = “1”, the encoding result of 1 is output as the lower 2 bits P1 and P0 of the output code of the 4-bit input PE 1012, respectively.

(Embodiment 2) FIG. 3 is a circuit diagram of a 16-bit input PE according to a second embodiment of the present invention. This circuit does not care the output when all the inputs are "0". The 16-bit input PE of FIG. 3 is configured by combining 8-bit inputs PE 1031 and 1032 with a selection circuit 1033, and the input terminals I15 to I8 of the 16-bit input PE are the input terminals I7 to I8 of the 8-bit input PE 1031. The input terminals I7 to I0 of the 16-bit input PE are connected to I0 and the input terminals I7 to I0 of the 8-bit input PE 1032. The selection circuit 1033 includes two switch circuits 11 each including three pairs of CMOS transfer gates.
1, 112 are provided. The output XS8 (logical sum negation) of the 8-bit input PE 1031 is directly output as the most significant bit P3 of the output code of the 16-bit input PE. 8-bit input PE 1031 outputs P2, P1,
P0 and 8-bit input PE1032 outputs P2, P1, P
0 means the selection circuit 10 using the output XS8 (logical sum negation) and the output S8 (logical sum) of the 8-bit input PE 1031.
It is selected by 33 and is output as the lower 3 bits P2, P1, P0 of the output code of the 16-bit input PE, respectively.

FIG. 4 shows the 8-bit input PE 103 shown in FIG.
1 is a circuit diagram of 1032. The circuit of FIG. 4 includes two 4-bit inputs PE 1041 and 1042 and one selection circuit 1043 similar to those of FIG. 1, a 2-input NOR gate 1044 for generating a logical sum negation XS8, and a logical sum. S
And a two-input NAND gate 1045 for generating eight. However, one 8-bit input PE1
032 may have the same configuration as that in FIG.

Table 3 shows the operation required for the 16-bit input PE in FIG.

[0029]

[Table 3]

Looking at Table 3, if there is at least one bit "1" among the inputs I15 to I8 including the most significant bit I15, the output P3 becomes "0", and the inputs I15 to I8.
It can be seen that the output P3 is "1" if all of the above are "0". Further, when P3 = "0", the input I15
~ 8-bit input encoding result for I8 is P3
It can be seen that when = 1, the 8-bit input encoding results for the inputs I7 to I0 are the outputs P2, P1 and P0, respectively.

The 16-bit PE of FIG. 3 has inputs I15-I.
8 logical sum negation XS8 is output as the most significant bit P3 of the code
And inputs I15 to I8 and inputs I7 to I0 are encoded by 8-bit inputs PE 1031 and 1032, respectively, and 8-bit input PE10 when XS8 = "0".
The encoding result of 31 is 8 when XS8 = "1".
The encoding result of the bit input PE 1032 is output as the lower 3 bits P2, P1, P0 of the output code, respectively.

According to the principles of the first and second embodiments described above, when n is an arbitrary integer of 2 or more, 2 ^{n + 1} bit input PE and 2 2 ⁿ bit input PE and 1 It can be configured with individual selection circuits. For example, the 32-bit input PE is constructed in this way. In the case of handling 24-bit input data with this 32-bit input PE, if eight dummy “1” are given as the lower 8 bits I7 to I0, all the 24-bit inputs I23 to I0 become “0”. Does not occur.

In the first and second embodiments, the structure in which the most significant bit is searched in the lower direction and the bit position which is first "1" is encoded has been described, but it is first "0". It is also possible to adopt a configuration in which the bit position that exists is encoded. It is also possible to perform a search from the least significant bit to the upper direction, and to encode the bit position that is initially "1" or the bit position that is initially "0".

(Third Embodiment) FIG. 5 is a circuit diagram of a 24-bit input PE according to a third embodiment of the present invention. This circuit does not care the output when all the inputs are "0". The 24-bit input PE of FIG. 5 is a 16-bit input PE 1051 and an 8-bit input P.
The input terminal I23 to I8 of the 24-bit input PE is connected to the input terminals I15 to I0 of the 16-bit input PE 1051 and the input terminals I7 to I0 of the 24-bit input PE are configured by combining the E1052 and the selection circuit 1053. Is an 8-bit input PE1052 input terminal I
7 to 10 are connected. The selection circuit 1053 includes two switch circuits 211 and 212 each composed of four pairs of CMOS transfer gates. A pair of CMOS transfer circuits in one switch circuit 212.
The gate input is fixed to "0" (ground). The output XS16 (logical sum negation) of the 16-bit input PE 1051 is directly output as the most significant bit P4 of the output code of the 24-bit input PE. 16-bit input PE1051 outputs P3, P2, P1, P0 and 8
A 4-bit code obtained by adding "0" to the higher order of the outputs P2, P1, P0 of the bit input PE1052 is the output XS16 (logical NOT) and the output S16 (logical OR) of the 16-bit input PE1051. It is selected by the selection circuit 1053 and is output as the lower 4 bits P3, P2, P1, P0 of the output code of the 24-bit input PE.

FIG. 6 shows the 16-bit input PE10 shown in FIG.
It is a circuit diagram of 51. The circuit of FIG. 6 has two 8-bit inputs PE 1061 and 1062 and one selection circuit 1063 similar to those of FIG. 3, a 2-input NOR gate 1064 for generating a logical sum negation XS16, and a logical sum. And a two-input NAND gate 1065 for generating S16. The internal configuration of the 8-bit input PE 1052 in FIG. 5 is as shown in FIG. 1 or 4.

Table 4 shows the operations required for the 24-bit input PE of FIG.

[0037]

[Table 4]

Looking at Table 4, if there is at least one "1" bit among the inputs I23 to I8 including the most significant bit I23, the output P4 becomes "0", and the inputs I23 to I8.
It can be seen that the output P4 is "1" if all of the above are "0". If P4 = "0", the input I2
It can be seen that the 16-bit input encoding results for 3 to I8 are outputs P3, P2, P1 and P0. Further, when P4 = "1", the output P3 is always "0", and the 8-bit input encoding result for the inputs I7 to I0 is output P2, P1, P0.

The 24-bit input PE of FIG.
~ I8 is output as the most significant bit P4 of the output code (XS16), inputs I23 to I8 are encoded by 16-bit input PE1051, inputs I7 to I0 are encoded by 8-bit input PE1052, and XS16
If "0", the 16-bit input PE 1051 encodes the result, and if XS16 = "1", 8-bit input PE 1052 encodes the 4-bit code obtained by adding "0" to the upper position. It is output as the lower 4 bits P3, P2, P1, P0 of the output code.

(Fourth Embodiment) FIG. 7 is a circuit diagram of an 11-bit input PE according to a fourth embodiment of the present invention. This circuit does not care the output when all the inputs are "0". The 11-bit input PE in FIG. 7 is an 8-bit input PE 1071 and a 3-bit input PE.
The input terminal I of the 11-bit input PE is formed by combining a selection circuit 1072 and a selection circuit 1073.
10 to I3 are input terminals I7 of the 8-bit input PE 1071
~ I0, 11-bit input PE input terminal I2
To I0 are input terminals I2 to I of the 3-bit input PE1072
It is connected to 0. The selection circuit 1073 includes two switch circuits 111 and 112 each composed of three pairs of CMOS transfer gates. The inputs of the pair of CMOS transfer gates in one of the switch circuits 112 are fixed to "0" (ground). 8
Bit input PE1071 output XS8 (logical NOT)
Is directly output as the most significant bit P3 of the output code of the 11-bit input PE. 8-bit input PE
1071 outputs P2, P1, P0 and 3-bit input PE1
The 3-bit code formed by adding “0” to the higher order of the outputs P1 and P0 of 072 is the output of the 8-bit input PE 1071 XS8 (logical sum negative) and the output S8 (logical sum). The lower 3 bits P2, P1, of the output codes of the selected 11-bit input PEs are selected.
It is output as P0.

The internal structure of the 8-bit input PE 1071 in FIG. 7 is as shown in FIG. FIG. 8 is a circuit diagram of the 3-bit input PE 1072 shown in FIG. The circuit of FIG. 8 has one inverter 1081 and two two-input NOR gates 1082, 10 so that the operation shown in Table 5 is realized.
83, and the configuration is such that the least significant bit I0 is not used.

[0042]

[Table 5]

Table 6 shows the operation required for the 11-bit input PE in FIG.

[0044]

[Table 6]

Looking at Table 6, if there is at least one "1" bit among the inputs I10 to I3 including the most significant bit I10, the output P3 becomes "0" and the inputs I10 to I3.
It can be seen that the output P3 is "1" if all of the above are "0". If P3 = "0", the input I1
It can be seen that the 8-bit input encoding results for 0 to I3 are outputs P2, P1 and P0. Furthermore, P3
It can be seen that when = 1, the output P2 is always "0" and the 3-bit input encoding results for the inputs I2 to I0 are the outputs P1 and P0.

The 11-bit input PE in FIG. 7 is the input I10.
~ I3 is ORed as negative (XS8) as the most significant bit P3 of the output code, inputs I10 to I3 are encoded by 8-bit input PE1071, inputs I2 to I0 are encoded by 3-bit input PE1072, and XS8 =
When it is "0", the encoding result of the 8-bit input PE 1071 is shown. When XS8 = "1", it is the 3-bit input PE.
A 3-bit code obtained by adding "0" to the higher order of the encoding result of 1072 is output as the lower 3 bits P2, P1, P0 of the output code, respectively.

According to the principles of the third and fourth embodiments, n, m and k are n ≧ m + 2, m ≧ 1 and 1 ≦ k.
If it is an arbitrary integer satisfying ≦ 2 ^m , (2 ⁿ +2 ^m +
The k) bit input PE can be composed of one 2 ⁿ bit input PE, one (2 ^m + k) bit input PE, and one selection circuit (with fixed input). In the third and fourth embodiments, the configuration has been described in which the most significant bit is searched in the lower direction and the bit position which is first "1" is encoded, but the bit position which is initially "0" is described. Can be configured to be encoded. It is also possible to perform a search from the least significant bit to the upper direction, and to encode the bit position that is initially "1" or the bit position that is initially "0".

Further, one 4-bit input PE1 shown in FIG.
If 012 is replaced with the 3-bit input PE 1072 in FIG. 7, the 7-bit input PE can be realized without changing the other 4-bit input PE 1011 and the selection circuit (without fixed input) 1013. Generally speaking, n, m and k are n ≧
Assuming that m + 1, m ≧ 1, and any integer satisfying 1 ≦ k ≦ 2 ^m , a (2 ⁿ +2 ^m + k) bit input PE is a 2 ⁿ bit input PE and a (2 ^m + k) bit PE. It can be configured by a bit input PE and one selection circuit (without fixed input).

(Fifth Embodiment) FIG. 9 is a circuit diagram of an 8-bit input PE according to a fifth embodiment of the present invention. This circuit is a modification of the circuit of FIG. 1 so that the search direction of the first "1" can be changed according to the control signal C. However, when all the inputs other than the control signal C are "0", the output is not cared.

The 8-bit input PE shown in FIG. 9 is constructed by combining 4-bit input PEs 1091 and 1092 with a selection circuit 1093.
Input terminals I7 to I4 are connected to the input terminals I3 to I0 of the 4-bit input PE 1091, and the input terminals I3 to I0 of the 8-bit input PE are connected to the input terminals I3 to I0 of the 4-bit input PE 1092. The selection circuit 1093 is composed of two pairs of CMOS transfer gates.
Switch circuits 11 and 12, an inverter 1, five 2-input NOR gates 2D, 2U, 3D, 3U, and 7,
It is provided with two 2-input AND gates 4D and 4U and two 2-input OR gates 5 and 6.

When C = "0", the output S4 (logical sum) of the 4-bit input PE 1091 is inverted through the 2-input NOR gate 2D and the 2-input OR gate 5, that is, the output of the 4-bit input PE 1091. XS4 (logical sum negation)
Is output as the most significant bit P2 of the output code of the 8-bit input PE. 4-bit input PE109
The outputs P1 and P0 of 1 and the outputs P1 and P0 of the 4-bit input PE 1092 are the output XS of the 4-bit input PE 1091.
4 (logical OR negation) and output S4 (logical OR) are used to select by the selection circuit 1093, which are respectively output as the lower 2 bits P1 and P0 of the output code of the 8-bit input PE. As a result, as in the case of FIG. 1, the 3-bit binary code relating to the first bit position of "1" obtained by searching the most significant bit I7 of the 8-bit data in the lower direction is output.

On the other hand, when C = "1", 2-input NO
Through the R gate 2U and the 2-input OR gate 5, the output S4 (logical sum) of the 4-bit input PE 1092 is inverted, that is, the output XS4 (logical negative) of the 4-bit input PE 1092 is the output code of the 8-bit input PE. It is output as the most significant bit P2 of them. 4-bit input PE
1092 outputs P1 and P0 and 4-bit input PE1091
Outputs P1 and P0 are selected by the selection circuit 1093 by using the output XS4 (logical sum negation) and the output S4 (logical sum) of the 4-bit input PE 1092, and the lower two of the output codes of the 8-bit input PE are respectively selected. It is output as bits P1 and P0. As a result, contrary to the case of FIG. 1, a 3-bit binary code relating to the first bit position of "1" obtained by searching the least significant bit I0 of the 8-bit data in the upper direction is output.

FIG. 10 shows the 4-bit input PE10 shown in FIG.
It is a circuit diagram of 91,1092. The circuit of FIG.
Four inverters 1101D, 1101U, 110 are provided so as to realize the operation shown in (a) and Table 7 (b).
6, 1107 and two 2-input NOR gates 1102
D, 1102U and four 3-input NOR gates 1103
D, 1103U, 1104D, 1104U and one 4
It is composed of an input NOR gate 1105 and two 2-input OR gates 1108 and 1109. Inverter 1101D and 2-input NOR gate 1102D in FIG.
3-input NOR gate 1103D, 3-input NOR gate 1
104D, 4-input NOR gate 1105 and inverter 1106 are inverter 1021, 2-input NO in FIG.
R gate 1022, 2-input NOR gate 1023, 2-input NOR gate 1024, 4-input NOR gate 1025
And the inverter 1026, respectively.

[0054]

[Table 7]

The operations required for the 8-bit input PE of FIG. 9 are shown in Tables 8 (a) and 8 (b).

[0056]

[Table 8]

The 8-bit input PE of FIG. 9 has C = “0”.
In the case of (search in the lower direction), the logical sum negation XS4 of the inputs I7 to I4 is output as the most significant bit P2 of the output code, and the inputs I7 to I4 and the inputs I3 to I0 are set to 4 respectively.
When the bit inputs PE1091 and 1092 are encoded and the logical sum negation XS4 of the inputs I7 to I4 is "0", the encoding result of the 4-bit input PE1091 is input to the inputs I7 to I4.
4 bit input PE if logical sum negation XS4 of 4 is "1"
The encoding result of 1092 is output as the lower 2 bits P1 and P0 of the output code, respectively. Also,
The 8-bit input PE in FIG. 9 has the logical sum negation XS4 of the inputs I0 to I3 when C = “1” (search in the upper direction).
Is output as the most significant bit P2 of the output code, and the input I
0 to I3 and inputs I4 to I7 are 4-bit inputs PE respectively
Encoded by 1092 and 1091, and if the logical sum negation XS4 of inputs I0 to I3 is "0", 4-bit input PE10
If the logical sum NOT XS4 of the inputs I0 to I3 is "1", the encoding result of the 4-bit input PE1091 is the lower 2 bits P1 of the output code.
It is output as P0.

(Embodiment 6) FIG. 11 is a circuit diagram of an 8-bit input PE according to a sixth embodiment of the present invention. This circuit is a modification of the circuit of FIG. 1 so that the first "1" can be searched from both directions of the most significant bit and the least significant bit. However, the output is not cared when all the inputs are "0".

The 8-bit input PE of FIG. 11 is constructed by combining 4-bit inputs PE 1111 and 1112 and a selection circuit 1113, and 8-bit input P
The input terminals I7 to I4 of E are connected to the input terminals I3 to I0 of the 4-bit input PE 1111, and the input terminals I3 to I0 of the 8-bit input PE are connected to the input terminals I3 to I0 of the 4-bit input PE 1112. The selection circuit 1113 is
It is provided with four switch circuits 11D, 12D, 11U and 12U each of which is composed of two pairs of CMOS transfer gates. Output XS4 of 4-bit input PE1111
(Logical OR negation) is output as it is as the most significant bit D2 of the first output code of the 8-bit input PE. The outputs D1 and D0 of the 4-bit input PE1111 and the outputs D1 and D0 of the 4-bit input PE1112 are two switch circuits 11D by using the output XS4 (logical NOT) and the output S4 (logical OR) of the 4-bit input PE1111. , 1
It is selected by 2D and is output as the lower 2 bits D1 and D0 of the first output code of the 8-bit input PE, respectively. The output XS4 (logical NOT) of the 4-bit input PE 1112 is output as it is as the most significant bit U2 of the second output code of the 8-bit input PE. Outputs U1 and U0 of 4-bit input PE1112 and 4-bit input P
E1111 outputs U1 and U0 are 4-bit input PE1
The output XS4 (logical NOT) of 112 and the output S4 (logical OR) are used to select the two switch circuits 11U and 12U, and the lower 2 bits U1 of the second output code of the 8-bit input PE are respectively selected. It is output as U0.

FIG. 12 shows the 4-bit input PE1 shown in FIG.
It is a circuit diagram of 111,1112. The circuit of FIG. 12 has three inverters 1121D, 1121U, 112 so as to realize the operations shown in Table 9 (a) and Table 9 (b).
6 and 6 two-input NOR gates 1122D and 1122
U, 1123D, 1123U, 1124D, 1124U
And one 4-input NOR gate 1125. Inverter 1121D and 2-input NOR in FIG.
Gate 1122D, 2-input NOR gate 1123D, 2
Input NOR gate 1124D, 4-input NOR gate 11
25 and the inverter 1126 are the inverter 1 in FIG.
021, 2-input NOR gate 1022, 2-input NOR gate 1023, 2-input NOR gate 1024, 4-input N
They correspond to the OR gate 1025 and the inverter 1026, respectively.

[0061]

[Table 9]

The operations required for the 8-bit input PE of FIG. 11 are shown in Tables 10 (a) and 10 (b).

[0063]

[Table 10]

The 8-bit input PE of FIG. 11 has inputs I7 ...
The logical sum negation XS4 of I4 is output as the most significant bit D2 of the first output code, and the inputs I7 to I4 and the inputs I3 to I are output.
0 is encoded by 4-bit inputs PE1111 and 1112 respectively, and when the logical sum negation XS4 of the inputs I7 to I4 is "0", the encoding result of the 4-bit input PE1111 is converted to the logical sum negation XS4 of the inputs I7 to I4. 1 ”
In the case of, the encoding result of the 4-bit input PE 1112 is converted into the lower 2 bits D1 and D0 of the first output code, respectively.
Is output as. Further, the 8-bit input PE of FIG. 11 outputs the logical sum negation XS4 of the inputs I0 to I3 as the most significant bit U2 of the second output code, and the input I0
To I3 and inputs I4 to I7 are 4-bit inputs PE1 respectively
112, 1111 encoded, 4-bit input PE1 when logical sum negation XS4 of inputs I0 to I3 is "0"
When the logical sum negation XS4 of the inputs I0 to I3 is “1”, the encoded result of 112 is input as a 4-bit input PE1111.
The encoding result of each is the lower 2 of the second output code
It is output as bits U1 and U0.

According to the principles of the fifth and sixth embodiments, when n is an arbitrary integer of 2 or more, bidirectional 2
Two bidirectional 2 ⁿ bit input PEs with ^{n + 1} bit input PEs
And one selection circuit. Further, it is also possible to adopt a configuration in which the position which is initially "0" is encoded.

[0066]

As described above, the 2 ^{n + 1} bit input PE according to the present invention is composed of two 2 ⁿ bit input PEs that operate in parallel with each other and a simple selection circuit. Therefore, regardless of the position of the searched bit, the output binary code of (n + 1) bits is determined with a constant and small delay. Further, the difference between the delay of the 2 ^{n + 1} bit input PE and the delay of the 2 ⁿ bit input PE is reduced to the extent of the delay in one logic gate. Further, the 2 ^{n +1} bit input PE according to the present invention does not require a decode selection circuit unlike the conventional case, so that the amount of hardware is reduced.

[Brief description of drawings]

FIG. 1 is a circuit diagram of an 8-bit input priority encoder according to a first embodiment of the present invention.

2 is a circuit diagram of a 4-bit input priority encoder shown in FIG.

FIG. 3 is a circuit diagram of a 16-bit input priority encoder according to a second embodiment of the present invention.

4 is a circuit diagram of an 8-bit input priority encoder shown in FIG.

FIG. 5 is a circuit diagram of a 24-bit input priority encoder according to a third embodiment of the present invention.

6 is a circuit diagram of the 16-bit input priority encoder shown in FIG.

FIG. 7 is a circuit diagram of an 11-bit input priority encoder according to a fourth embodiment of the present invention.

8 is a circuit diagram of the 3-bit input priority encoder shown in FIG. 7. FIG.

FIG. 9 is a circuit diagram of an 8-bit input priority encoder according to a fifth embodiment of the present invention.

10 is a circuit diagram of a 4-bit input priority encoder shown in FIG.

FIG. 11 is a circuit diagram of an 8-bit input priority encoder according to the sixth embodiment of the present invention.

12 is a circuit diagram of the 4-bit input priority encoder in FIG.

[Explanation of symbols]

11 and 12 switch circuits 11D, 11U, 12D and 12U switch circuits 111 and 112 switch circuits 211 and 212 switch circuits 1011 and 1012 4-bit input priority encoder 1013 selection circuit 1031 and 1032 8-bit input priority encoder 1033 selection circuit 1041 1042 4-bit input priority encoder 1043 selection circuit 1044 2-input NOR gate 1045 2-input NAND gate 1051 16-bit input priority encoder 1052 8-bit input priority encoder 1053 selection circuit 1061, 1062 8-bit input priority encoder 1063 selection circuit 1064 2-input NOR gate 1065 2-input NAND gate 1071 8-bit input Priority encoder 1072 3-bit input priority encoder 1073 selection circuit 1091, 1092 4-bit input priority encoder 1093 selection circuit 1111, 1112 4-bit input priority encoder 1113 selection circuit

Claims (16)

[Claims] 1. When a bit having a value of "1" or a bit having a value of "0" is defined as a designated value bit and the other is defined as a non-designated value bit, a given 2 ^{n + is} given. ¹
The designated value bit that first appears in the binary data of bits (n is an integer of 2 or more) is searched from the most significant bit of the binary data, and the position of the searched first designated value bit is indicated (n + 1). A priority encoder for outputting a binary code of bits, wherein the designated value bit first appearing in the first data composed of the upper 2 ⁿ bits of the binary data is the first specified value bit. From the most significant bit of the data, generate an n-bit first code indicating the position of the found first designated value bit, and all the bits forming the first data are non-designated value bits. first means for outputting a 1-bit code indicating whether the most significant bit of the binary code, in the second data constituted by the lower 2 ⁿ bits of said binary data Second means for searching the designated value bit that appears first from the most significant bit of the second data, and generating an n-bit second code indicating the position of the searched first designated value bit; A third for selecting one of the first and second codes according to only the value of the most significant bit of the binary code and outputting the selected code as the lower n bits of the binary code. Priority encoder characterized by having the means of. 2. The priority encoder according to claim 1, wherein the third means includes two switch circuits each having at least n transfer gates. 3. The priority encoder according to claim 1, wherein the first means first appears in the third data composed of upper 2 ^n-1 bits of the first data. The designated value bit to be specified is searched from the most significant bit of the third data, and the third (n-1) -th bit indicating the position of the found first designated value bit is searched.
To generate a first 1-bit code that indicates whether or not all the bits that make up the third data are non-specified value bits as the most significant bit of the first code. And a designated value bit first appearing in the fourth data composed of lower 2 ^n-1 bits of the first data from the most significant bit of the fourth data. The fourth (n-1) -th bit indicating the position of the first designated value bit searched for
Means for generating a second 1-bit code indicating whether or not all the bits forming the fourth data are non-designated value bits, and the first means. Means for selecting one of the third and fourth codes as the lower (n-1) bits of the first code depending only on the value of the most significant bit of the code of Based on the first and second 1-bit codes, the first
Priority means for generating a 1-bit code indicating whether or not all the bits forming the data are non-designated value bits. 4. The priority encoder according to claim 3, wherein the sixth means includes two switch circuits each having at least (n-1) transfer gates. Encoder. 5. The priority encoder according to claim 3, wherein the seventh means includes at least one two-input logic gate. 6. The priority encoder according to claim 1, wherein the second means first appears in the fifth data composed of upper 2 ⁿ⁻¹ bits of the second data. The designated value bit to be specified is searched from the most significant bit of the fifth data, and the fifth (n-1) -th bit indicating the position of the searched first designated value bit.
And a 1-bit code indicating that all the bits forming the fifth data are non-specified value bits as the most significant bit of the second code. And searching for the designated value bit that first appears in the sixth data composed of the lower 2 ^n-1 bits of the second data from the most significant bit of the sixth data, 6th (n-1) -th bit indicating the position of the first specified value bit found
Means for generating a code of the second code and one of the fifth code and the sixth code depending on only the value of the most significant bit of the second code. n-1) tenth for selecting as bit
Priority encoder characterized by having the means of. 7. The priority encoder according to claim 6, wherein the tenth means includes two switch circuits each having at least (n-1) transfer gates. -Encoder. 8. The priority encoder according to claim 1, wherein the binary code represents the number of non-specified value bits consecutive from the most significant bit in the binary data. . 9. When one of a bit having a value of "1" and a bit having a value of "0" is defined as a designated value bit and the other is defined as a non-designated value bit, given (2 ⁿ
+2 ^m + k) bits (n, m, k are integers, n = m + 1,
m ≧ 1, and 1 ≦ k ≦ 2 ^m ), the specified value bit that first appears in the binary data is searched from the most significant bit of the binary data, and the position of the searched specified value bit is indicated. A priority encoder for outputting a binary code of (n + 1) bits, wherein a designated value bit first appearing in first data composed of upper 2 ⁿ bits of the binary data is Searching from the most significant bit of the first data, generating an n-bit first code indicating the position of the found first designated value bit, and all bits constituting the first data are undesignated Means for outputting a 1-bit code indicating whether or not it is a value bit as the most significant bit of the binary number code; and a second (2 ^m + k) bit of the binary number data. Of data Means for searching the most significant bit of the second data for the first appearing designated value bit therein, and generating an n-bit second code indicating the position of the found first designated value bit; Means for selecting one of the first and second codes according to only the value of the most significant bit of the binary code and outputting the selected code as the lower n bits of the binary code. A priority encoder that is equipped with. 10. The priority encoder according to claim 9, wherein the binary code represents the number of non-specified value bits consecutive from the most significant bit in the binary data. . 11. When one of a bit having a value of "1" and a bit having a value of "0" is defined as a designated value bit and the other is defined as a non-designated value bit, the given (2
ⁿ +2 ^m + k) bits (n, m, k are integers, n ≧ m +
2, m ≧ 1, and 1 ≦ k ≦ 2 ^m ), the specified value bit that first appears in the binary data is searched from the most significant bit of the binary data, and the position of the found specified value bit is searched. Which is a priority encoder for outputting a (n + 1) -bit binary code indicating that the designated value first appearing in the first data composed of the upper 2 ⁿ bits of the binary data. A bit is searched for from the most significant bit of the first data, an n-bit first code indicating the position of the first specified value bit searched for is generated, and all the bits forming the first data are Means for outputting a 1-bit code indicating whether or not it is a non-specified value bit as the most significant bit of the binary code, and a low-order (2 ^m + k) bit of the binary data. Day 2 To find the designated value bit that first appears in the data from the most significant bit of the second data, and to generate a (m + 1) -bit second code indicating the position of the searched designated value bit. Means for generating an n-bit third code by adding at least one fixed value bit higher than the most significant bit of the second code, and the most significant bit of the binary code. Means for selecting one of the first and third codes according to only the value and outputting the selected code as the lower n bits of the binary code. -Encoder. 12. The priority encoder according to claim 11, wherein the binary code represents the number of non-specified value bits consecutive from the most significant bit in the binary data. . 13. A control for instructing a search direction when one of a bit having a value of "1" and a bit having a value of "0" is defined as a designated value bit and the other is defined as a non-designated value bit. 2 of the given 2 ^{n + 1} bits (n is an integer of 2 or more) according to the received control signal.
The designated value bit that first appears in the binary data is searched in order from the most significant bit of the binary data, or
To search for a designated value bit that first appears in the binary data from the least significant bit of the binary data, and output an (n + 1) -bit binary code indicating the position of the searched first designated value bit. A priority encoder, which appears first in the first data composed of the upper 2 ⁿ bits of the binary data when the control signal instructs a search in the lower direction. The designated value bits are searched in order from the most significant bit of the first data, and if the control signal indicates a search in the upper direction, then the first bit is searched.
For finding the designated value bit first appearing in the data of the first data from the least significant bit of the first data, and generating the n-bit first code indicating the position of the found first designated value bit. Means, means for generating a first 1-bit code indicating whether or not all the bits forming the first data are non-designated value bits, and the control signal is used for searching in a lower direction. When instructed, the designated value bit that first appears in the second data composed of the lower 2 ⁿ bits of the binary data is searched in order from the most significant bit of the second data, If the control signal indicates a search in the upper direction, then the second
To find the designated value bit that first appears in the data of the second data from the least significant bit of the second data, and to generate an n-bit second code indicating the position of the searched first designated value bit. Means, means for generating a second 1-bit code indicating whether or not all the bits forming the second data are non-designated value bits, and the control signal performs a search in a lower direction. When instructed, the first 1-bit code is output as the most significant bit of the binary code, and the first and second codes are output according to only the first 1-bit code. Means for selecting one of the two and outputting the selected code as the lower n bits of the binary code; and if the control signal instructs a search in the upper direction, the second 1 The bit code is the binary code Output as the most significant bit, and selects one of the second and first codes according to only the second 1-bit code, and the selected code is the lower n bits of the binary code. And a means for outputting as a priority encoder. 14. The priority encoder according to claim 13, wherein the binary code is consecutive from the most significant bit of the binary data when the control signal indicates a search in a lower direction. The number of non-designated value bits that are consecutive from the least significant bit in the binary data when the control signal directs a search in the upper direction. Characteristic priority encoder. 15. When one of a bit having a value of “1” and a bit having a value of “0” is defined as a designated value bit and the other is defined as a non-designated value bit, a given 2 ^{n + 1 is} given. The designated value bit that first appears in the binary data of bits (n is an integer of 2 or more) is searched from the most significant bit of the binary data, and the position of the searched first designated value bit is indicated (n + 1). A first binary code of bits is output, and the designated value bit that first appears in the binary data is searched from the least significant bit of the binary data, and the position of the searched first designated value bit is determined. A priority encoder for outputting a second binary code of (n + 1) bits shown, which first appears in the first data composed of the upper 2 ⁿ bits of the binary data. The designated value bit is the first Means for searching the most significant bit of the data and generating an n-bit first code indicating the position of the found first designated value bit; and the designated value bit first appearing in the first data For searching the least significant bit of the first data, and generating an n-bit second code indicating the position of the first specified value bit found, and all of the units forming the first data. The 1-bit code indicating whether the bit is a non-specified value bit is the first 2
Means for outputting as the most significant bit of a binary code, and a designated value bit that first appears in the second data composed of the lower 2 ⁿ bits of the binary data, of the second data Means for searching from the most significant bit and generating an n-bit third code indicating the position of the found first designated value bit; and a designated value bit that appears first in the second data, Means for searching the least significant bit of the second data and generating an n-bit fourth code indicating the position of the first specified value bit found, and all the bits forming the second data The 1-bit code indicating whether it is a non-specified value bit is the second 2
Means for outputting as the most significant bit of a binary code, and selecting one of the first and third codes according to only the value of the most significant bit of the first binary code, and selecting Means for outputting a code as the lower n bits of the first binary code, one of the second and fourth codes depending on only the value of the most significant bit of the second binary code And a means for outputting the selected code as the lower n bits of the second binary code. 16. The priority encoder according to claim 15, wherein the first binary code is the number of unspecified value bits consecutive from the most significant bit in the binary data.
2. The priority encoder according to claim 1, wherein the binary code represents the number of non-specified value bits consecutive from the least significant bit in the binary data.