Hello Forum, given a N-point window h(n), how do I create an oversampled Fourier transform H out of h(n)? I need to have very high resolution of the H so that I can find out the magnitude of arbitrary frequency with little frequency error. This is what I did: to oversample h(n) with factor 2, I first sampled the window h with N * 2 points, and then simply FFT the 'new h' with N*2-point. But the H with N*2 points looks very different from H with N points. What am I doing wrong? Thanks in advance! _____________________________ Posted through www.DSPRelated.com
oversampled Fourier transform
Started by ●March 31, 2015
Reply by ●March 31, 20152015-03-31
On Tue, 31 Mar 2015 19:07:55 -0500, "mfl" <103819@dsprelated> wrote:>Hello Forum, > >given a N-point window h(n), how do I create an oversampled Fourier >transform H out of h(n)? I need to have very high resolution of the H so >that I can find out the magnitude of arbitrary frequency with little >frequency error. > >This is what I did: to oversample h(n) with factor 2, I first sampled the >window h with N * 2 points, and then simply FFT the 'new h' with N*2-point. >But the H with N*2 points looks very different from H with N points. What >am I doing wrong? > >Thanks in advance! > > > >_____________________________ >Posted through www.DSPRelated.comI would look up Chirp Z-Transform. I have seen the source code to a few implementations floating around the internet before. Mark
Reply by ●April 1, 20152015-04-01
On Tuesday, March 31, 2015 at 5:08:00 PM UTC-7, mfl wrote:> Hello Forum, > > given a N-point window h(n), how do I create an oversampled Fourier > transform H out of h(n)? I need to have very high resolution of the H so > that I can find out the magnitude of arbitrary frequency with little > frequency error. > > This is what I did: to oversample h(n) with factor 2, I first sampled the > window h with N * 2 points, and then simply FFT the 'new h' with N*2-point. > But the H with N*2 points looks very different from H with N points. What > am I doing wrong? > > Thanks in advance!A direct fft approach is to append (p-1)*n zeros to your n samples and perform a p*n size fft. Every p-th fft bin should match the output from each sample from the n point fft to within a scale factor determined by your fft code. Iff you have access to more data and you know that the peak frequencies are stationary over the longer period, simply increasing n will give finer peak picking resolution and better accuracy against noise. Alternatively, if you want to estimate the frequency of well separated peaks, you can interpolate the fft coefficient values around the peaks to estimate the frequency, amplitude and phase of the peak frequencies. Algorithms to calculate quick and dirty approximations have been discussed here in the past. More accurate interpolations can produce estimates likely to be limited in accuracy by the noise and interference levels in your signal. Fft based algorithms that originally appeared under the name "frequency reassignment" using multiple windows and ffts on the n samples provide both interpolation of frequency, amplitude and phase and the ability to estimate the amount of frequency shift (fm) of the peak frequencies during the n samples. Dale B. Dalrymple
Reply by ●April 1, 20152015-04-01
>On Tuesday, March 31, 2015 at 5:08:00 PM UTC-7, mfl wrote: >> Hello Forum, >> >> given a N-point window h(n), how do I create an oversampled Fourier >> transform H out of h(n)? I need to have very high resolution of the Hso>> that I can find out the magnitude of arbitrary frequency with little >> frequency error. >> >> This is what I did: to oversample h(n) with factor 2, I first sampledthe>> window h with N * 2 points, and then simply FFT the 'new h' withN*2-point.>> But the H with N*2 points looks very different from H with N points.What>> am I doing wrong? >> >> Thanks in advance! > >A direct fft approach is to append (p-1)*n zeros to your n samples andperform a p*n size fft. Every p-th fft bin should match the output from each sample from the n point fft to within a scale factor determined by your fft code.> >Iff you have access to more data and you know that the peak frequenciesare stationary over the longer period, simply increasing n will give finer peak picking resolution and better accuracy against noise.> >Alternatively, if you want to estimate the frequency of well separatedpeaks, you can interpolate the fft coefficient values around the peaks to estimate the frequency, amplitude and phase of the peak frequencies. Algorithms to calculate quick and dirty approximations have been discussed here in the past. More accurate interpolations can produce estimates likely to be limited in accuracy by the noise and interference levels in your signal.> >Fft based algorithms that originally appeared under the name "frequencyreassignment" using multiple windows and ffts on the n samples provide both interpolation of frequency, amplitude and phase and the ability to estimate the amount of frequency shift (fm) of the peak frequencies during the n samples.> >Dale B. DalrympleThanks Mark and Dale for the suggestions! @Dale: is there any keywords to find out the alternative technique using interpolation? Is it called parabolic interpolator? Cheers, MF --------------------------------------- Posted through http://www.DSPRelated.com
Reply by ●April 1, 20152015-04-01
On Wednesday, April 1, 2015 at 12:20:24 PM UTC-7, 103...@dsprelated wrote:> > Thanks Mark and Dale for the suggestions! > > @Dale: is there any keywords to find out the alternative technique using > interpolation? Is it called parabolic interpolator?"interpolated fft" and "peak interpolation" are common phrases. One of the interpolation methods is the parabolic. It is the know-nothing choice with three points and can be good enough. When looking at interpolation formulas, pay attention to whether they are derived for use with a particular window function for improved accuracy. Dale B. Dalrymple
Reply by ●April 1, 20152015-04-01
On 3/31/15 8:07 PM, mfl wrote:> Hello Forum, > > given a N-point window h[n], how do I create an oversampled Fourier > transform H out of h[n]? I need to have very high resolution of the H so > that I can find out the magnitude of arbitrary frequency with little > frequency error. > > This is what I did: to oversample h[n] with factor 2, I first sampled the > window h with N * 2 points, and then simply FFT the 'new h' with N*2-point. > But the H with N*2 points looks very different from H with N points. What > am I doing wrong? >listen, ukelady, we *did* respond to this at the music-dsp mailing list and we *did* tell you about the quadratic interpolation of peaks and about **zero**-padding the time-domain data (which is h[n]) to get greater resolution (in a sense) in the frequency domain. one of the two is what you should do. interpolating h[n] will (if you interpolate well) have the effect of virtual zero-padding the frequency domain data and, in and of itself, will *not* increase resolution of the peaks in the frequency domain. so you'll get approximately the same answer here at comp.dsp as you did at music-dsp. good luck with your application, whatever it is. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●April 1, 20152015-04-01
Hi! Robert, sorry, I posted this question on both places at the same time, just hoping to get someone's attention. I didn't realise people are so supportive here and on the music-dsp. As a newbie I didn't see the link between these two forums. I'll for sure not to post the same question on both site again. I know you did answered about the zero padding and someone also mentioned about the interpolation technique. I asked Dale again about the keyword just to make sure he is not talking about something else. Sorry to waste your time on viewing the same post twice. I'm really sorry for that.>On 3/31/15 8:07 PM, mfl wrote: >> Hello Forum, >> >> given a N-point window h[n], how do I create an oversampled Fourier >> transform H out of h[n]? I need to have very high resolution of the Hso>> that I can find out the magnitude of arbitrary frequency with little >> frequency error. >> >> This is what I did: to oversample h[n] with factor 2, I first sampledthe>> window h with N * 2 points, and then simply FFT the 'new h' withN*2-point.>> But the H with N*2 points looks very different from H with N points.What>> am I doing wrong? >> > >listen, ukelady, we *did* respond to this at the music-dsp mailing list >and we *did* tell you about the quadratic interpolation of peaks and >about **zero**-padding the time-domain data (which is h[n]) to get >greater resolution (in a sense) in the frequency domain. > >one of the two is what you should do. interpolating h[n] will (if you >interpolate well) have the effect of virtual zero-padding the frequency >domain data and, in and of itself, will *not* increase resolution of the >peaks in the frequency domain. > >so you'll get approximately the same answer here at comp.dsp as you did >at music-dsp. > >good luck with your application, whatever it is. > > >-- > >r b-j rbj@audioimagination.com > >"Imagination is more important than knowledge."--------------------------------------- Posted through http://www.DSPRelated.com
Reply by ●April 2, 20152015-04-02
On Wed, 1 Apr 2015 12:58:56 -0700 (PDT), dbd <d.dalrymple@sbcglobal.net> wrote:>On Wednesday, April 1, 2015 at 12:20:24 PM UTC-7, 103...@dsprelated wrote: > >>=20 >> Thanks Mark and Dale for the suggestions!=20 >>=20 >> @Dale: is there any keywords to find out the alternative technique using >> interpolation? Is it called parabolic interpolator? > >"interpolated fft" and "peak interpolation" are common phrases. One of the = >interpolation methods is the parabolic. It is the know-nothing choice with = >three points and can be good enough. When looking at interpolation formulas= >, pay attention to whether they are derived for use with a particular windo= >w function for improved accuracy.What I did for my own use was a piecewise-linear interpolation. I generated sine waves at frequencies that were fractional increments of the spectral line spacing. I used 16ths. Then took the ratio between the two highest spectrum peaks for my FFT size (1024 samples) and stored in a 16-value table. This only needs to be done between a single pair of spectral lines, but the pair should not be too near either end of the spectrum. Repeat to create a separate table for each window function you want to use. Then on your actual spectrum, you determine the ratio of peak bin to its nearest neighbor and interpolate from the table. This gives about 50x resolution improvement, but please note that this is for a *single* peak, not for resolving adjacent peaks. Performance is poor for the lowest few spectral lines. (Maybe the top few as well... didn't test.) Best regards, Bob Masta DAQARTA v7.60 Data AcQuisition And Real-Time Analysis www.daqarta.com Scope, Spectrum, Spectrogram, Sound Level Meter Frequency Counter, Pitch Track, Pitch-to-MIDI FREE Signal Generator, DaqMusiq generator Science with your sound card!
