Abstract:
A circuit outputs, upon receipt of data and a parity of the data, count information on the number of bits in the data represented as a base-n number (n: a natural number equal to or larger than 2) and the parity of the count information. The circuit includes a determining unit and an inverting unit. The determining unit determines that the number of bits in the data represented as a base-n number is a specific value. The inverting unit outputs, as the parity of the count information, any one of a value of the parity of the data and an inverted value of the parity depending on a result of determination by the determining unit.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates to a parity generation circuit, a counter circuit, and a counting method. 
         [0003]    2. Description of the Related Art 
         [0004]    A population count refers to counting the number of ‘1&#39;s in binary data, and some central processing units (CPUs) is configured to issue a population count (POPC) instruction to perform the counting. 
         [0005]    The POPC instruction, formerly implemented by software emulation and not as an instruction set because of its low frequency of use, has been frequently used in recent years to calculate a hamming distance (the number of bits that differ between two bit strings). To increase the instruction processing speed, the POPC instruction is increasingly implemented by hardware. For example, Japanese Patent Application Laid-open No. 2005-165793 discloses a conventional technology to realize a circuit that executes the POPC instruction. 
         [0006]    To improve reliability, a CPU is used that ensures the validity of data using a parity added to operation input/output data. When such CPU executes a POPC instruction by hardware, how to obtain the parity of the operation result of the POPC instruction becomes an issue. 
         [0007]    Assume, for example, that the population count is performed using the above conventional technology, and that the parity of the operation result is calculated later using another circuit. In this case, the instruction processing time is prolonged by the time taken to calculate the parity. This reduces the effect of implementing the POPC instruction by hardware to process the instruction at high speed. Therefore, to avoid affecting the cycle time required for the operation, the parity needs to be calculated in the cycle time equal to or less than that of the operation. To accomplish this, the parity of the result of the POPC instruction needs to be predicted from input data. 
         [0008]    To obtain the parity of the operation result without increasing the time taken to process the POPC instruction, the parity needs to be predicted by a separate circuit in parallel with the population count. This parity prediction is required to predict the parity of the operation result from the input data of the POPC instruction and its parity. 
       SUMMARY 
       [0009]    It is an object of the present invention to at least partially solve the problems in the conventional technology. 
         [0010]    According to an aspect of the present invention, there is provided a parity generation circuit that receives data and a parity of the data, and outputs a parity of count information on a specific item of the data represented as a base-n number (n: a natural number equal to or larger than 2), including a determining unit that determines that the number of specific items of the data represented as a base-n number is a specific value; and an inverting unit that outputs, as the parity of the count information, any one of a value of the parity of the data and an inverted value of the parity depending on a result of determination by the determining unit. 
         [0011]    According to another aspect of the present invention, there is provided a counter circuit that receives data and a parity of the data, and outputs count information on a specific item of the data represented as a base-n number (n: a natural number equal to or larger than 2), and a parity of the count information, including a determining unit that determines that the number of specific items of the data represented as a base-n number is a specific value; and an inverting unit that outputs, as the parity of the count information, any one of a value of the parity of the data and an inverted value of the parity depending on a result of determination by the determining unit. 
         [0012]    According to still another aspect of the present invention, there is provided a counting method for counting, upon receipt of data and a parity of the data, specific items of the data represented as a base-n number (n: a natural number equal to or larger than 2) to output count information and a parity of the count information, including determining that the number of specific items of the data represented as a base-n number is a specific value; and outputting, as the parity of the count information, any one of a value of the parity of the data and an inverted value of the parity depending on a determination result obtained at the determining. 
         [0013]    According to still another aspect of the present invention, there is provided a counting method for counting, upon receipt of N-bit data (N: a natural number equal to or larger than 2) and a parity of the data, specific items of the data represented as a base-n number (n: a natural number equal to or larger than 2) to output count information and a parity of the count information, including dividing the N-bit data into n-bit portions (n: a natural number that satisfies N&gt;n≧1); determining that the number of specific items of each of the n-bit portions represented as a base-n number is a specific value; outputting, as the parity of the count information, any one of a value of a parity of each of the n-bit portions and an inverted value of the parity of each of the n-bit portions depending on a determination result obtained at the determining; summing the count information of the n-bit portions; and summing parities of the count information of the n-bit portions. 
         [0014]    The above and other objects, features, advantages and technical and industrial significance of this invention will be better understood by reading the following detailed description of presently preferred embodiments of the invention, when considered in connection with the accompanying drawings. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0015]      FIGS. 1A to 1C  are tables showing correspondence between eight-bit input data and POP; 
           [0016]      FIG. 2  is a table in which the parity of input data matches the parity of the POP; 
           [0017]      FIG. 3A  is a table showing combinations of POP in upper four bits and POP in lower four bits of eight-bit input data with POP of any one of “0”, “1”, “6”, and “7”; 
           [0018]      FIG. 3B  is a table showing combinations of POP in upper four bits and POP in lower four bits of eight-bit input data with POP of any one of “2”, “3”, “4”, “5”, and “8”; 
           [0019]      FIG. 4  is a block diagram of a population counter circuit corresponding to eight-bit input data according to an embodiment of the present invention; 
           [0020]      FIGS. 5A to 5C  are block diagrams of a parity predicting unit shown in  FIG. 4 ; 
           [0021]      FIG. 6  is a block diagram of a population counter circuit corresponding to 64-bit input data; and 
           [0022]      FIG. 7  is a block diagram of a population counter circuit corresponding to N-bit input data. 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0023]    Exemplary embodiments of the present invention are explained in detail below with reference to the accompanying drawings. 
         [0024]    First described is a principle of a parity predicting system according to an embodiment of the present invention.  FIGS. 1A to 1C  are tables showing correspondence between eight-bit input data and the number of ‘1’s (hereinafter, “POP”) in the data represented as a binary number. 
         [0025]      FIGS. 1A to 1C  depict eight-bit data (X&lt;7:0&gt;) having 256 possible values, from “00000000” to “11111111”, values of parity (X&lt;P&gt;) of the input data, POP (Z&lt;3:0&gt;), and parity (Z&lt;P&gt;) of the POP. 
         [0026]    Because the input data is made up of eight bits, the POP can take values from “0000 (0 in the decimal notation)” to “1000 (8 in the decimal notation)”. In  FIGS. 1A to 1C , an odd parity is employed, and “1” is set as the parity of the eight-bit input data “00000000”. To the POP “0000” of this input data, “1” is set as a parity. 
         [0027]      FIG. 2  depicts data extracted from the data shown in  FIGS. 1A to 1C  (data marked with “*”) in which the parity of the input data matches the parity of the POP. As can be seen from  FIG. 2 , when the parity of the input data matches the parity of the POP, the POP takes any one of “0000” (0 in the decimal notation), “0001” (1 in the decimal notation), “0110” (6 in the decimal notation), and “0111” (7 in the decimal notation). 
         [0028]    On the other hand, in the case of data among the data shown in  FIGS. 1A to 1C , in which the parity of the input data does not match the parity of the POP (data not marked with “*”), the POP takes any one of “0010” (2 in the decimal notation), “0011” (3 in the decimal notation), “0100 (4 in the decimal notation)”, “0101” (5 in the decimal notation), and “1000” (8 in the decimal notation). 
         [0029]    Based on this rule, the parity of POP can be predicted in the following manner. That is, in obtaining the POP of eight-bit input data, when the POP is any one of “0”, “1”, “6”, and “7”, it is expected that the parity of the POP is the same as the parity of the input data. When the POP has other values, it is expected that the parity of the POP is an inverted value of the parity of the input data. 
         [0030]    In obtaining the POP of input data having a width of eight bits or more, the parity can be predicted by dividing the input data into eight-bit portions. Specifically, the parity of the POP of each eight-bit portion is predicted according to the above rule, and the parity of the POP of the input data can be predicted by summing the prediction results. 
         [0031]    As described above, according to the embodiment, prediction is performed according to a POPC instruction from the CPU in parallel with the population count operation not to increase the execution time of the POPC instruction. Therefore, the cycle time of the parity predicting process is equal to or shorter than the cycle time of the population count operation. When the cycle time of the parity predicting process is equal to or shorter than that of the population count operation, the parity predicting process is masked by the population count operation, and does not affect the execution time of the POP instruction. 
         [0032]    Although the POP of input data needs to be determined, it is sufficient if it can be determined whether the POP is any one of “0”, “1”, “6”, and “7” in the decimal notation or any one of “2”, “3”, “4”, “5”, and “8” in the decimal notation. Therefore, the POP does not need to be calculated using the combination of adders as disclosed in Patent Document 1, and the execution speed can be increased by realizing a determining circuit using a decoder. 
         [0033]    However, when the determination of the POP of the input data having an eight-bit width is implemented by the decoder, the circuit size increases. Consequently, the processing is performed by dividing the eight-bit input data into the upper four-bit data and the lower four-bit data. 
         [0034]      FIG. 3A  depicts all combinations of the POP of the upper four bits (&lt;7:4&gt;) and the POP of the lower four bits (&lt;3:0&gt;) when the POP of the eight-bit input data takes any one of “0”, “1”, “6”, and “7” in the decimal notation. As shown in  FIG. 3A , there are eight combinations in this case. 
         [0035]      FIG. 3B  depicts all combinations of the POP of the upper four bits and the POP of the lower four bits when the POP of the eight-bit input data takes any one of “2”, “3”, “4”, “5”, and “8” in the decimal notation. As shown in  FIG. 3B , there are 15 combinations in this case. 
         [0036]    Thus, it can be understood that, when the process is performed by dividing eight-bit input data into an upper-bit portion and a lower-bit portion, the circuit size for achieving the parity prediction can be reduced by determining whether the POP of the eight-bit input data is any one of “0”, “1”, “6”, and “7” in the decimal notation consisting of eight combinations as compared to by determining whether the POP of the data is any one of “2”, “3”, “4”, “5”, and “8” in the decimal notation consisting of 15 combinations. 
         [0037]    The following example describes determination as to whether the POP of eight-bit input data is any one of “0”, “1”, “6”, and “7” in the decimal notation is made by dividing the input data into an upper-bit portion and a lower-bit portion. When the circuit size does not present a problem, whether the POP of eight-bit input data is any one of “2”, “3”, “4”, “5”, and “8” in the decimal notation can be determined by dividing the input data into an upper-bit portion and a lower-bit portion. Alternatively, the determination can be performed without dividing the eight-bit input data into upper four-bit data and lower four-bit data. 
         [0038]    Explained below is a population counter circuit according to the present embodiment.  FIG. 4  is a block diagram of a population counter circuit  100  corresponding to eight-bit input data. The population counter circuit  100  receives eight-bit input data (X&lt;7:0&gt;) and its parity (X&lt;P&gt;), and outputs a operation result (Z&lt;3:0&gt;) of the population count and its parity (Z&lt;P&gt;). 
         [0039]    The population counter circuit  100  includes a population counting unit  1000 , a parity predicting unit  2000 , and a parity inverting circuit  3000 . 
         [0040]    The population counting unit  1000  receives the eight-bit input data (X&lt;7:0&gt;), counts POP of this data, and outputs the operation result (Z&lt;3:0&gt;). The population counting unit  1000  includes a combination of a CAS (Carry Save Adder), and a HA (Half Adder). The configuration of the population counting unit  1000  need not necessarily be as illustrated in  FIG. 4 , and can be, for example, as disclosed in Patent Document 1. 
         [0041]    The parity predicting unit  2000  and the parity inverting circuit  3000  predict the parity of the operation result using the parity predicting system of the present embodiment. The parity predicting unit  2000  receives and decodes the eight-bit input data (X&lt;7:0&gt;). The parity predicting unit  2000  outputs 0 as an INV_P signal when the POP of the data is any one of “0”, “1”, “6”, and “7” in the decimal notation, and otherwise outputs 1. 
         [0042]    When the INV_P signal is 0, the parity inverting unit  3000  directly outputs the parity (X&lt;P&gt;) of the input data as the parity (Z&lt;P&gt;) of the operation result. When the INV_P signal is 1, the parity inverting unit  3000  outputs an inversion of the parity (X&lt;P&gt;) of the input data as the parity (Z&lt;P&gt;) of the operation result. 
         [0043]      FIGS. 5A to 5C  are block diagrams of a configuration of the parity predicting unit  2000 .  FIG. 5A  depicts a circuit configuration for determination by decoding the POP of the upper four bits (X&lt;7:4&gt;) of the input data. 
         [0044]    NOT circuits  2111  to  2114  invert the input bits X&lt;7&gt; to X&lt;4&gt;, respectively. 
         [0045]    AND circuits  2121 ,  2131  to  2134 ,  2141  to  2146 ,  2151  to  2154 , and  2161  are configured as decoding circuits that decode inputs of signals obtained by inverting a part or all of the input bits X&lt;7&gt; to X&lt;4&gt;, using the NOT circuits  2111  to  2114 , so that only one circuit outputs 1 corresponding to a bit pattern of the input bits X&lt;7&gt; to X&lt;4&gt;, and other circuits output 0. 
         [0046]    When the POP of the upper four bits is 0, i.e., when all bits are 0, the AND circuit  2121  outputs 1. This output is a POPC — 74 — 0 signal. 
         [0047]    When the POP of the upper four bits is 1, i.e., when one bit has 1, any one of the AND circuits  2131  to  2134  outputs 1. An OR circuit  2135  calculates a logical sum of these outputs, and outputs a POPC — 74 — 1 signal. 
         [0048]    When the POP of the upper four bits is 2, i.e., when two bits have 1, any one of the AND circuits  2141  to  2146  outputs 1. An OR circuit  2147  calculates a logical sum of these outputs, and outputs a POPC — 74 — 2 signal. 
         [0049]    When the POP of the upper four bits is 3, i.e., when three bits have 1, any one of the AND circuits  2151  to  2154  outputs 1. An OR circuit  2155  calculates a logical sum of these outputs, and outputs a POPC — 74 — 3 signal. 
         [0050]    When the POP of the upper four bits is 4, i.e., when all bits are 1, the AND circuit  2161  outputs 1. This output is a POPC — 74 — 4 signal. 
         [0051]      FIG. 5B  depicts a circuit configuration for determining the POP of the lower four bits (X&lt;3:0&gt;) of the input data. The configuration of the circuit is similar to that shown in  FIG. 5A , and therefore only signals to be output are explained. 
         [0052]    A POPC — 30 — 0 signal is 1 when the POP of the lower four bits is 0. A POPC — 30 — 1 signal is 1 when the POP of the lower four bits is 1. A POPC — 30 — 2 signal is 1 when the POP of the lower four bits is 2, and a POPC — 30 — 3 signal is 1 when the POP of the lower four bits is 3. A POPC — 30 — 4 signal is 1 when the POP of the lower four bits is “4” in the decimal notation. 
         [0053]      FIG. 5C  depicts a circuit configuration for determining whether the POP of the eight-bit input data (X&lt;7:0&gt;) is any one of “0”, “1”, “6”, and “7” in the decimal notation. 
         [0054]    AND circuits  2311 ,  2321  to  2322 ,  2331  to  2333 , and  2341  to  2342  determine a value of the POP of the eight-bit input data (X&lt;7:0&gt;) based on combinations of determination results of the POP of the upper four bits (X&lt;7:4&gt;) and the POP of the lower four bits (X&lt;3:0&gt;). 
         [0055]    The AND circuit  2311  outputs 1 when the POP of the upper four bits is 0 and when the POP of the lower four bits is 0, i.e., when the POPC — 74 — 0 signal is 1 and when the POPC — 30 — 0 signal is 1. This output is a POPC — 70 — 0 signal. 
         [0056]    The AND circuit  2321  outputs 1 when the POP of the upper four bits is 0 and when the POP of the lower four bits is “1” in the decimal notation, i.e., when the POPC — 74 — 0 signal is 1 and when the POPC — 30 — 1 signal is 1. 
         [0057]    The AND circuit  2322  outputs 1 when the POP of the upper four bits is 1 and when the POP of the lower four bits is “0” in the decimal notation, i.e., when the POPC — 74 — 1 signal is 1 and when the POPC — 30 — 0 signal is 1. An OR circuit  2323  calculates a logical sum of the outputs of the AND circuit  2321  and the AND circuit  2322 , and outputs a POPC — 70 — 1 signal. 
         [0058]    The AND circuit  2331  outputs 1 when the POP of the upper four bits is 4 and when the POP of the lower four bits is “2” in the decimal notation, i.e., when the POPC — 74 — 4 signal is 1 and when the POPC — 30 — 2 signal is 1. 
         [0059]    The AND circuit  2332  outputs 1 when the POP of the upper four bits is 3 and when the POP of the lower four bits is “3” in the decimal notation, i.e., when the POPC — 74 — 3 signal is 1 and when the POPC — 30 — 3 signal is 1. 
         [0060]    The AND circuit  2333  outputs 1 when the POP of the upper four bits is 2 and when the POP of the lower four bits is “4” in the decimal notation, i.e., when the POPC — 74 — 2 signal is 1 and when the POPC — 30 — 4 signal is 1. An OR circuit  2334  calculates a logical sum of the outputs of the AND circuit  2331 , the AND circuit  2332 , and the AND circuit  2333 , and outputs a POPC — 70 — 6 signal. 
         [0061]    The AND circuit  2341  outputs 1 when the POP of the upper four bits is “4” in the decimal notation and when the POP of the lower four bits is “3” in the decimal notation, i.e., when the POPC — 74 — 4 signal is 1 and when the POPC — 30 — 3 signal is 1. 
         [0062]    The AND circuit  2342  outputs 1 when the POP of the upper four bits is “3” in the decimal notation and when the POP of the lower four bits is “4” in the decimal notation, i.e., when the POPC — 74 — 3 signal is 1 and when the POPC — 30 — 4 signal is 1. An OR circuit  2343  calculates a logical sum of the outputs of the AND circuit  2341  and the AND circuit  2342 , and outputs a POPC — 70 — 7 signal. 
         [0063]    An NOR circuit  2351  calculates a logical sum of the POPC — 70 — 0 signal, the POPC — 70 — 1 signal, the POPC — 70 — 6 signal, and the POPC — 70 — 7 signal, and outputs an inversion of the operation result as an INV_P signal. 
         [0064]    With the configuration shown in  FIGS. 5A to 5C , the INV_P signal as an output of the parity predicting unit  2000  is 0 when the POP of the eight-bit input data (X&lt;7:0&gt;) is any one of “0”, “1”, “6”, and “7” in the decimal notation, and is 1 when the POP is other value. 
         [0065]    Explained below is an application of the parity predicting system of the present embodiment to a population counter circuit corresponding to 64-bit input data.  FIG. 6  is a block diagram of a population counter circuit  10  corresponding to 64-bit input data. The population counter circuit  10  receives 64-bit input data (X&lt;63:00&gt;) and its parities (X&lt;7:P0&gt;) each corresponding to eight bits, and outputs a operation result (Z&lt;6:0&gt;) of the population count and its parity (Z&lt;P&gt;). 
         [0066]    The population counter circuit  10  includes population counter circuits  101   a  to  101   h , and adder circuits  201   a  to  201   g.    
         [0067]    The population counter circuits  101   a  to  101   h  are similar to the population counter circuit  100 , and each receive eight-bit input data and its parity and output a POP and its parity. 
         [0068]    The population counter circuit  101   a  receives lowest eight bits (X&lt;07:00&gt;) of the input data and their parity (X&lt;P 0 &gt;). The population counter circuit  101   b  receives upper eight bits (X&lt;15:08&gt;) and their parity (X&lt;P 1 &gt;). The population counter circuit  101   c  receives upper eight bits (X&lt;23:16&gt;) and their parity (X&lt;P 2 &gt;). The population counter circuit  101   d  receives upper eight bits (X&lt;31:24&gt;) and their parity (X&lt;P 3 &gt;). 
         [0069]    The population counter circuit  101   e  receives upper eight bits (X&lt;39:32&gt;) and their parity (X&lt;P 4 &gt;). The population counter circuit  101   f  receives upper eight bits (X&lt;47:40&gt;) and their parity (X&lt;P 5 &gt;). The population counter circuit  101   g  receives upper eight bits (X&lt;55:48&gt;) and their parity (X&lt;P 6 &gt;). The population counter circuit  101   h  receives upper eight bits (X&lt;63:56&gt;) of the input data and their parity (X&lt;P 7 &gt;). 
         [0070]    The adder circuits  201   a  to  201   g  add POPs and parities, and output an addition result of the POPs and an addition result of the parities. 
         [0071]    The adder circuit  201   a  adds together the addition result and the parity result from the population counter circuit  101   a , and the addition result and the parity result from the population counter circuit  101   b , respectively. The adder circuit  201   b  adds together the addition result and the parity result from the population counter circuit  101   c , and the addition result and the parity result from the population counter circuit  101   d , respectively. The adder circuit  201   c  adds together the addition result and the parity result from the population counter circuit  101   e , and the addition result and the parity result from the population counter circuit  101   f , respectively. The adder circuit  201   d  adds together the addition result and the parity result from the population counter circuit  101   g , and the addition result and the parity result from the population counter circuit  101   h , respectively. 
         [0072]    The adder circuit  201   e  adds together the addition result and the parity result from the adder circuit  201   a , and the addition result and the parity result from the adder circuit  201   b , respectively. The adder circuit  201   f  adds together the addition result and the parity result from the adder circuit  201   c , and the addition result and the parity result from the adder circuit  201   d , respectively. The adder circuit  201   g  adds together the addition result and the parity result from the adder circuit  201   e , and the addition result and the parity result from the adder circuit  201   f , respectively. A result of the addition by the adder circuit  201   g  is output as the result of the population count (Z&lt;6:0&gt;) and the parity (Z&lt;P&gt;). 
         [0073]    As described above, even when input data has a bit width larger than eight bits, the POP can be counted and the parity can be predicted with population counter circuits corresponding to eight-bit input data arranged in parallel and adder circuits that add the output results. Thus, a population counter circuit corresponding to a bit width larger than 64 bits can also be realized as shown in  FIG. 7 . 
         [0074]    As set forth hereinabove, according to an embodiment of the present invention, the parity of a result of population count can be predicted at high speed without affecting population count operation. 
         [0075]    Moreover, since input data is divided to determine the bit pattern, the circuit size can be reduced as compared to the case of determining the bit pattern based on all bits without dividing the input data. 
         [0076]    Furthermore, a population counter circuit corresponding to data of any bit width can be realized. 
         [0077]    Although the invention has been described with respect to a specific embodiment for a complete and clear disclosure, the appended claims are not to be thus limited but are to be construed as embodying all modifications and alternative constructions that may occur to one skilled in the art that fairly fall within the basic teaching herein set forth.