Forums

spreading code with low autocorrelation

Started by Thomas Magma August 20, 2007
Hello,

I'm looking for a spreading code that I can output from a microcontroller 
(PIC). The sequence must have low autocorrelation with a good merit factor. 
It should be a long sequence of between 4000 and 20000 and does not have to 
be done with a LFSR (shift register) since I have lots of code space left 
and I can just hard code it into memory. Therefore it does not have to be a 
2^N value.

My first question is fundamental...does a low autocorrelation sequence give 
you a flat-ish power spectral density? Or are some sequences better for 
spreading while others are better for correlation?

My second question is, does anyone know of an online resource of large 
sequences with good merit factors? (I found one awhile back, but can't seem 
to find it now)

Thanks,
Thomas 



Thomas Magma wrote:

> Hello, >=20 > I'm looking for a spreading code that I can output from a microcontroll=
er=20
> (PIC). The sequence must have low autocorrelation with a good merit fac=
tor.=20
> It should be a long sequence of between 4000 and 20000 and does not hav=
e to=20
> be done with a LFSR (shift register) since I have lots of code space le=
ft=20
> and I can just hard code it into memory. Therefore it does not have to =
be a=20
> 2^N value.
If the goal is having a good ACF, you can take pretty much any random or = quasi-random sequence. Some sequences could have better ACF then the=20 others however there is not going to be much of a difference if the=20 sequences are that long. There could be many other application dependent considerations for the=20 sequence design, too.
> My first question is fundamental...does a low autocorrelation sequence =
give=20
> you a flat-ish power spectral density?
Fundamental answer: yes.
> Or are some sequences better for=20 > spreading while others are better for correlation?
It depends. Better for what application?
> My second question is, does anyone know of an online resource of large =
> sequences with good merit factors?
online =3D=3D bullshit
> (I found one awhile back, but can't seem=20 > to find it now)
P. Fan, M. Darnell. =93Sequence design for communications applications=94= John Wiley & Sons ISBN 0-471-96557 Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
On Aug 20, 1:25 pm, "Thomas Magma" <somewh...@overtherainbow.com>
wrote:
> Hello, > > I'm looking for a spreading code that I can output from a microcontroller > (PIC). The sequence must have low autocorrelation with a good merit factor. > It should be a long sequence of between 4000 and 20000 and does not have to > be done with a LFSR (shift register) since I have lots of code space left > and I can just hard code it into memory. Therefore it does not have to be a > 2^N value. > > My first question is fundamental...does a low autocorrelation sequence give > you a flat-ish power spectral density? Or are some sequences better for > spreading while others are better for correlation?
By the Fourier transform properties, things that are narrow in one domain is spread out in the other. That said, you can explicitly search for sequences to optimize their autocorrelation properties.
> > My second question is, does anyone know of an online resource of large > sequences with good merit factors? (I found one awhile back, but can't seem > to find it now)
Try searching for "Barker sequences".
> > Thanks, > Thomas
> > Try searching for "Barker sequences". >
The longest known Barker Code has a length of 13, I need lengths three of four magnitudes greater than that. Thomas
On Aug 21, 6:15 pm, "Thomas Magma" <somewh...@overtherainbow.com>
wrote:
> > Try searching for "Barker sequences". > > The longest known Barker Code has a length of 13, I need lengths three of > four magnitudes greater than that. > > Thomas
So do a search for other sequences. Barker sequences are defined by its optimality. There is debate about whether a Barker sequence exists for really large lengths, so you know your limits! This is a problem that only has to be done once, so it's worth keeping your computer humming for a while, depending on your constraints. Julius
> This is a problem that only has to be done once, so it's worth > keeping your computer humming for a while, depending on > your constraints. >
I think it might blow the budget of my project if I were to rent a super computer to run for 5 or 10 years to do what you suggested. However if I did discover a large Barker sequence, I would probably forget about my project and sprint down to the closest patent office. How long would it take your computer to iterate through all the possible combinations of 2^65536 determining the merit factor of each? Thomas
On Aug 20, 1:25 pm, "Thomas Magma" <somewh...@overtherainbow.com>
wrote:
> Hello, > > I'm looking for a spreading code that I can output from a microcontroller > (PIC). The sequence must have low autocorrelation with a good merit facto=
r=2E
> It should be a long sequence of between 4000 and 20000 and does not have =
to
> be done with a LFSR (shift register) since I have lots of code space left > and I can just hard code it into memory. Therefore it does not have to be=
a
> 2^N value. > ............... >=2E.................. > My second question is, does anyone know of an online resource of large > sequences with good merit factors? (I found one awhile back, but can't se=
em
> to find it now)
A Legendre sequence rotated by one-fourth of the period has a merit factor of about 6 (asymptotically). This is about the best result known for specifically constructible sequences, though there has been some work on adding a few bits at the end of the Legendre sequence (like a cyclic extension in other contexts) to improve the merit factor to somewhat more than 6. T=2E H=F8holdt and H.E. Jensen. Determination of the merit factor of Legendre sequences. IEEE Trans. Inform. Theory, 34:161-164, 1988. J=2E Jedwab. A survey of the merit factor problem for binary sequences. In T. Helleseth et al., editors, Sequences and Their Applications - Proceedings of SETA 2004, vol- ume 3486 of Lecture Notes in Computer Science, pages 30-55. Springer- Verlag, Berlin Heidelberg, 2005. Hope this helps.