Patent Publication Number: US-4924421-A

Title: Priority encoding system

Description:
BACKGROUND OF THE INVENTION 
     This invention relates to a logic operation system for detecting the first bit position having a 1 (or 0) as viewed from the least significant bit (LSB) of an input data by using a priority encoder capable of encoding the first bit position having a 1 (or 0) as viewed from the most significant bit (MSB). 
     FIG. 3 shows a conventional logic circuit for performing such an encoding operation. See the 1985 Mitsubishi Data Book, Bipolar Digital IC &lt;LSTTL&gt;, pp 2-162 to 2-163. In this figure, D is an 8-bit input data and D 0  -D 7  are respective bits. When the 8-bit data D is applied to the input terminals, a pair of priority encoders 11 and 12 detect the predetermined priority bit positions among those having a 1 and generate 3-bit binary encoded outputs A M  and A L , respectively. The priority encoder 11 encodes the first bit position having a 1 as viewed from the MSB of the input data D while the priority encoder 12 encodes the first bit position having a 1 as viewed from the LSB. 
     FIG. 4 shows respective input and output bits of the priority encoder 11 or 12 of FIG. 3, in which like reference characters denote identical or equivalent parts or components of FIG. 3 and A 0  -A 2  are respective bits of the encoded output A M  or A L . 
     FIGS. 5(a) and 5(b) show truth tables for the priority encoders 11 and 12, respectively, when the input and encoded output are 8-bit and 3-bit binary numbers, respectively. The symbol X is a given value. 
     The operation of this logic circuit will be described. Suppose that the input 8-bit data D is a binary number 00101010 and that the MSB and LSB are the 7th (D 7 ) and 0th (D 0 ) bits, respectively. This input data D has 1s at the 5th (D 5 ), 3rd (D 3 ), and 1st (D 1 ) bit positions. 
     The priority encoder 11 encodes the bit position of the 1 that is closest to the MSB in the input data D. In this example, it is the 5th bit (D 5 ). Consequently, the priority encoder 11 generates a binary number 101 encoding 5 of the 5th bit position D 5  according to the truth table of FIG. 5(a). The priority encoder 12, on the other hand, encodes the bit position of the 1 that is closest to the LSB in the input data D. In this example, it is the 1st bit (D 1 ). Consequently, the priority encoder 12 generates a binary number 001 encoding 1 of the 1st bit position D 1  according to the truth table of FIG. 5(b). 
     SUMMARY OF THE INVENTION 
     It is an object of the present invention to provide a compact logic operation system having a single priority encoder in contrast to the conventional one which has a pair of priority encoders. 
     Another object of the invention is to provide a simple logic operation system capable of performing a logic operation with a conventional logic circuit. 
     According to the invention, the first bit position having a 1 as viewed from the LSB may be encoded by feeding the result of an exclusive OR (XOR) operation on the input data and the value obtained by subtracting 1 from the input data to a priority encoder capable of encoding the first bit position having a 1 as viewed from the MSB. 
     Other objects, features, and advantages of the invention will be apparent from the following description taken in conjunction with the accompanying drawing. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram of a logic circuit for a logic operation system according to an embodiment of the invention; 
     FIG. 2 is a flow chart showing the operational steps of the system of FIG. 1; 
     FIG. 3 is a block diagram of a conventional logic circuit; 
     FIG. 4 is a block diagram of the priority encoder of the logic circuit of FIG. 3; and 
     FIGS. 5(a) and 5(b) are truth tables of the priority encoders. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     In FIG. 1, there is shown a logic operation system in which like reference characters denote identical or equivalent parts or components of FIG. 3. A latch 1 is a first hold circuit for holding the input data D. An arithmetic and logical unit (ALU) 2 is capable of performing at least both subtraction and exclusive OR (XOR) operations. An operation control signal controls which operation is performed in the ALU 2. The system is also provided with a latch 3 as a second hold circuit and a data bus 4. The input data D is input in parallel to priority encoder 11 and the latch 1 via the data bus 4. 
     FIG. 2 shows respective steps from Step 1 through Step 6 of the operation of the system of FIG. 1. The operation will be described with reference to FIGS. 1 and 2. The input data D is applied to the data bus 4 in step 1. As the input data D proceeds from step 1 to step 6, the input data D is applied to the priority encoder 11. At this stage, the first bit position having a 1 as viewed from the MSB is detected and an encoded output A m  is obtained (step 5). 
     As the input data D proceeds from Step 1 to Step 2, since the input data D has also been input to the latch 1, the input data D is held in the latch 1 and, then, 1 is substracted from the input data D in the ALU 2. Let the subtraction result be E or E=D-1. The output destination of the subtraction result E is designated and this subtraction result E is held in the latch 3. 
     Then, the result F is applied to the priority encoder 11 after changing the destination by the arithmetic control signal. Once this is complete the bit position having a 1 is viewed from the MSB is encoded (Step 4), and the bit position is detected by the priority encoder 11 (Step 5). The new result is an encoded output A L  representing the 1st bit position having a 1 as viewed from the LSB. 
     A specific example will be described. Suppose that the input 8-bit data D is 01101000. This data has 1s at the 6th (D 6 ), 5th (D 5 ), and 3rd (D 3 ) bit positions. Thus, the first bit positions having a 1 as viewed from the MSB and the LSB are the 6th and 3rd bit positions, respectively. 
     To encode the first bit position having a 1 as viewed from the MSB, the value of the input data D may simply be applied to the priority encoder 11. In this example, the priority encoder 11 generates a binary number 110 encoding the 6th bit position. 
     In order to encode the first bit position having a 1 as viewed from the LSB, on the other hand, 1 is subtracted from the input data D in the ALU 2 as described above. The subtraction result E is given as follows: 
     
         E=D-1=01101000-1=01100111. 
    
     The input data D and the subtraction result E are then exclusively ored in the ALU 2. This XOR result F is given as follows: 
     
         F=D+E=01101000+01100111=00001111. 
    
     The first bit position having a 1 in the XOR result F as viewed from the MSB is then encoded in the priority encoder 11. The XOR result F has 1s at the 3rd (D 3 ), 2nd (D 2 ), 1st (D 1 ), and 0th (D 0 ) bit positions. Thus, the output of the priority encoder 11 is a binary number 011 encoding the 3rd bit position according to the truth table of FIG. 5(a). 
     As described above, according to the invention, where the first bit position having a 1 as viewed from the MSB of the input data is detected, the input data D may merely be applied to the priority encoder 11 while, where the first bit position having a 1 as viewed from the LSB is detected, the result F computed in the ALU 2 according to the predetermined procedure may be applied to the priority encoder 11. The width of the input data D in the above embodiment is 8 bits but may be greater than this value to provide similar results. 
     The ALU 2 for performing the above subtraction and XOR operations may be conventional. The priority encoder for encoding the first bit position having a 1 as viewed from the MSB in the input data is necessary for standardizing the results of floating point computations so that it is almost always incorporated in a system capable of performing floating point computations, thus making it possible to use the existing system as it is. 
     In the above embodiment, the first bit position having a 1 as viewed from the LSB of the input data is encoded by means of the priority encoder capable of encoding the first bit position having a 1 as viewed from the MSB of the input data, but the present invention may be applied to encode the first bit position having a 0 as viewed from the MSB or LSB of the input data. For example, where a priority encoder capable of encoding the first bit position D 6  as viewed from the MSB of the input data 10010111 is used, 1 is added to the input data 10010111 to provide an addition result 10011000. The respective bits of an XOR result 00001111 of the input data 10010111 and the addition result 10011000 are inverted to provide an inverted result 11110000, which is applied to the above priority encoder to encode the first bit position having a 0 as viewed from the LBS of the input data or D 3 . In this case, the operation of inverting the respective bits is required, but this operation is so basic that the existing system is used as it is in the same manner as in the above embodiment. 
     While a preferred embodiment of the invention has been described using specific terms, such description is given for illustrative purposes only, and it is to be understood that changes and variations may be made without departing the spirit and scope of the invention as recited in the appended claims.