Information Technology Reference
In-Depth Information
1-decimation
x
7
x
6
x
5
x
4
x
3
x
2
x
1
x
0
S
full adder with
reentering carry
sub-shift register 1
sub-shift register 2
carry path
2-decimation
x
7
x
5
x
3
x
1
S
2
2
x
6
x
4
x
2
x
0
S
2-bit ripple carry adder
with reentering carry
Fig. 7.
Multiple steps generator for a Galois FCSR
⎧
⎨
(
x
0
)
t
+
d−m
+
i
⊕
m−
2
−i
a
i
+
k
[(
x
0
)
t
+
d−k−
1
⊕
(
c
i
+
k
)
t
+
d−k−
1
]
if
m
k
=0
−
d
≤
i<m
(
x
i
)
t
+
d
=
(10)
(
x
i
+
d
)
t
⊕
d−
1
⎩
k
=0
a
i
+
k
[(
x
0
)
t
+
d−k−
1
⊕
(
c
i
+
k
)
t
+
d−k−
1
]
if
i<m
−
d
(
c
i
)
t
+
d
=[(
x
0
)
t
+
d−
1
⊕
(
x
i
+1
)
t
+
d−
1
][(
x
0
)
t
+
d−
1
⊕
(
c
i
)
t
+
d−
1
]
⊕
(
x
0
)
t
+
d−
1
(11)
The Equation 11 shows the dependencies between the carries which corresponds
to the propagation of the carry in a ripple carry adder. The Equation 10 corre-
sponds to the path of the content of a memory cell (
x
i
)
t
through the different
levels of the ripple carry adders.
Comparison
The construction using FCSR synthesis is more complicated than in
the case of LFSRs. The size of the minimal generator producing
S
d
can depend on
i
, and we can only give upper bounds for
q
namely that
q
2
T
|
−
1 in the general
case and that
q
2
T/
2
+1ifgcd(
d, T
) = 1. Based on Conjecture 1, we saw that
q
>q
if gcd(
T,d
) = 1. Moreover, in the case
p
=2
p
+1with
p
and
q
prime, the
resulting sub-sequences generator is always larger than the original one.
Apart from the carry path and the cost of the addition with carry, the com-
plexity of a multiple steps implementation of a FCSR is very similar to the
multiple steps implementation of an LFSR. There is no overhead in memory
and the number of logic gates for a Galois FCSR is 5
d
|
wt
(
q
)where
wt
(
q
)isthe
number of ones in the binary representation of
q
and the number 5 corresponds
to the five gates required for a full-adder (four Xors and one And
cf.
Equation 8).
In the case of Fibonacci setup, the number of logic gates is given by:
×
d
×
(5
×
(
wt
(
q
)
−
log
2
(
wt
(
q
)+1)
)+
+2
×
(
log
2
(
wt
(
q
)+1)
−
wt
(
wt
(
q
)) + 5
×
size
(
c
))
with (5
wt
(
wt
(
q
))) the
cost of the implementation of a parallel bit counter [24],
i.e.
the
h
function (
cf.
×
(
wt
(
q
)
−
log
2
(
wt
(
q
)+1)
)+2
×
(
log
2
(
wt
(
q
)+1)
−
