Dual FFT

Hi,

The following link shows the ADC values of 1024 samples of a waveform and
512 bins of the corresponding FFT.

http://pho.to/7ofZe

This represents a rather week input signal of aprox. 11.7mv p-p obtained by
placing the accelerometer near a speaker emitting a 121Hz tone. While there
is a small amount of noise present occasionally there is a larger spike
that appears for only one sample. This spike causes an equal amount energy
to be distributed across the entire spectrum as expected. Essentially this
lifts the baseline of the FFT from near zero to a value proportional to the
amplitude of the spike. Is there a standard method of detecting this and
compensating for it? I am considering taking an average across the spectrum
to find the baseline and then subtract this value from the magnitude of the
peaks I am interested in.

Another question, I have two identical channels being sampled
simultaneously and I need to calculate the FFT of both. If I recall
correctly I can calculate two 1024 pt FFTs simultaneously by using a 2048
pt FFT and loading the even samples from one channel and the odd samples
from the second channel. In the resulting FFT the even bins will hold the
result for one channel and the odd bins the second channel. Is this
correct?

Thanks again for all your help.
Rob

	 

_____________________________		
Posted through www.DSPRelated.com

On Fri, 07 Nov 2014 13:29:08 -0600, Robd wrote:

> Hi,
> 
> The following link shows the ADC values of 1024 samples of a waveform
> and 512 bins of the corresponding FFT.
> 
> http://pho.to/7ofZe
> 
> This represents a rather week input signal of aprox. 11.7mv p-p obtained
> by placing the accelerometer near a speaker emitting a 121Hz tone. While
> there is a small amount of noise present occasionally there is a larger
> spike that appears for only one sample. This spike causes an equal
> amount energy to be distributed across the entire spectrum as expected.
> Essentially this lifts the baseline of the FFT from near zero to a value
> proportional to the amplitude of the spike. Is there a standard method
> of detecting this and compensating for it? I am considering taking an
> average across the spectrum to find the baseline and then subtract this
> value from the magnitude of the peaks I am interested in.

I don't see the spike in your picture.  Time domain problems should be 
dealt with in the time domain, not after you get things into the frequency 
domain.  If you can reliably detect such spikes, then deal with them in 
your data.

Better yet, fix your measuring system so that you don't get spurious 
spikes!

> Another question, I have two identical channels being sampled
> simultaneously and I need to calculate the FFT of both. If I recall
> correctly I can calculate two 1024 pt FFTs simultaneously by using a
> 2048 pt FFT and loading the even samples from one channel and the odd
> samples from the second channel. In the resulting FFT the even bins will
> hold the result for one channel and the odd bins the second channel. Is
> this correct?

That doesn't sound right at all.  Why confuse things?  Just do two FFTs.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

>On Fri, 07 Nov 2014 13:29:08 -0600, Robd wrote:
>
>> Hi,
>> 
>> The following link shows the ADC values of 1024 samples of a waveform
>> and 512 bins of the corresponding FFT.
>> 
>> http://pho.to/7ofZe
>> 
>> This represents a rather week input signal of aprox. 11.7mv p-p
obtained
>> by placing the accelerometer near a speaker emitting a 121Hz tone.
While
>> there is a small amount of noise present occasionally there is a larger
>> spike that appears for only one sample. This spike causes an equal
>> amount energy to be distributed across the entire spectrum as expected.
>> Essentially this lifts the baseline of the FFT from near zero to a
value
>> proportional to the amplitude of the spike. Is there a standard method
>> of detecting this and compensating for it? I am considering taking an
>> average across the spectrum to find the baseline and then subtract this
>> value from the magnitude of the peaks I am interested in.
>
>I don't see the spike in your picture.  Time domain problems should be 
>dealt with in the time domain, not after you get things into the frequency

>domain.  If you can reliably detect such spikes, then deal with them in 
>your data.
>
>Better yet, fix your measuring system so that you don't get spurious 
>spikes!
>
>> Another question, I have two identical channels being sampled
>> simultaneously and I need to calculate the FFT of both. If I recall
>> correctly I can calculate two 1024 pt FFTs simultaneously by using a
>> 2048 pt FFT and loading the even samples from one channel and the odd
>> samples from the second channel. In the resulting FFT the even bins
will
>> hold the result for one channel and the odd bins the second channel. Is
>> this correct?
>
>That doesn't sound right at all.  Why confuse things?  Just do two FFTs.
>
>-- 
>
>Tim Wescott
>Wescott Design Services
>http://www.wescottdesign.com
>

Hi Tim,

No, the image I posted was a "clean" one. I can also post one with noise if
anyone is interested. Of course I am working on determining the source of
this noise (spike) and eliminate it. I have removed the accelerometer and
grounded the input and the noise is still present so it appears to be being
coupled into the analogue signal after the filtering. It would seem to be
external noise entering through the power lines. I plan to try adding a
ferrite core to my DC power lines. Internally all my voltages are supplied
from switching regulators which appear to be clean.

As for the dual FFT, I remember reading something similar in the past and
have been trying to find it again. From what I have found so far I
understand that the samples from one channel are loaded into the real part
and the second channel into the imaginary part. The two results are then
extracted from the resulting FFT. The FFT is still only 1024 and not 2048.
I am still reading.

Rob
	 

_____________________________		
Posted through www.DSPRelated.com

On 11/7/2014 2:29 PM, Robd wrote:
> Hi,
>
> The following link shows the ADC values of 1024 samples of a waveform and
> 512 bins of the corresponding FFT.
>
> http://pho.to/7ofZe
>
> This represents a rather week input signal of aprox. 11.7mv p-p obtained by
> placing the accelerometer near a speaker emitting a 121Hz tone. While there
> is a small amount of noise present occasionally there is a larger spike
> that appears for only one sample. This spike causes an equal amount energy
> to be distributed across the entire spectrum as expected. Essentially this
> lifts the baseline of the FFT from near zero to a value proportional to the
> amplitude of the spike. Is there a standard method of detecting this and
> compensating for it? I am considering taking an average across the spectrum
> to find the baseline and then subtract this value from the magnitude of the
> peaks I am interested in.
>
> Another question, I have two identical channels being sampled
> simultaneously and I need to calculate the FFT of both. If I recall
> correctly I can calculate two 1024 pt FFTs simultaneously by using a 2048
> pt FFT and loading the even samples from one channel and the odd samples
> from the second channel. In the resulting FFT the even bins will hold the
> result for one channel and the odd bins the second channel. Is this
> correct?

I'm not sure you are describing it correctly, but yes, there is a way to 
save computations when performing FFTs on real data.  What I have seen 
wraps the real data into half as many points of complex data.  In the 
end you perform one less passes using half as many points, then follow 
it up with a final pass to correctly produce the final result.  I'm 
pretty sure this does not use "odd" and "even" data samples in the sense 
you are referring to.  Odd and even pertain to symmetry properties of 
the FFT which I believe this process is making use of in the final pass.

It has been too long since I did this sort of work to remember the 
details.  If you search on "real FFT" I expect you can find all sorts of 
references.  Unfortunately most of them will be rather theoretical 
rather than a simple explanation of what you need to do.

I will say that I'm pretty sure Tim is right.  Your savings in 
computation will come from the fact that your data is real and not 
complex.  Rather than combining the data into one FFT, I expect you will 
find more info on how to do a half size FFT to process your real data 
and you can then just do two of them.  But I could be wrong.  There may 
very well be an equivalent way to process two independent real data sets 
in a single FFT by taking advantage of the odd and even symmetries of 
the FFT.

-- 

Rick

Your dB scale must be wrong, there's no way a speaker plus accelerometer will give you 170dB distortion. 

Bob

On 11/7/2014 3:12 PM, Robd wrote:
>
> As for the dual FFT, I remember reading something similar in the past and
> have been trying to find it again. From what I have found so far I
> understand that the samples from one channel are loaded into the real part
> and the second channel into the imaginary part. The two results are then
> extracted from the resulting FFT. The FFT is still only 1024 and not 2048.
> I am still reading.

That sounds like what I remember.  I don't remember for sure, but there 
is a way to separate the data from the imaginary and the real 
components.  A spectrum from all real data is symmetrical about the 
Nyquist frequency.  I want to say the real input data produces even 
symmetry in the spectrum and the imaginary input data produces odd 
symmetry.  So to recover the spectrum from the real part of the data you 
add the two halves of the spectrum.  To get the spectrum from the 
imaginary portion the two halves of the spectrum are added.

Please don't take this as accurate.  It was some 15 years ago I worked 
with FFTs.

-- 

Rick

On Fri, 07 Nov 2014 14:12:58 -0600, Robd wrote:

>>On Fri, 07 Nov 2014 13:29:08 -0600, Robd wrote:
>>
>>> Hi,
>>> 
>>> The following link shows the ADC values of 1024 samples of a waveform
>>> and 512 bins of the corresponding FFT.
>>> 
>>> http://pho.to/7ofZe
>>> 
>>> This represents a rather week input signal of aprox. 11.7mv p-p
> obtained
>>> by placing the accelerometer near a speaker emitting a 121Hz tone.
> While
>>> there is a small amount of noise present occasionally there is a
>>> larger spike that appears for only one sample. This spike causes an
>>> equal amount energy to be distributed across the entire spectrum as
>>> expected.
>>> Essentially this lifts the baseline of the FFT from near zero to a
> value
>>> proportional to the amplitude of the spike. Is there a standard method
>>> of detecting this and compensating for it? I am considering taking an
>>> average across the spectrum to find the baseline and then subtract
>>> this value from the magnitude of the peaks I am interested in.
>>
>>I don't see the spike in your picture.  Time domain problems should be
>>dealt with in the time domain, not after you get things into the
>>frequency
> 
>>domain.  If you can reliably detect such spikes, then deal with them in
>>your data.
>>
>>Better yet, fix your measuring system so that you don't get spurious
>>spikes!
>>
>>> Another question, I have two identical channels being sampled
>>> simultaneously and I need to calculate the FFT of both. If I recall
>>> correctly I can calculate two 1024 pt FFTs simultaneously by using a
>>> 2048 pt FFT and loading the even samples from one channel and the odd
>>> samples from the second channel. In the resulting FFT the even bins
> will
>>> hold the result for one channel and the odd bins the second channel.
>>> Is this correct?
>>
>>That doesn't sound right at all.  Why confuse things?  Just do two FFTs.
>>
>>--
>>
>>Tim Wescott Wescott Design Services http://www.wescottdesign.com
>>
>>
> Hi Tim,
> 
> No, the image I posted was a "clean" one. I can also post one with noise
> if anyone is interested. Of course I am working on determining the
> source of this noise (spike) and eliminate it. I have removed the
> accelerometer and grounded the input and the noise is still present so
> it appears to be being coupled into the analogue signal after the
> filtering. It would seem to be external noise entering through the power
> lines. I plan to try adding a ferrite core to my DC power lines.
> Internally all my voltages are supplied from switching regulators which
> appear to be clean.
> 
> As for the dual FFT, I remember reading something similar in the past
> and have been trying to find it again. From what I have found so far I
> understand that the samples from one channel are loaded into the real
> part and the second channel into the imaginary part. The two results are
> then extracted from the resulting FFT. The FFT is still only 1024 and
> not 2048. I am still reading.

That you can do.  You utilize the fact that when you take the FFT of all-
real data, the result is a function whose real part is even around zero, 
and whose imaginary part is odd around zero.  By superposition, if you 
take the FFT of all imaginary data, the even-ness and odd-ness are 
reversed.

It's conceptually pretty easy to extract an even and an odd part from an 
arbitrary function, although you end up doing more math.

All of this is in pursuit of a small reduction in execution time, which 
can be gotten far more easily by using an FFT routine that's optimized to 
work on all-real data, calling it twice with the different data, and then 
not having to do the math on the results.

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

On Friday, November 7, 2014 6:15:33 PM UTC-5, Tim Wescott wrote:
> On Fri, 07 Nov 2014 14:12:58 -0600, Robd wrote:
> 
> >>On Fri, 07 Nov 2014 13:29:08 -0600, Robd wrote:
> >>
> >>> Hi,
> >>> 
> >>> The following link shows the ADC values of 1024 samples of a waveform
> >>> and 512 bins of the corresponding FFT.
> >>> 
> >>> http://pho.to/7ofZe
> >>> 
> >>> This represents a rather week input signal of aprox. 11.7mv p-p
> > obtained
> >>> by placing the accelerometer near a speaker emitting a 121Hz tone.
> > While
> >>> there is a small amount of noise present occasionally there is a
> >>> larger spike that appears for only one sample. This spike causes an
> >>> equal amount energy to be distributed across the entire spectrum as
> >>> expected.
> >>> Essentially this lifts the baseline of the FFT from near zero to a
> > value
> >>> proportional to the amplitude of the spike. Is there a standard method
> >>> of detecting this and compensating for it? I am considering taking an
> >>> average across the spectrum to find the baseline and then subtract
> >>> this value from the magnitude of the peaks I am interested in.
> >>
> >>I don't see the spike in your picture.  Time domain problems should be
> >>dealt with in the time domain, not after you get things into the
> >>frequency
> > 
> >>domain.  If you can reliably detect such spikes, then deal with them in
> >>your data.
> >>
> >>Better yet, fix your measuring system so that you don't get spurious
> >>spikes!
> >>
> >>> Another question, I have two identical channels being sampled
> >>> simultaneously and I need to calculate the FFT of both. If I recall
> >>> correctly I can calculate two 1024 pt FFTs simultaneously by using a
> >>> 2048 pt FFT and loading the even samples from one channel and the odd
> >>> samples from the second channel. In the resulting FFT the even bins
> > will
> >>> hold the result for one channel and the odd bins the second channel.
> >>> Is this correct?
> >>
> >>That doesn't sound right at all.  Why confuse things?  Just do two FFTs.
> >>
> >>--
> >>
> >>Tim Wescott Wescott Design Services http://www.wescottdesign.com
> >>
> >>
> > Hi Tim,
> > 
> > No, the image I posted was a "clean" one. I can also post one with noise
> > if anyone is interested. Of course I am working on determining the
> > source of this noise (spike) and eliminate it. I have removed the
> > accelerometer and grounded the input and the noise is still present so
> > it appears to be being coupled into the analogue signal after the
> > filtering. It would seem to be external noise entering through the power
> > lines. I plan to try adding a ferrite core to my DC power lines.
> > Internally all my voltages are supplied from switching regulators which
> > appear to be clean.
> > 
> > As for the dual FFT, I remember reading something similar in the past
> > and have been trying to find it again. From what I have found so far I
> > understand that the samples from one channel are loaded into the real
> > part and the second channel into the imaginary part. The two results are
> > then extracted from the resulting FFT. The FFT is still only 1024 and
> > not 2048. I am still reading.
> 
> That you can do.  You utilize the fact that when you take the FFT of all-
> real data, the result is a function whose real part is even around zero, 
> and whose imaginary part is odd around zero.  By superposition, if you 
> take the FFT of all imaginary data, the even-ness and odd-ness are 
> reversed.
> 
> It's conceptually pretty easy to extract an even and an odd part from an 
> arbitrary function, although you end up doing more math.
> 
> All of this is in pursuit of a small reduction in execution time, which 
> can be gotten far more easily by using an FFT routine that's optimized to 
> work on all-real data, calling it twice with the different data, and then 
> not having to do the math on the results.
> 
> -- 
> 
> Tim Wescott
> Wescott Design Services
> http://www.wescottdesign.com

Yes, you can transform two real valued sequences by using one complex-in/out FFT:

http://fftguru.com/fftguru.com.tutorial2.pdf

The first technique desribed above is the one you want.  You end up doing one N size complex-in/out FFT plus some bookkeeping instead of two N size complex-in/out FFTs (and no bookkeeping).

But if you have an FFT optimized for real-only inputs, you may (or may not) be better off doing two N size real-in/complex out FFTs - it all depends on the relative efficiency of the programs.

Kevin McGee

On Friday, November 7, 2014 1:29:12 PM UTC-6, Robd wrote:
> Hi,
> 
> The following link shows the ADC values of 1024 samples of a waveform and
> 512 bins of the corresponding FFT.
> 
> http://pho.to/7ofZe
> 
> This represents a rather week input signal of aprox. 11.7mv p-p obtained by
> placing the accelerometer near a speaker emitting a 121Hz tone. While there
> is a small amount of noise present occasionally there is a larger spike
> that appears for only one sample. This spike causes an equal amount energy
> to be distributed across the entire spectrum as expected. Essentially this
> lifts the baseline of the FFT from near zero to a value proportional to the
> amplitude of the spike. Is there a standard method of detecting this and
> compensating for it? I am considering taking an average across the spectrum
> to find the baseline and then subtract this value from the magnitude of the
> peaks I am interested in.
> 
> Another question, I have two identical channels being sampled
> simultaneously and I need to calculate the FFT of both. If I recall
> correctly I can calculate two 1024 pt FFTs simultaneously by using a 2048
> pt FFT and loading the even samples from one channel and the odd samples
> from the second channel. In the resulting FFT the even bins will hold the
> result for one channel and the odd bins the second channel. Is this
> correct?
> 
> Thanks again for all your help.
> Rob
> 
> 	 
> 
> _____________________________		
> Posted through www.DSPRelated.com

Look into the median filter. If the spike is only one sample wide, then a 5-element median filter will eliminate it.

On 11/7/2014 7:04 PM, kevinjmcee wrote:
> On Friday, November 7, 2014 6:15:33 PM UTC-5, Tim Wescott wrote:
>> On Fri, 07 Nov 2014 14:12:58 -0600, Robd wrote:
>>
>>>> On Fri, 07 Nov 2014 13:29:08 -0600, Robd wrote:
>>>>
>>>>> Hi,
>>>>>
>>>>> The following link shows the ADC values of 1024 samples of a waveform
>>>>> and 512 bins of the corresponding FFT.
>>>>>
>>>>> http://pho.to/7ofZe
>>>>>
>>>>> This represents a rather week input signal of aprox. 11.7mv p-p
>>> obtained
>>>>> by placing the accelerometer near a speaker emitting a 121Hz tone.
>>> While
>>>>> there is a small amount of noise present occasionally there is a
>>>>> larger spike that appears for only one sample. This spike causes an
>>>>> equal amount energy to be distributed across the entire spectrum as
>>>>> expected.
>>>>> Essentially this lifts the baseline of the FFT from near zero to a
>>> value
>>>>> proportional to the amplitude of the spike. Is there a standard method
>>>>> of detecting this and compensating for it? I am considering taking an
>>>>> average across the spectrum to find the baseline and then subtract
>>>>> this value from the magnitude of the peaks I am interested in.
>>>>
>>>> I don't see the spike in your picture.  Time domain problems should be
>>>> dealt with in the time domain, not after you get things into the
>>>> frequency
>>>
>>>> domain.  If you can reliably detect such spikes, then deal with them in
>>>> your data.
>>>>
>>>> Better yet, fix your measuring system so that you don't get spurious
>>>> spikes!
>>>>
>>>>> Another question, I have two identical channels being sampled
>>>>> simultaneously and I need to calculate the FFT of both. If I recall
>>>>> correctly I can calculate two 1024 pt FFTs simultaneously by using a
>>>>> 2048 pt FFT and loading the even samples from one channel and the odd
>>>>> samples from the second channel. In the resulting FFT the even bins
>>> will
>>>>> hold the result for one channel and the odd bins the second channel.
>>>>> Is this correct?
>>>>
>>>> That doesn't sound right at all.  Why confuse things?  Just do two FFTs.
>>>>
>>>> --
>>>>
>>>> Tim Wescott Wescott Design Services http://www.wescottdesign.com
>>>>
>>>>
>>> Hi Tim,
>>>
>>> No, the image I posted was a "clean" one. I can also post one with noise
>>> if anyone is interested. Of course I am working on determining the
>>> source of this noise (spike) and eliminate it. I have removed the
>>> accelerometer and grounded the input and the noise is still present so
>>> it appears to be being coupled into the analogue signal after the
>>> filtering. It would seem to be external noise entering through the power
>>> lines. I plan to try adding a ferrite core to my DC power lines.
>>> Internally all my voltages are supplied from switching regulators which
>>> appear to be clean.
>>>
>>> As for the dual FFT, I remember reading something similar in the past
>>> and have been trying to find it again. From what I have found so far I
>>> understand that the samples from one channel are loaded into the real
>>> part and the second channel into the imaginary part. The two results are
>>> then extracted from the resulting FFT. The FFT is still only 1024 and
>>> not 2048. I am still reading.
>>
>> That you can do.  You utilize the fact that when you take the FFT of all-
>> real data, the result is a function whose real part is even around zero,
>> and whose imaginary part is odd around zero.  By superposition, if you
>> take the FFT of all imaginary data, the even-ness and odd-ness are
>> reversed.
>>
>> It's conceptually pretty easy to extract an even and an odd part from an
>> arbitrary function, although you end up doing more math.
>>
>> All of this is in pursuit of a small reduction in execution time, which
>> can be gotten far more easily by using an FFT routine that's optimized to
>> work on all-real data, calling it twice with the different data, and then
>> not having to do the math on the results.
>>
>> --
>>
>> Tim Wescott
>> Wescott Design Services
>> http://www.wescottdesign.com
>
> Yes, you can transform two real valued sequences by using one complex-in/out FFT:
>
> http://fftguru.com/fftguru.com.tutorial2.pdf
>
> The first technique desribed above is the one you want.  You end up doing one N size complex-in/out FFT plus some bookkeeping instead of two N size complex-in/out FFTs (and no bookkeeping).
>
> But if you have an FFT optimized for real-only inputs, you may (or may not) be better off doing two N size real-in/complex out FFTs - it all depends on the relative efficiency of the programs.


I think the two are largely equivalent, N point FFT plus house keeping 
to separate the two separate results or two N-1 point FFTs plus a 
special butterfly pass to complete the final pass of each FFT.  I expect 
the two processes will be very similar in processing time.

BTW, I did a quick search and the odd/even thing the OP mentioned is how 
they do the FFT of a single block of real data.  By splitting the input 
into odd and even data the output of the N/2 FFT is the appropriate 
input for the final pass of the N point FFT.  The FFT of two real 
sequences does not deal with odd and even samples from the two 
sequences, but processes them intact.

-- 

Rick