Abstract:
A random number circuit includes an oscillator capable of generating a clock signal including a sequence of clocks at a center frequency, the clock signal having a frequency offset from the center frequency, a reset circuitry capable of generating a reset signal indicating a transition from a first state to a second state, an initial value generator capable of generating an initial value, and a counter coupled to at least one of the oscillator, the reset circuitry, and the initial value generator and capable of receiving at least one of the clock signal, the reset signal, and the initial value, the counter capable of generating a random number, the random number being dependent on at least one of the frequency offset, a timing of the transition, and the initial value.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     The present invention relates generally to a random number generating circuit, and more particularly, to a circuit for generating a seed number and a method for generating the seed number.  
         [0002]     A random number generator refers to a computational or physical device for generating a sequence of numbers in a pattern that is not easily discernable, so that the sequence can be treated as being random. Random number generators may generally be divided into pseudo-random number generators and hardware random number generators. A pseudo-random number generator often includes software routines implementing algorithms instead of hardware devices for producing random numbers, which are not truly random outputs. Given the original state (seed state) of a pseudo-random number generator, and the implementation of the algorithm employed by the generator, the randum outputs produced by the pseudo-random number generator are predictable, i.e. not random. In other words, if two random number generators operating under the same algorithm are seeded with the same seed value, both generators will produce the same sequence of numbers. On the other hand, a hardware random number generator includes an apparatus or device for generating random numbers from a physical process that, in theory, is unpredictable. In the hardware random number generator, the seed value, which determines a sequence of numbers to be produced, is generally random.  
       BRIEF SUMMARY OF THE INVENTION  
       [0003]     Examples of the invention may provide a circuit and a method for generating a random seed value, which in turn may be used as a base for generating a sequence of random numbers.  
         [0004]     Examples of the invention may provide a random number circuit that comprises an oscillator capable of generating a clock signal including a sequence of clocking pulses at a center frequency, the clock signal having a frequency offset from the center frequency, a reset circuitry capable of generating a reset signal indicating a transition from a first state to a second state, an initial value generator capable of generating an initial value, and a counter coupled to at least one of the oscillator, the reset circuitry, and the initial value generator and capable of receiving at least one of the clock signal, the reset signal, and the initial value, the counter capable of generating a random number, the random number being dependent on at least one of the frequency offset, a timing of the transition, and the initial value.  
         [0005]     Examples of the invention may also provide a random number circuit that comprises a device capable of providing a first voltage, an oscillator capable of generating a clock signal including a sequence of clocking pulses at a center frequency, the clock signal having a frequency offset from the center frequency, a charge pump capable of generating a second voltage being an integer multiple of the first voltage, a reset circuitry capable of generating a reset signal, the reset signal transitioning from a first state to a second state once the second voltage reaches a predetermined voltage level, an initial value generator capable of generating an initial value, and a counter capable of counting the number of clocking pulses starting from the initial value in response to the clock signal, and generating a random number in response to the transitioning of the reset signal.  
         [0006]     Some examples of the invention may also provide a random number circuit that comprises a first random number generator capable of generating a first random number comprising an oscillator capable of generating a clock signal including a sequence of clocking pulses, a reset circuitry capable of generating a reset signal indicating a transition from a first state to a second state, an initial value generator capable of generating an initial value, and a counter capable of generating the first random number in response to the clock signal, the reset signal and the initial value, and a second random number generator receiving the first random number capable of generating a second random number.  
         [0007]     Examples of the invention may also provide a method for generating a random number that comprises providing a first voltage, generating a clock signal including a sequence of clocking pulses, generating a second voltage being an integer multiple of the first voltage, generating a reset signal including a first state and a second state, transitioning the reset signal from one of the first and second states to the other of the first and second states once the second voltage reaches a predetermined voltage level, generating an initial value, and counting the number of clocking pulses starting from the initial value in response to the clock signal, and generating the random number in response to the transitioning of the reset signal.  
         [0008]     Examples of the invention may also provide a method for generating a random number that comprises generating a clock signal including a sequence of clocking pulses, generating a reset signal indicating a transition from a first state to a second state, generating an initial value, generating a first random number in response to the clock signal, the reset signal and the initial value, and generating a second random number using the first random number as a seed number.  
         [0009]     It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed. 
     
    
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS  
       [0010]     The foregoing summary, as well as the following detailed description of the invention, will be better understood when read in conjunction with the appended drawings. For the purpose of illustrating the invention, there are shown in the drawings examples consistent with the invention. It should be understood, however, that the invention is not limited to the precise arrangements and instrumentalities shown.  
         [0011]     In the drawings:  
         [0012]      FIG. 1A  is a block diagram of a random number generator consistent with an example of the invention;  
         [0013]      FIG. 1B  is a circuit diagram of a unit of an initial value generator illustrated in  FIG. 1A  for producing a random bit value;  
         [0014]      FIG. 1C  is a schematic timing diagram for the random number generator illustrated in  FIG. 1A ;  
         [0015]      FIG. 2  is a flow diagram of a method for generating a random number consistent with an example of the invention;  
         [0016]      FIG. 3A  is a schematic block diagram of a radio frequency identification (“RFID”) device consistent with an example of the invention; and  
         [0017]      FIG. 3B  is a block diagram of a seed number generator of the RFID device illustrated in  FIG. 3A .  
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0018]     Reference will now be made in detail to the present embodiments of the invention, examples of which are illustrated in the accompanying drawings. Wherever possible, the same reference numbers will be used throughout the drawings to refer to the same or like portions.  
         [0019]      FIG. 1A  is a block diagram of a random number generator  10  in accordance with one embodiment of the present invention. Referring to  FIG. 1A , the random number generator  10  includes a power supply  11 , an oscillator  12 , a charge pump  13 , a regulator  14 , a reset circuit  15 , an initial value generator  16  and a counter  17 . The power supply  11  such as a battery provides a supply voltage sufficient to cause oscillation of the oscillator  12 . Once oscillates, the oscillator  12  generates a clock signal to the charge pump  13  and the counter  17 . In one example, the oscillator  12  includes a ring oscillator, which generates a clock signal at a center frequency of approximately 10 megahertz (MHz). As compared to other oscillators, the ring oscillator is less precise and may have a relatively high tolerance up to approximately 10% in the clock frequency, resulting in a frequency offset of 0.1 MHz from the center frequency. Such a high tolerance, however, helps increase the randomness of the random numbers generated.  
         [0020]     The charge pump  13  includes but is not limited to a conventional switched capacitor multi-stage structure comprising a plurality of capacitors (not shown) and switches controlled under clocks of inverted phases. Specifically, the charge pump  13  adds voltages on capacitors charged by the supply voltage from the power supply  11  in response to the clock signal from the oscillator  12 . The charge pump  13  provides an output voltage which is an integer multiple of the supply voltage. The regulator  14  regulates the output voltage from the charge pump with respect to a predetermined voltage level. In one example, a regulated charge pump is used to replace the charge pump  13  and the regulator  14 . The regulated charge pump includes, for example, a voltage multiplier module to pull up the supply voltage provided from the power supply  11 , and a regulator module to then maintain the output voltage sent from the voltage multiplier module with respect to the predetermined voltage level.  
         [0021]     The reset circuit  15  provides a reset signal to the counter  17 . In one example, the reset signal is kept at a logic low state if the regulated voltage from the regulator  14  does not reach the predetermined voltage level, and is transitioned to a logic high state once the regulated voltage reaches the predetermined voltage level. The transition of the reset signal “latches” the counter  17 . That is, in response to a transition of the reset signal from logic low to logic high, the counter  17  provides a count having been counted since the clock signal is provided to the counter  17 . In some examples, the counter  17  does not need to provide a count until the reset signal is transitioned from a logic high state to a logic low state. Since the time the regulated voltage reaches the predetermined voltage level is not certain, the time the counter  17  is latched and hence the count provided is not certain, either. The count serves as a random number (RN) of the random number generator  10 , which may be used as an initial value, i.e., a seed number, for a pseudo random number generator. In one example, the random number RN has a 16-bit bandwidth, resulting in a 16-bit random number generator  10 .  
         [0022]     The initial value generator  16  provides an initial value to the counter  17 , from which the random number RN is counted. The initial value is provided at substantially the time as the clock signal is provided to the counter  17 . In one example, the initial value has a  16 -bit bandwidth, resulting in a 16-bit random number generator  10 . As a result, the count or the random number RN provided by the counter  17  is dependent on at least one of the frequency offset (F OFFSET ) due to the oscillator  12 , the transition time (T RESET ) of the reset circuit  15 , and the initial value (INIV) of the initial value generator  16 , as may be derived from the mathematical function below. 
 
 RN=f ( F   OFFSET   , T   RESET   , INIV ) 
 
         [0023]     Furthermore, the random number RN is indirectly dependent on the charging efficiency of the charge pump  13 , the predetermined voltage level selected, and the process parameters or conditions regarding the manufacturing of the initial value generator  16 . Therefore, the random number RN is not predictable.  
         [0024]      FIG. 1B  is a circuit diagram of a unit  16 - 1  of the initial value generator  16  illustrated in  FIG. 1A  for producing a random bit value. Referring to  FIG. 1B , the unit  16 - 1  includes a capacitor labeled C, a p-type metal-oxide-semiconductor (“PMOS) transistor labeled P and an n-type metal-oxide-semiconductor (“NMOS”) transistor labeled N. The capacitor C includes one end (not numbered) connected to a voltage reference and the other end (not numbered) connected to the gates of the PMOS and NMOS transistor. The PMOS transistor P includes a source connected to a power supply labeled DC, and a drain where an output voltage V OUT  of the unit  16 - 1  is provided. The NMOS transistor N includes a drain connected to the drain of the PMOS transistor P and a source connected to the voltage reference. A voltage level V C  at the gates is dependent on the temperature of the capacitor C, the process parameters used in manufacturing the unit  16 - 1 , or the residual charge in the capacitor C. The value of V C  therefore is not predictable. If V C  is negative enough to turn on the PMOS transistor P, the output voltage V OUT  is pulled to approximately the voltage level of the power supply DC such that the unit  16 - 1  provides a logic high value, i.e., logic 1. If V C  is positive enough to turn on the NMOS transistor N, the output voltage V OUT  is pulled to the voltage reference such that the unit  16 - 1  provides a logic low value, i.e., logic 0. Given an example of a 16-bit initial value generator  16 , a total number of sixteen (16) units such as the unit  16 - 1  are required. Each of the sixteen units accounts for a bit value of the resultant initial value. Since the capacitor condition is different from unit to unit, the initial value provided by the initial value generator  16  is not predictable and, in other words, random.  
         [0025]      FIG. 1C  is a schematic timing diagram for the random number generator  10  illustrated in  FIG. 1A . Referring to  FIG. 1C , the oscillator  12  does not oscillate until time to, and provides the clock signal including a train of clocking pulses at the time t 0 . The initial value generator  16  provides a random initial value K substantially at the same time t 0  since when the number of clocking pulses is counted from the initial value K. The counting continues till a transition of the reset signal occurs at time t N+1 . The counter  17  counts (K+N) at the time t N+1 , wherein N is the number of clocking pulses counted thus far. The value (K+N) serves as a random number and is then provided by the random number generator  10 .  
         [0026]     In some examples, the oscillator  12  may include a crystal oscillator, which allows a relatively low tolerance so that the effect on the resultant random number RN due to the frequency offset can be negated. For example, the oscillator  12  may provide the clock signal at a precise frequency of 10 MHz. The random number RN in the present example is expressed in a function below. 
 
 RN=g (   F OFFSET       , T   RESET   , INIV ) 
 
         [0027]     In some examples, the time period to reset the counter  17  may be a constant, regardless of whether the output voltage from the regulator  14  equals the predetermined voltage level. For example, the counter  17  is reset once every second. The random number RN in the present example is expressed in the function below. 
 
 RN=h ( F   OFFSET   ,  T RESET       , INIV ) 
 
         [0028]     In one example, the initial value can be a predetermined value, for example, a full-zero or full-one output such that the effect on the resultant random number RN due to the randomness in each of the bits is negated. The random number RN in the present example is expressed in a function below. 
 
 RN=p ( F   OFFSET   , T   RESET   ,  INIV )  
 
         [0029]      FIG. 2  is a flow diagram of a method for generating a random number consistent with an example of the invention. Referring to  FIG. 2 , at step  21 , a supply voltage is provided. The supply voltage may include a DC voltage from a power supply such as a battery or a rectified DC voltage from a voltage rectifier rectifying an input alternating current (AC) voltage. At step  22 , a clock signal including a sequence of clocking pulses is generated by, for example, an oscillator, which oscillates in response to the supply voltage. Next, an initial value is provided at step  23 . The number of clocking pulses is counted from the initial value at step  24 . An output voltage, which is an integer multiple of the supply voltage, is generated at step  25  by, for example, a charge pump circuit. The output voltage is compared with a predetermined voltage level at step  26  to determine whether the output voltage reaches the predetermined voltage level. If confirmative, a count is provided at step  27 . The count is dependent on at least one of a frequency offset from a center frequency of the clock signal, the time the output voltage equals the predetermined voltage level, and the initial value.  
         [0030]      FIG. 3A  is a schematic block diagram of a radio frequency identification (“RFID”) device  30  consistent with an example of the invention. Referring to  FIG. 3A , the RFID device  30 , which may be termed an RFID tag or a transponder, includes an analog module  31 , a digital module  32  and a memory  33 . The analog module  31  receives a carrier signal transmitted from a reader  40  through an antenna  34  such as a coiled antenna, and demodulates the carrier signal to obtain a command included in the carrier signal. The command generally requests the RFID device  30  to respond with identification (“ID”) information, which complies with the Electronic Product Code (“EPC”) standard. The ID information is stored in the memory  33  and may include the product name and price associated with a product item. The command is decoded by the digital module  32  before sent to the memory  33 . The ID information provided by the memory  33  in response to the decoded command is encoded in the digital module  32 , modulated in the analog module  31  and then transmitted to the reader  40  through the antenna  34 .  
         [0031]     In the RFID industry, the traffic between an RFID device and a reader may suffer from a phenomenon called “tag collision”, which may occur when plural RFID tags communicate with one reader at substantially the same time. A solution to solve the problem is to provided a random number generator in the RFID device for generating a random number. By distinguishing among the random numbers provided by the plural RFID devices, the reader is able to match a specific ID information with a specific random number at a specific time slot. However, as noted above, a conventional random number generator like a pseudo random number generator may often provide a number that is predictable and is not quite random. Consequently, the tag collision may not be alleviated.  
         [0032]     Referring again to  FIG. 3A , in one example, the RFID device  30  may further include a seed number generator  50  in the analog module  31  and a random number generator  32 - 1  in the digital module  32 . The seed number generator  50  generates a seed number (SN), which is an unpredictable random number, to serve as an initial seed value for the random number generator  32 - 1 . The random number generator  32 - 1 , which may include a pseudo random number generator, generates a random number based on the seed number. Since the seed number is not predictable, the random number provided by the random number generator  32 - 1  is not predictable, either.  
         [0033]      FIG. 3B  is a block diagram of the seed number generator  50  of the RFID device  30  illustrated in  FIG. 3A . Referring to  FIG. 3B , the seed number generator  50  has a similar structure to the random number generator  10  illustrated in  FIG. 1A  except that a rectifier  51  replaces the power supply  11 . The rectifier  51  receives the carrier signal transmitted from the reader  40  and obtains a DC voltage by rectifying the carrier signal. The DC voltage is provided to an oscillator  52  and a charge pump  53 . Once oscillates, the oscillator provides a clock signal including a sequence of clocking pulses to the charge pump  53  and a counter  57 . The clock signal has a frequency offset from a center frequency of the oscillator  52 . In response to the cock signal, the charge pump  53  provides an output voltage which is an integer multiple of the DC voltage. The output voltage is regulated by a regulator  54  with respect to a predetermined voltage level. A reset circuit  55  latches the counter  57  once the output voltage reaches the predetermined voltage level. An initial value generator  56  provides an initial value to the counter  57  at substantially the same time the clock signal is provided to the counter  57 . The seed number SN generated by the counter  57  is dependent on at least one of the frequency offset, the latch time and the initial value.  
         [0034]     The RFID device  30  further includes a demodulation circuit  58  electrically connected to the rectifier  51  and the regulator  54  for providing the command (CMD). The seed number SN and the command CMD are sent to the digital module  32  illustrated in  FIG. 3A .  
         [0035]     It will be appreciated by those skilled in the art that changes could be made to one or more of the examples described above without departing from the broad inventive concept thereof. It is understood, therefore, that this invention is not limited to the particular examples disclosed, but it is intended to cover modifications within the scope of the present invention as defined by the appended claims.  
         [0036]     Further, in describing certain illustrative examples of the present invention, the specification may have presented the method and/or process of the present invention as a particular sequence of steps. However, to the extent that the method or process does not rely on the particular order of steps set forth herein, the method or process should not be limited to the particular sequence of steps described. As one of ordinary skill in the art would appreciate, other sequences of steps may be possible. Therefore, the particular order of the steps set forth in the specification should not be construed as limitations on the claims. In addition, the claims directed to the method and/or process of the present invention should not be limited to the performance of their steps in the order written, and one skilled in the art can readily appreciate that the sequences may be varied and still remain within the spirit and scope of the present invention.