2
$\begingroup$

Pseudonoise LFSR sequences of length $N = 2^k-1$ have the nice property that their cyclical autocorrelation is $N$ when the sequence is lined up with itself, and $-1$ elsewhere.

Is there a way to construct sequences of other lengths, that their cyclical correlation is close to $0$ or $-1$ when not lined up? If not, why not?

  • 0
    Now that I know a little more about this, Barker sequences are for non-periodic autocorrelation, while Legendre and MLS sequences are for periodic autocorrelation. Gold and Kasami codes are derived from MLS, so are presumably periodic. [What can be used instead of a Barker sequence?](http://people.math.sfu.ca/~jed/Papers/Jedwab.%20Barker%20Sequence%20Alternatives.%202008.pdf) explains alternatives.2014-04-29

1 Answers 1

2

Are LFSR sequences sequences of $1$s and $-1$s? If so, then you can construct a sequence with the desired autocorrelation properties using the quadratic residues modulo a prime congruent to 3 (mod 4). For example, if $p=19$, then the quadratic residues (perfect squares) in the field are 0, 1, 4, 5, 6, 7, 9, 11, 16, 17. The sequence with $1$ in each of the listed positions and $-1$ in every other position has periodic autocorrelation $-1$ when the sequences are not lined up and autocorrelation 19 when they are lined up.

I believe that such sequences can also be constructed when the length is a product of twin primes. If this is the kind of thing you have in mind, I can try to dig up some references.

  • 0
    @endolith There is only one $0$, and that can be replaced with $\pm 1$ with only a small change in the periodic autocorrelation function. The out-of-phase autocorrelation value is constant, but might be $+1$ instead of $-1$. See Golomb's book.2014-04-20