Abstract:
A priority encoding technique is provided which outputs a code corresponding to the highest-priority input line among input lines having a true value when true values are input to more than one of the input lines, which are prioritized and given codes. The technique includes performing higher-order-bit encoding by outputting higher-order bits corresponding to the group having its highest priority among those groups distinguished by the higher-order bits to which true values are input; and performing lower-order-bit encoding to output lower-order bits corresponding to the input line having the highest priority among input lines to which the true values are input. Further, the lower-order-bit encoding includes invalidating the input of true values into the input lines to groups having lower priorities than the highest-priority group distinguished by the higher-order bits.

Description:
RELATED PATENT APPLICATION 
     This application claims priority from Japanese patent application number 11-302088, filed Oct. 25, 1999, which is hereby incorporated herein by reference in its entirety. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a priority encoder and an encoding method using the priority encoder, and more particularly to a compact and high-speed priority encoder and a high-speed encoding method. 
     2. Description of Related Art 
     The function of a priority encoder is to output a code corresponding to the highest-priority input line among a plurality of input lines having a true value when input signal is input to more than one of input lines which are prioritized and given codes. FIG. 13 shows an example of a prior encoder and FIG. 14 is a truth table showing inputs and outputs of the priority encoder shown in FIG.  13 . In the priority encoder  100  (all the inputs are negative logic) shown in FIG. 13, when more than one of eight data inputs (IN 7 N, IN 6 N, IN 5 N, IN 4 N, IN 3 N, IN 2 N, IN 1 N, and IN 0 N) are simultaneously activated (“0”), a 3-bit code (binary code) representing the input having the highest priority among the activated inputs (this input will be hereinafter referred to as “highest-priority input”) is output. As shown in FIG. 13, this code is generated by combining input signals and their inverted signals. 
     The input IN 7 N has the highest priority. The smaller the number t in INtN is, the lower the priority is. In this example, the highest-priority input is determined with respect to an active input (“0”). As shown in FIG. 14, when the input IN 7 N having the highest priority has the highest-priority true input, the output signals (“A2 A1 A0”) of the encoder  100  are “0 0 0”, and when the input IN 0 N having the lowest priority has the highest-priority true input, the output signals are “1 1 1”. Thus, the output signals are signals in which a binary code corresponding to the number t of INtN is inverted. The mark “−” in FIG. 14 denotes “don&#39;t care”. An output GS is a signal representing the presence or absence of active input signals into the encoder  100 . An input EI and an output EO are signals for expansion, and the output EO is connected to the input EI of the next-stage encoder. 
     FIG.  15 ( a ) shows another example of a priority encoder and FIG.  15 ( b ) is a truth table showing inputs and outputs of the priority encoder shown in FIG.  15 ( a ). A priority encoder  110  shown in FIG.  15 ( a ) comprises a selector circuit  116  and a plurality of priority encoders  112  and  114 . FIG.  16 ( a ) shows an example of a 4-to-2 priority encoder  112 , and FIG.  16 ( b ) is a truth table showing inputs and outputs of the priority encoder  112  shown in FIG.  16 ( a ). FIG. 17 shows an example of the selector circuit  116 . Unlike the priority encoder  100  shown in FIG.  13  and its inputs and outputs shown in FIG. 14, the input IN 0 N has the highest priority in the priority encoder  110 . The larger the number t in INtN is, the lower the priority is. As shown in FIG.  15 ( b ), when the input IN 0 N having the highest priority has the highest-priority true input, the output signals (“A2 A1 A0”) of the encoder  110  are “0 0 0”, and when the input IN 7 N having the lowest priority has the highest-priority true input, the output signals are “1 1 1”. Thus, the output signals are represented in binary notation, indicating the number t in INtN of the highest-priority input having a true value. 
     Eight data inputs (IN 0 N, IN 1 N, IN 2 N, IN 3 N, IN 4 N, IN 5 N, IN 6 N, and IN 7 N) are divided into two groups, namely a group of four higher-priority inputs (IN 0 N, IN 1 N, IN 2 N, and IN 3 N) and a group of four lower-priority inputs (IN 4 N, IN 5 N, IN 6 N, and IN 7 N). The 4-to-2 priority encoders  112  and  114  receives these two groups of inputs, respectively. The encoders  112  and  114  each output a 2-bit binary code representing the active highest-priority input of the four inputs. The selector circuit  116  outputs lower-order 2 bits (“A1 A0”) of the output signals (“A2 A1 A0”) in response to the output from the higher encoder  112 . 
     By combination of a selector circuit and a plurality of priority encoders, and by expanding the input and output of the selector circuit, the priority encoder can be configured as a greater whole encoder, for example, a 64-to-6 priority encoder  120 , by using four 16-to-4 priority encoders  122 , as shown in FIG.  18 . However, since the priority encoder contains a number of components as shown in FIG. 13, a combination of a plurality of priority encoders as shown in FIG. 18 increases the number of components in the greater whole encoder, which leads to the increase in the circuit size of the greater whole encoder, the increase in the number of circuit stages, and the reduction of processing speed. 
     SUMMARY OF THE INVENTION 
     Objects of the present invention are to downsize the priority encoder by reducing the number of components and to achieve a high-speed encoding. 
     The priority encoder of the present invention comprises: 
     higher-order-bit encoding means for outputting a higher-order m-bit code corresponding to the group having the highest priority among those groups out of 2 m  groups distinguished by higher-order m bits to which true values are input (hereinafter referred to as “highest-priority group distinguished by the higher-order m bits”); each of the 2 m  groups consisting of 2 n  input lines having common higher-order m bits of (m+n)-bit output code; and 
     lower-order-bit encoding means for outputting a lower-order n-bit code corresponding to the input line having the highest priority among input lines to which true values are input; the input lines being part of 2 n  input lines which make up the highest-priority group distinguished by the higher-order m bits and which are distinguished by the lower n bits of the (m+n)-bit output code. 
     An encoding method using the priority encoder of the present invention comprises the steps of: 
     outputting higher-order bits corresponding to the group having the highest priority among those groups distinguished by higher-order bits to which true values are input (hereinafter referred to as “highest-priority group distinguished by the higher-order bits”); each of the groups distinguished by higher-order bits comprising input lines which are grouped on the basis of higher-order bits of the code; and 
     outputting lower-order bits corresponding to the input line having the highest priority among input lines to which true values are input; the input lines being part of input lines which make up the highest-priority group distinguished by the higher-order bits and are distinguished by the lower bits of the output code. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a circuit diagram showing an embodiment of a priority encoder of the present invention; 
     FIG.  2 ( a ) shows an example of a NOR circuit included in the priority encoder of FIG. 1, and FIG.  2 ( b ) shows an example of an OR circuit included in the priority encoder of FIG. 1; 
     FIG. 3 is a truth table showing inputs and outputs of the priority encoder shown in FIG. 1; 
     FIG. 4 is a truth table showing inputs and outputs of a 4-to-2 priority encoder  20  included in the priority encoder shown in FIG. 1; 
     FIG. 5 is a truth table showing inputs and outputs of a 4-to-2 priority encoder  40  included in the priority encoder shown in FIG. 1; 
     FIG. 6 is a circuit diagram showing another embodiment of the priority encoder of the present invention; 
     FIG. 7 is a conceptual view of a memory divided into subarray blocks; 
     FIGS.  8 ( a ) and  8 ( b ) are enlarged circuit diagrams showing further embodiments of a main part of the priority encoder of the present invention; 
     FIG. 9 is a circuit diagram showing a still further embodiment of the priority encoder of the present invention; 
     FIG.  10 ( a ) is an enlarged circuit diagram showing another embodiment of a main part of the priority encoder of the present invention and FIG.  10 ( b ) is a truth table showing inputs and outputs of the main part of the priority encoder shown in FIG.  10 ( a ); 
     FIGS.  11 ( a ) and  11 ( b ) are circuit diagrams showing further embodiments of FIGS.  8 ( a ) and  8 ( b ). 
     FIGS.  12 ( a ) and  12 ( b ) are circuit diagrams showing further examples of FIGS.  2 ( a ) and  2 ( b ). 
     FIG. 13 is a circuit diagram showing an example of a conventional priority encoder; 
     FIG. 14 is a truth table showing inputs and outputs of the priority encoder shown in FIG. 13; 
     FIG.  15 ( a ) is a circuit diagram showing another example of a conventional priority encoder, and FIG.  15 ( b ) is a truth table showing inputs and output of the priority encoder shown in FIG.  15 ( a ); 
     FIG.  16 ( a ) is a circuit diagram showing an example of a priority encoder  112  included in the priority encoder shown in FIG.  15 ( a ), and FIG.  16 ( b ) is a truth table showing inputs and outputs of the priority encoder  112  shown in FIG.  16 ( a ); 
     FIG. 17 is a circuit diagram showing an example of a selector circuit included in the priority encoder shown in FIG.  15 ( a ); and 
     FIG. 18 is a block diagram showing a further example of a conventional priority encoder. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     An embodiment of the priority encoder and the encoding method according to the present invention will hereinafter be described in detail with reference to the accompanying drawings. In this embodiment, as shown in FIG. 1, the priority encoder outputs a 4-bit code (“A3 A2 A1 A0”) corresponding to the number of the input (namely, t of INt) having the highest priority among the active (“1”) inputs in 16 inputs (IN 0 , IN 1 , IN 2 , IN 3 , IN 4 , IN 5 , IN 6 , IN 7 , IN 8 , IN 9 , IN 10 , IN 11 , IN 12 , IN 13 , IN 14 , IN 15 ). This code is a signal in which a binary code corresponding to the number of the input is inverted. The lower the number of the input (t of INt) is, the higher the priority is. In this embodiment, input lines are grouped into blocks A, B, C, and D according to higher-order 2 bits (“A3 A2”) of an output code (“A3 A2 A1 A0”). The higher-order 2 bits (“A3 A2”) of the output code are output from the 4-to-2 priority encoder  20 . The lower-order 2 bits (“A1 A0”) are output from the 4-to-2 priority encoder  40  on the basis of an output from the block E. 
     The block A, B, C, and D are input groups of input lines whose higher-order bits of output code are “1 1 ”, “1 0”, “0 1”, and “0 0”, respectively. More specifically, the blocks A, B, C, and D receive the inputs IN 0 , IN 1 , IN 2  and IN 3 , the inputs IN 4 , IN 5 , IN 6  and IN 7 , the inputs IN 8 , IN 9 , IN 10  and IN 11 , and the inputs IN 12 , IN 13 , IN 14 , and IN 15 , respectively. 
     The block A comprises a NOR circuit  12   a  which receives the inputs IN 0 , IN 1 , IN 2 , and IN 3 . An output (NOR_A) of the NOR circuit  12   a  comes out of the block A. An example of the NOR circuit  12   a  is shown in FIG.  2 ( a ). In this figure, TP 0  indicates a pMOS transistor, and TN 0 , TN 1 , TN 2 , and TN 3  each indicate an nMOS transistor. The output NOR_A is initially precharged to an H-level (“1”) with a PRCHG signal being active and then when at least one of the inputs IN 1 , IN 1 , IN 2 , and IN 3  becomes active (“1”), the NOR_A goes down to an L-level (“0”). 
     The block B comprises a NOR circuit  12   b  and four AND circuits  22 . The NOR circuits  12   b  receives the inputs IN 4 , IN 5 , IN 6 , and IN 7 . The AND circuits  22  each receive the output (NOR_A) from the NOR circuit  12   a  of the block A, while they each receive the inputs IN 4 , IN 5 , IN 6 , and IN 7 . The block B sends out an output (IN 4   v ) of the AND circuit to which NOR_A and the input IN 4  are input, an output (IN 5   v ) of the AND circuit to which NOR_A and the input IN 5  are input, an output (IN 6   v ) of the AND circuit to which NOR_A and the input IN 6  are input, an output (IN 7   v ) of the AND circuit to which NOR_A and the input IN 7  are input, and an output (NOR_B) of the NOR circuit  12   b.    
     The block C comprises a NOR circuit  12   c  and four AND circuits  24 . The NOR circuit  12   c  receives the inputs IN 8 , IN 9 , IN 10 , and IN 11 . The AND circuits  24  each receive a logical product (AND_C) of the output (NOR_A) from the NOR circuit  12   a  of the block A and an output (NOR_B) from the NOR circuit  12   b  of the block B, while they each receive the inputs IN 8 , IN 9 , IN 10 , and IN 11 . The logical product (AND_C) is obtained with an AND circuit  14 . The block C sends out an output (IN 8   v ) of the AND circuit to which AND_C and the input IN 8  are input, an output (IN 9   v ) of the AND circuit to which AND_C and the input IN 9  are input, an output (IN 10   v ) of the AND circuit to which AND_C and the input IN 10  are input, an output (IN 11   v ) of the AND circuit to which AND_C and the input IN 11  are input, and an output (NOR_C) of the NOR circuit  12   c.    
     The block D comprises a NOR circuit  12   d  and four AND circuits  26 . The NOR circuit  12   d  receives the inputs IN 12 , IN 13 , IN 14 , and IN 15 . The AND circuits  26  each receive a logical products (AND_D) of the output (NOR_A) from the NOR circuit  12   a  of the block A, the output (NOR_B) from the NOR circuit  12   b  of the block B, and the output (NOR_C) from the NOR circuit  12   c  of the block C, while they each receive the inputs IN 12 , IN 13 , IN 14 , and IN 15 . The logical product (AND_D) is calculated in the AND circuit  16 . The block D sends out an output (IN 12   v ) of the AND circuit to which AND_D and the input IN 12  are input, an output (IN 13   v ) of the AND circuit to which AND_D and the input IN 13  are input, an output (IN 14   v ) of the AND circuit to which AND_D and the input IN 14  are input, an output (IN 15   v ) of the AND circuit to which AND_D and the input IN 15  are input, and an output (NOR_D) of the NOR circuit  12   d.    
     The block E comprises four OR circuits ( 18   a ,  18   b ,  18   c , and  18   d ). The OR circuits each receive inputs corresponding to the outputs (“A3 A2 A1 A0”) having common lower-order bits (A1 A0). The OR circuits  18   a ,  18   b ,  18   c , and  18   d  receive inputs corresponding to lower-order bits “1 1”, “1 0”, “0 1”, and “0 0”, respectively. More specifically, the OR circuits  18   a ,  18   b ,  18   c , and  18   d  receive the inputs IN 0 , IN 4   v , IN 8   v  and IN 12   v , the inputs IN 1 , IN 5   v , IN 9   v  and IN 13   v , the inputs IN 2 , IN 6   v , IN 10   v  and IN 14   v , and the inputs IN 3 , IN 7   v , IN 11   v  and IN 15   v , respectively. The block E sends out an output (OR_ 0 ) from the OR circuit  18   a , an output (OR_ 1 ) from the OR circuit  18   b , the output (OR_ 2 ) from the OR circuit  18   c , and the output (OR_ 3 ) from the OR circuit  18   d . An example of the OR circuit  18   a  is shown in FIG.  2 ( b ). In this figure, TP 0 , TP 1 , TP 2 , and TP 3  each indicate a pMOS transistor, and TN 0  indicates an nMOS transistor. The OR_ 0  is initially precharged to an L-level (“0”) with a PRCHG signal being active and then when at least one of IN 0 , IN 4   v , IN 8   v , and IN 12   v  becomes active (“1”), the OR_ 0  goes up to an H-level (“1”) . 
     The output (NOR_A) from the NOR circuit  12   a  indicates the presence or absence of a true value or an active input in the inputs (IN 0 , IN 1 , IN 2 , and IN 3 ) included in the block A. The output (NOR_A) becomes active (“0”) if at least one true value is present, whereas it becomes inactive (“1”) if true value is absent. Likewise, the outputs (NOR_B, NOR_C, and NOR_D) of the NOR circuits  12   b ,  12   c , and  12   d  indicate the presence or absence of a true value in the inputs (IN 4 , IN 5 , IN 6 , and IN 7 ) included in the block B, in the inputs (IN 8 , IN 9 , IN 10 , and IN 11 ) included in the block C, and in the inputs (IN 12 , IN 13 , IN 14 , and IN 15 ) included in the block D, respectively. The outputs (NOR_B, NOR_C and NOR_D) become active (“0”) if at least one true value is present, whereas they become inactive (“1”) if true value is absent. Thus, the outputs (NOR_A ,NOR_B, NOR_C, and NOR_D) of the NOR circuits  12   a ,  12   b ,  12   c , and  12   d  each indicate the presence or absence of a true value in each block. 
     The outputs (NOR_A ,NOR_B, NOR_C, and NOR_D) from the NOR circuits  12   a ,  12   b ,  12   c , and  12   d  are input to the 4-to-2 priority encoder  20 . The outputs NOR_A, NOR_B, NOR_C, and NOR_D indicate the presence or absence of inputs corresponding to the outputs having higher-order bits of “1 1”, “1 0”, “0 1”, and “0 0”, respectively. As shown in FIG.  3  and FIG. 4, higher-order bits (“A3 A2 ”) of the output code (“A3 A2 A1 A0”) are obtained by encoding NOR_A, NOR_B, NOR_C, and NOR_D by the priority encoder  20 . 
     On the other hand, the AND circuits  22  may invalidate the inputs IN 4 , IN 5 , IN 6  and IN 7  to the block B before sending them to the block E. Invalidation of these inputs is determined according to the output (NOR_A) from the NOR circuit  12   a  in the block A. If at least one of the inputs IN 0 , IN 1 , IN 2 , and IN 3  is “1”, the inputs IN 4   v , IN 5   v , IN 6   v  and IN 7   v  are invalidated (“IN 4   v  IN 5   v  IN 6   v  IN 7   v ”=“0 0 0 0”) regardless of inputs IN 4 , IN 5 , IN 6  and IN 7  because the output NOR_A becomes “0”. Only if none of the inputs IN 0 , IN 1 , IN 2 , and IN 3  are a true value, the inputs IN 4 , IN 5 , IN 6  and IN 7  to the block B are sent to the block E as they are (“IN 4   v  IN 5   v  IN 6   v  IN 7   v ”=“IN4 IN5 IN6 IN7”) because the output NOR_A becomes “1”. 
     The AND circuits  24  may invalidate the inputs IN 8 , IN 9 , IN 10  and IN 11  to the block C before sending them to the block E. Invalidation of these inputs is determined by the output (AND_C) from the AND circuit  14 . If at least one of the inputs IN 0 , IN 1 , IN 2 , IN 3 , IN 4 , IN 5 , IN 6 , and IN 7  is “1”, either output NOR A or NOR B becomes “0” and the output AND_C becomes “0”. Therefore, inputs IN 8   v , IN 9   v , IN 10   v  and IN 11   v  are invalidated (“IN 8   v  IN 9   v  IN 10   v  IN 11   v ”=“0 0 0 0”) regardless of inputs IN 8 , IN 9 , IN 10  and IN 11 . Only if none of the inputs IN 0 , IN 1 , IN 2 , IN 3 , IN 4 , INS, IN 6 , and IN 7  are a true value, the inputs IN 8 , IN 9 , IN 10  and IN 11  to the block C are sent to the block E as they are (“IN 8   v  IN 9   v  IN 10   v  IN 11   v ”=“IN8 IN9 IN10 IN11”) because both of outputs NOR_A and NOR_B become “1” and the output AND_C becomes “1”. 
     The AND circuits  26  may invalidate the inputs IN 12 , IN 13 , IN 14  and IN 15  to the block D before sending them to the block E. Invalidation of these inputs is determined by the output (AND_D) from the AND circuit  16 . If at least one of the inputs IN 0 , IN 1 , IN 2 , IN 3 , IN 4 , IN 5 , IN 6 , IN 7 , IN 8 , IN 9 , IN 10 , and IN 11  is “1”, at least one of outputs NOR_A, NOR_B and NOR_C becomes “0” and the output AND_D becomes “0”. Therefore, inputs IN 12   v , IN 13   v , IN 14   v  and IN 15   v  are invalidated (“IN 12   v  IN 13   v  IN 14   v  IN 15   v ”=“0 0 0 0”) regardless of the inputs IN 12 , IN 13 , IN 14  and IN 15 . Only if none of the inputs IN 0 , IN 1 , IN 2 , IN 3 , IN 4 , IN 5 , IN 6 , IN 7 , IN 8 , IN 9 , IN 10 , and IN 11  is a true value, the inputs IN 12 , IN 13 , IN 14  and IN 15  to the block D are sent to the block E as they are (“IN 12   v  IN 13   v  IN 14   v  IN 15   v ”=“IN12 IN13 IN14 IN15”) because all the outputs NOR_A, NOR_B, and NOR_C become “1” and the output AND_D becomes “1”. 
     As described above, the AND circuits  22 ,  24 , and  26  invalidate or validate the inputs IN 4 , IN 5 , IN 6  and IN 7 , the inputs IN 8 , IN 9 , IN 10 , and IN 11 , and the inputs IN 12 , IN 13 , IN 14  and IN 15 , respectively. If any input to the block A (IN 0 , IN 1 , IN 2 , and IN 3 ) has a true value, all the inputs other than the inputs IN 0 , IN 1 , IN 2  and IN 3  are sent to the block E in an invalidated state. If there is no true value in the block A (“IN0 IN1 IN2 IN3”=“0 0 0 0”) but there is at least one true value in the block B (IN 4 , IN 5 , IN 6 , and IN 7 ), any input other than IN 4 , IN 5 , IN 6  and IN 7  is sent to the block E in an invalidated state. Alternatively, if there is no true value in the blocks A and B (“IN0 IN1 IN2 IN3 IN4 IN5 IN6 IN7”=“0 0 0 0 0 0 0 0”) but there is at least one true value in the block C (IN 8 , IN 9 , IN 10 , and IN 11 ), any input other than IN 8 , IN 9 , IN 10  and IN 11  is sent to the block E in an invalidated state. Alternatively, if there is no true value in the blocks A, B and C (“IN 0  IN 1  IN 2  IN 3  IN 4  IN 5  IN 6  IN 7  IN 8  IN 9  IN 10  IN 11 ”=“ 0   0   0   0   0   0   0   0   0   0   0   0 ”) but there is at least one true value in the block D (IN 12 , IN 13 , IN 14 , and IN 15 ), any input other than IN 12 , IN 13 , IN 14  and IN 15  is sent to the block E in an invalidated state. The outputs (OR_ 0 , OR_ 1 , OR_ 2 , and OR_ 3 ) from the OR circuits  18   a ,  18   b ,  18   c , and  18   d  indicate the presence or absence of a true value in the respective input lines included in the highest-priority block (block A, B, C, or D) among the blocks to which true values are input. 
     The outputs OR_ 0 , OR_ 1 , OR_ 2 , and OR_ 3  from the OR circuits  18   a ,  18   b ,  18   c , and  18   d  are input into the 4-to-2 priority encoder  40 . The outputs OR_ 0 , OR_ 1 , OR_ 2 , and OR_ 3  indicate the presence or absence of a true value in the respective input lines included in the highest-priority block among the blocks to which true values are input. Specifically, the outputs OR_ 0 , OR_ 1 , OR_ 2 , and OR_ 3  indicate the presence or absence of a true value to inputs corresponding to an output code whose lower-order bits are “1 1”, “1 0”, “0 1”, and “0 0”, respectively. As shown in FIG.  3  and FIG. 5, the outputs OR_ 0 , OR_ 1 , OR_ 2 , and OR_ 3  are encoded by the priority encoder  40  to obtain lower-order bits (“A1 A0”) of the outputs (“A3 A2 A1 A0”). 
     In the present invention, the blocks A, B, C, and D do not comprise any priority encoders. The block A comprises only a NOR circuit, and the blocks B, C, and D each comprise a NOR circuit and AND circuits only. There are only two priority encoders used in the present invention: the one is the priority encoder  20  for outputting higher-order bits of a output code; and the other is the priority encoder  40  which outputs lower-order bits of the code. In general, an OR circuit and AND circuit are superior to a priority encoder in reducing a circuit size. 
     In the present invention, the whole priority encoder comprises fewer priority encoders than the conventional one, and therefore the reduction in circuit size can be achieved. For example, since the blocks A, B, C, D comprise a NOR circuit and AND circuits instead of priority encoders, the reduction in circuit stages and a high-speed encoding can be achieved. In the present invention, higher-order bits and lower-order bits can be encoded by separate two priority encoders  20  and  40 , and therefore an even higher speed encoding can be achieved. 
     FIG. 6 shows another example of the priority encoder of the present invention. This priority encoder  30  outputs a 6-bit code (“A5 A4 A3 A2 A1 A0”) representing the highest-priority input among a plurality of active (“1”) inputs in 64 inputs (IN 0  to IN 63 ). The 64-to-6 priority encoder  30  shown in FIG. 6 has two more lower-order bits than the priority encoder  10  shown in FIG.  1 . The blocks A, B, C, and D receives the inputs IN 0  to IN 15 , the inputs IN 16  to IN 31 , the inputs IN 32  to IN 47 , and the inputs IN 48  to IN 63 , respectively. The block E comprises OR circuits  38   a  to  38   p  to each of which signals from input lines having the common lower-order bits in each block are input. The outputs (OR_ 0  to OR_ 15 ) from the OR circuits  38   a  to  38   p  are input into a 16-to-4 priority encoder  48 . Just as in the above case, only two priority encoders are used in this case for separately outputting higher-order bits and lower-order bits. The 4-to-2 priority encoder  20  outputs higher-order bits, and the 16-to-4 priority encoder outputs lower-order bits. Compared to a conventional 64-to-6 priority encoder  120  shown in FIG. 18, it is clear that the number of 16-to-4 priority encoders of a large circuit size is significantly reduced in the present invention. 
     The priority encoder and the encoding method of the present invention can be used in a content addressable memory (“CAM”). In general, where memory capacity is large, a memory  102  is divided into a plurality of subarray blocks, for example, four subarray blocks A, B, C, and D as shown in FIG.  7 . Outputs  104  (for example, outputs indicating matches and mismatches of words) from memory cell arrays in each subarray block are input into a priority encoder. These memory cell arrays are systematically arranged. Conventionally, each of subarray blocks A, B, C, and D needs to include a priority encoder. However, in the priority encoder and the encoding method of the present invention, the blocks A to D shown in FIGS. 1 and 6 are included in the subarray blocks A to D, so that each subarray block only needs to include a NOR circuit and AND circuits. Since priority encoders do not need to be included in subarray blocks, subarray blocks can be downsized. This downsizing of subarray blocks allows downsizing of the whole memory and shortening of signal lines which control the whole memory and signal lines such as global word lines across a wide area. Thus, downsizing, high-speed, and low power consumption of memory can be achieved. 
     As shown in FIG.  8 ( b ), the block B, C, and D may comprise OR circuits  42   a ,  44   a , and  46   a  to reduce wirings between blocks to one. FIG.  8 ( a ) is an enlarged circuit diagram of a main part of the priority encoder  30  shown in FIG. 6, mainly showing input lines IN 0 , IN 16 , IN 32 , and IN 48 , and OR circuit  38   a . As shown in FIG.  8 ( a ), where the logical sum of the inputs IN 0 , IN 16   v , IN 32   v , and IN 48   v  is determined by the OR circuit  38   a  in the block E, there are two wirings (W 0 , W 16 ) between blocks B and C, three wirings (W 0 , W 16 , W 32 ) between blocks C and D, and four wirings (W 0 , W 16 , W 32 , W 48 ) between blocks D and E. As shown in FIG.  8 ( b ), where the blocks B, C, and D comprise the OR circuits  42   a ,  44   a , and  46   a , respectively, only one wiring (W′ 0 , W′ 16 , W′ 32 , W′ 48 ) is required between every two blocks. 
     As shown in FIG. 9, the blocks A, B, C, and D may comprise the NOR circuits  12   a ,  12   b ,  12   c , and  12   d , respectively, and the block E may comprise the selector circuits  0 ,  1 ,  2 , and  3 . A selection control signal input terminal of each selector circuit receives outputs (NOR_A, NOR_B, NOR_C, and NOR_D) from the NOR circuits. The selector circuits  0 ,  1 ,  2  and  3  selectively output one of the inputs IN 0 , IN 4 , IN 8  and IN 12 , one of the inputs IN 1 , IN 5 , IN 9  and IN 13 , one of the inputs IN 2 , IN 6 , IN 10  and IN 14 , and one of the inputs IN 3 , IN 7 , IN 11  and IN 15 , respectively, to the 4-to-2 priority encoder  40  as an output OR_ 0 , OR_ 1 , OR_ 2  and OR_ 3  in accordance with an output of each NOR circuit. The inputs selected by the selector circuits  0 ,  1 ,  2 , and  3  are included in the highest-priority block (block A, B, C, or D) among the blocks to which true values are input. 
     As shown in FIG.  10 ( a ), the priority encoder may comprise OR circuits  52  and AND circuits  54 . In this case, where a higher block is active (“0”), outputs NOR_A, NOR_B, NOR_C, and NOR_D in lower blocks are invalidated (“1”). FIG.  10 ( b ) shows outputs (NOR_A′, NOR_B′, NOR_C′, and NOR D′) after invalidation. The signals shown in FIG.  10 ( b ) can be input into an ordinal encoder having no priority to obtain two higher order bits (“A3 A2”) of the output code. The circuits shown in FIG.  10 ( a ) transforms the selectors  0 ,  1 ,  2 , and  3  shown in FIG. 9 to simple selectors having no priority. 
     The priority encoder and the encoding method of the present invention can reduce the number of priority encoders used inside the greater whole priority encoder, so that its circuit size can be reduced. The use of OR circuits and AND circuits instead of priority encoders leads to the reduction in number of circuit stages, and therefore a high-speed encoding can be achieved. In the present invention, higher-order bits and lower-order bits can be encoded in parallel by separate two priority encoders, so that a higher-speed encoding can be achieved. Furthermore, by using the priority encoder and the encoding method of the present invention in a content addressable memory (“CAM”), memory subarray blocks can be downsized, so that downsizing, high-speed, and low power consumption of memory can be achieved. 
     While the embodiments of the present invention have thus been described with reference to the drawings, it should be understood that the present invention be not limited to the embodiments shown in the drawings. For example, in circuitry shown in FIG.  11 ( a ) in which the AND circuits  34  and  36  shown in FIG. 6 are added to the circuitry shown in FIG.  8 ( b ), the number of components (the number of transistors) can be further reduced by employing positive and negative logic. Where the circuitry shown in FIG.  11 ( a ) is CMOS (complementary metal-oxide semiconductor) static circuitry, six transistors are required in the AND circuits  22 ,  24 ,  26  and  34 , and the OR circuits  42   a ,  44   a , and  46   a , and eight transistors are required in the AND circuit  36 . Thus  50  transistors are required. In the case of the circuitry shown in FIG.  11 ( b ), α, β, and γ parts of the circuitry may each consist of six transistors, a NAND circuit of four transistors, and a NOT circuit of two transistors. Thus the circuitry shown in FIG.  11 ( b ) may be comprised of  34  transistors. Furthermore, as output Y 1  of the α part and output Y 3  of the γ part are negative logic and output Y 2  of the β part and output Y 4  of the NOT circuit  33  are positive logic, the NOT circuit  33  in the final stage can be omitted if the output OR_ 0  is received by a negative logic circuit. Thus the circuitry shown in FIG.  11 ( b ) may be comprised of  32  transistors. Although the AND circuits  34  and  36  and the NAND circuit  35  are used only once in each higher-bit group, other circuits are repeatedly used in the same pattern in each higher-bit group. Assuming that an integer indicating the number of repetitions is n, the number of transistors required in the circuitry shown in FIG.  11 ( a ) is (36n+14), and the number of transistors required in the circuitry shown in FIG.  11 ( b ) is (22n+12), so that the difference between these circuities are (14n+2). As the integer n is higher, the number of transistors required in circuitry can be more reduced. 
     The NOR circuit and the OR circuit shown in FIGS.  2 ( a ) and  2 ( b ) may be configured as shown in FIGS.  12 ( a ) and  12 ( b ). If the input lines IN 0  to IN 15  into the NOR circuits ( 12   a ,  12   b ,  12   c  and  12   d ) in FIG. 1 are driven by a open drain circuit of a nMOSFET (N-channel Metal Oxide Semiconductor Field Effect Transistor), a wired AND circuitry with a pull-up resistor can be used, so that the circuitry becomes simpler than the one shown in FIG.  2 ( a ). In this case, however, since the inputs IN 0 N to IN 15 N are negative logic, the circuitry shown in FIG.  12 ( a ) works as a NOR circuit, and TP 0  is a substitute for a resistor. Alternatively, if the input lines IN 0  to IN 15   v  into the OR circuits ( 18   a ,  18   b ,  18   c , and  18   d ) in FIG. 1 are driven by a pMOSFET open-drain circuit, a wired OR circuit with a pull-down resistor can be used, so that the circuitry become quite simple as shown in FIG.  12 ( b ). In this case, TN 0  is a substitute for a resistor. This circuitry requires only one wiring crossing the blocks A to D in FIG.  1 . In both circuits shown in FIG.  12 ( a ) and  12 ( b ), DC current can be effectively controlled by controlling the gates in such a manner that transistors turns on only during a precharging period. Various improvements, modifications and variations can be made to the embodiments on the basis of knowledge of those skilled in the art without departing from the scope of the present invention.