D Sesqunces Randomness
D Sesqunces Randomness
D Sesqunces Randomness
Introduction
There exist two approaches to randomness [1]: one takes the path of probability, the other
that of complexity [2]. From the point of view of probability, all binary sequences of
length n are equivalent, but from the point of view of complexity, the sequence
01001011110
is more random than the all-zero sequence
00000000000
Ritter [1] summarizes several methods to measure algorithmic complexity that includes
the application of suitable transforms [3].
In this paper, we consider a new measure, due to Kak, to quantify randomness. It is based
on the idea of how much the autocorrelation departs from the ideal that is true for white
noise. Kak defines the randomness, R(x), of a discrete sequence x by the expression
below:
n 1
C (k )
R( x) = 1
k =1
n 1
where C(k) is the autocorrelation value for k and n is the period of sequence. The value of
the autocorrelation is defined as in the equation below:
1 n
C (k ) = a j a j +k
n j =0
Since the randomness measure of discrete-time white noise sequence is 1 whereas that of
a constant sequence is 0, this measure conforms to our intuitive expectations. Likewise,
the value of randomness for a binary shift register maximum-length sequence is close to
1, in accord with our expectations.
This measure will be tried on the class of d-sequences [4-12], that are decimal
sequences in an arbitrary base, although binary (base-2) sequences will be the only ones
that will be considered in this paper. D-sequences have found several applications in
cryptography, watermarking, spread-spectrum [5-12], and as generator of random
numbers [13]. They constitute a very versatile source of random sequences, since, unlike
maximum-length shift-register sequences [14], they are not constrained to only a limited
number of period values. They have the additional virtue that other periodic sequences
(including maximum-length shift register sequences) can be seen as special cases of dsequences.
The motivation for this study is the search of new classes of random sequences for
applications to cryptography and spread spectrum systems.
That the decimal sequences of rational and irrational numbers may be used to generate
pseudo-random sequences is suggested by the following theorems of decimals of real
numbers.
Theorem 2: Almost all decimals, in any base, contain all possible digits. The expression
almost all implies that the property applies everywhere except to a set of measure zero.
Theorem 3: Almost all decimals, in any base, contain all possible sequences of any
number of digits.
Theorems 2 and 3 guarantee that a decimal sequence missing any digit is exceptional.
Autocorrelation and cross-correlation properties of d-sequences are given in [4] and [5].
It is easy to generate d-sequences, which makes them attractive for many engineering
applications. For a maximum-length d-sequence, 1/q, the digits of a/q, where a < q, are
permutations of the digits of 1/q, which makes it possible to use them for error-correction
coding applications [5].
We are concerned primarily with maximum-length binary d-sequences (which are
generated by prime numbers) because, as we will show later, the randomness measure for
such sequences is generally better than for non-maximum-length d-sequences. The binary
d-sequence is generated by means of the algorithm [6]:
1
1
1 1
(.0011101)2 = + +
+
8 16 32 128 10
Hence .0011101 2
1
1 1 1 1
1
1
1 1
= + +
+ 7 + +
+
+
+
8 16 32 128 2 8 16 32 128
1 1 1
1
1
+
+ +
+
14
2 8 16 32 128
1
1
1 1
= + +
+
8 16 32 128
1
1
1 + 2 7 + 214 + ......
3
16
+
8
+
4
+
1
1
=
128
1 1
2 7
29 128
=
128 127
29
=
127
d-sequences
PN sequence
C (k )
We apply the randomness measure R ( x )
=1
k =1
n 1
autocorrelation value for k and n is the period of sequence, to determine how it varies for
different values of q.
We first consider the general d-sequence 1/n, where n is an odd number. For doing so we
The randomness measure has its minima for n = 2k-1, since for such a case the sequence
would be k-1 0s followed by 1, which is a highly non-random sequence. However,
multiplying such a sequence with an appropriate integer could generate a PN sequence as
given by the previous example.
1.2
Randomness measure
0.8
0.6
0.4
0.2
27449
28429
29409
60733
63179
26469
58391
25489
24509
23529
22549
21569
20589
19609
18629
17649
16669
15689
14709
13729
12749
11769
9809
10789
8829
7849
6869
5889
4909
3929
2949
1969
989
Odd numbers
Randomness Measure
0.8
0.6
0.4
0.2
56179
53887
51577
49307
47059
44687
42407
40193
37963
35771
33533
31337
29147
26953
24841
22697
20611
18443
16417
14423
12401
10337
8461
6553
4721
2953
1307
Prime Number
Randomness measure
0.8
0.6
0.4
0.2
61331
58427
55813
53147
50227
47507
44939
42403
39869
37013
34651
32237
29723
27299
24709
22157
19739
17077
14797
12251
9803
7573
5563
3499
1531
Prime number
Randomness measure
0.8
0.6
0.4
0.2
62311
59833
57791
55903
53441
51343
48857
46663
44351
41959
39791
37561
35159
32999
30727
28663
26681
24439
22409
20479
18089
15991
13879
12097
10223
8297
6287
4639
2753
1279
Prime numbers
Conclusions
This note has shown that the randomness measure R(x) has excellent characteristics since
it accords with our intuitive ideas of randomness. The application of this measure to dsequences has shown that these have good randomness properties and, therefore, their use
in cryptographic applications may be appropriate in many situations.
References
1. T. Ritter, Randomness tests: a literature survey.
http://www.ciphersbyritter.com/RES/RANDTEST.HTM
2. Kolmogorov, Three approaches to the quantitative definition of information.
Problems of Information Transmission. 1, 1-17, 1965.
3. S. Kak, Classification of random binary sequences using Walsh-Fourier analysis.
Proceedings of Applications of Walsh Functions. Pp. 74-77. Washington, 1971.
4. S. Kak and A. Chatterjee, On decimal sequences. IEEE Transactions on
Information Theory, IT-27: 647 652, 1981.
5. S. Kak, Encryption and error-correction coding using D sequences. IEEE
Transactions on Computers, C-34: 803-809, 1985.
6. S. Kak, New results on d-sequences. Electronics Letters, 23: 617, 1987.
7. D. Mandelbaum, On subsequences of arithmetic sequences. IEEE Trans on
Computers, vol. 37, pp 1314-1315, 1988.
8. S. Kak, A new method for coin flipping by telephone. Cryptologia, vol. 13, pp.
73-78, 1989.
9. N. Mandhani and S. Kak, Watermarking using decimal sequences. Cryptologia,
vol 29, pp. 50-58, 2005; arXiv: cs.CR/0602003
10. R. Vaddiraja, Generalized d-sequences and their applications in CDMA Systems.
MS Thesis, Louisiana State University, 2003.
11. K. Penumarthi and S. Kak, Augmented watermarking. Cryptologia, vol. 30, pp
173-180, 2006.
12. S. Kak, Joint encryption and error-correction coding, Proceedings of the 1983
IEEE Symposium on Security and Privacy, pp. 55-60 1983.
13. G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers. Oxford
University Press, 1954.
14. S.W. Golomb, Shift Register Sequences. Aegean Park Press, 1982.