Information Technology Reference
In-Depth Information
For balanced sequences, the number of runs takes values between 1 and
n
, but as
the weight of the sequence deviates from
n/
2, the maximum possible number of
runs decreases. Sequences with weight less than
n/
4, it is not possible to achieve
expected number of runs. Conversely, given the number of runs
R
,
w
≥
2
.
Frequency versus Random Walk Height Test.
Given a sequence of length
n
and weight
w
, the random walk height test statistic
H
attains the maximum
value as max
{
w, n
−
w
}
and minimum value
=
1
if
w
=
2
min
{
H
}
.
|
n
−
2
w
|
otherwise
Given
H
, the weight of the sequence is at least min
{
H, n
−
H
}
. From this prop-
erty, if a sequence fails random walk height test, it is very likely that it also fails
the frequency test. The relation is more significant for short sequences.
Frequency versus Longest Run of Ones.
Given a sequence of length
n
and
weight
w
, the longest run of ones test statistic
L
takes its maximum value as
w
and minimum value as
n−w−
1
.
w
Frequency versus Random Walk Excursion Test.
Given the weight
w
of
a
n
-bit sequence, the number of random walk excursion test statistic
E
takes its
maximum value as min
{w, n − w}
and minimum value as
=
1if
w
=
2
{
E
}
0otherwise
.
min
Runs versus Random Walk Excursion.
Both tests are related to the speed
of changes from 0 to 1 (or from 1 to 0). Sequences with large number of excursions
are expected to have large number of runs, similarly sequences with small number
of runs, are expected to have less number of excursions. Each excursion consists
of at least two runs, therefore number of runs is at least twice the number of
excursions.
Frequency versus Linear Complexity.
There is no direct relation between
the weight and the linear complexity of the sequence. Even with very low weight,
it is possible to achieve high linear complexity values. As an example, consider
the sequences with
w
= 1, location of the bit 1 determines the linear com-
plexity. There is however a strong relation between the weight of the Discrete
Fourier Transform of the sequence and its linear complexity, so-called Blahut's
theorem [12].
3.2 Experiments on Short Sequences
As an alternative definition of independence, tests
T
1
and
T
2
can be considered
independent, if their rejection regions are independent for all selection of
α
.In
