JP2007087064A - Random number generation apparatus and random number generation method - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide a random number generator capable of generating a plurality of uniform random numbers without increasing the scale of hardware when generating normal random numbers using a central limit theorem.
A seed value held in a seed register 102 connected to a CPU (not shown) via a CPU 101 bus is set in a 28-bit long M-sequence cyclic code generator 103. The 28-bit length M-sequence cyclic code generator 103 generates a seed value for each of the 28-bit length M-sequence cyclic code generators 104 to 108 and performs a cyclic code generation operation. Each of the 28-bit length M-sequence cyclic code generators 104 to 108 performs a cyclic code generation operation on the basis of the seed value generated by the 28-bit length M-sequence cyclic code generator 103, and a 12-bit uniform random number u _{0. [11: 0] ~u 11 [} 11: 0] to output.
[Selection] Figure 1

Description

  The present invention relates to a random number generation device and a random number generation method for generating a noise signal having uniform distribution characteristics.

  In an image forming apparatus such as a color copying machine or a color printer, various processes are performed on an image signal input from an image reading apparatus such as a color image scanner or a computer. For example, after processing such as Log conversion, color space conversion to CMYK, and gamma conversion that matches the characteristics of the printer engine, pseudo halftone processing such as error diffusion processing is performed. Normally, in the pseudo halftone process, a random number addition process for intentionally adding a uniform random number value, a normal random number value, or the like as small noise to image data is performed in order to make moire due to quantization noise inconspicuous.

  In order to generate the normal random number value, a central limit theorem is generally used in which a normal random number is generated by adding a plurality of uniform random numbers. For example, when 12 12-bit uniform random numbers are used and the uniform random number is uk (k = 0 to 11), the normal random number x is calculated by the following equation (1).

  For the uniform random number used to generate the normal random number, an M-sequence cyclic code generator is usually used (see, for example, Patent Document 1).

  A random number generation apparatus capable of outputting 12 12-bit uniform random numbers will be described with reference to FIG. FIG. 7 is a block diagram showing the configuration of a conventional random number generator capable of outputting uniform random numbers.

  As shown in FIG. 7, the random number generation device capable of outputting twelve 12-bit uniform random numbers has a plurality of seed registers 702 to 707 connected to a CPU (not shown) via a CPU bus 701. . Each seed register 702 to 707 sets an initial value (hereinafter referred to as a seed value) in the corresponding 28-bit M-sequence cyclic code generator 708 to 713. Here, the seed registers 702 to 707 have 28 bits having a bit length equivalent to that of the 28-bit M-sequence cyclic code generators 708 to 713. The 28-bit length M-sequence cyclic code generators 708 to 713 generate 28-bit cyclic codes that are the basis of uniform random numbers. This cyclic code is represented by a primitive polynomial of the following equation (2).

x ²⁸ + x ³ +1 (2)
Here, the bit length of the 28-bit length M-sequence cyclic code generators 708 to 713 is determined to be a bit length that does not correlate normal random numbers within a desired number of pixels, that is, 28 bits. These 28 bits are necessary to generate a normal random number so that no correlation is generated when a random number is added at an interval of 1 pixel to an image having a resolution of 1200 pixels per inch for an A3 paper size. Bit length.

Each of the 28-bit length M-sequence cyclic code generators 708 to 713 outputs two uniform random numbers. The uniform random numbers u ₀ [11: 0] and u ₁ [11: 0] output from the 28-bit long M-sequence cyclic code generator 708 are 12-bit uniform random numbers, and the following equation (3) and It is represented by the formula (4).

u ₀ [11: 0]
= [22, 7, 11, 2, 18, 1, 3, 14, 23, 9, 21, 10] (3)
u ₁ [11: 0]
= [5, 20, 8, 16, 19, 0, 12, 17, 4, 6, 13, 15] (4)
Here, the number on the right side of the above equation (3) is the bit number of the 28-bit long M-sequence cyclic code generator 708, and uniform random numbers are generated by extracting desired bits. Further, extraction of bits is performed from discontinuous bit positions so as not to be continuous bit positions in order to improve characteristics as a random number. The same applies to u ₁ [11: 0] represented by the above formula (4). Here, u ₀ [11: 0] and u ₁ [11: 0] are set so that the bit positions extracted from the 28-bit length M-sequence cyclic code generator 708 do not overlap with each other in order to eliminate the correlation between them. Yes.

The 12-bit uniform random numbers u ₂ [11: 0] and u ₃ [11: 0] output from the 28-bit length M-sequence cyclic code generator 709 are expressed by the following equations (5) and (6). Is done.

u ₂ [11: 0]
= [7, 11, 2, 18, 1, 3, 14, 23, 9, 21, 10, 22] (5)
u ₃ [11: 0]
= [20, 8, 16, 19, 0, 12, 17, 4, 6, 13, 15, 5] (6)
Here, the notations of the above formulas (5) and (6) are the same as the above formula (3). However, regarding the bit position extracted by the 28-bit length M-sequence cyclic code generator 709, u ₂ [11: 0] is shifted by 1 bit to the MSB side with respect to u ₀ [11: 0], and u ₀ [11 : 0], the MSB bit number “22” is assigned to the LSB. _Similarly, u 3 [11: 0] _is, u 1 assigned: [0 11] the bit number "5" was MSB in the LSB [11 0] shifted one bit to the MSB side with respect _to, u 1 ing. Thus, by changing the extraction position from the M-sequence cyclic code generator between uniform random numbers, the correlation between uniform random numbers due to the dependency of the extraction position can be reduced.

The 12-bit uniform random numbers u ₄ [11: 0] and u ₅ [11: 0] output from the 28-bit length M-sequence cyclic code generator 710 are expressed by the following equations (7) and (8). The

u ₄ [11: 0]
= [11, 2, 18, 1, 3, 14, 23, 9, 21, 10, 22, 7] (7)
u ₅ [11: 0]
= [8, 16, 19, 0, 12, 17, 4, 6, 13, 15, 5, 20] (8)
Here, the notations of the above expressions (7) and (8) are the same as those of the above expression (3). However, regarding the bit position extracted by the 28-bit length M-sequence cyclic code generator 710, u ₄ [11: 0] is shifted by 1 bit to the MSB side with respect to u ₂ [11: 0], and u ₂ [11: 0], the MSB bit number “7” is assigned to the LSB. _Similarly, u 5 [11: 0] _is, u 3 [11: 0] by one bit shifted to the MSB side of _the, u 3 [11: 0] assigned bit number "20" to the LSB is MSB in It has been.

The 12-bit uniform random numbers u ₆ [11: 0] and u ₇ [11: 0] output from the 28-bit length M-sequence cyclic code generator 711 are expressed by the following equations (9) and (10). The

u ₆ [11: 0]
= [2, 18, 1, 3, 14, 23, 9, 21, 10, 22, 7, 11] (9)
u ₇ [11: 0]
= [16, 19, 0, 12, 17, 4, 6, 13, 15, 5, 20, 8] (10)
Here, the expressions (9) and (10) are the same as the expressions (3). However, regarding the bit position extracted by the 28-bit length M-sequence cyclic code generator 711, u ₆ [11: 0] is shifted by 1 bit to the MSB side with respect to u ₄ [11: 0], and u ₄ [11 : 0], the MSB bit number “11” is assigned to the LSB. _Similarly, u 7 [11: 0] _is, u 5 [11: 0] by one bit shifted to the MSB side with respect _to, u 5 [11: 0] assigned bit number "8" is the LSB is MSB in It has been.

The 12-bit uniform random numbers u ₈ [11: 0] and u ₉ [11: 0] output from the 28-bit length M-sequence cyclic code generator 712 are expressed by the following equations (11) and (12). The

u ₈ [11: 0]
= [18, 1, 3, 14, 23, 9, 21, 10, 22, 7, 11, 2] (11)
u ₉ [11: 0]
= [19, 0, 12, 17, 4, 6, 13, 15, 5, 20, 8, 16] ... (12)
Here, the notations of the above expressions (11) and (12) are the same as those of the above expression (3). However, regarding the bit position extracted by the 28-bit length M-sequence cyclic code generator 712, u ₈ [11: 0] is shifted by 1 bit to the MSB side with respect to u ₆ [11: 0], and u ₆ [11 : 0], the MSB bit number “2” is assigned to the LSB. _Similarly, u 9 [11: 0] _is, u 7 [11: 0] _by one bit shifted to the MSB side of the, u 7 [11: 0] assigned bit number "16" to the LSB is MSB in It has been.

The 12-bit uniform random numbers u ₁₀ [11: 0] and u ₁₁ [11: 0] output from the 28-bit length M-sequence cyclic code generator 713 are expressed by the following equations (13) and (14). The

u ₁₀ [11: 0]
= [1,3,14,23,9,21,10,22,7,11,2,18] ... (13)
u ₁₁ [11: 0]
= [0, 12, 17, 4, 6, 13, 15, 5, 20, 8, 16, 19] (14)
The expressions (13) and (14) are the same as the expressions (3). However, regarding the bit position extracted by the 28-bit length M-sequence cyclic code generator 713, u ₁₀ [11: 0] is shifted by 1 bit to the MSB side with respect to u ₈ [11: 0], and u ₈ [11: 0], the MSB bit number “18” is assigned to the LSB. _Similarly, u 11 [11: 0] _is, u 9 [11: 0] by one bit shifted to the MSB side of _the, u 9 [11: 0] assigned bit number "19" is the LSB is MSB in It has been.

Next, the processing procedure will be described. First, seed values are written to the seed registers 702 to 707 via the CPU bus 701. Different values are written in the seed registers 702 to 707 so that the 8-bit long M-sequence cyclic code generators 708 to 713 generate different cyclic codes. This eliminates the correlation between the uniform random numbers u ₀ [11: 0] to u ₁₁ [11: 0]. The 28-bit long M-sequence cyclic code generators 708 to 713 generate a cyclic code for each pixel based on the values of the seed registers 702 to 707, and a 12-bit uniform random number u ₀ from the generated cyclic code. _{[11: 0] ~u 11 [} 11: 0] extracting and outputting a.
JP 2000-196559 A

  However, in the conventional configuration, it is necessary to set different seed values from a CPU or the like for a plurality of M-sequence cyclic code generators. At the same time, it is necessary to provide a register having a bit length equivalent to the bit length of the cyclic code generator as a register for storing the set values. As a result, the scale of hardware increases. For example, in the case of the configuration shown in FIG. 7, a 28 × 6 = 168 bit length register is required, which increases the hardware scale.

  An object of the present invention is to provide a random number generation device and a random number generation method capable of generating a plurality of uniform random numbers without increasing the scale of hardware when generating normal random numbers using the central limit theorem. There is to do.

  In order to achieve the above object, the present invention is provided corresponding to each of a plurality of cyclic code generating means for generating a plurality of cyclic codes and the plurality of cyclic code generating means, and generated by the corresponding cyclic code generating means. A plurality of uniform random number generation means for generating a plurality of uniform random numbers from the plurality of cyclic codes, a single initial value storage means for storing an initial value, and an initial value stored in the initial value storage means And a random number generation device comprising: initialization means for initializing each of the plurality of cyclic code generation means.

  In order to achieve the above object, the present invention is provided corresponding to each of a plurality of cyclic code generating means for generating a plurality of cyclic codes and the plurality of cyclic code generating means, and generated by the corresponding cyclic code generating means. A random number generation method using a plurality of uniform random number generation means for generating a plurality of uniform random numbers from a plurality of cyclic codes, wherein the initial value storage step stores the initial value in a single initial value storage means; There is provided a random number generation method comprising an initialization step of initializing each of the plurality of cyclic code generation means using an initial value stored in the initial value storage means.

  According to the present invention, when generating a normal random number using the central limit theorem, a plurality of uniform random numbers can be generated without increasing the scale of hardware.

  Hereinafter, embodiments of the present invention will be described with reference to the drawings.

(First embodiment)
FIG. 1 is a block diagram showing the main configuration of a random number generation device according to the first embodiment of the present invention.

  As shown in FIG. 1, the random number generator includes a seed register 102 connected to a CPU (not shown) via a CPU 101 bus, a plurality of 28-bit length M-sequence cyclic code generators 103 to 108, and a 28-bit length. An OR gate circuit 112 provided in association with the M-sequence cyclic code generator 103 is provided.

  The seed register 102 is a register for setting a seed value for the 28-bit length M-sequence cyclic code generator 103. Here, the seed register 102 is a 28-bit register having a bit length equivalent to that of the 28-bit length M-sequence cyclic code generator 103.

  28-bit length M-sequence cyclic code generators 103 to 108 have the same configuration and function as the 28-bit length M-sequence cyclic code generator shown in FIG.

  The OR gate circuit 112 calculates the logical sum of the input seed generation period signal init and the cyclic code generation enable signal enable, and outputs the calculation result. The output of the OR gate circuit 112 is input to the 28-bit length M-sequence cyclic code generator 103. Here, when the seed generation period signal init is “0”, the seed value of the 28-bit length M-sequence cyclic code generators 104 to 108 is generated for the 28-bit length M-sequence cyclic code generator 103. It is a signal for instructing to do. The cyclic code generation enable signal enable is a signal for instructing the 28-bit long M-sequence cyclic code generators 103 to 108 to perform a cyclic code generation operation when the value thereof is “1”. Here, when the value of the seed generation period signal init or the cyclic code generation enable signal “enable” is “0”, the 28-bit length M-sequence cyclic code generator 103 is compared with the 28-bit length M-sequence cyclic code generator 103. An instruction is made to generate a seed value of 108. On the other hand, when the value of the seed generation period signal init or the cyclic code generation enable signal enable is “1”, the 28-bit length M-sequence cyclic code generator 103 is instructed to perform a cyclic code generation operation. Done.

  The load signal load 0 is input to the 28-bit length M-sequence cyclic code generator 103. The load signal load0 is a signal for loading a seed value into the 28-bit length M-sequence cyclic code generator 103. When the value is “1”, the load signal load0 is sent to the 28-bit length M-sequence cyclic code generator 103. The seed value is loaded. Further, as described above, the 28-bit length M-sequence cyclic code generator 103 generates the seed values of the 28-bit length M-sequence cyclic code generators 104 to 108 according to the output of the OR gate circuit 112, or cyclically. A code generation operation is performed.

  The load signal load1 for loading the seed value is input to the 28-bit length M-sequence cyclic code generator 104, and the 28-bit length M-sequence cyclic code generator 103 when the value of the load signal load1 is “1”. The seed value generated by is loaded. When the cyclic code generation enable signal “enable” of “1” is input to the 28-bit length M-sequence cyclic code generator 104, the 28-bit length M-sequence cyclic code generator 104 performs a cyclic code generation operation.

  Similarly, load signals load2 to load5 and cyclic code generation enable signal enable for loading seed values are input to 28-bit length M-sequence cyclic code generators 105 to 108, respectively. The 28-bit length M-sequence cyclic code generators 105 to 108 load the seed value generated by the 28-bit length M-sequence cyclic code generator 103 or perform a cyclic code generation operation according to the value of the input signal. Do.

The 28-bit length M-sequence cyclic code generators 103 to 108 output 12-bit uniform random numbers u ₀ “11: 0” to u ₁₁ “11: 0”, respectively. Since these outputs are equivalent to those described with reference to FIG. 7, description thereof is omitted here.

  Next, the operation of the random number generation device according to the present embodiment will be described with reference to FIG. FIG. 2 is a timing chart showing the operation timing of the random number generation device of FIG. Here, the operation timing of each block shown in FIG. 2 will be described as being synchronized with the rising edge of a system clock (not shown).

  If a seed value is set for the seed register 102 by time t0, this seed value is held in the sheet register 102 during the processing period. After setting the seed value, the value of the load signal load0 becomes “1” in the period from time t1 to time t2, and the seed value held in the sheet register 102 is set to the 28-bit length M-sequence cyclic code generator 103. Is set.

  Next, in the period from time t2 to t11, the value of the seed generation period signal init is set to “1”, and the 28-bit length M-sequence cyclic code generator 103 is 28-bit length M-sequence cyclic code generator 104-108. Generate a seed value for each of.

  Specifically, the seed value is generated for the 28-bit long M-sequence cyclic code generator 104 during the period from time t2 to time t3. Here, during the period from time t2 to time t3, more cyclic codes are generated than the number of bits of the M-sequence cyclic code generator so that the correlation with the seed value given to the seed register 102 becomes small. Done. In the present embodiment, for example, 30 cyclic codes are generated. Thereafter, during the period from time t3 to t4, the value of the load signal load1 becomes “1”, and the value held in the 28-bit length M-sequence cyclic code generator 103 is used as a seed value for the 28-bit length M-sequence cyclic code generator. 104 is loaded. The seed value loaded into the 28-bit length M-sequence cyclic code generator 104 is held until time t15 when the random number addition process is performed.

  Next, a seed value is generated for the 28-bit long M-sequence cyclic code generator 105 during the period from time t4 to time t5. Here, during the period from time t4 to t5, it is performed similarly to the generation of the seed value to be given to the 28-bit long M-sequence cyclic code generator 104 during the period from time t2 to t3. That is, more cyclic codes are generated than the number of bits of the M-sequence cyclic code generator so that the correlation with the seed value given to the 28-bit length M-sequence cyclic code generator 104 becomes small. Thereafter, during the period from time t5 to t6, the value of the load signal load2 becomes “1”, and the value held in the 28-bit length M-sequence cyclic code generator 103 is used as a seed value to generate a 28-bit length M-sequence cyclic code. Loaded into the instrument 105. The seed value loaded into the 28-bit length M-sequence cyclic code generator 105 is held until time t15 when the random number addition process is performed.

  Next, a seed value is generated for the 28-bit length M-sequence cyclic code generator 106 during the period of time t6 to t7, and this seed value is the seed value given to the 28-bit length M-sequence cyclic code generator 105. Is a small value. After that, during the period from time t7 to t8, the value of the load signal load3 becomes “1”, and the value held in the 28-bit length M-sequence cyclic code generator 103 is used as a seed value to generate a 28-bit length M-sequence cyclic code. Loaded into the device 106. The seed value loaded into the 28-bit length M-sequence cyclic code generator 106 is held until time t15 when the random number addition process is performed.

  Next, a seed value is generated for the 28-bit length M-sequence cyclic code generator 107 during the period of time t8 to t9, and this seed value is the seed value given to the 28-bit length M-sequence cyclic code generator 106. Is a small value. Thereafter, during the period from time t9 to t10, the value of the load signal load4 becomes “1”, and the value held in the 28-bit length M-sequence cyclic code generator 103 is used as a seed value to generate a 28-bit length M-sequence cyclic code. Loaded into the device 107. The seed value loaded into the 28-bit length M-sequence cyclic code generator 107 is held until time t15 when the random number addition process is performed.

  Next, a seed value is generated for the 28-bit length M-sequence cyclic code generator 108 during the period of time t10 to t11, and this seed value is the seed value given to the 28-bit length M-sequence cyclic code generator 107. Is a small value. Thereafter, during the period from time t11 to t12, the value of the load signal load5 becomes “1”, and the value held in the 28-bit length M-sequence cyclic code generator 103 is used as a seed value to generate a 28-bit length M-sequence cyclic code. Loaded into the instrument 108. The seed value loaded into the 28-bit length M-sequence cyclic code generator 108 is held until time t15 when the random number addition process is performed.

  In this manner, the 28-bit length M-sequence cyclic code generator 103 generates and sets seed values for each of the 28-bit length M-sequence cyclic code generators 104 to 108.

Next, the value of the load signal load0 becomes “1” during the period of time t13 to t14, and the seed value is reset for the 28-bit length M-sequence cyclic code generator 103. After time t15, the value of the cyclic code generation enable signal “enable” becomes “1”, and cyclic codes are generated from the 28-bit long M-sequence cyclic code generators 103 to 108, and the uniform random number u ₀ “11: 0”. ”To u ₁₁ “ 11: 0 ”are output.

  As described above, according to the present embodiment, the 28-bit length M-sequence cyclic code generator 103 generates seeds for the 28-bit length M-sequence cyclic code generators 104 to 108 based on the seed value set in the seed register 102. A value is generated. Thereby, when generating a normal random number using the central limit theorem, a plurality of uniform random numbers can be generated without increasing the scale of hardware.

(Second Embodiment)
Next, a second embodiment of the present invention will be described with reference to FIGS. FIG. 3 is a block diagram showing the configuration of the random number generation device according to the second embodiment of the present invention, and FIG. 4 is a timing chart showing the operation timing of the random number generation device of FIG.

  As shown in FIG. 3, the random number generator includes a seed register 302 connected to a CPU (not shown) via a CPU 301 bus, a plurality of 28-bit length M-sequence cyclic code generators 303 to 308, and a 28-bit length. OR gate circuits 315 to 319 provided in association with the M-sequence cyclic code generators 304 to 308, respectively.

  The seed register 302 is a register for setting a seed value for each 28-bit long M-sequence cyclic code generator 303 to 308. Here, the seed register 302 is a 28-bit register having a bit length equivalent to that of the 28-bit length M-sequence cyclic code generators 303 to 308.

  Each 28-bit length M-sequence cyclic code generator 303 to 308 receives a load signal load for loading a seed value. When the value of the load signal load is “1”, seed values are loaded into the 28-bit length M-sequence cyclic code generators 303 to 308. Further, cyclic code generation enable signal enable is input to 28-bit length M-sequence cyclic code generator 303. When the value of the cyclic code generation enable signal “enable” is “1”, the 28-bit long M-sequence cyclic code generator 303 performs a cyclic code generation operation.

  Each of the OR gate circuits 315 to 319 performs a logical operation on the input cyclic code generation enable signal enable and the seed generation period signals init0 to init4, and outputs the operation result. Here, the seed generation period signals init0 to init4 are signals that instruct the 28-bit length M-sequence cyclic code generators 304 to 308 to generate seed values when the value is “1”. It is.

The outputs of the OR gate circuits 315 to 319 are input to the corresponding 28-bit length M-sequence cyclic code generators 304 to 308, respectively. Here, when the values of the seed generation period signals init0 to init4 or the cyclic code generation enable signal enable are “0”, the 28-bit length M-sequence cyclic code generators 304 to 308 generate seed values. On the other hand, when the value of the seed generation period signals init0 to init4 or the cyclic code generation enable signal enable is “1”, each 28-bit long M-sequence cyclic code generators 304 to 308 perform a cyclic code generation operation. Each 28-bit length M-sequence cyclic code generator 304 to 308 outputs 12-bit uniform random numbers u ₀ [11: 0] to u ₁₁ [11: 0].

  Next, the operation of the random number generation device according to the present embodiment will be described with reference to FIG. Here, the operation timing of each block shown in FIG. 4 will be described as being synchronized with the rising edge of a system clock (not shown).

  A seed value is set for the seed register 302 by time t0, and this seed value is continuously held in the seed register 302 during the processing period. Thereafter, during the period from time t1 to time t2, the value of the load signal load becomes “1”, and a seed value is set for each of the 28-bit length M-sequence cyclic code generators 303 to 308. The 28-bit length M-sequence cyclic code generator 303 holds the seed value during the period from time t2 to time t8.

  Next, during the period of time t2 to t3, the value of the seed generation period signal init0 is “1”, and the 28-bit length M-sequence cyclic code generator 304 generates a seed value. Here, in the generation of the seed value, the number of cyclic codes larger than the number of bits of the M-sequence cyclic code generator is set so that the generated seed value has a small correlation with the value given to the seed register 302. Occurrence occurs. For example, 30 cyclic codes are generated. Thereafter, the 28-bit long M-sequence cyclic code generator 304 holds the seed value during the period from time t3 to t8.

  In addition, during the period from time t2 to t4, the value of the seed generation period signal init1 is “1”, and the 28-bit length M-sequence cyclic code generator 305 generates a seed value. Here, in the generation of the seed value, the correlation between the generated seed value and the seed value generated by the 28-bit long M-sequence cyclic code generator 304 during the period from time t2 to time t3 is made small. For this purpose, cyclic codes are generated in excess of the bit length of the M-sequence cyclic code generator from the period of time t2 to t3. Thereafter, the 28-bit length M-sequence cyclic code generator 305 holds the seed value during the period of time t4 to t8.

  Further, during the period from time t2 to time t5, the value of the seed generation period signal init2 becomes “1”, and the 28-bit length M-sequence cyclic code generator 306 generates a seed value. Here, the generation of the seed value is performed such that the correlation between the generated seed value and the seed value generated by the 28-bit long M-sequence cyclic code generator 305 during the period from time t2 to time t4 is reduced. For this reason, cyclic codes are generated in excess of the bit length of the M-sequence cyclic code generator from the period of time t2 to t4. Thereafter, the 28-bit length M-sequence cyclic code generator 306 holds the seed value during the period from time t5 to t8.

  Further, during the period from time t2 to t6, the value of the seed generation period signal init3 becomes “1”, and the 28-bit length M-sequence cyclic code generator 307 generates a seed value. Here, in the generation of the seed value, the correlation between the generated seed value and the seed value generated by the 28-bit length M-sequence cyclic code generator 306 during the period of time t2 to t5 is made small. For this reason, cyclic codes are generated in excess of the bit length of the M-sequence cyclic code generator from the period of time t2 to t5. Thereafter, the 28-bit long M-sequence cyclic code generator 307 holds the seed value during the period from time t6 to t8.

  Further, during the period from time t2 to time t7, the value of the seed generation period signal init4 becomes “1”, and the 28-bit length M-sequence cyclic code generator 308 generates a seed value. Here, in the generation of the seed value, the correlation between the generated seed value and the seed value generated by the 28-bit length M-sequence cyclic code generator 36 during the period from time t2 to time t6 is made small. Therefore, cyclic codes are generated in excess of the bit length of the M-sequence cyclic code generator from the period from time t2 to t6. Thereafter, the 28-bit long M-sequence cyclic code generator 307 holds the seed value during the period from time t7 to t8.

After time t8, the value of the cyclic code generation enable signal “enable” becomes “1”, and each 28-bit length M-sequence cyclic code generator 303 to 308 generates a cyclic code and generates a uniform random number u ₀ [11. : 0] to u ₁₁ [11: 0] are output.

(Third embodiment)
Next, a third embodiment of the present invention will be described with reference to FIGS. FIG. 5 is a block diagram showing the configuration of the random number generation device according to the third embodiment of the present invention, and FIG.

  As shown in FIG. 5, the random number generator includes a seed register 502 connected to a CPU (not shown) via a CPU 501 bus, and a plurality of 28-bit length M-sequence cyclic code generators 503 to 508.

  The seed register 502 is a register for setting a seed value for each 28-bit long M-sequence cyclic code generator 503 to 508. Here, the seed register 502 is a 28-bit register having a bit length equivalent to that of the 28-bit length M-sequence cyclic code generators 503 to 508.

Corresponding load signals load0 to load5 are input to the 28-bit length M-sequence cyclic code generators 503 to 508, respectively. load0 to load5 are signals for loading a seed value. When the value is “1”, the corresponding 28-bit length M-sequence cyclic code generators 503 to 508 are held in the register 502. The value is loaded as a seed value. Each 28-bit long M-sequence cyclic code generator 503 to 508 receives a cyclic code generation enable signal enable. When the value of this cyclic code generation enable signal “enable” is “1”, each 28-bit length M-sequence cyclic code generator 503 to 508 performs a cyclic code generation operation, and a 12-bit uniform random number u ₀ [ 11: 0] to u ₁₁ [11: 0] are output.

  Next, the operation of the random number generation device according to the present embodiment will be described with reference to FIG. Here, the operation timing of each block shown in FIG. 6 is described as being synchronized with the rising edge of a system clock (not shown).

  At time t0, the seed value of the 28-bit long M-sequence cyclic code generator 503 is set in the seed register 502. Thereafter, during the period from time t1 to time t2, the value of the load signal load0 becomes “1”, and the 28-bit length M-sequence cyclic code generator 503 is loaded with the seed value from the sheet register 502. This loaded seed value is held until time t18.

  At time t3, the seed value of the 28-bit length M-sequence cyclic code generator 504 is set in the seed register 502. Thereafter, during the period from time t4 to time t5, the value of the load signal load1 becomes “1”, and the 28-bit length M-sequence cyclic code generator 504 is loaded with the seed value from the register 502. The 28-bit long M-sequence cyclic code generator 504 holds the loaded seed value until time t18.

  At time t6, the seed value of the 28-bit long M-sequence cyclic code generator 505 is set in the seed register 502. Thereafter, during the period from time t7 to time t8, the value of the load signal load2 becomes “1”, and the 28-bit length M-sequence cyclic code generator 505 is loaded with the seed value set in the register 502. The 28-bit long M-sequence cyclic code generator 505 holds the loaded seed value until time t18.

  At time t9, the seed value of the 28-bit length M-sequence cyclic code generator 506 is set in the seed register 502. Thereafter, during the period from time t10 to time t11, the value of the load signal load3 becomes “1”, and the seed value set in the seed register 502 is loaded into the 28-bit length M-sequence cyclic code generator 506. The 28-bit long M-sequence cyclic code generator 506 holds the loaded seed value until time t18.

  At time t12, the seed value of the 28-bit length M-sequence cyclic code generator 507 is set in the seed register 502. Thereafter, during the period from time t13 to time t14, the value of the load signal load4 becomes “1”, and the 28-bit length M-sequence cyclic code generator 507 is loaded with the seed value set in the seed register 502. The 28-bit long M-sequence cyclic code generator 507 holds the loaded seed value until time t18.

  At time t15, the seed value of the 28-bit length M-sequence cyclic code generator 508 is set in the seed register 502. Thereafter, during the period from time t16 to t17, the value of the load signal load5 becomes “1”, and the seed value is loaded into the 28-bit length M-sequence cyclic code generator 508. The 28-bit long M-sequence cyclic code generator 508 holds the loaded seed value until time t18.

After time t18, the value of the cyclic code generation enable signal enable becomes “1”, and each 28-bit length M-sequence cyclic code generator 503 to 508 generates a cyclic code, and generates a uniform random number u _{0. [11: 0] ~u 11 [} 11: 0] to output.

  As described above, in the present embodiment, the seed value calculated for each of the 28-bit length M-sequence cyclic code generators 503 to 508 by the CPU or the like corresponds to the corresponding 28 bits via one seed register 502. The long M-sequence cyclic code generators 503 to 508 are configured to be loaded.

  According to each of the embodiments described above, the seed value can be set using only one seed register for the six M-sequence cyclic code generators. The register hardware scale can be reduced to 1/6.

  In this embodiment, the 28-bit length M-sequence cyclic code generator has been described. However, if a bit length is selected so that autocorrelation of random numbers in a desired image area does not become a problem, bits other than 28 bits are selected. The present invention can be applied to a long one.

It is a block diagram which shows the principal part structure of the random number generator which concerns on the 1st Embodiment of this invention. It is a timing chart which shows the operation timing of the random number generation device of FIG. It is a block diagram which shows the structure of the random number generator which concerns on the 2nd Embodiment of this invention. It is a timing chart which shows the operation timing of the random number generation device of FIG. It is a block diagram which shows the structure of the random number generator which concerns on the 3rd Embodiment of this invention. It is a timing chart which shows the operation timing of the random number generator of FIG. It is a block diagram which shows the structure of the random number generator which can output the conventional uniform random number.

Explanation of symbols

101, 301, 501 CPU bus 102, 302, 502 Seed register 103-108, 303-308, 503-508 28-bit length M-sequence cyclic code generator 112, 315-319 OR gate circuit

Claims (14)

A plurality of cyclic code generating means for generating a plurality of cyclic codes;
A plurality of uniform random number generating means provided to respectively correspond to the plurality of cyclic code generating means, and generating a plurality of uniform random numbers from a plurality of cyclic codes generated by the corresponding cyclic code generating means;
A single initial value storage means for storing initial values;
A random number generation device comprising: initialization means for initializing each of the plurality of cyclic code generation means using an initial value stored in the initial value storage means.   Each of the uniform random number generation means generates a plurality of uniform random numbers by extracting a predetermined number of bits from discontinuous bit positions of the plurality of cyclic codes generated by the corresponding cyclic code generation means. The random number generation device according to claim 1, wherein:   2. The random number generation according to claim 1, wherein each of the uniform random number generation means generates a plurality of uniform random numbers by extracting a predetermined number of bits from different bit positions of the plurality of cyclic codes. apparatus.   The initialization unit sets an initial value stored in the initial value storage unit for one specific cyclic code generation unit among the plurality of cyclic code generation units, and generates another cyclic code generation The means is characterized in that each of the plurality of cyclic code generation means is initialized by setting a cyclic code generated by the specific one cyclic code generation means as an initial value. The random number generator described.   The initialization unit sets an initial value stored in the initial value storage unit for one specific cyclic code generation unit among the plurality of cyclic code generation units, and generates another cyclic code generation Means for initializing the plurality of cyclic code generation means by setting initial values generated by the other cyclic code generation means using the initial values stored in the initial value storage means. The random number generation device according to claim 1, wherein:   The initialization means stores, in the initial value storage means, initial values respectively corresponding to the plurality of cyclic code generation means in time series, and sets corresponding initial values to the corresponding cyclic code generation means in time series, respectively. The random number generation device according to claim 1, wherein the plurality of cyclic code generation units are each initialized.   7. The random number generation device according to claim 1, wherein initial values for each of the cyclic code generation means are different from each other. A plurality of cyclic code generation means for generating a plurality of cyclic codes, and a plurality of uniform codes from the plurality of cyclic codes generated by the corresponding cyclic code generation means, provided corresponding to the plurality of cyclic code generation means, respectively. A random number generation method using a plurality of uniform random number generation means for generating random numbers,
An initial value storing step of storing the initial value in a single initial value storing means;
A random number generation method comprising: an initialization step of initializing each of the plurality of cyclic code generation means using an initial value stored in the initial value storage means.   Each of the uniform random number generation means generates a plurality of uniform random numbers by extracting a predetermined number of bits from discontinuous bit positions of the plurality of cyclic codes generated by the corresponding cyclic code generation means. The random number generation method according to claim 8, wherein:   9. The random number generator according to claim 8, wherein each of the uniform random number generation means generates a plurality of uniform random numbers by extracting a predetermined number of bits from different bit positions of the plurality of cyclic codes. Method.   In the initialization step, an initial value stored in the initial value storage unit is set for one specific cyclic code generation unit among the plurality of cyclic code generation units, and another cyclic code generation is performed. 9. The information processing apparatus according to claim 8, wherein each of the plurality of cyclic code generation means is initialized by setting, as an initial value, a cyclic code generated by the specific one cyclic code generation means. The random number generation method described.   In the initialization step, an initial value stored in the initial value storage unit is set for one specific cyclic code generation unit among the plurality of cyclic code generation units, and another cyclic code generation is performed. Means for initializing the plurality of cyclic code generation means by setting initial values generated by the other cyclic code generation means using the initial values stored in the initial value storage means. The random number generation method according to claim 8, wherein: In the initial value storing step, initial values corresponding to the plurality of cyclic code generating means are stored in time series in the initial value storing means,
In the initialization step, the initial values stored in time series in the initial value storage means are read in time series and set in the corresponding cyclic code generation means, respectively, thereby initializing the plurality of cyclic code generation means respectively. The random number generation method according to claim 8, wherein:   14. The random number generation method according to claim 8, wherein initial values for each of the cyclic code generation means are different from each other.

Images