Forums

practical FFT

Started by Sharan123 January 1, 2016
Hello,

I am having some questions related to FFT while using inbuilt Matlab or
Octave FFT functions.

These functions seem to take N samples of the signal that needs to be
analyzed. 

Are there any requirement on the length of the input signal that needs to
be fed into. A signal can be made up of many frequencies, so, it is
obvious that a signal of N length can have any or all of the following
conditions,

a) one cycle of a signal
b) multiple cycles of a signal

Also, it is also not clear to me which sample of FFT output (X[n])
contains what frequency.

Thanks ...
---------------------------------------
Posted through http://www.DSPRelated.com
On Saturday, January 2, 2016 at 5:39:29 AM UTC+13, Sharan123 wrote:
> Hello, > > I am having some questions related to FFT while using inbuilt Matlab or > Octave FFT functions. > > These functions seem to take N samples of the signal that needs to be > analyzed. > > Are there any requirement on the length of the input signal that needs to > be fed into. A signal can be made up of many frequencies, so, it is > obvious that a signal of N length can have any or all of the following > conditions, > > a) one cycle of a signal > b) multiple cycles of a signal > > Also, it is also not clear to me which sample of FFT output (X[n]) > contains what frequency. > > Thanks ... > --------------------------------------- > Posted through http://www.DSPRelated.com
are you talking deterministic or a random signal. For periodic signals the more cycles the better and for random signals (as well as others) you need to average over many FFTs to get an accurate result. Don't forget a window to get more frequency accuracy. There is no limit to the length of an FFT.
On Saturday, January 2, 2016 at 5:39:29 AM UTC+13, Sharan123 wrote:
> Hello, > > I am having some questions related to FFT while using inbuilt Matlab or > Octave FFT functions. > > These functions seem to take N samples of the signal that needs to be > analyzed. > > Are there any requirement on the length of the input signal that needs to > be fed into. A signal can be made up of many frequencies, so, it is > obvious that a signal of N length can have any or all of the following > conditions, > > a) one cycle of a signal > b) multiple cycles of a signal > > Also, it is also not clear to me which sample of FFT output (X[n]) > contains what frequency. > > Thanks ... > --------------------------------------- > Posted through http://www.DSPRelated.com
are you talking deterministic or a random signal. For periodic signals the more cycles the better and for random signals (as well as others) you need to average over many FFTs to get an accurate result. Don't forget a window to get more frequency accuracy. There is no limit to the length of an FFT.
>Hello, > >I am having some questions related to FFT while using inbuilt Matlab or >Octave FFT functions. > >These functions seem to take N samples of the signal that needs to be >analyzed. > >Are there any requirement on the length of the input signal that needs
to
>be fed into. A signal can be made up of many frequencies, so, it is >obvious that a signal of N length can have any or all of the following >conditions, > >a) one cycle of a signal >b) multiple cycles of a signal > >Also, it is also not clear to me which sample of FFT output (X[n]) >contains what frequency. > >Thanks ... >--------------------------------------- >Posted through http://www.DSPRelated.com
I think it would be very beneficial for you to do a little internet searching on the Discrete Fourier Transform (DFT), of which the FFT is a special case. In brief, for the FFT the value of N must be a power of 2, or there is a version for prime numbers. The DFT has no restriction on N. There are many ways to conceptually comprehend the meaning of the DFT output. The one I think is best is the one I describe in my blog article titled "DFT Graphical Interpretation: Centroids of Weighted Roots of Unity" which can be found here" http://www.dsprelated.com/showarticle/768.php Of course, I recommend you read all my blog articles which are all related to the DFT and can be found by clicking on my name at the top of the article. The second interpretation is as the coordinates of an orthogonal basis using linear algebra. A third, which I believe is most common in the engineering curriculum, is to consider it the limit case of a dirac delta impulse train applied to continuous functional analysis. The value of the nth bin, X[n], is the complex representation of the magnitude and phase of a signal having n cycles per frame (N samples). If you have a pure sinusoidal, with an integer number of cycles within your frame, only the nth bin will be non-zero. I hope that is a good start for you. Ced --------------------------------------- Posted through http://www.DSPRelated.com
Cedron <103185@DSPRelated> wrote:

>>I am having some questions related to FFT while using inbuilt Matlab or >>Octave FFT functions.
>>These functions seem to take N samples of the signal that needs to be >>analyzed.
>>Are there any requirement on the length of the input signal
No
>>Also, it is also not clear to me which sample of FFT output (X[n]) >>contains what frequency.
>I think it would be very beneficial for you to do a little internet >searching on the Discrete Fourier Transform (DFT), of which the FFT is a >special case. > >In brief, for the FFT the value of N must be a power of 2, or there is a >version for prime numbers. The DFT has no restriction on N.
Yes, but Matlab uses "fft" to refer to any of the above, even for prime lengths.
>There are many ways to conceptually comprehend the meaning of the DFT >output.
Yep
>The one I think is best is the one I describe in my blog article titled >"DFT Graphical Interpretation: Centroids of Weighted Roots of Unity" which >can be found here" > >http://www.dsprelated.com/showarticle/768.php
Cool. Googling on "Mathworks FFT Manual Page" will come up with specific information; their versions of the DFT equations are towards the end of the man page. Of course, the index starts with one, since it's Mathworks. Steve
On Friday, January 1, 2016 at 11:39:29 AM UTC-5, Sharan123 wrote:
> > Are there any requirement on the length of the input signal that needs to > be fed into. A signal can be made up of many frequencies, so, it is > obvious that a signal of N length can have any or all of the following > conditions, > > a) one cycle of a signal > b) multiple cycles of a signal > > Also, it is also not clear to me which sample of FFT output (X[n]) > contains what frequency.
don't forget to subtract 1 from the index to fix a lousy decision of MathWorks dating back to the 90s. r b-j
On Fri, 01 Jan 2016 10:39:26 -0600, "Sharan123" <99077@DSPRelated>
wrote:

>Hello, > >I am having some questions related to FFT while using inbuilt Matlab or >Octave FFT functions. > >These functions seem to take N samples of the signal that needs to be >analyzed. > >Are there any requirement on the length of the input signal that needs to >be fed into.
Not in matlab/octave. Either of those figure out a good algorithm to use for the length of the given vector, whatever it might be. That might be a power-of-two algorithm, a mixed-radix algorithm, a DFT, or one of many other methods of doing various lengths of "FFT". Matlab and Octave both use a package called "FFTW" to do the transforms. It is pretty well-known and well-documented on the internet. The basic Cooley-Tukey algorithm for FFTs generally supports only vectors with lengths of powers-of-two, but Matlab/Octave use other algorithms for other lengths.
> A signal can be made up of many frequencies, so, it is >obvious that a signal of N length can have any or all of the following >conditions, > >a) one cycle of a signal >b) multiple cycles of a signal
Up to the Nyquist frequency for the sample rate.
>Also, it is also not clear to me which sample of FFT output (X[n]) >contains what frequency.
For the length-N input vector and the natural ordering of the FFT outputs (i.e., using the index definitions for general transforms), each output bin is the correlation of the input with a sinusoid of k cycles per N samples, where k is the index of the bin. In other words, bin 1 will contain the cross-correlation of the input and a (complex) sinusoid with exactly 1 cycle per N samples. Bin 2 will correlate against 2 cycles/N samples, etc. Bin 0 has the DC energy, and bin -1 (folded about DC, or bin N-1), has the cross-correlation of the input against a (complex) sinusoid of 1 cycle/N samples rotating in the opposite direction of that used for bin 1. One bad thing about Matlab/Octave is that they use matrix indexing, so everything is off-by-one, i.e., natural bin 0 is really index 1, since Matlab/Octave do not support zero-based indexing.
>Thanks ... >--------------------------------------- >Posted through http://www.DSPRelated.com
Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
>are you talking deterministic or a random signal. For periodic signals
the
>more cycles the better and for random signals (as well as others) you
need
>to average over many FFTs to get an accurate result. Don't forget a
window
>to get more frequency accuracy. There is no limit to the length of an
FFT. Dear ".", I an using two simple sinuosoids in my example by adding them. I intend to add increase the complexity of this signal. I guess for my simple example, windowing is not needed ... --------------------------------------- Posted through http://www.DSPRelated.com
>If you have a pure sinusoidal, with an integer number of cycles within >your frame, only the nth bin will be non-zero.
Dear Cedron, I am going through your blog on DFT. I will come back with questions specific to that ... with respect to your comment above, when a natural signal is sampled where only the frequency range is possibly known, it is rather difficult to ensure "integer number of cycles". Integer number of cycles could also be not possible if relative frequencies are not integer multiples ... Maybe, I am misinterpreting your comment above ... --------------------------------------- Posted through http://www.DSPRelated.com
>I an using two simple sinuosoids in my example by adding them. I intend
to
>add increase the complexity of this signal. I guess for my simple
example,
>windowing is not needed ... >
Since the DFT (matlab fft) is a linear transform, the DFT of a sum is the sum of the DFTs. If your two sinusoids have distinct integer frequencies relative to your frame, the the resulting DFT will have two non-zero bins. If you have non-integer frequencies, the bins closest to the two frequencies will have the greatest magnitude. For non-integer frequency pure sinusoidal tones, the DFT bin results can be calculate directly without doing a summation. The formulas can be found in my blog article titled "DFT Bin Value Formulas for Pure Real Tones" which can be found here: http://www.dsprelated.com/showarticle/771.php They are not available in matlab, but if you have the ability to understand math, they will give you insight into how the DFT behaves on tones composed of sinusoidal tones. Ced --------------------------------------- Posted through http://www.DSPRelated.com