Information Technology Reference
In-Depth Information
Theorem 3.
For al l
d, d
μ
d
+
μ
d
≥
μ
d
+
d
.
(12)
In particular,
2
μ
d
≥
μ
2
d
.
=
d
define a mapping from realizations of
d
+
d
to realizations of
d
and
d
as follows: for each
b
i
>b
i
+
d
+
d
,map(
i, i
+
d
+
d
)to(
i, i
+
d
)if
b
i
+
d
=0,
else map to (
i
+
d, i
+
d
+
d
). Clearly this map is injective.
If
d
=
d
then similarly every realization of 2
d
can be mapped to exactly one
realization of
d
, and no more than two realizations of 2
d
can map to the same
point.
Proof.
If
d
3.1 Lower Bounds for the Sliding Window Construction
To obtain lower bounds, we recall the following well-known [5] concept:
Definition 3.
A
(
v, k, λ
)
-
cyclic difference set
is a subset
D
⊂
Z
v
such that
#
D
=
k
and, for each
d
∈
Z
v
\{
0
}
, there are exactly
λ
pairs
a, b
∈
D
with
a
−
b
=
d.
1). In particular, if
k
=
v−
1
2
If such a set exists we must have
λ
(
v
−
1) =
k
(
k
−
,
k−
1
2
then for each
d
= 0 there are exactly
pairs
x, y
∈
D
with
x
−
y
=
d
mod
v
;
k
+1
2
y
=
d
mod
v
.Soif
b
is
a binary sequence of length
v
with
b
i
= 1 precisely when
i
pairs
x
∈
D, y
∈
D
with
x
−
thus there are exactly
∈
D
,wehave
k
+1
2
=
v
+1
4
μ
(
b
)
≥
.
(13)
We can have strict inequality in (13), because we may have
y
=
x
d<
0when
the indices are not taken modulo
v
, giving a realization of
d
even though
y
−
∈
D
.
. Clearly any translate of a
difference set is another difference set with the same parameters, but different
translates can give different values of
μ
(
b
). However, we have
μ
(
b
)
A
translate
of
D
is a set
D
+
t
=
{
a
+
t
|
a
∈
D
}
1+
v
+1
4
≤
1+
v
+
4
; the only way to get a non-cyclic realization of
d
=1isat
b
0
=1when
b
v−
1
= 1. Experimentation suggests the following
because
μ
1
≤
Conjecture 1.
for every difference set of size
v
, there exists a translate with
μ
(
b
)=1+
v
+1
4
.
Going in the other direction, a difference set always gives us a sequence
b
at-
taining
μ
(
b
)=
q
with length strictly less than 4
q
−
1; taking a translate with
b
v−t
=
b
v−t
+1
=
t
.
Cyclic difference sets do not take advantage of the edge effects inherent in
this problem, and they do not necessarily provide optimal solutions. It appears
to be possible to do somewhat better than
···
=
b
v−
1
= 0, let us truncate
b
to length
v
−
t
=4
q
−
1
−
v
+1
4
for all
v
(see Sect. 3.3), although
it also seems that the maximum
μ
(
b
)
/v
approaches
1
4
as
v
approaches infinity.
