Patent Publication Number: US-2004049525-A1

Title: Feedback random number generation method and system

Description:
TECHNICAL FIELD  
       [0001] The present invention generally relates to physical random number generators (i.e., a device that generates a bit or bits representative of a number by operating one or more components of the device in an undeterminable manner). The present invention specifically relates to an improvement of a randomness of a physical random number generator.  
       BACKGROUND AND SUMMARY OF THE INVENTION  
       [0002] Physical random number generators as known in the art generate a random number bit or bits by operating one or more components of the device in an undeterminable manner. Conceptually, the undeterminable operation of the component(s) yields an unbiased random generation of the random number bit(s). In practice, the undeterminable operation of the component(s) typically yields a biased generation of the random number bit(s) due to various tolerances related to the operation of the component(s).  
       [0003] The present invention employs a linear feedback shift register and a decimator to improve upon a biased generation of a true random bit sequence by a physical random number generator. Various aspects of the present invention are novel, non-obvious, and provide various advantages. While the actual nature of the present invention covered herein can only be determined with reference to the claims appended hereto, certain features, which are characteristic of the embodiments disclosed herein, are described briefly as follows.  
       [0004] One form of the present invention is a random number generation system comprising a physical random number generator, a linear feedback shift register,  
       [0005] One form of the present invention is a random number generation system comprising a physical random number generator, a linear feedback shift register, a clock, and a decimator. The physical random number generator operates to generate one or more true random bit sequences that are communicated to the linear feedback shift register, which operates to periodically latch one or more feedback random bit sequences as a function of the true random bit sequence(s). A clock signal from the clock triggers the periodic latching of the feedback random bit sequence(s) by the linear feedback shift register. The periodic latching of one of feedback random bit sequences is communicated to the decimator, which operates to provide one or more output random bit sequences that are representative of a selective outputting of the feedback random bit sequence(s).  
       [0006] The foregoing form as well as other forms, features and advantages of the present invention will become further apparent from the following detailed description of the presently preferred embodiments, read in conjunction with the accompanying drawings. The detailed description and drawings are merely illustrative of the present invention rather than limiting, the scope of the present invention being defined by the appended claims and equivalents thereof. 
     
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
     [0007]FIG. 1 illustrates a block diagram of a first embodiment of a random number generation system in accordance with the present invention;  
     [0008]FIG. 2 illustrates a schematic diagram of a first embodiment of the FIG. 1 random number generation system in accordance with the present invention; and  
     [0009]FIG. 3 illustrates a block diagram of a second embodiment of the FIG. 1 random number generation system in accordance with the present invention.  
    
    
     DETAILED DESCRIPTION OF THE INVENTION  
     [0010]FIG. 1 illustrates a random number generation system  10  (hereinafter “system  10 ”) comprising a physical random number generator  20  (hereinafter “PRNG  20 ”), linear feedback shift register  30  (hereinafter “LFSR  30 ”), a conventional clock  40 , and a conventional decimator  50 . The PRNG  20  is in communication with the LFSR  30  to thereby provide one or more true random bit sequences TRB 1 -TRB X  to the logic LFSR  30 . The LFSR  30  operates to periodically latch one or more feedback random bit sequences FRB 1 -FRB Y  as a function of the true random bit sequences TRB 1 -TRB X . The clock  40  is in communication with the LFSR  30  to thereby provide a clock signal CS to the LFSR  30 , the clock signal CS having a predetermined operating frequency for triggering a periodic latching of the feedback random bit sequences FRB 1 -FRB Y  by the LFSR  30 . The LSFR  30  is in communication with the decimator  50  to thereby provide the feedback random bit sequences FRB 1 -FRB Y  to the decimator  50  whereby the decimator  50  provides an one or more output random bit sequence ORB 1 -ORB Z  that are representative of a selective outputting of the feedback random bit sequences FRB 1 -FRB Y .  
     [0011] The number of configurations of the PRNG  20 , the LFSR  30 , the clock  40 , and the decimator  50  is without limit. Additionally, the aforementioned communications among the PRNG  20 , the LFSR  30 , the clock  40 , and the decimator  50  can be achieved in numerous ways (e.g., electrically, optically, acoustically, and/or magnetically). The number of embodiments of the system  10  is therefore essentially limitless.  
     [0012]FIG. 2 illustrates a random number generation system  11  (hereinafter “system  11 ”) as one embodiment of system  10  (FIG. 1). The system  11  includes a physical random number generator  21  (hereinafter “PRNG  21 ”) and a linear feedback shift register  31  (hereinafter “LFSR  31 ”). The PRNG  21  is operable to a true random bit sequence TRB, (X=1). In one embodiment, the PRNG  21  is configured in accordance with a U.S. Patent Application Serial No. [FILL IN} entitled “Latching Electronic Circuit For Random Number Generation”, the entirety of which is hereby incorporated by reference and commonly owned by the assignee. In another embodiment, the PRNG  21  is configured in accordance with a U.S. Patent Application Serial No. [FILL IN} entitled “Switching Electronic Circuit For Random Number Generation”, the entirety of which is hereby incorporated by reference and commonly owned by the assignee.  
     [0013] The LFSR  31  includes a logic circuit in the form of an XOR gate  32  having a first input electrically coupled to the PRNG  21  to thereby receive the true random bit sequence TRB 1 . The LFSR  31  further includes a conventional arrangement of bi-stable latches in the form of D-type flip-flops  33   1 - 33   Y  where a data output Q is electrically coupled to a data input D of a succeeding flip flop. Each flip-flop  33   1 - 33   Y  periodically latches a corresponding feedback random bit sequence FRB 1 -FRB Y  in response to a reception of the clock signal CS. The clock  40  is electrically coupled to each latch input  1  of the flip-flops  33   1 - 33   Y  to thereby provide the clock signal CS to each flip-flop  33   1 - 33   Y . To enforce a periodic latching of the feedback random bit sequences FRB 1 -FRB Y  by the flip-flops  33   1 - 33   Y , a triggering transition time of the clock signal CS honors the data setup and hold times of the flip-flops  33   1 - 33   Y .  
     [0014] The data output Q of a flip-flop  332  is electrically coupled to a second input of the XOR gate  32  to thereby provide a feedback random bit sequence FRB 2  to the XOR gate  32 . The data output Q of a flip-flop  33   Z  is electrically coupled to a second input of the XOR gate  32  to thereby provide a feedback random bit sequence FRB Y  to the XOR gate  32 . The data output Q of a number of the other flip-flops can be currently electrically coupled to the other illustrated inputs of the XOR gate  32  to thereby provide additional feedback random bit sequences to the XOR gate  32 . The output of the XOR gate  32  is electrically coupled to the data input D of the first flip-flop  33   1  to thereby provide a mixed random bit sequence MRB to the flip-flop  33   1 . The Q output of the flip-flop  32   Y  is also electrically coupled to a decimator  51  to thereby provide the feedback random bit sequence FRB Y  to the decimator  51  whereby the decimator  51  provides an output random bit sequence ORB 1  (Z=1) that is representative of a selective outputting of the feedback random bit sequence FRB Y . In one embodiment, the decimator  51  is a counter having a data input electrically coupled to the Q output of the flip-flop  32   Y  whereby a selection input of the counter is controlled to implement a selective outputting of the feedback random bit sequence FRB Y .  
     [0015] System  11  can be varied in numerous ways to yield alternative embodiments of system  11  as would be appreciated by those having ordinary skill in the art. For example, to enhance and/or alter the bit mixing, different feedback random bit sequences among FRB 1 -FRB Y  can be communicated to XOR gate  32 . Second, only one feedback random bit sequence among feedback random bit sequences FRB 1 -FRB Y  can be communicated to embodiments of a logic circuit having two inputs. Third, additional true random bit sequences among TRB 2 -TRB X  (FIG. 1) and/or additional feedback random bit sequences among feedback random bit sequences FRB 1 -FRB Y  can be communicated to embodiments of a logic circuit having four or more inputs. Fourth, additional mixed random bit sequences can be communicated to LFSR  31  and/or additional LFSRs  31 . Fifth, one or more of the inverted data outputs Q of the flip-flops  33   1 - 33   Y  can be utilized to generate the one or more of the feedback random bit sequences FRB 1 -FRB Y . Sixth, other types of bi-stable latches can be substituted for one or more of the D-type flip-flops  33   1 - 33   Y .  
     [0016] An operation of the system  11  will now be described herein. For purposes of the operational description, an initial state of the system  11  consists of the true random bit sequence TRB 1  and the feedback random bit sequences FRB 1 -FRB Y  being set as 0 bits. Accordingly, the mixed bit MRB is also set as a 0 bit. Also for purposes of the operational description, the LFSR  31  consists of five (5) flip-flops  33   1 - 33   5  where the illustrated flip-flop  33   Y  serves as the flip-flop  33   5 . Further, the flip-flops  33   1 - 33   5  are designed to be triggered upon a rising edge of the clocks signal CS.  
     [0017] The following TABLE 1 illustrates an exemplary operation of the system  11  when the PRNG  20  is biased toward generating the true random bit sequence TRB 1  as a 1 bit:  
                                           TABLE 1                       TIME   TRB 1     MRB   FRB 1     FRB 2     FRB 3     FRB 4     FRB 5                    T 0      1   1   0   0   0   0   0       T 1      1   1   1   0   0   0   0       T 2      1   1   1   1   0   0   0       T 3      1   1   1   1   1   0   0       T 4      1   1   1   1   1   1   0       T 5      1   1   1   1   1   1   1       T 6      1   0   0   1   1   1   1       T 7      1   0   0   0   1   1   1       T 8      1   1   1   0   0   1   1       T 9      1   1   1   1   0   0   1       T 10     1   0   0   1   1   0   0       T 11     1   1   0   0   1   1   0       T 12     1   1   1   0   0   1   1       T 13     1   1   1   1   0   0   1       T 14     1   0   0   1   1   0   0       T 15     1   1   1   0   1   1   0       T 16     1   1   1   1   0   1   1       T 17     1   0   0   1   1   1   0       T 18     1   1   1   0   1   1   1       T 19     1   1   1   1   0   1   1       T 20     1   0   1   1   1   0   1                  
 
     [0018] The following TABLE 2 illustrates another exemplary operation of the system  11  when the PRNG  20  is not very random generating the true random bit sequence TRB, as a periodic  0011  sequence:  
                                           TABLE 2                       TIME   TRB 1     MRB   FRB 1     FRB 2     FRB 3     FRB 4     FRB 5                    T 0      0   0   0   0   0   0   0       T 1      0   0   0   0   0   0   0       T 2      0   0   0   0   0   0   0       T 3      1   1   0   0   0   0   0       T 4      1   1   1   0   0   0   0       T 5      0   0   0   1   1   0   0       T 6      0   0   0   0   1   1   0       T 7      1   1   1   0   0   1   1       T 8      1   1   1   1   0   0   1       T 9      0   1   1   1   1   0   0       T 10     0   1   1   1   1   1   0       T 11     1   1   1   1   1   1   1       T 12     1   0   0   1   1   1   1       T 13     0   1   1   0   1   1   1       T 14     0   1   1   1   0   1   1       T 15     1   0   0   1   1   0   1       T 16     1   0   0   0   1   1   0       T 17     0   0   0   0   0   1   1       T 18     0   1   1   0   0   0   1       T 19     1   1   1   1   0   0   0       T 20     1   1   1   1   1   0   0                  
 
     [0019]FIG. 3 illustrates a random number generation system  12  (hereinafter “system  12 ”) as another embodiment of system  10  (FIG. 1). The system  12  employs the PRNG  21 , the clock  40 , a plurality of LFSRs  31   1 - 31   A , a plurality of decimators  51   1 - 51   A , and a logic circuit  60  (e.g., a multi-input XOR gate). The decimators  51   1 - 51   A  are in communication with logic circuit  60  to thereby provide a plurality of output random bit sequences ORB 1 -ORB A  to the logic circuit  60 . In response thereto, the logic circuit  60  will provide a system random bit sequence SRB that is sufficiently insensitive to any of the output random bit sequences ORB 1 -ORB A  being provided as a constant bit stream. As long as any one of the corresponding pairs of LFSRs  31   1 - 31   A  and decimators  51   1 - 51   A  produce random bits, the resulting system random bit sequence SRB will also be random. On a VLSI chip, integrating several hundreds of different LFSRs  31   1 - 31   A  and decimators  51   1 - 51   A  is feasible and the resulting bit stream will be highly unpredictable.  
     [0020] System  12  can be varied in numerous ways to yield alternative embodiments of system  12  as would be appreciated by those having ordinary skill in the art. For example, alternative to each LFSR  31   1 - 31   A  receiving the clock signal CS, additional clocks can be employed within an alternative embodiment of system  12  to provide two or more clock signals of different frequencies with each clock signal being strategically provided to selected LFSRs  31   1 - 31   A . Second, additional PRNGs  21  can be employed within an alternative embodiment of system  12  with each true random bit sequence being strategically provided to the selected LFSRs  31   1 - 31   A . Third, one or more of the decimators  51   1 - 51   A  can be in communication with two or more of the LFSRs  31   1 - 31   A . Fourth, the decimators  51   1 - 51   A  can be removed and the LFSRs  31   1 - 31   A  can be in communication with the logic circuit  60  whereby the system random bit sequence SRB is a function of selected feedback random bit sequences from the LFSRs  31   1 - 31   A .  
     [0021] While the embodiments of the present invention disclosed herein are presently considered to be preferred, various changes and modifications can be made without departing from the spirit and scope of the present invention. The scope of the present invention is indicated in the appended claims, and all changes that come within the meaning and range of equivalents are intended to be embraced therein.