2
$\begingroup$

On what basis, N of N-point-fft is chosen? What can go wrong if I don't select it to be power of 2? How is this N related to sampling frequency?

$\endgroup$

1 Answer 1

6
$\begingroup$

Firstly, you need to know that the FFT computes the DFT (discrete Fourier transform) in an efficient manner. Hence, the output of an N-point FFT and N-point DFT are exactly the same.

Now, especially, if N is a power-of-two, the FFT can be calculated very efficiently. Though, if N can be factorized into rel. small prime numbers (2, 3, 5), still the calculation can be done very efficiently. Strictly speaking, the Radix-2 FFT only works, if N is power-of-two. However, in common implementations in software, N can be any number and the implementation chooses the appropriate algorithms for most efficient calculation.

Hence, if N is power of two, the calculation by FFT is just a bit faster, compared to when N would be a large prime number.

Regarding sampling frequency: If $F_s$ is your sampling frequency and $T$ is the duration of the FFT window, then $N=TF_s$. It's hard to answer more detailed what you mean by relation to sampling frequency, because I dont know exactly what you are asking.

Regarding your comment: The DFT maps a subset of the frequency range $[0,\dots,F_s]$ to the $N$ DFT-bins, which are indexed by $k=0,\ldots,N-1$. Since all frequency bins in the DFT output have the same distance to each other (i.e. they are linearly spaced), you immediately end up with $f=\frac{k}{N}F_s$, i.e. the $k$th bin corresponds to the physical frequency $f=\frac{k}{N}F_s$.

$\endgroup$
4
  • $\begingroup$ I'm asking about this mapping formula: f/fs=k/N, where f is the analog bandwidth. I'm unable to understand it. $\endgroup$
    – Sumbul
    Feb 27, 2017 at 9:49
  • $\begingroup$ I added a small explanation. Is it still unclear? $\endgroup$ Feb 27, 2017 at 10:03
  • $\begingroup$ " T is the duration of the FFT window, then N=TFs ". Here T=k/N? For example, if I take N =1024 and k is the range of samples of signal of interest e.g., k =750-290=460, then f=(0.44921875)* fs. Am I getting the formula right? $\endgroup$
    – Sumbul
    Feb 27, 2017 at 10:20
  • 1
    $\begingroup$ No, you first define $T$ and $F_s$. Then, within the time window $T$ you get $N$ samples (in time domain), due to sampling with frequency $F_s$. So, you define $T$ and $F_s$ a priori, and then you get $N$. From this, after DFT, you can calculate that the value in the $k$th bin of the N-point DFT corresponds to the physical frequency $k/N F_s$. $\endgroup$ Feb 27, 2017 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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