Forums

autocorrelation negative values

Started by Thomas Magma August 9, 2006
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