Efficient Generation of Elementary Sequences

David Gardner, Ana Salagean, Raphael C.-w. Phan

Abstract

Given an irreducible non-primitive polynomial g of degree n over \(\mathbb{F}_{2}[x]\) we aim to compute in parallel all the elementary sequences with minimal polynomial g (i.e. one sequence from each class of equivalence under cyclic shifts). Moreover, they need to each be in a suitable phase such that interleaving them will produce an m-sequence with linear complexity deg(g); this m-sequence is therefore produced at the rate of q = (2n − 1)/ord(g) bits per clock cycle. A naive method would use q LFSRs so our aim is to use considerably fewer. We explore two approaches: running a small number of Galois LFSRs with suitable seeds and using certain registers, possibly with a small amount of buffering; alternatively using only one (Galois or Fibonacci) LFSR and computing certain linear combinations of its registers. We ran experiments for all irreducible polynomials of degree n up to 14 and for each n we found that efficient methods exist for at least one m-sequence. A combination of the two approaches above is also described.
BibTeX
@inproceedings{gardner2013efficient,
  author = {David Gardner and Ana Salagean and Raphael C.-W. Phan},
  title = {{Efficient Generation of Elementary Sequences}},
  booktitle = {Imacc},
  year = {2013},
  doi = {10.1007/978-3-642-45239-0\_2},
}

Loading related content...

Figure