FPGA Central

I have a unique problem where I need to predict the "peakedness" of th
time domain signal just by looking at the frequency transform of th
signal.
Let us call this as y1[n]<--> Y1[f]

I.e, I have Y1[f] and would like to have an indicator on how sharp a pea
is there in y1[n](closer to a delta is better).
I cannot afford to do a IFFT. The reason being I need to do this operatio
on many of these Y[f]'s, name Y1[f], Y2[f], Y3[f], etc. etc.

What I need to do is is to make a good estimation of how peaky the y1[t]
y2[t] ...etc are, and choose the one that is the "most" peaky, i.e, has
dominant peak!

So, is there any way by which the frequency domain info can help u
estimate the time domain peak sharpness without doing IFFT?
Note that I dont really need to know where the peak is..
I may or may not have multiple peaks in y[n]'s, but all I care is
"dominant" peak in the time domain signal.

Ksen wrote:
....
> What I need to do is is to make a good estimation of how peaky the y1[t],
> y2[t] ...etc are, and choose the one that is the "most" peaky, i.e, has a
> dominant peak!

You have to exactly define what you mean. Given two vectors y1 and y2,
how exactly do you determine which one is "more peaky" than the other
(in time domain)? Once you have described your procedure in time
domain, there might be something similar in the frequency domain.

For example: y1 = [ 0 1 -1 0 ] and y2 = [0 1 3 0]. Which one is "more
peaky"?

>
>Ksen wrote:
>...
>> What I need to do is is to make a good estimation of how peaky th
y1[t],
>> y2[t] ...etc are, and choose the one that is the "most" peaky, i.e, ha
a
>> dominant peak!
>
>You have to exactly define what you mean. Given two vectors y1 and y2,
>how exactly do you determine which one is "more peaky" than the other
>(in time domain)? Once you have described your procedure in time
>domain, there might be something similar in the frequency domain.
>
>For example: y1 = [ 0 1 -1 0 ] and y2 = [0 1 3 0]. Which one is "more
>peaky"?
>
>


I would say y2 is more peaky.
In general, the problem I am solving is a matching problem of a quer
signal, vs. say, 10 template signals.

y1, y2,y3.....y10 are outputs of matching the query signal with templat
1, template 2, etc., respectively. All my operations are however in th
frequency domain, Y1, Y2,...Y10.

Only one of them in time domain (1 thru 10) will have a sharp peak, al
others will look like noise (garbage). I have no "time" to do 10 IFFTs, a
this will work on a very very low end platform. Would rather look a
Y1[f]...Y10[f} and make a judgement on which one will be most peaky whil
I do an IFFT.. I dont care where the peak is!!!

Ksen wrote:

> I have a unique problem where I need to predict the "peakedness" of the
> time domain signal just by looking at the frequency transform of the
> signal.

In the general case, there is no way to estimate the time domain
peakedness from the spectrum. You will have to do the IFT or solve the
system of equations for max x(t). May be your signal has some special
properties which you can use to find the peaks.

Vladimir Vassilevsky

DSP and Mixed Signal Design Consultant

http://www.abvolt.com

> y1, y2,y3.....y10 are outputs of matching the query signal with template
> 1, template 2, etc., respectively. All my operations are however in the
> frequency domain, Y1, Y2,...Y10.
>
> Only one of them in time domain (1 thru 10) will have a sharp peak, all
> others will look like noise (garbage). I have no "time" to do 10 IFFTs, as
> this will work on a very very low end platform. Would rather look at
> Y1[f]...Y10[f} and make a judgement on which one will be most peaky while
> I do an IFFT.. I dont care where the peak is!!!

Seems like you want to do a cross-corelation.

So you can just multiply the FFT of your signals with your template and
pick the one with the biggest magnitude.

Ksen wrote:
>> Ksen wrote:
>> ...
>>> What I need to do is is to make a good estimation of how peaky the
> y1[t],
>>> y2[t] ...etc are, and choose the one that is the "most" peaky, i.e, has
> a
>>> dominant peak!
>> You have to exactly define what you mean. Given two vectors y1 and y2,
>> how exactly do you determine which one is "more peaky" than the other
>> (in time domain)? Once you have described your procedure in time
>> domain, there might be something similar in the frequency domain.
>>
>> For example: y1 = [ 0 1 -1 0 ] and y2 = [0 1 3 0]. Which one is "more
>> peaky"?
>>
>>
>
>
> I would say y2 is more peaky.
> In general, the problem I am solving is a matching problem of a query
> signal, vs. say, 10 template signals.
>
> y1, y2,y3.....y10 are outputs of matching the query signal with template
> 1, template 2, etc., respectively. All my operations are however in the
> frequency domain, Y1, Y2,...Y10.
>
> Only one of them in time domain (1 thru 10) will have a sharp peak, all
> others will look like noise (garbage). I have no "time" to do 10 IFFTs, as
> this will work on a very very low end platform. Would rather look at
> Y1[f]...Y10[f} and make a judgement on which one will be most peaky while
> I do an IFFT.. I dont care where the peak is!!!

The only difference between the spectra of uniformly distributed noise
and a single sharp impulse lies in the phases. The amplitudes of the
frequency components are the same. Figuring out what the phases tell you
is as much work as an IFFT.

Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Jerry Avins wrote:
> Ksen wrote:

(snip)

>>> You have to exactly define what you mean. Given two vectors y1 and y2,
>>> how exactly do you determine which one is "more peaky" than the other
>>> (in time domain)? Once you have described your procedure in time
>>> domain, there might be something similar in the frequency domain.

>>> For example: y1 = [ 0 1 -1 0 ] and y2 = [0 1 3 0]. Which one is "more
>>> peaky"?

>> I would say y2 is more peaky. In general, the problem I am solving is
>> a matching problem of a query
>> signal, vs. say, 10 template signals.

How about the absolute value or square of the second derivative
(or second difference for discrete data) as a peakiness measure?
Then you either want the maximum or mean over the whole signal.

(snip)

> The only difference between the spectra of uniformly distributed noise
> and a single sharp impulse lies in the phases. The amplitudes of the
> frequency components are the same. Figuring out what the phases tell you
> is as much work as an IFFT.

This is what I thought, too. Though given that he doesn't need to
know where the peaks are there might be some small simplifications.

For a not-so-obvious example, there is an O(n) algorithm for median,
though the usual implementation would be an O(n log n) sort.
I don't know at what n value the O(n) value is faster, but it
might be large.

So, say one wants to compute the second difference of the IFFT,
is there anything that can be done besides computing the whole IFFT
and then applying the second difference?

-- glen

I think glen shows avery good example of median, where a "supposedl
mistaken" O(nlogn) operation is actually O(n).

My initial question was very similar...
Can the FT of a signal tell anything about its time domain peakedness..

Actually, in the limiting case, where x[n] = d[n-n0],
then you can do the math and see |X(f)| = 1, and Phase(X(f)) = straigh
line, passing thru the origin.

Now, given a bunch of readings of Phase(X(f)) one can fit a line (or
plane, in 2d case) and verify how "off" the readings are from a bes
fitted plane.

However, the real world will have many side-spikes...

BTW, fitting a plane is O(n), and certainly is not as much work a
O(nlogn).

Infact, one does not need to fit a plane, all we are interested is what i
the dispersion of the data from the best plane out there (hence all we car
is minimizing an error metric!!).

Would be interesing to see the application of this in real world...

>For a not-so-obvious example, there is an O(n) algorithm for median,
>though the usual implementation would be an O(n log n) sort.
>I don't know at what n value the O(n) value is faster, but it
>might be large.
>
>So, say one wants to compute the second difference of the IFFT,
>is there anything that can be done besides computing the whole IFFT
>and then applying the second difference?
>
>-- glen
>
>

glen herrmannsfeldt wrote:
> Jerry Avins wrote:
> > Ksen wrote:
>
> (snip)
>
> >>> You have to exactly define what you mean. Given two vectors y1 and y2,
> >>> how exactly do you determine which one is "more peaky" than the other
> >>> (in time domain)? Once you have described your procedure in time
> >>> domain, there might be something similar in the frequency domain.
>
> >>> For example: y1 = [ 0 1 -1 0 ] and y2 = [0 1 3 0]. Which one is "more
> >>> peaky"?
>
> >> I would say y2 is more peaky. In general, the problem I am solving is
> >> a matching problem of a query
> >> signal, vs. say, 10 template signals.
>
> How about the absolute value or square of the second derivative
> (or second difference for discrete data) as a peakiness measure?
> Then you either want the maximum or mean over the whole signal.

I thought of that too. There are some subtle and not so subtle problems
with this approach (see below).

>
> (snip)
>
> > The only difference between the spectra of uniformly distributed noise
> > and a single sharp impulse lies in the phases. The amplitudes of the
> > frequency components are the same. Figuring out what the phases tell you
> > is as much work as an IFFT.
>
> This is what I thought, too. Though given that he doesn't need to
> know where the peaks are there might be some small simplifications.
>
> For a not-so-obvious example, there is an O(n) algorithm for median,
> though the usual implementation would be an O(n log n) sort.
> I don't know at what n value the O(n) value is faster, but it
> might be large.

This paragraph completely OT:
The QuickSelect O(n) median search should be faster for every value of
n than the obvious QuickSort based O(n log n) median search method. The
reason is that QuickSelect performs a genuine subset of the operations
that the QuickSort needs.

>
> So, say one wants to compute the second difference of the IFFT,
> is there anything that can be done besides computing the whole IFFT
> and then applying the second difference?

One has several vectors y_1, y_2, ..., y_m. The task is to rank these
vectors according to "peakedness", where "peakedness" can have some
arbitrary definition, given only the DFTs Y_1, Y_2, ...., Y_m. If
possible, using a O(n) algorithm.

Here is my solution:

1. Apply the first or second difference operator in frequency domain
via windowing (this is an O(n) operation).
2. Compute the energy of the differenced signal by computing the energy
in the frequency domain using Parseval's theorem (this again is an O(n)
operation).
3. Rank the vectors according to this energy.

As only a fixed number of O(n) operations are required, the whole
algorithm runs in linear time. The problems are:

1 (not so subtle): the OP specified that the y vectors contain some
background noise plus possibly one or several spikes. After
differencing, hopefully the signals containing spikes have more energy
than those without. However, if the spikey signal contains less general
noise than a non-spikey signal, this ranking might not reflect the true
"peakedness".

2 (subtle): since windowing in frequency domain applies circular
convolution in time domain, there is the possibility of creating
non-existant spikes due to edge effects (convolving around the borders)
- this is a problem if the noise in the signal has varying mean value.

Wether the solution works and the problems really are problems depends,
of course, as always, on the application. One possible cure might be to
IDFT only the top ranking vector and check for peaks in time domain.

Regards,
Andor

Vladimir Vassilevsky wrote:
>
>
> Ksen wrote:
>
>> I have a unique problem where I need to predict the "peakedness" of the
>> time domain signal just by looking at the frequency transform of the
>> signal.
>
>
> In the general case, there is no way to estimate the time domain
> peakedness from the spectrum.

Seems a pretty bold statement.

What you really mean is you don't know of any way.


-- Mark Borgerding

Ksen wrote:
> I have a unique problem where I need to predict the "peakedness" of the
> time domain signal just by looking at the frequency transform of the
> signal.
> Let us call this as y1[n]<--> Y1[f]
>
> I.e, I have Y1[f] and would like to have an indicator on how sharp a peak
> is there in y1[n](closer to a delta is better).
> I cannot afford to do a IFFT. The reason being I need to do this operation
> on many of these Y[f]'s, name Y1[f], Y2[f], Y3[f], etc. etc.
>
> What I need to do is is to make a good estimation of how peaky the y1[t],
> y2[t] ...etc are, and choose the one that is the "most" peaky, i.e, has a
> dominant peak!
>
> So, is there any way by which the frequency domain info can help us
> estimate the time domain peak sharpness without doing IFFT?
> Note that I dont really need to know where the peak is..
> I may or may not have multiple peaks in y[n]'s, but all I care is a
> "dominant" peak in the time domain signal.
>
>


Interesting problem. Here's my solution:

A delta pulse in the time domain creates a flat magnitude frequency
response having linear phase with a slope that is related to the
position of the pulse.

To get a peakiness estimator, conjugate and multiply each frequency bin
from -pi to pi with its previous (unconjugated) neighboring bin. Then
take the sum of this complex vector. In other words, a dot product of
the frequency response with the conjugated and shifted-by-1 frequency
response.
in matlab/octave terms:
fx = fftshift( fft(x) );
peaky = fx(2:end)' * fx(1:end-1)

The magnitude of this quantity indicates the signal 'peakiness' and the
phase is related to the pulse position via Nfft/(2pi)


I'm not sure if I'm the first to come up with this. But, if no one
chimes in and provides a reference, I'd appreciate the attribution.


-- Mark Borgerding
3dB Labs, Inc.
Innovate. Develop. Deliver.

Mark Borgerding wrote:
> Ksen wrote:
>
>> I have a unique problem where I need to predict the "peakedness" of the
>> time domain signal just by looking at the frequency transform of the
>> signal.
>> Let us call this as y1[n]<--> Y1[f]
>>
>> I.e, I have Y1[f] and would like to have an indicator on how sharp a peak
>> is there in y1[n](closer to a delta is better).
>> I cannot afford to do a IFFT. The reason being I need to do this
>> operation
>> on many of these Y[f]'s, name Y1[f], Y2[f], Y3[f], etc. etc.
>>
>> What I need to do is is to make a good estimation of how peaky the y1[t],
>> y2[t] ...etc are, and choose the one that is the "most" peaky, i.e, has a
>> dominant peak!
>>
>> So, is there any way by which the frequency domain info can help us
>> estimate the time domain peak sharpness without doing IFFT?
>> Note that I dont really need to know where the peak is..
>> I may or may not have multiple peaks in y[n]'s, but all I care is a
>> "dominant" peak in the time domain signal.
>>
>>
>
>
> Interesting problem. Here's my solution:
>
> A delta pulse in the time domain creates a flat magnitude frequency
> response having linear phase with a slope that is related to the
> position of the pulse.
>
> To get a peakiness estimator, conjugate and multiply each frequency bin
> from -pi to pi with its previous (unconjugated) neighboring bin. Then
> take the sum of this complex vector. In other words, a dot product of
> the frequency response with the conjugated and shifted-by-1 frequency
> response.
> in matlab/octave terms:
> fx = fftshift( fft(x) );
> peaky = fx(2:end)' * fx(1:end-1)
>
> The magnitude of this quantity indicates the signal 'peakiness' and the
> phase is related to the pulse position via Nfft/(2pi)
>
>
> I'm not sure if I'm the first to come up with this. But, if no one
> chimes in and provides a reference, I'd appreciate the attribution.
>
>
> -- Mark Borgerding
> 3dB Labs, Inc.
> Innovate. Develop. Deliver.


It's worth mentioning that this method's effectiveness is reduced when
there is more than one peak in a transform. It would seem the
degenerate case occurs when pulses are equally spaced at integer >= 2
submultiples of the transform period.



-- Mark Borgerding
3dB Labs, Inc.
Innovate. Develop. Deliver.

Mark Borgerding wrote:

>
> A delta pulse in the time domain creates a flat magnitude frequency
> response having linear phase with a slope that is related to the
> position of the pulse.

First question: what is the definition of the "peakedness" ?
Is it the max.peak to average ratio or something else?

> To get a peakiness estimator, conjugate and multiply each frequency bin
> from -pi to pi with its previous (unconjugated) neighboring bin. Then
> take the sum of this complex vector. In other words, a dot product of
> the frequency response with the conjugated and shifted-by-1 frequency
> response.
> in matlab/octave terms:
> fx = fftshift( fft(x) );
> peaky = fx(2:end)' * fx(1:end-1)
>
> The magnitude of this quantity indicates the signal 'peakiness' and the
> phase is related to the pulse position via Nfft/(2pi)

This will work reliably only if you have one delta pulse.

> I'm not sure if I'm the first to come up with this.

Wiener Khintchine Theorem

> But, if no one
> chimes in and provides a reference, I'd appreciate the attribution.

Keep digging

Vladimir Vassilevsky

DSP and Mixed Signal Design Consultant

http://www.abvolt.com

Vladimir Vassilevsky wrote:
>
>
> Mark Borgerding wrote:
>
>>
>> A delta pulse in the time domain creates a flat magnitude frequency
>> response having linear phase with a slope that is related to the
>> position of the pulse.
>
>
> First question: what is the definition of the "peakedness" ?
> Is it the max.peak to average ratio or something else?

See the OP, "how sharp a peak is there in y1[n](closer to a delta is
better)."

>
>> To get a peakiness estimator, conjugate and multiply each frequency
>> bin from -pi to pi with its previous (unconjugated) neighboring bin.
>> Then take the sum of this complex vector. In other words, a dot
>> product of the frequency response with the conjugated and shifted-by-1
>> frequency response.
>> in matlab/octave terms:
>> fx = fftshift( fft(x) );
>> peaky = fx(2:end)' * fx(1:end-1)
>>
>> The magnitude of this quantity indicates the signal 'peakiness' and
>> the phase is related to the pulse position via Nfft/(2pi)
>
>
> This will work reliably only if you have one delta pulse.
>

Yes, I noted this in my second post.

>> I'm not sure if I'm the first to come up with this.
>
>
> Wiener Khintchine Theorem

I don't see how this is relevant. Perhaps you could elaborate.


According to Wikipedia,

"The Wiener–Khinchin theorem (also known as the Wiener–Khintchine
theorem and sometimes as the Khinchin–Kolmogorov theorem) states that
the power spectral density of a wide-sense-stationary random process is
the Fourier Transform of the corresponding autocorrelation function."


The method I described has nothing to do with autocorrelation nor power
spectral density. Indeed, "power spectral density" indicates phase is
removed. The phase response is crucial. Without phase, there is no
difference between a delta pulse and white noise.


--
Mark Borgerding
3dB Labs, Inc
Innovate. Develop. Deliver.

Vladimir Vassilevsky wrote:

>
> First question: what is the definition of the "peakedness" ?

Kinda late to be asking the first question dontcha think:}

The OP I believe has something like 10 signals. One has a large peak (I
don't think he explained much beyond that) the rest have no peak just
flat noise. He wants to ID the one with the peak in the frequency
domain.

Would seem that that the Peaked Signal in the frequency domain would
have a narrow or wide peak also at F0 depending on whether the time
domain peak was wide or narrow. You would think this would be rather
obvious by simply looking at the data so there probably is something
that hasn't been revealed.

-jim

----== Posted via Newsfeeds.Com - Unlimited-Unrestricted-Secure Usenet News==----
http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----

Mark Borgerding wrote:
> Vladimir Vassilevsky wrote:
> >
> >
> > Mark Borgerding wrote:
> >
> >>
> >> A delta pulse in the time domain creates a flat magnitude frequency
> >> response having linear phase with a slope that is related to the
> >> position of the pulse.
> >
> >
> > First question: what is the definition of the "peakedness" ?
> > Is it the max.peak to average ratio or something else?
>
> See the OP, "how sharp a peak is there in y1[n](closer to a delta is
> better)."
>
> >
> >> To get a peakiness estimator, conjugate and multiply each frequency
> >> bin from -pi to pi with its previous (unconjugated) neighboring bin.
> >> Then take the sum of this complex vector. In other words, a dot
> >> product of the frequency response with the conjugated and shifted-by-1
> >> frequency response.
> >> in matlab/octave terms:
> >> fx = fftshift( fft(x) );
> >> peaky = fx(2:end)' * fx(1:end-1)
> >>
> >> The magnitude of this quantity indicates the signal 'peakiness' and
> >> the phase is related to the pulse position via Nfft/(2pi)
> >
> >
> > This will work reliably only if you have one delta pulse.
> >
>
> Yes, I noted this in my second post.
>
> >> I'm not sure if I'm the first to come up with this.
> >
> >
> > Wiener Khintchine Theorem
>
> I don't see how this is relevant. Perhaps you could elaborate.
>
>
> According to Wikipedia,
>
> "The Wiener-Khinchin theorem (also known as the Wiener-Khintchine
> theorem and sometimes as the Khinchin-Kolmogorov theorem) states that
> the power spectral density of a wide-sense-stationary random process is
> the Fourier Transform of the corresponding autocorrelation function."
>
>
> The method I described has nothing to do with autocorrelation nor power
> spectral density. Indeed, "power spectral density" indicates phase is
> removed. The phase response is crucial. Without phase, there is no
> difference between a delta pulse and white noise.

Computationally, the fft and ifft are the more or less the same thing.
Therefore what works one way will work the other. A peak in
the frequency domain implies a sinusoid in the time domain.
Therefore a sinusoid in the frequency domain implies a peak
in the time domain.

The following is just a wild guess:

Your matlab solution looks like an autocorrelation form of a sinusoid
detector. It removes the "phase" from the time domain signal, since
you don't care about the imaginary portion of a real signal.


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

Ron N. wrote:
> Mark Borgerding wrote:
>
>>Vladimir Vassilevsky wrote:
>>
>>>
>>>Mark Borgerding wrote:
>>>
>>>
>>>>A delta pulse in the time domain creates a flat magnitude frequency
>>>>response having linear phase with a slope that is related to the
>>>>position of the pulse.
>>>
>>>
>>>First question: what is the definition of the "peakedness" ?
>>>Is it the max.peak to average ratio or something else?
>>
>>See the OP, "how sharp a peak is there in y1[n](closer to a delta is
>>better)."
>>
>>
>>>>To get a peakiness estimator, conjugate and multiply each frequency
>>>>bin from -pi to pi with its previous (unconjugated) neighboring bin.
>>>>Then take the sum of this complex vector. In other words, a dot
>>>>product of the frequency response with the conjugated and shifted-by-1
>>>>frequency response.
>>>> in matlab/octave terms:
>>>> fx = fftshift( fft(x) );
>>>> peaky = fx(2:end)' * fx(1:end-1)
>>>>
>>>>The magnitude of this quantity indicates the signal 'peakiness' and
>>>>the phase is related to the pulse position via Nfft/(2pi)
>>>
>>>
>>>This will work reliably only if you have one delta pulse.
>>>
>>
>>Yes, I noted this in my second post.
>>
>>
>>>>I'm not sure if I'm the first to come up with this.
>>>
>>>
>>>Wiener Khintchine Theorem
>>
>>I don't see how this is relevant. Perhaps you could elaborate.
>>
>>
>>According to Wikipedia,
>>
>>"The Wiener-Khinchin theorem (also known as the Wiener-Khintchine
>>theorem and sometimes as the Khinchin-Kolmogorov theorem) states that
>>the power spectral density of a wide-sense-stationary random process is
>>the Fourier Transform of the corresponding autocorrelation function."
>>
>>
>>The method I described has nothing to do with autocorrelation nor power
>>spectral density. Indeed, "power spectral density" indicates phase is
>>removed. The phase response is crucial. Without phase, there is no
>>difference between a delta pulse and white noise.
>
>
> Computationally, the fft and ifft are the more or less the same thing.
> Therefore what works one way will work the other. A peak in
> the frequency domain implies a sinusoid in the time domain.
> Therefore a sinusoid in the frequency domain implies a peak
> in the time domain.
>
> The following is just a wild guess:
>
> Your matlab solution looks like an autocorrelation form of a sinusoid
> detector. It removes the "phase" from the time domain signal, since
> you don't care about the imaginary portion of a real signal.
>
>
> IMHO. YMMV.

Okay. I can see how to swap time with frequency and apply the same
mathematics to do either
a) frequency-domain detection of a time-domain pulse
or
b) time-domain detection of a complex sinusoid

The above "peakiness estimator" is analogous to a FM discriminator,
smoothed coherently.

But I still don't see where autocorrelation fits in.

Can you provide a reference for "autocorrelation form of a sinusoid
detector"?


--
Mark Borgerding
3dB Labs, Inc
Innovate. Develop. Deliver.

Okie guys, not to flash anything, but my simulations show that my suggeste
solution seems to be doing well.

i.e, if you have Y1(f)....Yn(f).

Unwrap(Phase(Yk(f))) should follow "closest to" a straight line if this i
the best answer of the n candidates.


I checked this for a few signals..It seems the thing works even if ther
are small peaks elsewhere in the time domain, provided there is one larg
enough peak in the time domain.

Now that I spilled it on this discussion group, can I patent this ?
Seems will be useful in many target recognition applications!!

I will try others suggested by you guys..

I wonder why no one else has encountered this problem before!


>Ron N. wrote:
>> Mark Borgerding wrote:
>>
>>>Vladimir Vassilevsky wrote:
>>>
>>>>
>>>>Mark Borgerding wrote:
>>>>
>>>>
>>>>>A delta pulse in the time domain creates a flat magnitude frequency
>>>>>response having linear phase with a slope that is related to the
>>>>>position of the pulse.
>>>>
>>>>
>>>>First question: what is the definition of the "peakedness" ?
>>>>Is it the max.peak to average ratio or something else?
>>>
>>>See the OP, "how sharp a peak is there in y1[n](closer to a delta is
>>>better)."
>>>
>>>
>>>>>To get a peakiness estimator, conjugate and multiply each frequency
>>>>>bin from -pi to pi with its previous (unconjugated) neighboring bin.
>>>>>Then take the sum of this complex vector. In other words, a dot
>>>>>product of the frequency response with the conjugated an
shifted-by-1
>>>>>frequency response.
>>>>> in matlab/octave terms:
>>>>> fx = fftshift( fft(x) );
>>>>> peaky = fx(2:end)' * fx(1:end-1)
>>>>>
>>>>>The magnitude of this quantity indicates the signal 'peakiness' and
>>>>>the phase is related to the pulse position via Nfft/(2pi)
>>>>
>>>>
>>>>This will work reliably only if you have one delta pulse.
>>>>
>>>
>>>Yes, I noted this in my second post.
>>>
>>>
>>>>>I'm not sure if I'm the first to come up with this.
>>>>
>>>>
>>>>Wiener Khintchine Theorem
>>>
>>>I don't see how this is relevant. Perhaps you could elaborate.
>>>
>>>
>>>According to Wikipedia,
>>>
>>>"The Wiener-Khinchin theorem (also known as the Wiener-Khintchine
>>>theorem and sometimes as the Khinchin-Kolmogorov theorem) states that
>>>the power spectral density of a wide-sense-stationary random proces
is
>>>the Fourier Transform of the corresponding autocorrelation function."
>>>
>>>
>>>The method I described has nothing to do with autocorrelation no
power
>>>spectral density. Indeed, "power spectral density" indicates phase is
>>>removed. The phase response is crucial. Without phase, there is no
>>>difference between a delta pulse and white noise.
>>
>>
>> Computationally, the fft and ifft are the more or less the same thing.
>> Therefore what works one way will work the other. A peak in
>> the frequency domain implies a sinusoid in the time domain.
>> Therefore a sinusoid in the frequency domain implies a peak
>> in the time domain.
>>
>> The following is just a wild guess:
>>
>> Your matlab solution looks like an autocorrelation form of a sinusoid
>> detector. It removes the "phase" from the time domain signal, since
>> you don't care about the imaginary portion of a real signal.
>>
>>
>> IMHO. YMMV.
>
>Okay. I can see how to swap time with frequency and apply the same
>mathematics to do either
>a) frequency-domain detection of a time-domain pulse
>or
>b) time-domain detection of a complex sinusoid
>
>The above "peakiness estimator" is analogous to a FM discriminator,
>smoothed coherently.
>
>But I still don't see where autocorrelation fits in.
>
>Can you provide a reference for "autocorrelation form of a sinusoid
>detector"?
>
>
>--
>Mark Borgerding
>3dB Labs, Inc
>Innovate. Develop. Deliver.
>

Hi All,

I just happened to catch this thread...

I published a paper in the Astronomical Journal that discusses how to
measure the "centroid" (i.e. the position of a signal in a chunk of
data) and "purity" (the RMS dispersion of a pulsation in time wrt the
centroid) of a time domain signal (specifically a sinusoid) by using
derivatives of the fourier amplitude (2nd deriv of power for purity)
and phase (1st derive for centroid). The derivatives are computed
using Fourier interpolation (one version of which is also discussed in
the paper) and finite differences.

If you are interested, a link to the paper is here:
http://tinyurl.com/lg2oc

Scott

PS: Credit goes to John Middleditch for originally coming up with
quite a bit of what is "new" in that paper. (Although, "new" in
astronomy is not necessarily "new" in DSP I realize!)

Ksen wrote:
> Okie guys, not to flash anything, but my simulations show that my suggested
> solution seems to be doing well.
>
> i.e, if you have Y1(f)....Yn(f).
>
> Unwrap(Phase(Yk(f))) should follow "closest to" a straight line if this is
> the best answer of the n candidates.
>
>
> I checked this for a few signals..It seems the thing works even if there
> are small peaks elsewhere in the time domain, provided there is one large
> enough peak in the time domain.
>
> Now that I spilled it on this discussion group, can I patent this ?
> Seems will be useful in many target recognition applications!!
>
> I will try others suggested by you guys..
>
> I wonder why no one else has encountered this problem before!
>
>
> >

I got a copy of the astro-physics paper..seems the method assumes sinusoid
for signals..May not have applications in general purpose image/signal, bu
the definitions laid on centroid and purity can be extended for sure..


BTW, any critical views on my solution on looking at Unwrap(Phase(Yk(f))
and looking at how close it to a straight line as an indicator of tim
domain peakedness?



>Hi All,
>
>I just happened to catch this thread...
>
>I published a paper in the Astronomical Journal that discusses how to
>measure the "centroid" (i.e. the position of a signal in a chunk of
>data) and "purity" (the RMS dispersion of a pulsation in time wrt the
>centroid) of a time domain signal (specifically a sinusoid) by using
>derivatives of the fourier amplitude (2nd deriv of power for purity)
>and phase (1st derive for centroid). The derivatives are computed
>using Fourier interpolation (one version of which is also discussed in
>the paper) and finite differences.
>
>If you are interested, a link to the paper is here:
>http://tinyurl.com/lg2oc
>
>Scott
>
>PS: Credit goes to John Middleditch for originally coming up with
>quite a bit of what is "new" in that paper. (Although, "new" in
>astronomy is not necessarily "new" in DSP I realize!)
>
>Ksen wrote:
>> Okie guys, not to flash anything, but my simulations show that m
suggested
>> solution seems to be doing well.
>>
>> i.e, if you have Y1(f)....Yn(f).
>>
>> Unwrap(Phase(Yk(f))) should follow "closest to" a straight line if thi
is
>> the best answer of the n candidates.
>>
>>
>> I checked this for a few signals..It seems the thing works even i
there
>> are small peaks elsewhere in the time domain, provided there is on
large
>> enough peak in the time domain.
>>
>> Now that I spilled it on this discussion group, can I patent this ?
>> Seems will be useful in many target recognition applications!!
>>
>> I will try others suggested by you guys..
>>
>> I wonder why no one else has encountered this problem before!
>>
>>
>> >
>
>

Ksen wrote:
> BTW, any critical views on my solution on looking at Unwrap(Phase(Yk(f)))
> and looking at how close it to a straight line as an indicator of time
> domain peakedness?


Strangely enough, people tend to get less interested in helping someone
once he's made clear his hopes of patenting the ideas others help him
develop gratis.


--
Mark Borgerding
3dB Labs, Inc
Innovate. Develop. Deliver.

Ksen said the following on 25/08/2006 20:58:
> Okie guys, not to flash anything, but my simulations show that my suggested
> solution seems to be doing well.
>
> i.e, if you have Y1(f)....Yn(f).
>
> Unwrap(Phase(Yk(f))) should follow "closest to" a straight line if this is
> the best answer of the n candidates.
>
>
> I checked this for a few signals..It seems the thing works even if there
> are small peaks elsewhere in the time domain, provided there is one large
> enough peak in the time domain.
>
> Now that I spilled it on this discussion group, can I patent this ?
> Seems will be useful in many target recognition applications!!
>
> I wonder why no one else has encountered this problem before!

Well, I came up with this approach to use as an OFDM timing offset
estimator in my MEng project earlier this year; and I would hazard a
guess that I'm not the first person to think of it independently.

Therefore, I'm not sure the novelty and non-obvious requirements for a
patent will hold water on this.

--
Oli

Thanks Oli. I thought it was thought about by someone too.

As for the previous post on "gratis", hello sir, but the linearity o
phase unwrapping was mine and mine alone. Did anyone help me with th
phase unwrap thingee? If so, please raise you hand, so that I can give m
ack. There were several ideas put forth, which I have not checked yet.

Infact, this is a scholarly discussion going on.

Yes, I checked, once its out in open, no one can patent. It was just
curiousity question. I was hardly serious (mainly out of zest) when I mad
the statemant.

Also, it will possibly help many people reading the post. Many people d
not have the fastest of the processors, and no time for IFFT.


>Ksen said the following on 25/08/2006 20:58:
>> Okie guys, not to flash anything, but my simulations show that m
suggested
>> solution seems to be doing well.
>>
>> i.e, if you have Y1(f)....Yn(f).
>>
>> Unwrap(Phase(Yk(f))) should follow "closest to" a straight line if thi
is
>> the best answer of the n candidates.
>>
>>
>> I checked this for a few signals..It seems the thing works even i
there
>> are small peaks elsewhere in the time domain, provided there is on
large
>> enough peak in the time domain.
>>
>> Now that I spilled it on this discussion group, can I patent this ?
>> Seems will be useful in many target recognition applications!!
>>
>> I wonder why no one else has encountered this problem before!
>
>Well, I came up with this approach to use as an OFDM timing offset
>estimator in my MEng project earlier this year; and I would hazard a
>guess that I'm not the first person to think of it independently.
>
>Therefore, I'm not sure the novelty and non-obvious requirements for a
>patent will hold water on this.
>
>--
>Oli
>

Ksen wrote:
> As for the previous post on "gratis", hello sir, but the linearity on
> phase unwrapping was mine and mine alone.

I think many calculus textbooks might say something about
one definition of the frequency of a sinusoid being the slope
of its phase.

One question is whether calculating phase angles for an
entire complex vector, and then doing a linear regression
on those phase angles is actually more computationally
efficient the just doing another (I)FFT. The arctan2 would
have to require less flops than log(N).


IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M

I have figured a fast technique out anyways for 2D case..
if you have an 100x100 array in the freq domain, you need not do phas
compuytation on 10^4 elements.

Just take up the 4 lines that run E-W, N-S, and the 2 diagonals throug
the origin.

phase values on these lines can be unwrapped (BTW, optimal 2D phas
unwraping is a unsolved problem till date...that's another story..hav
done enough rsch on that to know it well..!!)

Then fit lines.

Technically, 2 lines in 3D are enough to define a plane, but 4 is a bi
better from regression viewpoint.


As for arc tan2 (some 40 of them and not 10000), you can do it smartl
using LUT.

So in essence, this technique is much much much *** faster than IFFT.

QED!





>Ksen wrote:
>> As for the previous post on "gratis", hello sir, but the linearity on
>> phase unwrapping was mine and mine alone.
>
>I think many calculus textbooks might say something about
>one definition of the frequency of a sinusoid being the slope
>of its phase.
>
>One question is whether calculating phase angles for an
>entire complex vector, and then doing a linear regression
>on those phase angles is actually more computationally
>efficient the just doing another (I)FFT. The arctan2 would
>have to require less flops than log(N).
>
>
>IMHO. YMMV.
>--
>rhn A.T nicholson d.0.t C-o-M
>
>