Information Technology Reference
In-Depth Information
Galois setup.
x
7
x
6
x
5
x
4
x
3
x
2
x
1
x
0
x
7
x
6
x
5
x
4
x
3
x
2
x
1
x
0
Fibonacci setup.
Fig. 1.
Galois and Fibonacci LFSR
as we show in Figure 1. Both setups use the addition modulo 2. The Fibonacci
setup is characterized by
a multiple inputs and single output feedback function
,
while the Galois setup has
multiple feedback functions with a common input
.In
both setups, we denote by
x
0
the cell corresponding to the output of the LFSR.
The same sequence can be produced by an LFSR in Fibonacci or Galois setup
with the same characteristic polynomial but with different initializations. The
linear complexity
of a sequence
S
is defined as the size of the smallest LFSR
which is able to produce this sequence [17].
2.2 FCSRs
FCSRs were introduced by Klapper and Goresky in [6]. Instead of addition mod-
ulo 2, FCSRs use additions with carry, which means that they need additional
memory to store the carry. Their non-linear update function makes them par-
ticularly interesting for areas where linearity is an issue, like for instance stream
ciphers. The output of a binary FCSR corresponds to the 2-adic expansion of
the rational number:
h
q
≤
0
.
As for the LFSRs, there exists a Fibonacci and a Galois setup [7]. Their different
structures can be seen in Figure 2, where
represents the hamming weight of
the incoming bits, + an integer addition,
c
the additional memory for the carry,
and
an addition with carry of two bits where the carry is stored in
.The
Galois setup.
x
7
x
6
x
5
x
4
x
3
x
2
x
1
x
0
Fibonacci setup.
mod2
x
7
x
6
x
5
x
4
x
3
x
2
x
1
x
0
/
2
c
Fig. 2.
Galois and Fibonacci FCSR
