autocorrelation negative values

Hi,

If your data consists of ones and negative ones then you get negative values 
in your autocorrelation function, but if your data is ones and zeros you 
don't. In an autocorrelation plot you often see large negative values on 
either side of your correlation peak. Is this a good thing or bad thing? The 
reason I ask is because at first glance it appears to be a good thing, 
however now that I'm learning about low autocorrelation binary sequences 
(LABS) these large negative values are simply large peaks in the power 
spectrum that reduce the over all merit factor and this is a bad thing.

So to repeat my question, in your autocorrelation plot are large negative 
values on either side of your correlation peak a good or bad thing?

Thanks in advance,
Thomas

Thomas Magma wrote:
>
> If your data consists of ones and negative ones then you get negative values
> in your autocorrelation function, but if your data is ones and zeros you
> don't. In an autocorrelation plot you often see large negative values on
> either side of your correlation peak. Is this a good thing or bad thing? The
> reason I ask is because at first glance it appears to be a good thing,
> however now that I'm learning about low autocorrelation binary sequences
> (LABS) these large negative values are simply large peaks in the power
> spectrum that reduce the over all merit factor and this is a bad thing.
>
> So to repeat my question, in your autocorrelation plot are large negative
> values on either side of your correlation peak a good or bad thing?

you need to define what "good" and "bad" is.  and/or why your
definition of "good" is preferable and why "bad" is not preferable.

all's i got to say is that the Fourier Transform of the autocorrelation
of some L^2 function is the square of the magnitude of the Fourier
Transform of the L^2 function.  if there is no DC component in the
original function, there can be no DC component in the autocorrelation.

if there is no DC component of some function that is not identically
zero, then there has to be some "negative area" to balance the
"positive area".  the only way to get negative area is for the function
to be negative somewhere.  so the autocorrelation of some non-zero
signal without any DC (perhaps the output of a DC blocking filter)
*must* have some negative values in it and it won't be at the lag of
zero.

r b-j

Thomas Magma wrote:
> Hi,
>
> If your data consists of ones and negative ones then you get negative values
> in your autocorrelation function, but if your data is ones and zeros you
> don't. In an autocorrelation plot you often see large negative values on
> either side of your correlation peak. Is this a good thing or bad thing? The
> reason I ask is because at first glance it appears to be a good thing,
> however now that I'm learning about low autocorrelation binary sequences
> (LABS) these large negative values are simply large peaks in the power
> spectrum that reduce the over all merit factor and this is a bad thing.
>
> So to repeat my question, in your autocorrelation plot are large negative
> values on either side of your correlation peak a good or bad thing?
>
> Thanks in advance,
> Thomas

The negative sidelobes around the peak tell you that when you shift
your sequence by one bit, it is closer to its inverse that it is to
itself, or in other words the Hamming distance is large. That is a good
thing in the sense that it will take many bit errors to create the true
sequence from the one bit shifted sequence. The bad thing is a large
positive correlation at nonzero lag. 

John

> you need to define what "good" and "bad" is.  and/or why your
> definition of "good" is preferable and why "bad" is not preferable.
>

I guess by good I mean the use of 'very early' and 'very late' correlators 
like what is used in Galileo navigation receivers:
http://www.gpsworld.com/gpsworld/article/articleDetail.jsp?id=121495&pageID=5

And bad would be like I explained before, that large negative values are 
simply large peak side lobes in the power spectrum and reduce the over all 
merit factor when considering low autocorrelation binary sequences.

Thomas 

Thomas Magma wrote:
> Hi,
>
> If your data consists of ones and negative ones then you get negative values
> in your autocorrelation function, but if your data is ones and zeros you
> don't. In an autocorrelation plot you often see large negative values on
> either side of your correlation peak.

Yes, you do. Try to compute the autocorrelation of f(t) = cos(t) for
shifts tau = [-4pi,...,4pi] and see what happens for tau = (2n-1)pi
where n is any integer.

> Is this a good thing or bad thing?

It's a good thing, since it means that the maths works.

> The
> reason I ask is because at first glance it appears to be a good thing,
> however now that I'm learning about low autocorrelation binary sequences
> (LABS) these large negative values are simply large peaks in the power
> spectrum that reduce the over all merit factor and this is a bad thing.

I can't see what the sign has to do with this? As you know,

-1 = exp(j(2n-1)pi)

which means that the negative sign in time domain translates to
a phase term in frequency domain. Which, in turn, means that you
are not so much concerned with *negative* correlations as with
*large* (magnitude) correlations. Which might have been expected
by contemplating the "L" in the LABS acronyme above.

> So to repeat my question, in your autocorrelation plot are large negative
> values on either side of your correlation peak a good or bad thing?

Find out what causes the problem: "Large" or "negative".

Rune

"Thomas Magma" <somewhere@overtherainbow.com> asked in message 
news:aIsCg.359093$Mn5.139126@pd7tw3no...

> So to repeat my question, in your autocorrelation plot are large negative 
> values on either side of your correlation peak a good or bad thing?

Although we talk of autocorrelation, what a receiver actually
computes is a crosscorrelation: the crosscorrelation between
the incoming signal x and a stored replica y.  Of course, the
stored replica is supposed to be the incoming signal itself
(that is, x should be a lagged version of the stored replica y),
giving rise to the autocorrelation....

But now, suppose that because of a phase shift or a phase
ambiguity, the signal input to the correlator is -x instead of
x, while the local input is y.  Then, the large negative value
of the autocorrelation function will appear as a large
positive value that might be mistaken for the peak that is
known to occur at 0 lag.  For this reason, large negative
values of the autocorrelation function are generally frowned
upon, and people strive to search for sequences and signals
for which the maximum off-peak autocorrelation *magnitude*
is small.

A contrarian viewpoint holds that a sideloby autocorrelation
function is better than a flat (thumbtack) autocorrelation
function because by measuring the sidelobes, one might be
able to make a good estimate of the lag, and thus quickly
converge to a 0 lag.  With a thumbtack autocorrelation
function, a low autocorrelation value simply tells us that the
lag is not 0 and we need to try again with a different lag
without any clues as to what the lag might be.

Just my two cents worth to confuse the issue further....

--Dilip Sarwate 

"Dilip V. Sarwate" <sarwate@YouEyeYouSee.edu> wrote in message 
news:ebfm7n$eo8$1@news.ks.uiuc.edu...
>
> "Thomas Magma" <somewhere@overtherainbow.com> asked in message 
> news:aIsCg.359093$Mn5.139126@pd7tw3no...
>
>> So to repeat my question, in your autocorrelation plot are large negative 
>> values on either side of your correlation peak a good or bad thing?
>
> Although we talk of autocorrelation, what a receiver actually
> computes is a crosscorrelation: the crosscorrelation between
> the incoming signal x and a stored replica y.  Of course, the
> stored replica is supposed to be the incoming signal itself
> (that is, x should be a lagged version of the stored replica y),
> giving rise to the autocorrelation....
>
> But now, suppose that because of a phase shift or a phase
> ambiguity, the signal input to the correlator is -x instead of
> x, while the local input is y.  Then, the large negative value
> of the autocorrelation function will appear as a large
> positive value that might be mistaken for the peak that is
> known to occur at 0 lag.  For this reason, large negative
> values of the autocorrelation function are generally frowned
> upon, and people strive to search for sequences and signals
> for which the maximum off-peak autocorrelation *magnitude*
> is small.
>
> A contrarian viewpoint holds that a sideloby autocorrelation
> function is better than a flat (thumbtack) autocorrelation
> function because by measuring the sidelobes, one might be
> able to make a good estimate of the lag, and thus quickly
> converge to a 0 lag.  With a thumbtack autocorrelation
> function, a low autocorrelation value simply tells us that the
> lag is not 0 and we need to try again with a different lag
> without any clues as to what the lag might be.
>
> Just my two cents worth to confuse the issue further....
>
> --Dilip Sarwate


On the contrary Dilip, you make perfect sense to me.

So you are saying that it really boils down to trade offs and pros and cons 
(like everything else in DSP). And the binary sequence should be engineered 
for the specific system. That is understandable. You mentioned a few of the 
pros and cons of certain autocorrelation functions, do you know of a good 
book that really breaks it down? If the processing time it takes to 0 lag is 
not a major concern, and if I am more concerned with coding gain and 
TOA(time of arrival), should I go with (as you put it) the thumbtack?

Thomas

Thomas Magma wrote:
> "Dilip V. Sarwate" <sarwate@YouEyeYouSee.edu> wrote in message
> news:ebfm7n$eo8$1@news.ks.uiuc.edu...
> >
> > "Thomas Magma" <somewhere@overtherainbow.com> asked in message
> > news:aIsCg.359093$Mn5.139126@pd7tw3no...
> >
> >> So to repeat my question, in your autocorrelation plot are large negative
> >> values on either side of your correlation peak a good or bad thing?
> >
> > Although we talk of autocorrelation, what a receiver actually
> > computes is a crosscorrelation: the crosscorrelation between
> > the incoming signal x and a stored replica y.  Of course, the
> > stored replica is supposed to be the incoming signal itself
> > (that is, x should be a lagged version of the stored replica y),
> > giving rise to the autocorrelation....
> >
> > But now, suppose that because of a phase shift or a phase
> > ambiguity, the signal input to the correlator is -x instead of
> > x, while the local input is y.  Then, the large negative value
> > of the autocorrelation function will appear as a large
> > positive value that might be mistaken for the peak that is
> > known to occur at 0 lag.  For this reason, large negative
> > values of the autocorrelation function are generally frowned
> > upon, and people strive to search for sequences and signals
> > for which the maximum off-peak autocorrelation *magnitude*
> > is small.
> >
> > A contrarian viewpoint holds that a sideloby autocorrelation
> > function is better than a flat (thumbtack) autocorrelation
> > function because by measuring the sidelobes, one might be
> > able to make a good estimate of the lag, and thus quickly
> > converge to a 0 lag.  With a thumbtack autocorrelation
> > function, a low autocorrelation value simply tells us that the
> > lag is not 0 and we need to try again with a different lag
> > without any clues as to what the lag might be.
> >
> > Just my two cents worth to confuse the issue further....
> >
> > --Dilip Sarwate
>
>
> On the contrary Dilip, you make perfect sense to me.
>
> So you are saying that it really boils down to trade offs and pros and cons
> (like everything else in DSP). And the binary sequence should be engineered
> for the specific system. That is understandable. You mentioned a few of the
> pros and cons of certain autocorrelation functions, do you know of a good
> book that really breaks it down? If the processing time it takes to 0 lag is
> not a major concern, and if I am more concerned with coding gain and
> TOA(time of arrival), should I go with (as you put it) the thumbtack?
>
> Thomas

http://www.amazon.com/gp/product/0521821045/sr=8-1/qid=1155254675/ref=pd_bbs_1/002-7908748-5186450?ie=UTF8