# practical FFT

Started by 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
```