Lec 11 Computer and Data Security

3.7 Measure Of Randomness
3.7.1 DEFINITION:
Run: sequence of identical bits (0 or 1) Ex: 01110000111
Runs are 0,111, 0000, 111
Gap: runs of zeroes
000011 contain the gap 0000
Block: runs of ones
1111001110 contain blocks 1111,111 For with period P , Sm + p = Sm

Auto correlation function: For any constant d, if we compare the sequence of S with Sd (after shifting d displacement), then Auto correlation function C(t) = (A - D) / P Where :
A = no. Of identical bits.
P = period of the sequence
D = period of different bits
d = displacement 0 <= d < p
Rundomness Chacteristics:
1. If p is even then ones equal zeros, other wise they differ by one only.
2. 1/2 of runs with length of 1 , 1/4 of runs with length of 2 , generally i / 2i = i.
3. Auto correlation function (for d < > 0 out of phase) has constant value. Where d is the displacement.



3.7.2 Randomness Tests
1. FREQUENCY TEST: Used to ensure that there is roughly the same number of O s and 1 s using the following formula:
X2 =(n0 – n1)2 / n
X2 = 0 if n0 = n1 For good sequence 0 < X2 < 3.84
2. SERIAL TEST: The serial test is used to ensure that the transition probabilities are reasonable. This will give as some level of confidence that each bit is independent of its predecessor suppose .01 occurs n01, 10 occurs n10, 00 occurs n00…and 11 occurs n11 times.
n01+n10=n0 or n0-1 , n10+n11 = n01 or n1-1 and
N10 + N01 + N00 + N11 = N-1
X2 = 4/n - 1 ?(nij)2 - 2/n ?(ni)2 + 1
For good sequence X2 <= 5.99.
Ideally we want: n01 = n10 = n00 = n11 ? n-1/4