Forums

Frequency estimation with MUSIC for single sin wave?

Started by rhines January 24, 2007
Hallo everyone,

I'm new to signal processing and spectral analysis,
and I want to determine freqency of one single sin wave in white noise
with MUSIC algorithm and bring it on uC and FPGA.

e.g I decide to use the SVD approach(singular value decomposition) and
begin with sample data length N=256. Let p = 100 then i have a data matrix
of p x (N-p) = 100 x 156. (U,S,V)=SVD(A) on a matrix of this scale should
be done. Taking one vector of signalspace of V (p x p vector space which
spans signal&noise space) and do matrix-matrix multiplication using
512-point-FFT to calculate MUSIC spectrum and find peak. It seems rather
great complexity for Hardware implementation. (all goes well in Matlab) 

My question is: 
1. If it makes sense to use MUSIC algo(or its variants..) .(As far as I
know, MUSIC has advantage of high resolution...-.- and relatively low
complexity.)
2. How I can determine the variables: sample data length, p, and
others...
3. How to cope with SVD? (real or complex, which algo..., tatally no idea
of it's complexity in Hardware)



On Jan 24, 12:11 pm, "rhines" <rhine...@gmail.com> wrote:
> Hallo everyone, > > I'm new to signal processing and spectral analysis, > and I want to determine freqency of one single sin wave in white noise > with MUSIC algorithm and bring it on uC and FPGA. > > e.g I decide to use the SVD approach(singular value decomposition) and > begin with sample data length N=256. Let p = 100 then i have a data matrix > of p x (N-p) = 100 x 156. (U,S,V)=SVD(A) on a matrix of this scale should > be done. Taking one vector of signalspace of V (p x p vector space which > spans signal&noise space) and do matrix-matrix multiplication using > 512-point-FFT to calculate MUSIC spectrum and find peak. It seems rather > great complexity for Hardware implementation. (all goes well in Matlab)
Why do you need an FFT to do a MUSIC-type estimation?
> My question is: > 1. If it makes sense to use MUSIC algo(or its variants..) .(As far as I > know, MUSIC has advantage of high resolution...-.- and relatively low > complexity.) > 2. How I can determine the variables: sample data length, p, and > others... > 3. How to cope with SVD? (real or complex, which algo..., tatally no idea > of it's complexity in Hardware)
At high SNR and high sampling rate, you can get good results just by counting the zero-crossings of the signal and averaging your count. Now, for MUSIC-type algorithms, if you only want one single tone estimate and your signal doesn't have much interference, there exists many simpler algorithms. Look up "frequency estimation" in google. Here are a few starters: http://home.comcast.net/~kootsoop/freqalgs.htm Hope that helps, Julius
"julius" <juliusk@gmail.com> writes:

> On Jan 24, 12:11 pm, "rhines" <rhine...@gmail.com> wrote: >> Hallo everyone, >> >> I'm new to signal processing and spectral analysis, >> and I want to determine freqency of one single sin wave in white noise >> with MUSIC algorithm and bring it on uC and FPGA. >> >> e.g I decide to use the SVD approach(singular value decomposition) and >> begin with sample data length N=256. Let p = 100 then i have a data matrix >> of p x (N-p) = 100 x 156. (U,S,V)=SVD(A) on a matrix of this scale should >> be done. Taking one vector of signalspace of V (p x p vector space which >> spans signal&noise space) and do matrix-matrix multiplication using >> 512-point-FFT to calculate MUSIC spectrum and find peak. It seems rather >> great complexity for Hardware implementation. (all goes well in Matlab) > > Why do you need an FFT to do a MUSIC-type estimation? > >> My question is: >> 1. If it makes sense to use MUSIC algo(or its variants..) .(As far as I >> know, MUSIC has advantage of high resolution...-.- and relatively low >> complexity.) >> 2. How I can determine the variables: sample data length, p, and >> others... >> 3. How to cope with SVD? (real or complex, which algo..., tatally no idea >> of it's complexity in Hardware) > > At high SNR and high sampling rate, you can get good results just by > counting the zero-crossings of the signal and averaging your count. > > Now, for MUSIC-type algorithms, if you only want one single tone > estimate > and your signal doesn't have much interference, there exists many > simpler > algorithms. Look up "frequency estimation" in google. > > Here are a few starters: > > http://home.comcast.net/~kootsoop/freqalgs.htm > > Hope that helps, > Julius
Julius, you're too modest. Rhines, Julius has done "some" work in this area. See his presentation on parametric frequency estimation at Connexions: http://cnx.org/content/m10588/latest/ and also his Ph.D. thesis: http://www.rle.mit.edu/stir/documents/KusumaJ_PhDThesis2006.pdf --Randy -- % Randy Yates % "Rollin' and riding and slippin' and %% Fuquay-Varina, NC % sliding, it's magic." %%% 919-577-9882 % %%%% <yates@ieee.org> % 'Living' Thing', *A New World Record*, ELO http://home.earthlink.net/~yatescr
On Jan 24, 10:11 am, "rhines" <rhine...@gmail.com> wrote:
> 1. If it makes sense to use MUSIC algo(or its variants..) .(As far as I > know, MUSIC has advantage of high resolution...-.- and relatively low > complexity.)
Depends on your signal and your requirements. There are a lot of frequency estimation methods of various (some lower that MUSIC) complexity which may or may not work in various situations. I have listed about a dozen Q&D frequency estimation methods in the middle of this web page: http://www.nicholson.com/rhn/dsp.html (not on my list is offering a barometer to whoever is generating the unknown frequency :-) IMHO. YMMV. -- rhn A.T nicholson d.0.t C-o-M
Yeah, google "frequency estimation"

The top search result you will get is this:
http://www.dsprelated.com/showmessage/7716/1.php

You can also go to www.uspto.gov/patft and read US Patent 7124075

Probably an overkill for your problem...

Also, one should do some signal filtering or use SVD-embedding to get
rid of white noise prior to computing periodicity histogram.


On Jan 24, 1:11 pm, "rhines" <rhine...@gmail.com> wrote:
> Hallo everyone, > > I'm new to signal processing and spectral analysis, > and I want to determine freqency of one single sin wave in white noise > with MUSIC algorithm and bring it on uC and FPGA. > > e.g I decide to use the SVD approach(singular value decomposition) and > begin with sample data length N=256. Let p = 100 then i have a data matrix > of p x (N-p) = 100 x 156. (U,S,V)=SVD(A) on a matrix of this scale should > be done. Taking one vector of signalspace of V (p x p vector space which > spans signal&noise space) and do matrix-matrix multiplication using > 512-point-FFT to calculate MUSIC spectrum and find peak. It seems rather > great complexity for Hardware implementation. (all goes well in Matlab) > > My question is: > 1. If it makes sense to use MUSIC algo(or its variants..) .(As far as I > know, MUSIC has advantage of high resolution...-.- and relatively low > complexity.) > 2. How I can determine the variables: sample data length, p, and > others... > 3. How to cope with SVD? (real or complex, which algo..., tatally no idea > of it's complexity in Hardware)
Randy Yates wrote:

   ...

> Julius, you're too modest.
So you had to out him? :-) Way to go! Jerry -- Engineering is the art of making what you want from things you can get. &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;

On Jan 25, 9:06 am, Jerry Avins <j...@ieee.org> wrote:
> Randy Yates wrote: ... > > > Julius, you're too modest. > So you had to out him? :-) Way to go! > > Jerry
Randy and Jerry, I think you guys are exaggerating here.... I have used it, but I can't say that I have contributed to it. But I do get citations on that document that I hastily wrote a long time ago, so maybe I should try to clean it up! Thanks, Julius
> > >On Jan 24, 12:11 pm, "rhines" <rhine...@gmail.com> wrote: >> Hallo everyone, >> >> I'm new to signal processing and spectral analysis, >> and I want to determine freqency of one single sin wave in white noise >> with MUSIC algorithm and bring it on uC and FPGA. >> >> e.g I decide to use the SVD approach(singular value decomposition) and >> begin with sample data length N=256. Let p = 100 then i have a data
matrix
>> of p x (N-p) = 100 x 156. (U,S,V)=SVD(A) on a matrix of this scale
should
>> be done. Taking one vector of signalspace of V (p x p vector space
which
>> spans signal&noise space) and do matrix-matrix multiplication using >> 512-point-FFT to calculate MUSIC spectrum and find peak. It seems
rather
>> great complexity for Hardware implementation. (all goes well in
Matlab)
> >Why do you need an FFT to do a MUSIC-type estimation? > >> My question is: >> 1. If it makes sense to use MUSIC algo(or its variants..) .(As far as
I
>> know, MUSIC has advantage of high resolution...-.- and relatively low >> complexity.) >> 2. How I can determine the variables: sample data length, p, and >> others... >> 3. How to cope with SVD? (real or complex, which algo..., tatally no
idea
>> of it's complexity in Hardware) > >At high SNR and high sampling rate, you can get good results just by >counting the zero-crossings of the signal and averaging your count. > >Now, for MUSIC-type algorithms, if you only want one single tone >estimate >and your signal doesn't have much interference, there exists many >simpler >algorithms. Look up "frequency estimation" in google. > >Here are a few starters: > >http://home.comcast.net/~kootsoop/freqalgs.htm > >Hope that helps, >Julius > >
Thanks all~~~appreciate your help^.^ The sine wave that i estimate is a mixed signal from 3 sine wave at the same frequency from a analog board , so it is just a "one" tone signal but may swing over time. SNR is somehow unclear(assumed to be 10 - 20db in simulation). So i assume MUSIC is suitable for this problem.(or to have sample rate/word length/number of points for one estimation/etc.. reduced to obtain speed/less hardware...) Is it an acceptable assumption? rhines
hi nicholson,
                 nice categorization of algorithms you have done on the
webpage..good keep it up.

regards
particlereddy

On Jan 26, 1:18 am, "rhines" <rhine...@gmail.com> wrote:
> >On Jan 24, 12:11 pm, "rhines" <rhine...@gmail.com> wrote: > >> Hallo everyone, > > >> I'm new to signal processing and spectral analysis, > >> and I want to determine freqency of one single sin wave in white noise > >> with MUSIC algorithm and bring it on uC and FPGA. > > >> e.g I decide to use the SVD approach(singular value decomposition) and > >> begin with sample data length N=256. Let p = 100 then i have a data > matrix > >> of p x (N-p) = 100 x 156. (U,S,V)=SVD(A) on a matrix of this scale > should > >> be done. Taking one vector of signalspace of V (p x p vector space > which > >> spans signal&noise space) and do matrix-matrix multiplication using > >> 512-point-FFT to calculate MUSIC spectrum and find peak. It seems > rather > >> great complexity for Hardware implementation. (all goes well in > Matlab) > > >Why do you need an FFT to do a MUSIC-type estimation? > > >> My question is: > >> 1. If it makes sense to use MUSIC algo(or its variants..) .(As far as > I > >> know, MUSIC has advantage of high resolution...-.- and relatively low > >> complexity.) > >> 2. How I can determine the variables: sample data length, p, and > >> others... > >> 3. How to cope with SVD? (real or complex, which algo..., tatally no > idea > >> of it's complexity in Hardware) > > >At high SNR and high sampling rate, you can get good results just by > >counting the zero-crossings of the signal and averaging your count. > > >Now, for MUSIC-type algorithms, if you only want one single tone > >estimate > >and your signal doesn't have much interference, there exists many > >simpler > >algorithms. Look up "frequency estimation" in google. > > >Here are a few starters: > > >http://home.comcast.net/~kootsoop/freqalgs.htm > > >Hope that helps, > >JuliusThanks all~~~appreciate your help^.^ > > The sine wave that i estimate is a mixed signal from 3 sine wave at the > same frequency from a analog board , so it is just a "one" tone signal but > may swing over time. SNR is somehow unclear(assumed to be 10 - 20db in > simulation). > So i assume MUSIC is suitable for this problem.(or to have sample > rate/word length/number of points for one estimation/etc.. reduced to > obtain speed/less hardware...) > Is it an acceptable assumption? > > rhines
On 24 Jan, 19:11, "rhines" <rhine...@gmail.com> wrote:
> Hallo everyone, > > I'm new to signal processing and spectral analysis, > and I want to determine freqency of one single sin wave in white noise > with MUSIC algorithm and bring it on uC and FPGA.
Why? Make sure you test whether MUSIC actually works as you think it does before you make any commitments on algorithms.
> e.g I decide to use the SVD approach(singular value decomposition) and > begin with sample data length N=256. Let p = 100 then i have a data matrix > of p x (N-p) = 100 x 156. (U,S,V)=SVD(A) on a matrix of this scale should > be done. Taking one vector of signalspace of V (p x p vector space which > spans signal&noise space) and do matrix-matrix multiplication using > 512-point-FFT to calculate MUSIC spectrum and find peak. It seems rather > great complexity for Hardware implementation. (all goes well in Matlab)
You are right. Since you expect exactly one sinusoidal, you need an covariance matrix of dimension 2x2.
> My question is: > 1. If it makes sense to use MUSIC algo(or its variants..) .(As far as I > know, MUSIC has advantage of high resolution...
...when it works...
> -.- and relatively low > complexity.)
Not at all. You need SVDs and bisection searches.
> 2. How I can determine the variables: sample data length, p, and > others...
That's the black art. You need to *know* -- not "assume" or "believe" -- the exact upper limit of the number of sinusoidals.
> 3. How to cope with SVD? (real or complex, which algo..., tatally no idea > of it's complexity in Hardware)
Computing the SVD is an iterative process. You can't give a definite measure of complexity. Check out "matrix computations" by Golub & van Loan. Rune