Information Technology Reference
In-Depth Information
Parallel Generation of
-Sequences
Cedric Lauradoux
1
and Andrea Rock
2
1
Princeton University, Department of electrical engineering
Princeton, NJ 08544, USA
claurado@princeton.edu
2
Team SECRET, INRIA Paris-Rocquencourt,
78153 Le Chesnay Cedex, France
andrea.roeck@inria.fr
Abstract.
The generation of pseudo-random sequences at a high rate is
an important issue in modern communication schemes. The representa-
tion of a sequence can be scaled by decimation to obtain parallelism and
more precisely a sub-sequences generator. Sub-sequences generators and
therefore decimation have been extensively used in the past for linear
feedback shift registers (LFSRs). However, the case of automata with a
non linear feedback is still in suspend. In this paper, we have studied
how to transform of a feedback with carry shit register (FCSR) into a
sub-sequences generator. We examine two solutions for this transforma-
tion, one based on the decimation properties of
-sequences,
i.e.
FCSR
sequences with maximal period, and the other one based on multiple
steps implementation. We show that the solution based on the decima-
tion properties leads to much more costly results than in the case of
LFSRs. For the multiple steps implementation, we show how the propa-
gation of carries affects the design.
Keywords:
sequences,
synthesis,
decimation,
parallelism,
LFSRs,
FCSRs.
1
Introduction
The synthesis of shift registers consists in finding the smallest automaton able
to generate a given sequence. This problem has many applications in cryptog-
raphy, sequences and electronics. The synthesis of a single sequence with the
smallest linear feedback shift register is achieved by the Berlekamp-Massey [1]
algorithm. There exists also an equivalent of Berlekamp-Massey in the case of
multiple sequences [2,3]. In the case of FCSRs, we can use algorithms based on
lattice approximation [4] or on Euclid's algorithm [5]. This paper addresses the
following issue in the synthesis of shift registers:
given an automaton generating
asequence
S
, how to find an automaton which generates in parallel the sub-
sequences associated to
S
. Throughout this paper, we will refer to this problem
as
the sub-sequences generator problem
. We aim to find the best solution to trans-
form a 1-bit output pseudo-random generator into a multiple outputs generator.
In particular, we investigate this problem when
S
is generated by a feedback
