Not a member?

# Discussion Groups | Comp.DSP | autocorrelation negative values

There are 8 messages in this thread.

You are currently looking at messages 1 to .

Is this discussion worth a thumbs up?

0

# autocorrelation negative values - Thomas Magma - 2006-08-09 17:45:00

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?

Thomas

______________________________

# Re: autocorrelation negative values - robert bristow-johnson - 2006-08-09 18:32:00

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

______________________________

# Re: autocorrelation negative values - 2006-08-09 18:57:00

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?
>
> 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

______________________________

# Re: autocorrelation negative values - Thomas Magma - 2006-08-09 19:02:00

> 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
http://www.gpsworld.com/gpsworld/article/articleDetail.jsp?id1495&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

______________________________

# Re: autocorrelation negative values - Rune Allnor - 2006-08-10 02:25:00

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)

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

______________________________

# Re: autocorrelation negative values - 2006-08-10 12:17:00

"Thomas Magma" <s...@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

______________________________

# Re: autocorrelation negative values - Thomas Magma - 2006-08-10 17:46:00

"Dilip V. Sarwate" <s...@YouEyeYouSee.edu> wrote in message
news:ebfm7n\$eo8\$1...@news.ks.uiuc.edu...
>
> "Thomas Magma" <s...@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

______________________________

# Re: autocorrelation negative values - 2006-08-10 20:05:00

Thomas Magma wrote:
> "Dilip V. Sarwate" <s...@YouEyeYouSee.edu> wrote in message
> news:ebfm7n\$eo8\$1...@news.ks.uiuc.edu...
> >
> > "Thomas Magma" <s...@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55254675/ref=pd_bbs_1/002-7908748-5186450
?ie=UTF8

______________________________