Information Technology Reference
In-Depth Information
A projective de Bruijn sequence of degree
m
is a cyclic sequence of period
p
x
0
,x
1
,...,x
p−
1
,x
p
=
x
0
,...
such that the multiset of the consecutive
m
-tuples
{
[
x
i
:
···
:
x
i
+
m−
1
]
|
≤
i
≤
p
−
}
0
1
has no multiplicity and equals to the point set of
P
(
q, m
−
1). Accordingly,
p
=(
q
m
1) holds.
To state a relation to coding theory, recall that a
q
-ary [(
q
−
1)
/
(
q
−
1)
,
(
q
−
1)
/
(
q
−
−
1)
/
(
q
,
3] Hamming code is a linear code characterized by its parity check
matrix whose columns are all points in
P
(
q,
−
1)
−
−
1) (e.g. [6]).
Put
k
:= (
q
and
n
:= (
q
−
1)
/
(
q
−
1)
−
−
1)
/
(
q
−
1). Consider the following
linear recurrence
a
j
+
k
=
−
c
i
a
i
+
j
(
j
=0
,
1
,...,n
−
1)
(1)
0
≤i≤k−
1
with constant coecients
c
0
,c
1
,...c
k−
1
∈
F
q
.
The following easy theorem is proved in [3, Theorem 10].
Theorem 2.
The set of solutions of (1) is the q-ary
[
n, k,
3]
Hamming code if
and only if the sequence
(0
,
0
,...,
0
,c
0
,c
1
,...,c
k−
1
,
1)
of length (and period) n
is a projective de Bruijn sequence of degree .
In [3, Remark 13], we raised the problem of determining the number of projective
de Bruijn sequences. In this paper, we settle this problem:
Theorem 3.
Let m be a positive integer. The number of q-ary projective de
Bruijn sequences of degree m
+1
is
q
m
−
1
(
q
!)
q
−
1
.
q
m
Here, we identify such a sequence with its nonzero scalar multiples.
In the rest of this paper, we prove this theorem. The outline of the proof is:
(1) define projective de Bruijn graphs
PD
(
q, m
), whose Eulerian circuits are
equivalent to projective de Bruijn sequences of degree
m
+ 1, (2) to show that
the line digraph
L
(
PD
(
q, m
1)) is almost isomorphic to
PD
(
q, m
), (3) use the
formula for the number of Eulerian circuits for line digraphs [4].
−
2
Line Digraph
Definition 1.
Let D be a digraph, with vertex set V
(
D
)
and the arrow set A
(
D
)
.
Its line digraph L
(
D
)
has V
(
L
(
D
)) :=
A
(
D
)
, and two vertices v, w
V
(
L
(
D
))
has an arrow from v to w if and only if v is adjacent to w (with ordering con-
sidered) as arrows in D.
∈
Let
E
(
D
) denote the number of Eulerian circuits of
D
. The following lemma is
a direct consequence of [4, Theorem 2, Lemmas 4,5].
