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?
1 Answer
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$.
-
$\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$– SumbulFeb 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$– SumbulFeb 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