Information Technology Reference
In-Depth Information
-
Runs Test:
Test statistic is the number runs throughout the sequence, taking
values between 1 and
n
.
-
Random Walk Height Test:
Test statistic is the height of random walk,
that is
i
t
=max
i
=1
,...,n
|
(2
s
j
−
|
1)
(5)
j
=1
taking values between 1 and
n
.
-
Random Walk Excursion Test:
Test statistic is the number of excursions in
the random walk, that is
i
t
=
|{
i
|
(2
s
j
−
1) = 0
,
1
≤
i
≤
n
}|
,
(6)
j
=1
taking values between 0 and
n/
2
-
Linear Complexity Test:
Test statistic is the linear complexity of the se-
quence, that is, the length of the shortest LFSR that generates the sequence,
taking values between 0 and
n
. Linear complexity of a sequence can eciently
be calculated using the Berlekamp-Massey algorithm.
-
k-error Linear Complexity Test:
Test statistic is the
k
-error linear complexity
of the sequence that is the length of the shortest LFSR that generate the
sequence with at most
k
bit difference. In our experiments, we focused on
the
k
= 1 case, in which the test statistic takes values between 0 and
n/
2.
-
Maximum Order Complexity Test:
Test statistic is the maximum order com-
plexity of the sequence that is the length of the shortest feedback shift reg-
ister that generates the sequence, taking values between 0 and
n
1.
-
Lempel-Ziv Test:
Test statistic is the Lempel-Ziv complexity of the sequence
that takes its maximum value as
n/
2. For instance, Lempel-Ziv complexity
of the sequence 010101001001011 is 7, since different patterns observed are
0
−
|
1
|
01
|
010
|
0100
|
10
|
11.
3.1 Theoretical Results
In this section, to analyze the relation of two tests
T
1
and
T
1
, we present some
theoretical bounds on the maximum and minimum values of
t
1
as a function
of
t
2
.
Frequency versus Runs Test.
Given a sequence of length
n
and weight
w
,
the maximum possible number of runs
R
is
=
n
if
w
=
2
max
{
R
}
=
2
min
{
2
w
+1
,
2(
n
−
w
)+1
}
if
w
whereas the minimum number of runs
R
is
=
2if1
w<n
1
w
=0
or w
=
n
≤
min
{
R
}
.
