0
$\begingroup$

My question is simple. I think I kind of understand FFT and DFT. what I dont understand is why, in Python or matlab, do we use FFT size as the number of samples? why does every sample taken in the time domain corresponds to a frequency bin in the frequency domain.

$\endgroup$
1
  • 3
    $\begingroup$ If you look at the equation for the DFT carefully, you'll see that it calculates the same number of values as there are samples in the input. So, the answer is, because of the the way the DFT is defined. $\endgroup$ – MBaz Jun 3 at 13:14
2
$\begingroup$

You can do DFT in a different way, but the most interesting scenario is when the DFT is unique and invertible.

DFT is a linear transformation, it can be defined as a matrix multiplication $X = W\, x$ where $x$ is a vector with time-domain samples and $X$ is the vector of coefficients. If you want an invertible $W$ you need to have the same number of rows and columns, thus $X$ has the same number of elements as $x$.

$\endgroup$
1
  • $\begingroup$ Thank you so much. $\endgroup$ – ftkhateeb Jun 3 at 14:23
2
$\begingroup$

The DFT is an orthogonal transform. This means it preserves the input with zero redundancy. If length is:

  • longer than input: redundancy
  • shorter than input: loss of information

It's also equivalent to solving a system of $N=\text{len(x)}$ equations for $N$ variables (less variables = can't solve, more = infinite solutions). Further reading.

$\endgroup$
1
  • $\begingroup$ Thank you so much. $\endgroup$ – ftkhateeb Jun 3 at 14:24
0
$\begingroup$

I got this answer from @dmuir on SO before my post was closed for being irrelevant.

Mathematically a key property of the fourier transform is that it is linear and invertible. The latter means that if two signals have the same fourier transform they are equal, and that for any spectrum there is a signal with that spectrum.

For implementations with a finite collection of samples of a signal the first property means that the fourier tramsform can be represented by a N x M matrix where N is the number of time samples and M the number of frequency samples. The second property means that the matrix must be invertible, and so square, ie we must have M == N.

You say that time bins and frequency correspond, and that is true in the sense that there are the same number of them. However the value in each frequency bin will depend on all time values.

$\endgroup$
1
  • $\begingroup$ And this answer is roughly equivalent to the two answers here. Just to complement, you can compute the DFT with a different number of coefficients than the length of the input by specifying $n$ to scipy.fftpack.fft. And you can even compute for non-equidistant points using nfft, but you will have difficulties with reconstruction $\endgroup$ – Bob Jun 4 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.