US5046036A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Pseudorandom number generator
Assignee: International Business Machines Corp
•
Filing: 1988-03-18
•
Granted: 1991-09-03
•
Expires: 2008-03-18
Abstract
Abstract A pseudorandom number generator includes: an M-sequence generator having a plurality of stages a i ; and a matrix product circuit which combines a matrix G having components g ji with the stages a i to provide output elements b j of a number, each b j being represented by the expression, b.sub.j =Σ.sub.i a.sub.j g.sub.ji.
Inventors
- 👤 Shu Tezuka
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 16:16
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/58; G06F7/582; G06F7/584; G06F2207/00; G06F2207/58; G06F2207/581; G06F2207/583
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
41 words
A pseudorandom number generator comprising: a polynomial circuit comprising a feedback shift register; and matrix multiplication means for receiving parallel data from said feedback shift register and performing matrix multiplication A×G wherein A is a vector and G is a matrix.
Claim 2
Dependent Claim
41 words
A pseudorandom number generator comprising: a polynomial circuit comprising a feedback shift register; and matrix multiplication means for receiving parallel data from said feedback shift register and performing matrix multiplication A×G wherein A is a vector and G is a matrix.
Claim 3
Dependent Claim
75 words
A pseudorandom number generator comprising: a polynomial circuit shift register storing a vector A; an exclusive-OR gate receiving as inputs two bit values of said shift register, the output of said exclusive-OR gate being input to said shift register; and means for matrix multiplying the vector A in said shift register by a shuffling matrix G wherein the multiplying of one A vector after another by the matrix G produces asymptotic random numbers in succession.
Claim 4
Dependent Claim
75 words
A pseudorandom number generator comprising: a polynomial circuit shift register storing a vector A; an exclusive-OR gate receiving as inputs two bit values of said shift register, the output of said exclusive-OR gate being input to said shift register; and means for matrix multiplying the vector A in said shift register by a shuffling matrix G wherein the multiplying of one A vector after another by the matrix G produces asymptotic random numbers in succession.
Claim 5
Dependent Claim
73 words
A pseudorandom number generator comprising: an M-sequence generator having a plurality of stages a i ; and a matrix product circuit which combines a matrix G having components g ji with the stages a i to provide output elements b j of a number, each b j being represented by the expression, b.sub.j =.sub.i.sup.Σ a.sub.i g.sub.ji wherein the numbers formed of b j elements are asymptotic random numbers having a uniform k distribution.
Claim 6
Dependent Claim
73 words
A pseudorandom number generator comprising: an M-sequence generator having a plurality of stages a i ; and a matrix product circuit which combines a matrix G having components g ji with the stages a i to provide output elements b j of a number, each b j being represented by the expression, b.sub.j =.sub.i.sup.Σ a.sub.i g.sub.ji wherein the numbers formed of b j elements are asymptotic random numbers having a uniform k distribution.
Claim 7
Dependent Claim
18 words
A pseudorandom number generator as in claim 3 wherein each row vector of G is linear and independent.
Claim 8
Dependent Claim
44 words
A pseudorandom number generator as in claim 3 wherein the M-sequence generator comprises (a) shift register and (b) a gate which exclusively ORs at least two stages of the shift register and directs the result as input to a stage of the shift register.
Claim 9
Dependent Claim
53 words
A pseudorandom number generator as in claim 5 wherein the shift register has seven stages and wherein said gate exclusively ORs the bit of one end stage a 0 with the bit of the middle stage a 3 , the result being input to bit of the other end stage a 6 .
Claim 10
Independent Claim
122 words
A method for generating l-bit pseudorandom numbers by using a feedback shift register having a polynomial characteristic equation of degree p, said shift register having stages which contain bit values where l is less than or equal to p, the method comprising the steps of: combining the current bit values of preselected stages of the shift register, the combined result being shifted into the shift register as the next input; forming a matrix G; and multiplying, in a matrix product circuit, the bit values contained in the stages of the shift register by the formed matrix G for successive shift register shifts, wherein successive products of the multiplying in response to successive shifts represents successive uniform k-distribution random numbers characterized by asymptoticity.
Claim 11
Independent Claim
122 words
A method for generating l-bit pseudorandom numbers by using a feedback shift register having a polynomial characteristic equation of degree p, said shift register having stages which contain bit values where l is less than or equal to p, the method comprising the steps of: combining the current bit values of preselected stages of the shift register, the combined result being shifted into the shift register as the next input; forming a matrix G; and multiplying, in a matrix product circuit, the bit values contained in the stages of the shift register by the formed matrix G for successive shift register shifts, wherein successive products of the multiplying in response to successive shifts represents successive uniform k-distribution random numbers characterized by asymptoticity.
Claim 12
Dependent Claim
62 words
The method of claim 7 wherein the step of forming the matrix G comprises the step of: forming one G L matrix after another for successive values of L, where L is less than or equal to p, wherein each matrix G L has rows which are linear and independent; the G L matrix, for the highest L, comprising the G matrix.
Claim 13
Dependent Claim
140 words
The method of claim 8 wherein the forming of G L matrixes comprises the steps of: for L=1, selecting an arbitrary row vector v L and deriving the remaining row vectors from v L ; for L greater than 1, (i) extracting some row vectors from previously formed matrixes of lesser L value and (ii) arbitrarily selecting a vector v L for a non-extracted row and deriving the remaining non-extracted rows from the selected vector v L ; and for each L, re-selecting the vector v L if each row vector in matrix G L is not linear and independent and re-deriving the remaining rows for the matrix G L with the re-selected vector v L ; row vectors in each G L matrix being extracted from only a previously formed G L matrix having only linear and independent rows.
References Cited (Backward Citations)
US3742381A
Cited
US3811038A
Cited
FR2172460A5
Cited
US4161041A
Cited
US4493046A
Cited
US4408298A
Cited
GB2163627A
Cited
US4774681A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-09-02 | 1995-03-04 | 1995-09-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-09-02 | 1999-03-04 | 1999-09-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-09-02 | 2003-03-04 | 2003-09-03 | $7700.00 | Window Closed / Lapsed |