Information Technology Reference
In-Depth Information
It is infinite if there is no such generator. Often there is another closely re-
lated measure that is defined algebraically and is much easier to work with.
We typically call this related measure the
-complexity
.Itmaybebasedon
a function defined on some related algebraic structure and satisfy properties
such as
f
(
ab
)=
f
(
a
)+
f
(
b
)or
f
(
a
+
b
)
F
≤
max(
f
(
a
)
,f
(
b
)) +
c
for some con-
stant
c
. In the case when
F
is the set of
linear feedback shift registers
(LFSRs)
the
-span is called the
linear span
. The size of an LFSR with connection
polynomial
q
(
x
) is simply the number of cells it contains. If the generating
function of the output sequence is
u
(
x
)
/q
(
x
), then the
linear complexity
is
max(deg(
q
)
,
deg(
u
) + 1) and equals the linear span. In the case of
feedback with
carry shift registers
(FCSRs) with output alphabet
F
{
0
,
1
,
···
,N
−
1
}
,
N
∈
Z
[5], the
-span is called the
N
-adic span
. The integer values of the carry are
encoded by their base
N
expansions. Thus the size of an FCSR with connection
integer
q
is the number of cells in the basic register plus the ceiling of the log
base
N
of the maximum absolute value of the carry over its infinite execution.
If the output sequence has associated
N
-adic number
α
=
u/q
, then the related
N
-adic complexity
is log
N
(max(
F
|
u
|
,
|
q
|
)) and differs from the
N
-adic span by
O
(log(the
N
-adic span)) [5].
More generally we may consider
algebraic feedback shift registers
(AFSRs)
with respect to some particular algebraic ring
R
and parameter
π
.The
F
-span
associated with the class
of AFSRs based on
R
and
π
is called the
π
-adic
span
. However, we know of no algebraic definition of a “
π
-adic complexity” that
makes sense for all (over even many) classes of AFSRs. AFSRs include both
LFSRs (
R
=
F
[
x
]with
F
afield,
π
=
x
) and FCSRs (
R
=
Z
,
π
F
≥
2) [6].
In more detail, let
R
be a commutative ring and
π
∈
R
. Assume that
R/
(
q
)is
finite for every nonzero
q
R
. We consider sequences over the ring
R/
(
π
), whose
cardinality we denote by
p
.Wealsolet
S
∈
R
be a complete set of representatives
for
R/
(
π
). We identify sequences over
R/
(
π
) with sequences over
S
.AnAFSR
based on
R
,
π
,and
S
is a stated device
D
with output. It is determined by
constants
q
0
,
⊆
R
with the image of
q
0
in
R/
(
π
) invertible. Its state is an
(
r
+1)-tuple
σ
=(
a
0
,a
1
,
···
,q
r
∈
···
,a
r−
1
;
m
)where
a
i
∈
S
,
i
=0
,
···
,r
−
1, and
m
∈
R
.
,a
r
;
m
)where
From this state the AFSR outputs
a
0
and changes state to (
a
1
,
···
a
r
∈
S
and
r
q
0
a
r
+
πm
=
m
+
q
i
a
r−i
.
i
=1
By repeating the state change operation, the AFSR generates an infinite se-
quence, denoted by
D
(
σ
). We refer to
D
(
σ
) as the sequence generated by
D
with initial state
σ
. In this paper we are concerned with average behavior of
the
-span is
commonly referred to as the
π
-span. See [6] for more details on AFSRs and their
analysis by
π
-adic numbers.
The element
F
-span where
F
is the class of AFSRs based on
R
,
π
,
S
.The
F
r
q
(
D
)
=
q
=
q
i
π
i
−
q
0
(1)
i
=1
