practical FFT

>Right at the Nyquist frequency, which is useless.  Suppose your sampling
>hit at every zero crossing, it would appear that there is no signal at
>all.
>
>Signals with a higher frequency than the Nyquist frequency will appear
to
>be a signal of a lower frequency.  This phenomena is called "aliasing".
>
>This also means when you detect a signal within your frame, you can't be
>sure it isn't an alias unless you know something about the signal you
are
>analysing that rules it out.
>
>This is reflected in my frequency formula because the result on an
inverse
>cosine function can have many values.

Thanks. I get it. I did realize sampling rate has to be > 2*Nyquist (and
no equal to).

>This is sort of an apples and oranges question, which is why I avoided
the
>term "rate" in my units labels.  The DFT itself does not care what the
>sampling rate is.  The Nyquist frequency will always be located at bin
>N/2.  (Which corresponds to two samples per signal cycle.)

I don't know if I am using terms correctly. But if N is increased then we
have more samples for a given frame. In such a case, delta frequency per
bin would decrease providing more resolution.

>Hope this helps.  It can be confusing, until you "get it", of course.

Thanks a lot and I ever indebted to the esteemed senior members on this
forum ...

---------------------------------------
Posted through http://www.DSPRelated.com

>
>I don't know if I am using terms correctly. But if N is increased then
we
>have more samples for a given frame. In such a case, delta frequency per
>bin would decrease providing more resolution.
>

Don't sweat using the terms incorrectly, that's part of the learning
process.

By a given frame, I assume you mean time frame, so increasing N is the
same as increasing the sampling rate.  This will *not* have any effect on
"delta frequency per bin".  Bin 3 will still refer to a signal with 3
cycles per frame and bin 4 will still refer to 4 cycles per frame.  No
change in the difference whatsoever.  What does increase is the range of
frequencies that can be detected without being aliases.

Sticking with your previous example numbers.  If you have a one second
interval with 200 samples, then the range of frequencies is from 0 to 100
Hz.  If you up the sampling rate by a factor of 10, and thus the number of
samples for that interval by a factor of 10, so now you have 2000 samples,
the limit frequency is 1000Hz.

If you have a signal of 3.5 Hz, the peak will be at bins 3 and 4 in either
the 200 or 2000 point DFT.

If you have two tones, say 3.2 Hz and 3.6 Hz as your signal, it won't look
much different superficially.

However if you expand your interval by a factor of 10 (up to 10 seconds
now), whether you use 200 points or 2000 points, the two tones will be at
bins 32 and 36, whereas the 3.5 Hz tone would be at bin 35.  It would be
easy to tell them apart.

Ced
---------------------------------------
Posted through http://www.DSPRelated.com

On Fri, 08 Jan 2016 10:38:13 -0600, "Cedron"
<103185@DSPRelated> wrote:

>>
>>Dear Cedron,
>>
>>My sincere apologies. My question above has nothing to do with PRNG I am
>>discussing in the other thread.
>>
>>So, to understand better. Are half the bins at the FFT out always sort
>of
>>throw away?. 
>
>Yes, for real valued signals.  For complex valued signals interpreting the
>upper half of the DFT as "negative frequencies", is more meaningful.

Not meaning to confuse the learning process with "too much,
too soon", I just want to assure the OP that people don't
*really* waste half the DFT when they have real-valued data.


Instead, they store even-numbered time samples as real and
odd-numbered as imaginary before taking the DFT, then
afterwards perform a complex-to-real conversion.  That way
if you start with N real time samples you get N/2 frequency
bins, where the N/2 bin is the Nyquist.  For your 200
samples, you'd still get 100 bins, but all of them would be
useful. (Actually, the usual approach is such that bin 0
would be DC, and bin 99 would be one bin less than the
Nyquist.)

Best regards,


Bob Masta
 
              DAQARTA  v8.00
   Data AcQuisition And Real-Time Analysis
              www.daqarta.com
Scope, Spectrum, Spectrogram, Sound Level Meter
 Frequency Counter, Pitch Track, Pitch-to-MIDI 
FREE 8-channel Signal Generator, DaqMusiq generator    
          Science with your sound card!

On Sat, 09 Jan 2016 14:11:53 GMT, N0Spam@daqarta.com (Bob Masta)
wrote:

>On Fri, 08 Jan 2016 10:38:13 -0600, "Cedron"
><103185@DSPRelated> wrote:
>
>>>
>>>Dear Cedron,
>>>
>>>My sincere apologies. My question above has nothing to do with PRNG I am
>>>discussing in the other thread.
>>>
>>>So, to understand better. Are half the bins at the FFT out always sort
>>of
>>>throw away?. 
>>
>>Yes, for real valued signals.  For complex valued signals interpreting the
>>upper half of the DFT as "negative frequencies", is more meaningful.
>
>Not meaning to confuse the learning process with "too much,
>too soon", I just want to assure the OP that people don't
>*really* waste half the DFT when they have real-valued data.
>
>
>Instead, they store even-numbered time samples as real and
>odd-numbered as imaginary before taking the DFT, then
>afterwards perform a complex-to-real conversion.  That way
>if you start with N real time samples you get N/2 frequency
>bins, where the N/2 bin is the Nyquist.  For your 200
>samples, you'd still get 100 bins, but all of them would be
>useful. (Actually, the usual approach is such that bin 0
>would be DC, and bin 99 would be one bin less than the
>Nyquist.)
>
>Best regards,

There are all kinds of crazy tricks like that, like simultaneously
transforming two real-valued vectors with a single DFT.  Rick Lyons
has done several blogs on various other similar non-intuitive tricks,
and some of the books written specifically about the FT/DFT/FFT cover
many more.

It gets hard to keep track of all of them.


Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

>
>Not meaning to confuse the learning process with "too much,
>too soon", I just want to assure the OP that people don't
>*really* waste half the DFT when they have real-valued data.
>
>
>Instead, they store even-numbered time samples as real and
>odd-numbered as imaginary before taking the DFT, then
>afterwards perform a complex-to-real conversion.  That way
>if you start with N real time samples you get N/2 frequency
>bins, where the N/2 bin is the Nyquist.  For your 200
>samples, you'd still get 100 bins, but all of them would be
>useful. (Actually, the usual approach is such that bin 0
>would be DC, and bin 99 would be one bin less than the
>Nyquist.)
>
>Best regards,
>
>
>Bob Masta
> 

I had my doubts about this so I did a little math and a little testing. 
This technique does not work as advertised.  There is no such thing as a
free lunch here either.  The Nyquist frequency gets moved to N/4, so the
bins between N/4 and N/2 are the new redundant upper half.  Any tones in
the signal in this range will show up in the 0 to N/4 buckets.  This is
not true for the full N point DFT.

In addition, by aligning the interleaved signal, an implicit phase shift
of 2Pi/N is introduced.  This has the effect of skewing the results of the
DFT that is produced.  The effect is more pronounced at the higher
frequencies where the phase shift is significant in size compared to the
wavelengths.

If you are only going to use a N/2 DFT, you are better off just using
either the even or the odd indexed values as a real signal.

All and all, people may use this, but I am not adding it to my toolbox. 
There is no need to calculate the upper half of the DFT when you have a
real valued signal.  I don't see a need for a complex signal either.  With
a brute force DFT, this saves half the calculations.  Having a specific
DFT routine for real signals vs complex signals will also save a bunch of
calculations.  (Multiplying a bin value by a scalar is cheaper than
multiplying it by a complex value).

Ced
---------------------------------------
Posted through http://www.DSPRelated.com

On Sun, 10 Jan 2016 16:20:05 -0600, "Cedron"
<103185@DSPRelated> wrote:

>>
>>Not meaning to confuse the learning process with "too much,
>>too soon", I just want to assure the OP that people don't
>>*really* waste half the DFT when they have real-valued data.
>>
>>
>>Instead, they store even-numbered time samples as real and
>>odd-numbered as imaginary before taking the DFT, then
>>afterwards perform a complex-to-real conversion.  That way
>>if you start with N real time samples you get N/2 frequency
>>bins, where the N/2 bin is the Nyquist.  For your 200
>>samples, you'd still get 100 bins, but all of them would be
>>useful. (Actually, the usual approach is such that bin 0
>>would be DC, and bin 99 would be one bin less than the
>>Nyquist.)
>>
>>Best regards,
>>
>>
>>Bob Masta
>> 
>
>I had my doubts about this so I did a little math and a little testing. 
>This technique does not work as advertised.  There is no such thing as a
>free lunch here either.  The Nyquist frequency gets moved to N/4, so the
>bins between N/4 and N/2 are the new redundant upper half.  Any tones in
>the signal in this range will show up in the 0 to N/4 buckets.  This is
>not true for the full N point DFT.
>
>In addition, by aligning the interleaved signal, an implicit phase shift
>of 2Pi/N is introduced.  This has the effect of skewing the results of the
>DFT that is produced.  The effect is more pronounced at the higher
>frequencies where the phase shift is significant in size compared to the
>wavelengths.
>
>If you are only going to use a N/2 DFT, you are better off just using
>either the even or the odd indexed values as a real signal.
>
>All and all, people may use this, but I am not adding it to my toolbox. 
>There is no need to calculate the upper half of the DFT when you have a
>real valued signal.  I don't see a need for a complex signal either.  With
>a brute force DFT, this saves half the calculations.  Having a specific
>DFT routine for real signals vs complex signals will also save a bunch of
>calculations.  (Multiplying a bin value by a scalar is cheaper than
>multiplying it by a complex value).
>


I didn't give much explanation, so I'm not sure exactly what
technique you implemented.  I first saw this in "Musical
Applications of Microprocessors" by Hal Chamberlin, 2nd
edition, 1985, pg 455: "Modification for Real Data".  I
believe it is the same as the one used in the TI paper
"Efficient FFT Computation of Real Input", and I'm pretty
sure I've seen it other places as well.  (I think even
including the old  IEEE "Programs for Digital Signal
Processing"... with code in Fortran!)

The Nyquist frequency is still Fs/2 as always.  If you use N
time samples, it comes out at N/2, not N/4.  If I had to
guess at why you are getting N/4, I'd say you are probably
not doing the whole process including the prescribed
complex-to-real at the end.  This is a specific operation
that reshuffles the data, not some general-purpose thing
that you can intuit from knowledge of complex numbers.

No, there is no free lunch...but there is no waste either.
(As there would be by nulling half the data going into the
FFT.)

And yes, it definitely works as advertised.  There may be
lots of other methods, but this one has been thoroughly
tested.  I've been using it for decades, and I *kinda*
think I'd have noticed if it had only half the advertised
frequency range!

Best regards,


Bob Masta
 
              DAQARTA  v8.00
   Data AcQuisition And Real-Time Analysis
              www.daqarta.com
Scope, Spectrum, Spectrogram, Sound Level Meter
 Frequency Counter, Pitch Track, Pitch-to-MIDI 
FREE 8-channel Signal Generator, DaqMusiq generator    
          Science with your sound card!

>Sticking with your previous example numbers.  If you have a one second
>interval with 200 samples, then the range of frequencies is from 0 to
100
>Hz.  If you up the sampling rate by a factor of 10, and thus the number
of
>samples for that interval by a factor of 10, so now you have 2000
samples,
>the limit frequency is 1000Hz.
>
>If you have a signal of 3.5 Hz, the peak will be at bins 3 and 4 in
either
>the 200 or 2000 point DFT.
>
>If you have two tones, say 3.2 Hz and 3.6 Hz as your signal, it won't
look
>much different superficially.
>
>However if you expand your interval by a factor of 10 (up to 10 seconds
>now), whether you use 200 points or 2000 points, the two tones will be
at
>bins 32 and 36, whereas the 3.5 Hz tone would be at bin 35.  It would be
>easy to tell them apart.

Dear Cedron,

I have tried a simple FFT example.

I have used,
 *F2 = 10
 *Length of signal = 10 samples; this gives one full cycle of a sine
signal
 *Freq = 1 Hz

The results are consistent with expected values. Peak bin at 2 and some
distribution around this bin.

Now, I increase samples to 20 to get 2 cycles of sine wave. No change in
frequency. Here, bin 3 has max value. 

However, there are 2 doubts I have after looking at the result.

* When I increase from 1 sample to 2 samples of input, I assumed that the
amplitude of bin 1 in the second case would be double but amplitude in
both the cases are 1

* When length of the signal is 10, I assume that the complex exponential
signal associated with bin 2 completes 1 cycle. When signal length is
changed to 20, would complex exponential at bin 2 complete 1 cycle and
complex exponential at bin 3 complete 2 cycles?
---------------------------------------
Posted through http://www.DSPRelated.com

[...snip...]
>
>The Nyquist frequency is still Fs/2 as always.  If you use N
>time samples, it comes out at N/2, not N/4.  If I had to
>guess at why you are getting N/4, I'd say you are probably
>not doing the whole process including the prescribed
>complex-to-real at the end.  This is a specific operation
>that reshuffles the data, not some general-purpose thing
>that you can intuit from knowledge of complex numbers.
>
>No, there is no free lunch...but there is no waste either.
>(As there would be by nulling half the data going into the
>FFT.)
>
>And yes, it definitely works as advertised.  There may be
>lots of other methods, but this one has been thoroughly
>tested.  I've been using it for decades, and I *kinda*
>think I'd have noticed if it had only half the advertised
>frequency range!
>
>Best regards,
>
>
>Bob Masta
> 
>              DAQARTA  v8.00
>   Data AcQuisition And Real-Time Analysis
>              www.daqarta.com
>Scope, Spectrum, Spectrogram, Sound Level Meter
> Frequency Counter, Pitch Track, Pitch-to-MIDI 
>FREE 8-channel Signal Generator, DaqMusiq generator    
>          Science with your sound card!


I stand corrected.  After following the documentation and some more
testing, and a few false paths, I was able to get it to work.  I had not
performed the last step which you called a "complex-to-real" conversion. 
It is actually a "complex-to-complex" conversion.  The N/2 DFT is the N
DFT sold of "folded over", and I think the last step is better
characterized as performing a series of two equation two unknowns
solutions in order to "unfold" the DFT.

The main false path was thinking I needed a bit-reversed DFT.

For the N/2 DFT, the Nyquist limit is still N/4, I stand by that.  But
when you "unfold it" you do indeed get the equivalent result of a N DFT
with a N/2 Nyquist limit.

The last step is actually rather calculation intensive, so there has to be
a cutoff point for which doing a real valued N point DFT is more efficient
than this technique.  For larger values of N, this technique will be more
efficient.

Ced


---------------------------------------
Posted through http://www.DSPRelated.com

>
>Dear Cedron,
>
>I have tried a simple FFT example.
>
>I have used,
> *F2 = 10
> *Length of signal = 10 samples; this gives one full cycle of a sine
>signal
> *Freq = 1 Hz
>
>The results are consistent with expected values. Peak bin at 2 and some
>distribution around this bin.
>
>Now, I increase samples to 20 to get 2 cycles of sine wave. No change in
>frequency. Here, bin 3 has max value. 
>
>However, there are 2 doubts I have after looking at the result.
>
>* When I increase from 1 sample to 2 samples of input, I assumed that
the
>amplitude of bin 1 in the second case would be double but amplitude in
>both the cases are 1
>
>* When length of the signal is 10, I assume that the complex exponential
>signal associated with bin 2 completes 1 cycle. When signal length is
>changed to 20, would complex exponential at bin 2 complete 1 cycle and
>complex exponential at bin 3 complete 2 cycles?
>---------------------------------------
>Posted through http://www.DSPRelated.com

It took me a little while to recognize that you are using Matlab indexing.
 I'm not a Matlab user, but I certainly have read plenty of complaints
here on comp.dsp about its one-based indexing.

From what you are describing, Matlab uses a 2/N normalization factor.  My
preference is 1/N.  The other common choices are 1 (no normalization) and
1/sqrt(N) (unitary normalization).  Don't worry about it really means, the
normalization factor is what the results of the DFT summation are
multiplied by to make a bin value.

To correct your terminology just a little bit:  "Length of Signal" would
be better called "Wavelength" or "Length of one cycle" (which you call it
afterward).  "Amplitude" relates to the signal in the time domain.  For a
sine wave it is the height of the peak.  "Magnitude" is a property of a
complex number, which the bin values are.  With a normalization factor of
1/N, the Magnitude of a bin value for an integer frequency pure tone (sine
wave) will be 1/2 the Amplitude.

For your first doubt, your results are correct.  No matter how many whole
cycles there are, the value in the bin will be the same for the same size
amplitude.

For your second doubt, you can see why one-based indexing is inappropriate
for this application.  It's a lot nicer to use the common referencing
which is zero-based so bin 0 refers to the DC component, bin 1 means one
cyle per frame, bin 2 means two cycles per frame, etc.  Instead with
Matlab's one-based indexing you get, bin 1 is the DC, bin 2 is one cycle
per frame, etc.

Hope this helps.  Sorry for a delay in answering, I've been busy.

Ced

---------------------------------------
Posted through http://www.DSPRelated.com

>Sticking with your previous example numbers.  If you have a one second
>interval with 200 samples, then the range of frequencies is from 0 to
100
>Hz.  If you up the sampling rate by a factor of 10, and thus the number
of
>samples for that interval by a factor of 10, so now you have 2000
samples,
>the limit frequency is 1000Hz.
>
>If you have a signal of 3.5 Hz, the peak will be at bins 3 and 4 in
either
>the 200 or 2000 point DFT.
>
>If you have two tones, say 3.2 Hz and 3.6 Hz as your signal, it won't
look
>much different superficially.
>
>However if you expand your interval by a factor of 10 (up to 10 seconds
>now), whether you use 200 points or 2000 points, the two tones will be
at
>bins 32 and 36, whereas the 3.5 Hz tone would be at bin 35.  It would be
>easy to tell them apart.

Dear Cedron & others,

I am opening an old topic.

I am not able to fully appreciate the last paragraph. I have worked out a
Matlab example and actually see the effect of increasing the increasing
FFT interval. However, I am looking for intuitive explanation on how
increasing the interval can change the bin values in the FFT

---------------------------------------
Posted through http://www.DSPRelated.com