KYBERNETIKA SLO 3, RONK 2/1966

On a Method of Pseudo-Random Numbers Generation

The present paper summarizes some knowledge, results and possibilities of use of the linear recurrence modulo 2 generation method of pseudo-random numbers. Characterization and properties of the method are briefly treated in the first part. Results of measurements and tests of the generator are presented in the second part. It is shown, that although the method fulfills some basic properties, required for generators of random binomial sequences, it is not, as compared with the generator based on physical principles, too useful for further transformations (filtering including).

I. DESCRIPTION AND PROPERTIES O F THE METHOD The above mentioned method is described in [1] and [2]. Nature of generating the sequence is represented on Fig. 1. Let us have an n-stage shift register and an arbitrary (with the only exception of the number 00 ... 000) n-place binary number

|mod|, I 2 I

Fig. 1. Block schema of the pseudo-random numbers generation.

recorded in it. Let one or several adders modulo 2 (0 + 0 = 1 + 1 = 0 , 0 + 1 = = 1 + 0 = 1 ) be connected to acceptable stages of the register and its or their output be connected to the input of the register. Then on the output of the register pseudo-random noncorrelated sequence of binary numbers (0,1) appears. Theory of generation of such sequences is treated in [3] and in the papers [4], [12] and it is a part of coding theory. Because of pseudo-random sequences, their period is to be determined. It may be shown that the length of the period depends on the degree of the polynomial, from which the sequence is generated and in the case of primitive

polynomial we can, by means of acceptable selection of stages, from which we add, reach the maximal length of period p = 2" 1, where n is the degree of the primitive polynomial (n is the number of stages of the shift register). It is possible to write the i-th term at of the above mentioned sequence {a J at = c 1 a i _i + c 2 a;_ 2 + ... + ca;_ where Cj, j = 1, 2, ..., n 1 is equal either 0 or 1 and cn = 1. Then the sequence is of degree n. In accordance with [1], the necessary and sufficient condition for reaching the maximal period, i.e. p 2" 1 is for polynomial f(x) = 1 + ctx + c2x2 + ... + x" to be primitive over GF(2) (Galois field modulo 2 cf. [3]). In this case, the output sequence has the following properties [5]: 1. For each period it holds, that the number of O's and the number of 1's differ at most by one. From realization we exclude n-tuple containing all zeros. It is clear, that such an n-tuple generates O's all the time. 2. In each period the number of groups of length k (where k < n) containing all zeros or all ones is twice as great as that of length k + 1. 3. Autocorrelation function of the output pseudo-random telegrafic signal (cf. Fig. 2) is:

IzlZ for
T(2" - 1) for

< T,

lu*) = (x
2" - 1

x > T

where T = l// c and fc is the repetition frequency of the output pseudo-random sequence and n is the degree of the primitive polynomial. 4. Spectral power density is a discrete function:
SM)

(2" - 1)-

. . (2" - If [ (an,r - l) J *{>T - l)

and the distance between separate harmonic frequencies is (L/2" lj and the bandwidth of the function Sxx(f) is approximately 0,32/ c . 5. This method of producing pseudo-random sequences may be used in digital computer techniques for gaining random numbers of more digits (maximal number of digits is n, where n is the length of the register) with uniform distribution in the interval (0,1), what is proved in [4]. Let us now for illustration take an example of a 4-stage register and observe closely the technique of generating a pseudo-random sequence. Maximal length of the period

is in this case p = 2 4 1 = 15. In Table 1 producing of this sequence is expressed in two cases. In the first one (column a) the modulo 2 adder is connected to the fourth (output) and the third stages of the register, in the second one (column b) the adder is connected to the fourth and the second stages of the register. In both cases the

Fig. 2. Pseudo-random telegraph signal x(t) (amplitude 1) and its autocorrelation function Rxx(t). Table 1. Possibilities of producing the pseudo-random sequence with 4-stage register (a complete period, b incomplete period) a step register state 1111 0111 0011 0001 1000 0100 0010 1001 1100 0110 1011 0101 1010 1101 1110 1111 output step b register state 1111 0111 0011 1001 1100 1110 1111 output

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1

1 2 3 4 5 6 7

1 1 1 1 0 0 1

1 2 3 4

0110 1011 1101 0110

0 1 1 0

group 1111 was selected for initial state of the register. In the first case we gain the maximal length of the period and it may be seen, that in the register all possible combinations except 0000 are recorded consecutively. We shall therefore call this period "complete". In the second case, the basic condition is not fulfilled and such a register does not produce the maximal period. The register takes only selected number of combinations and the output sequence has not formerly considered properties (cf. e.g. [I)]. It is also clear, that in this case the length of this "incomplete" period depends on the selection of the initial combination. From the point of view of technical realization of the generator using this principle it is necessary to predetermine whether the way of connection (number of stages n, selection of outputs for adding) corresponds to the primitive polynomial. Polynomials up to the degree 34 are given in [3], several other works and measurements in this field are mentioned in the second part of this paper. However, it is advantageous for technical realization to use as simple polynomials as possible (trinomial), which implies the use of minimal number (one) of adders modulo 2. If we compare the just described method of producing pseudo-random numbers with other methods used for digital computers, then its great advantage is its simplicity. It is in fact the only method of generation pseudo-random numbers usable for realization of special portable generators, working without the digital computer. At the same time no extreme length of the register is required, e.g. a 25-stage register can generate a sequence with the period equal to 33 554 431 bits, a 28-stage can produce already a sequence with the period equal to 268 435 455 bits. From the technical point of view, this method is capable of producing random numbers with very high repetition frequency because, except of adding modulo 2, it is necessary to ensure the reliable function of the shift register only. Thus in [6] a generator with output frequency 2 . 108 bit/sec is described and and in [7] a method of connection of pseudo-random numbers generator (operation frequency variable in the range 0 -J- 4 . 106 bit/sec) with an analogue computer is introduced. The generator described in [8] may serve as an example of simple laboratory device. In the latter paper application of this principle for producing continuous realizations is presented and a lowfrequency generator of pseudo-random noise is described. The author does not use the low-pass filter, usually used for producing continuous realizations, but generates the step function, the amplitude of which is directly proportional to the number of pulses of one kind (0) in the register. It is assumed that the distribution of amplitudes of this signal is binomial and in the case of register of sufficient length it approximates the Gaussian distribution. Other properties of the pseudo-random sequence generated by this method are equivalent to another methods of producing pseudo-random numbers, i.e. e.g.: realization may be arbitrarily repeated, it is possible to produce delayed realizations, etc.

II. MEASUREMENT DATA AND SOME RESULTS For verification of some properties the prototype of the generator was constructed and the following measurements performed: 1. measurements of the maximal period with the minimal number of modulo 2 adders (further only one adder considered), 2. measurements of properties of generated sequence. ad 1. Table 2 shows results of measurement of the length of period p of the output sequence as a function of both the length n of the register and the selection of places (n, k) for adding (only one adder modulo 2 is used). It means, that the adder is connected with the last (the n-th) stage and an arbitrary (say ^-th) stage, where l < t < n, and the output of the adder is led to the input of the register. Measurements were carried out for 10 ^ n ^ 28 and for the initial state of the register the combination 111 ... 1 was taken in all cases. As stated above, the necessary and
Table 2. The length p of the period of the output sequence as a function of the number n of stages of the register and the selection of stages for adding (n, k), (initial combination 11 ... 1) \ k \ n
10

1
11 889 1023

1 '
12 13

14

15

16

17

18

19

20

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

42 2047
1953

1533 3255 7905 126 1785

11811

62 1533 15 595 62 595

42 1953 889 2047

45 28 819 18 819 28 45 126

8001 7161 6141 7665 7665 6141 7161 8001 1785 7905

255 273 253921 413385 761763 146 129921 1778 126 114661 5115 63 57337 131071 189 491505 1048575 186: 32767 60 1023 930 91749 84 5461 35 16383 131071 32767 393213 75 93 42 520065 254 434 131071 2046 21 32767 63457 779907 4599 262143 520065 245 32767 24 35805 1022 47523 124 5461 93 63457 35805 27 174251 130305 186 35 434 1022 174251 30 4595
32767 254 | 4599 5115 32767 16383 131071 1023 131071 262143 47523 130305

254
11811

63
32767

60 131071 126 255 114661 273

42 520065
32767 520065

124
779907 2046

4599 57337

930 393213 189 91749 146 491505

75 84
1048575 1778 761763

2" - 1

1023 2047 4095 8191

16383

32767 65535

131071 262143 524287 1048575

Table 2. {Continuation)

\ / \ t 1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

21

22

23

24

25

26

27

28

5461 4194303 2088705 2097151

381

3066 7864305 3670009 32767

2097151 10961685 6510 25165821

298936 15810 2094081 3570 16002 13797

125829105 458745

17895697 23622

189 33554431
2420 16766977 2158065 4185601

406317 4094 2088705 5461 2752491 8388607

219 268435455 5592405 508

105 67074049

279 3906 458745 49 4063201 2094081

90

1048575 33554431 56 8322945

14322 133693183

105 372

381 3899535 8388607 33

651 32247967 155 1638

7469145 63 268435455 12282 130023393 10922 8371713 109226955 ,199753347 . 1533 508 39 130023393 268435455 42 15330 130023393 15330 1533 268435455 508 12282 109226985 7449145 130023393 199753347 10922 14322 63 8371713 13797 133693185 268435455 44564395 372 16002 1395 8877935 5592405

126945 1966065 3899535 87381 49 3066 8388607 279 4063201 2728341 5461 3906 2094081 406317 2752491 458745 381 4094 8388607 2097151 5461 3066 32767 2088705

381

36
5586603 1638

651 155 56 32247967

90 33554431
2420

3670009 2088705 16766977 4194303 7864305

105

189 2158065 67074049 6510 33554431 3570

105
10230 21082635

219

508

458745 268435455 125829105 23622 17895697

2" - 1

2097151 4194303 8388607 16777215 33554431

67108863

134217727 268435455

sufficient condition for obtaining the maximal period p = 2" - 1 is that the polynomial (in this special case the trinomial) f(x) = xn + xk + 1 be primitive. Therefore all primitive trinomials (in corresponding range of degrees) can be determined from Table 2. For other degrees (up to 127) some of the primitive polynomials can be found in [9]. ad 2. To determine the distribution of 0's and l's in the sequence during a period, the following measurements were carried out.

a) Output sequence was divided into consecutive couples (i.e. every particular number of the output sequence is contained just in one couple) and the distribution of relative frequencies of particular types of couples (00, 01, 10, 11) in the maximal period was tested. In this case period (20,17) was measured and results are shown 5 in Table 3. In this measurement, the period was divided into 10 parts with 10 bits in each and Table 3 shows results from each part. For testing %2 test was used.

Measurements of relative frequencies of couples in the period (20,17) k A00 A01 A A 11

X
21-3

1 2 3 4 5 6 7 8 9 10

+ 339 - 86 + 150 - 70 + 12 -170 - 13

+ 1
-108 + 122

-254 + 128 -168 - 65 - 41 + 100 + 14 + 145 + 48 - 32

-256 -110 + 229 + 117 - 48 + 109 + 61 -124 - 10 -155

+ 171 + 68 -211 + 18 + 77 - 39 - 62 - 22 + 70 + 65

10"

33 11-8

0-35

0-007

18 08 41 0-63

0-6
0-85 0-25 0-89 0-39 0-68 0-33

2-9
1-52

3-5

00 =

01

= 1 = H = Z 12500

HYPOTHETIC DISTRIBUTION PSG[,V= 500: per. (29.171] I'SG 1 'V - 500: per. (29.271]

Fig. 3. Histogram of the distribution of relative frequencies of l's in the complete period (29, 27) and in the incomplete period (29, 17).

b) The period was divided into intervals of length 10 4 bits each. In each interval, relative frequency of l's was determined. Obtained values were normalised (E = 0, D = 1) and the hypothesis of normal distribution of these values was tested. Fig. 3 shows these results in histogram form compared with the theoretical normal distribu tion. In this figure results from periods (29, 27) and (29, 17) are stated. 500 trials were carried out in both cases. The period (29, 27) is a complete one. However, in

OHNAPj/Y - 500) HYPOTHETIC DISTRIBUTION

-2.2 - 2 -1.8 -1.6 - . 4 -1.2 -

Fig. 4. Histogram of the distribution of relative frequencies of 1 's in the sequence generated by GENAP (generator based on physical principles).

this case it seems, that if the incomplete period does not differ too much in length from the complete one, then even its properties might be similar to those of the complete period. c) Let us assume that the hypothesis of binomial distribution of output pseudo random sequences holds and consider property 5 from part I., then it is possible to use so-called probability transformer (cf. [10]) by means of which the original random sequence of 0's and l's (where we consider P(0) = P(l) = 0,5) may be transformed into the random sequence of the same type with probabilities P(0*) = p, P(l*) = = 1 p, where p = m2~10, m = 0, 1, ..., 2 1 0 . A sequence of 0*'s and l*'s with probabilities P(0*) = p = 2"" 1 0 , P(l*) = 1 p was realized by means of this transformer*. The distribution of the lengths of l*-run was tested. Assuming the binomial distribution of the input sequence, the probability of l*-run of length T smaller than or equal to fc 1 is
* In this special case occurrence of 0* in the new sequences represents in the original sequence the 10-tuple of 0's. The function of the probability transformer is namely based on the comparison of the 10-digit binary random number with the prescribed number, determining the value p (for details see [10]).

6-1

P(T=

k - i) = 1 ( 1 - Py p =
,/ = o P(T
=

n) ]1 - (1 - P) 1- 1- p t' ,
Xk

= 1 - (1

Pf,

k -

1)=1-

where X = - I n (1 - p); in this case p = 2~ 1 0 yields 2 = 0,001. Altogether 103 numbers were gained and these were distributed into the groups according to Tas may be seen in Table 4, where results of the Kolmogorov-Smirnov test of a good fit of the empirical distribution function E(x) and the theoretical distribution function E(x) are stated. Table 4. Distribution function of l*-runs
X

F(x)

F(x)

F(x) - (x)

100 200 400 600 800

0-197 0-254 0-377 0-503 0-573 0-645 0-706 0-753 0-793 0-820 0-854

0095 0-181 0-330 0-451 0-551 0-632 0-699 0-753 0-798 0-835 0-865

0-102 0-073 0-047 0-052 0-022 0-013 0-007 0-000 0005 0-015 0-011

III. CONCLUSIONS AND COMPARISON WITH THE PHYSICAL SOURCE OF RANDOM SIGNAL As may be seen form Table 4, the Kolmogorov-Smirnov function 1 K(X) yields values much smaller than the significance level 0,05, (1 K(X )being smaller than 7 5 . 10" ). In Fig. 3 bad fit of the approximation with the theoretical distribution can be seen too. In both cases it may be seen, that the form of the distribution of the maximal (complete) period is similar to that of incomplete period when the latter is suficiently long. All deviations are concentrated practically in the range of a. On the other hand, some other properties required for generators of random binomial sequences are fulfilled very well by this method (see 1 5, part I.) as shown by ^-values from Table 3, too. Measurement data obtained using the generator of random binomial sequences based on physical principles (GENAP) (cf. [11]) are given in Fig. 4. Measurements were carried out under the same conditions as in the case of the pseudo-random

sequences, distribution of l*-runs' lengths for the physical generator was tested. In this case the Kolmogorov-Smirnov function 1 K(X) equals 0,8643. The presented results can be used for comparison of both types of generators. The advantages of pseudo-random numbers (their fast generation, reproducibility, etc.) are countervailed by the restrictions imposed on further transformations of the pseudorandom sequence. The pseudo-random generator will in general give worse results than the generator based on physical principles, provided the connection with a filter is considered. The transformation of the original pseudorandom sequence into the 0* 1* sequence with probabilities p, 1 p is not too good for small p. Finally it is necessary to point out, that all the measurements were carried out on sequences generated on the basis of trinomials. Properties of sequences derived from polynomials with more terms were not investigated. (Received October 16th, 1965.) REFERENCES [1] S. W. Golomb: Sequences with Randomness Properties. Glenn L. Martin Co., Baltimore, Md, June 14, 1955. [2] D . C. J. Poortvliet: The Measurement of System Impulse Response by Cross-correlation with Binary Signals. Technical University, Delft 1962. [3] W. W. Peterson: Error-Correcting Codes. M.I.T. Press, 1961 Russian translation, Moskva 1964. [4] R. C. Tausworthe: Random Numbers Generated by Linear Recurrence Modulo Two. Math, of Computation 19 (Apr. 1965), 90, 201-209. [5] R. L. T. Hampton: A Hybrid Analog-Digital Pseudo-Random Noise Generator. Analog Hybrid Computer Laboratory, The University of Arizona, Tuscon, Arizona. [6] Marolf R. A.: 200 Mbit/s Pseudo-Random Sequence Generators for very Wide Band Secure Communication Systems. Proc. Nat. Electron, Conf. Chicago III, (1963), 183 187. [7] Hampton L., Korn G. A., Mittchell B.: Hybrid Analog-Digital Random Noise Generation. IEEE Trans, on Electronic Comp. (1963), 4 1 2 - 4 1 3 . [8] C. Kramer: A Low Frequency Pseudo-Random Noise Generator. Electr. Eng. (1965), 465-467. [9] Watson E. J.: Primitive Polynomials (mod 2). Mathematics of Computation XV (1962), 368-369. [10] J. Havel: Menic pravdepodobnosti (Probability Transformer). Slaboproudy obzor 24 (1963), 2, 8 3 - 8 8 . [11] J. Havel: Elektronicky generator nahodnych posloupnosti (An Electronic Generator of Random Sequences). Slaboproudy obzor 20 (1959), 12, 735-740. [12] Huffman D. A.: The Synthesis of Linear Sequential Coding Networks. Proc. 3rd London Symp. on Inf. Theory.

O jedn metod vytven pseudonhodnch sel

lnek shrnuje nkter poznatky, vsledky a monosti vyuit metody generovn pseudonhodnch sel linernm rekurentnm zpsobem pi pouit setn modulo 2. Pseudonhodn sla jsou vytvena pomoc posuvnho registru, ve kterm je zapsna urit kombinace nul a jedniek. Z pedem zvolench mst registru jsou pak dvojkov sla setna modlilo 2, obsah registru je posunut o jedno msto a v sledek setn zaveden na prvn msto registru. V prv sti lnku je ve strunosti uvedena charakteristika a vlastnosti tohoto zpsobu generovn. Druh st obsahuje vsledky men a test, kter byly zskny na funknm vzorku. Ukazuje se, e akoliv tento zpsob generovn spluje velmi dobe nkter zkladn vlastnosti, kter jsou poadovny od genertor nhodnch binomickch posloupnost, ned se relativn etnosti nul a jedniek v dostaten dlouhch realizacch Gaussovm zkonem rozloen s rozptylem, kter by odpovdal korelan funkci pseudonhodn posloupnosti. V zvru je provedeno srovnn vsledk tto metody s vsledky dosahovanmi genertorem nhodn binomick posloupnosti, kter pracuje na fyziklnm principu.
Antonn Culek, Ing. Jan Havel CSc, SA V, Praha 2, Vyehradsk 49. Ing. Vclav Pibyl, stav teorie informace a automatizace