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
    hmm, looks like there's a lot of research on this: http://signalslab.marstu.net/?page_id=17692012-04-05
  • 0
    Look for _Legendre sequences_ among others.2012-04-05
  • 0
    You're referring to Maximum Length Sequence (MLS), right? Truly random white noise has similar properties, I think any spectrally-white signal does, so maybe multitone signals would be appropriate? https://gist.github.com/endolith/53227342014-04-18
  • 0
    "The most commonly used sequences in direct-sequence spread spectrum systems are maximal length sequences, Gold codes, Kasami codes, and Barker codes." https://en.wikipedia.org/wiki/Pseudorandom_noise2014-04-18
  • 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.

  • 1
    These sequences are called _Legendre sequences_ in the literature (cf. Golomb's 1967 book _Shift Register Sequences).2014-04-19
  • 0
    These are noise-like, and are not just 1s and -1s, there are 0s also.2014-04-19
  • 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