Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
hmm, looks like there's a lot of research on this: – Jason S Apr 5 '12 at 18:52
Look for Legendre sequences among others. – Dilip Sarwate Apr 5 '12 at 21:19
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? – endolith Apr 18 '14 at 20:28
"The most commonly used sequences in direct-sequence spread spectrum systems are maximal length sequences, Gold codes, Kasami codes, and Barker codes." – endolith Apr 18 '14 at 21:53
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? explains alternatives. – endolith Apr 29 '14 at 23:16

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.

share|cite|improve this answer
These sequences are called Legendre sequences in the literature (cf. Golomb's 1967 book _Shift Register Sequences). – Dilip Sarwate Apr 19 '14 at 13:22
These are noise-like, and are not just 1s and -1s, there are 0s also. – endolith Apr 19 '14 at 19:59
@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. – Dilip Sarwate Apr 20 '14 at 14:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.