Information Technology Reference
In-Depth Information
Projective de Bruijn Sequences
Yuki Ohtsuka
1
, Makoto Matsumoto
1
, and Mariko Hagita
2
1
Dept. of Math., Hiroshima University, Hiroshima 739-8526, Japan
m-mat@math.sci.hiroshima-u.ac.jp
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/eindex.html
2
Dept. of Info., Ochanomizu University, Tokyo 112-8610, Japan
Abstract.
Let
F
q
denote the
q
-element field. A
q
-ary de Bruijn sequence
of degree
m
is a cyclic sequence of elements of
F
q
, such that every ele-
ment in
F
q
m
appears exactly once as a consecutive
m
-tuple in the cyclic
sequence. We consider its projective analogue; namely, a cyclic sequence
such that every point in the projective space (
F
q
m
+1
−{
0
}
)
/
(
F
q
×
)ap-
pears exactly once as a consecutive (
m
+ 1)-tuple. We have an explicit
formula (
q
!)
q
m
−
1
q−
1
q
−m
for the number of distinct such sequences.
1
Introduction
Let
F
q
be the
q
-element field. Consider a cyclic sequence
C
=(
x
0
,x
1
,x
2
,...,
x
p
=
x
0
,x
p
+1
=
x
1
,...
)ofperiod
p
over
F
q
. For an integer
k
,the
k
-shadow of
C
is the multiset
C
[
k
]:=
{
(
x
i
,x
i
+1
,...,x
i
+
k−
1
)
|
i
=0
,
1
,
2
,...,p
−
1
}
of consecutive
k
-tuples in
C
for a full period. A cyclic sequence
C
is said to be a
q
-
ary de Bruijn sequence of degree
m
,if
C
[
m
] has no multiplicity and
C
[
m
]=
F
q
m
.
It follows that
p
=
q
m
. Such a sequence has interesting applications, for example
in the theory of shift-registers, see [2]. The number of the de Bruijn sequences
is known ([1] for the binary case, and [5] for the general case).
Theorem 1.
There exist
(
q
!)
q
m−
1
q
−m
distinct q-ary de Bruijn sequences of
degree m.
Through a study on the error-correcting sequence [3], we needed to introduce a
projectivised version of de Bruijn sequences. As usual, the (
m
1)-dimensional
projective space is defined as the set of non-zero vectors quotiented by the action
of scalar multiplication:
−
∈
F
q
m
P
(
q, m
−
1) :=
{
(
x
0
,x
1
,...,x
m−
1
)
\{
0
}}
/
∼
.
The class of (
x
0
,...,x
m−
1
) is denoted by [
x
0
:
···
:
x
m−
1
]. Thus, [
x
0
:
···
:
∈
F
q
×
such that
x
m−
1
]=[
y
0
:
···
:
y
m−
1
] if and only if there is a non-zero
λ
(
x
0
,...,x
m−
1
)=
λ
(
y
0
,...,y
m−
1
).
