Information Technology Reference
In-Depth Information
the sequences generated by LFSRs are exactly the eventually periodic sequences.
Thus they make up a countable subset of the uncountable set of all sequences
over
S
. The same is true of the sequences generated by FCSRs. However, some
AFSRs generate sequences that are not eventually periodic. This implies that
the memory is unbounded over an infinite execution of the AFSR, so the
π
-adic
span is infinite. However, it is known that if
R
is an integral domain whose field
of fractions is a number field, and for every embedding of
R
in the complex
numbers, the complex norm of
π
is greater than 1, then the memory of every
AFSR is bounded over every infinite execution [6]. When this happens, the
sequences for which
π
-adic span is defined are exactly the eventually periodic
sequences. This is the case for all rings studied in this paper.
Our goal in this paper is to find the average
π
-adic span of sequences with
fixed period
n
. A sequence has period
n
if and only if it has
π
n
−
1 as a connection
element. Several of the proofs are omitted for lack of space.
From here on we assume that
R
=
[
π
], with
π
d
=
p
,
p>
0and
x
d
Z
−
p
irreducible over
Z
.Wetake
S
=
. Our goal is to find the
expected
π
-adic complexity of sequences over
S
with fixed period
n
.Wehave
R
=
{
0
,
1
,
···
,p
−
1
}
{
d−
1
i
=0
b
i
π
i
:
b
i
∈
Z
}
=
p
. AFSRs over such a ring are called
d
-FCSRs, and many of their properties have been studied [2,3,4,7,14]. Note that
there are register synthesis algorithms for AFSRs over these rings and the output
from such AFSRs is eventually periodic.
and
|
R/
(
π
)
|
2 Size Measure and Algebraic Preliminaries
We define the size function
λ
d−
1
b
i
π
i
=max(
d
log
p
|
b
i
|
+
i
)
.
i
=0
This is the same size function that was used to establish the existence of a
rational approximation algorithm for
d
-FCSRs [14].
Theorem 1.
Let
c
1
=
d
log
p
(2)
,
c
2
=
d
log
p
(
d
)
,and
c
3
=
d
.Then
S1: For all
a, b
∈
R
, we have
λ
(
a
±
b
)
≤
max(
λ
(
a
)
,λ
(
b
)) +
c
1
;
S2: For all
a, b
∈
R
, we have
λ
(
ab
)
≤
λ
(
a
)+
λ
(
b
)+
c
2
;
S3: For all
a
∈
R
, we have
λ
(
πa
)=1+
λ
(
a
)
;
=0
, we have
λ
r−
1
i
=0
a
i
π
i
r
≤
S4: For all
a
0
,
···
,a
r−
1
∈
S
with
a
r−
1
−
c
3
;
S5: For any real number
x
, there are finitely many elements
a
∈
R
with
λ
(
a
)
≤
x
;
S6: For any
a
1
,
···
,a
r
∈
R
,
λ
(
a
1
±···±
a
r
)
≤
max
{
λ
(
a
i
)
,i
=1
,
···
,r
}
+
c
1
log
2
(
r
)
.
We make use of the algebraic norm function
N
:
R
→
Z
, defined by
d−
1
b
i
ζ
ij
π
i
,
d−
1
d−
1
b
i
π
i
)=
N
(
i
=0
j
=0
i
=0
